BACKGROUND Invented (presumably) by Herr Euler himself. Ja wohl!

---

BIG IDEA 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.

---

METHOD

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)

---

TECHNICAL ANALYSIS

Theoretical runtime:

O( ? ) - probably slow.

---

LINKS

• Time analysis: Not yet available
• Source code: Not yet available

---

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

Paul Herman
pherman@frenchfries.net

Last Updated: May 23, 1997