### Representing integers as the difference of two squares

Most integers can be represented as a 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.