Invented (presumably) by Herr Euler himself. Ja wohl!
First, express N as two quadratic forms:
N = a^2 + b^2 = c^2 + d^2
Hence : a^2 - c^2 = d^2 - b^2
So : (a-c)(a+c) = (d-b)(d+b)

Now, let k = gcd(a-c, d-b)
Then : a-c = k*l and d-b = k*m,
for some l and m, where (l,m) = 1

Then : l(a+c) = m(d+b)
Some icky algebra then shows that
N = [(k/2)^2 + (n/2)^2] * (l^2 + m^2)
where n = (a+c)/m = (b+d)/l
As soon as I work out some more of the details, and put this into code, I will post it here.
  1. Choose a number, N, you wish to factor.
  2. Somehow magically express it as the sum of two squares in two different ways.
  3. Do the algebra shown above.
  4. Done. (mod details)

Theoretical runtime:
O( ? ) - probably slow.


Back to the factoring theory page
Back to the factoring page
Back to my home page
Back to the pslc home page

Paul Herman

Last Updated: May 23, 1997