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`
`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.
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`
`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:
Comments
Post a Comment