Shanks's square forms factorization is a method for integer factorization devised by Daniel Shanks as an improvement on Fermat's factorization method.
Contents
The success of Fermat's method depends on finding integers
A practical algorithm for finding pairs
Algorithm
Input:
Output: a non-trivial factor of
The algorithm:
Initialize
Repeat
until
Initialize
Repeat
until
Then if
Shanks's method has time complexity
Stephen S. McMath (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.
Example
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.
Implementations
The PSIQS Java package contains a SquFoF implementation.