Works by expressing as a Quadratic Form in two different ways. Then
|
(1) |
so
|
(2) |
|
(3) |
Let be the Greatest Common Divisor of and so
(where denotes the Greatest Common Divisor of and ), and
|
(7) |
But since , and
|
(8) |
which gives
|
(9) |
so we have
See also Prime Factorization Algorithms
© 1996-9 Eric W. Weisstein
1999-05-25