Representing integers as the difference of two squares


Most integers can be represented as the difference of two squares, where each square is a non-negative integer.

Algebraically speaking:

`n = x^2 - y^2`

for some non-negative integers `x` and `y`.

In this blog post we're going to look at a simple and elegant algorithm for finding all the possible representations for any given integer that can be represented as a difference of two squares, using its divisors.

For example, if we have `n = 12345`, we can represent it in four different ways as a difference of two non-negative integer squares:

`12345 = 419^2 - 404^2`
`12345 = 1237^2 - 1232^2`
`12345 = 2059^2 - 2056^2`
`12345 = 6173^2 - 6172^2`

# Finding solutions

By writing `n` as the product of two whole numbers, `n = a*b`, we have the following identity:

`a*b = ((a+b)/2)^2 - ((a-b)/2)^2`

Then, by iterating over all the divisors of `n`, we generate all the possible representations for `n` as a difference of two non-negative squares.

In order to generate only integer solutions, we have to make sure that `a+b` is even. In general, when `n` is even, we can iterate only over its even divisors. Otherwise, we iterate over its odd divisors.

Algorithm:

Let `d` run over the divisors of `n` which are `d <= sqrt(n)` and have the same parity as `n`.

For each such divisor `d`, we generate a new solution to `n = x^2 - y^2`, as:

`x = (n/d + d)/2`

`y = (n/d - d)/2`

Illustrating this with an example, let `n = 24`. As `24` is even, we are going to iterate only over its even divisors, which are: `[2, 4, 6, 8, 12, 24]`.

First divisor in the list, `d=2`:

`x = (n/d+d)/2 = 7`

`y = (n/d-d)/2 = 5`

Second divisor in the list, `d=4`:

`x = (n/d+d)/2 = 5`

`y = (n/d-d)/2 = 1`

Solutions:

`24 = 7^2 - 5^2`
`24 = 5^2 - 1^2`

In fact, this are all the representations for `24` as a difference of two non-negative integer squares, because in the next iteration, `d=6`, we would have `n/d = 4`, and since `n/d < d`, this would generate negative solutions, which are essentially the same as the positive ones, so we can stop here.

# Extra

Finding a non-trivial representation for a semiprime `n` as a difference of two squares, is just as hard as factoring `n`, because:

`x^2 - y^2 = (x + y) * (x - y)`

For example, if we have `n = 15709691830279` and we also know a non-trivial representation for it:

`n = 4384780^2 - 1875261^2`

Then we can factorize it as:

`n = (4384780 + 1875261) * (4384780 - 1875261)`

From this results that if we know only the sum or the difference of the prime factors of a semiprime, we can find its prime factors in polynomial time.

Let `t` be the absolute difference between the two prime factors of a semiprime `n` (i.e.: `t=abs(p-q)`, for `n = p*q`):

`x = sqrt(t^2 + 4n) / 2`

`y = t/2`

Alternatively, let `s` be the sum of its two prime factors (i.e.: `s = p+q`, for `n = p*q`):

`x = s/2`

`y = sqrt(s^2 - 4n) / 2`

Then `n` can be factorized in both cases as:

`n = (x+y) * (x-y)`

# Implementations

Bellow we have a Perl implementation of the algorithm described in this post.

Difference of two squares - algorithm implementation:
Extra:

Next time we're going to look at an algorithm for representing an integer as a sum of two squares, which is a slightly more advanced problem.

See also: