Shanks' square forms factorization
||This article needs attention from an expert in mathematics. (November 2008)|
||This article includes a list of references, related reading or external links, but its sources remain unclear because it lacks inline citations. (March 2015) (Learn how and when to remove this template message)|
The success of Fermat's method depends on finding integers and such that , where is the integer to be factored. An improvement (noticed by Kraitchik) is to look for integers and such that . Finding a suitable pair does not guarantee a factorization of , but it implies that is a factor of , and there is a good chance that the prime divisors of are distributed between these two factors, so that calculation of the greatest common divisor of and will give a non-trivial factor of .
A practical algorithm for finding pairs which satisfy was developed by Shanks, who named it Square Forms Factorization or SQUFOF. The algorithm can be expressed in terms of continued fractions or in terms of quadratic forms. Although there are now much more efficient factorization methods available, SQUFOF has the advantage that it is small enough to be implemented on a programmable calculator.
Output: a non-trivial factor of .
until is a perfect square at some even .
Then if is not equal to and not equal to , then is a non-trivial factor of . Otherwise try another value of .
Shanks's method has time complexity .
Stephen S. McMasters (see link in External Link section) wrote a more detailed discussion of the mathematics of Shanks's method, together with a proof of its correctness.
N = 11111, k = 1
P0 = 105 Q0 = 1 Q1 = 86
P1 = 67 Q1 = 86 Q2 = 77
P2 = 87 Q2 = 77 Q3 = 46
P3 = 97 Q3 = 46 Q4 = 37
P4 = 88 Q4 = 37 Q5 = 91
P5 = 94 Q5 = 91 Q6 = 25
Here Q6 is a perfect square
P0 = 104 Q0 = 5 Q1 = 59
P1 = 73 Q1 = 59 Q2 = 98
P2 = 25 Q2 = 98 Q3 = 107
P3 = 82 Q3 = 107 Q4 = 41
P4 = 82
Here P3 = P4
gcd(11111, 82) = 41, which is a factor of 11111.
The PSIQS Java package contains a SquFoF implementation.
- D. A. Buell (1989). Binary Quadratic Forms. Springer-Verlag. ISBN 0-387-97037-1.
- D. M. Bressoud (1989). Factorisation and Primality Testing. Springer-Verlag. ISBN 0-387-97040-1.
- Riesel, Hans (1994). Prime numbers and computer methods for factorization (2nd ed.). Birkhauser. ISBN 0-8176-3743-5.
- Daniel Shanks: Analysis and Improvement of the Continued Fraction Method of Factorization, (transcribed by S. McMath 2004)
- Daniel Shanks: SQUFOF Notes, (transcribed by S. McMath 2004)
- Stephen McMath: Daniel Shanks’s Square Forms Factorization (Nov. 2004)
- Stephen S. McMath: Parallel integer factorization using quadratic forms, 2005
- S. McMath, F. Crabbe, D. Joyner: Continued fractions and parallel SQUFOF, 2005
- Jason Gower, Samuel Wagstaff: Square Form Factorisation (Published)
- Shanks' SQUFOF Factoring Algorithm