Shanks' square forms factorization

From Wikipedia, the free encyclopedia

Shanks' square forms factorization is a method for integer factorization, which was devised as an improvement on Fermat's factorization method.

The success of Fermat's method depends on finding integers x, and y such that x² − y² = N, where N is the integer to be factored, and a possible improvement (noticed by Kraitchik), is to look for integers x and y such that $x^2\equiv y^2 \pmod{N}$ . Finding a pair (x,y) does not guarantee a factorization of N, but it implies that N is a factor of x² − y² = (x-y)(x+y), and there is a good chance that the prime divisors of N are distributed between these two factors, so that calculation of the highest common factor of N and x-y will give a non-trivial factor of N.

A practical algorithm for finding pairs (x,y) which satisfy $x^2\equiv y^2 \pmod{N}$ was developed by Shanks and was named "Square Forms Factorization" or "SQUFOF". The algorithm can be couched either in terms of continued fractions or in terms of quadratic forms, and 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.

1 Algorithm
2 Example
3 References
4 External links

[edit] Algorithm

Input: N, the integer to be factored, which must be neither a prime number nor a perfect square.

Output: a non-trivial factor of N.

The algorithm:

Initialize $P_0=\lfloor\sqrt{N}\rfloor,Q_0=1,Q_1=N-P_0^2$

Repeat

$b_i=\left\lfloor\frac{\lfloor\sqrt{N}\rfloor+P_{i-1}}{Q_i}\right\rfloor,P_i=b_iQ_i-P_{i-1},Q_{i+1}=Q_{i-1}+b_i(P_{i-1}-P_i)$

until $Q i$ is a perfect square.

Initialize $b_0=\left\lfloor\frac{\lfloor\sqrt{N}\rfloor-P_{i-1}}{\sqrt{Q_i}}\right\rfloor,P_0=b_0\sqrt{Q_i}+P_{i-1},Q_0=\sqrt{Q_i},Q_1=\frac{N-P_0^2}{Q_0}$

Repeat

$b_i=\left\lfloor\frac{\lfloor\sqrt{N}\rfloor+P_{i-1}}{Q_i}\right\rfloor,P_i=b_iQ_i-P_{i-1},Q_{i+1}=Q_{i-1}+b_i(P_{i-1}-P_i)$

until $P i + 1 = P i .$

Then $gcd(N, P i)$ is a non-trivial factor of $N$ . Shanks' method has time complexity $O(\sqrt[4]{N})$ .

Stephen S. McMasters (see link in External Link section) wrote a more detailed discussion of the mathematics of Shanks' method, together with a proof of its correctness.

[edit] Example

N = 11111

P₀ = 105 Q₀ = 1 Q₁ = 86

P₁ = 67 Q₁ = 86 Q₂ = 77

P₂ = 87 Q₂ = 77 Q₃ = 46

P₃ = 97 Q₃ = 46 Q₄ = 37

P₄ = 88 Q₄ = 37 Q₅ = 91

P₅ = 94 Q₅ = 91 Q₆ = 25

Here Q₆ is a perfect square

P₀ = 104 Q₀ = 5 Q₁ = 59

P₁ = 73 Q₁ = 59 Q₂ = 98

P₂ = 25 Q₂ = 98 Q₃ = 107

P₃ = 82 Q₃ = 107 Q₄ = 41

P₄ = 82

Here P₃ = P₄

gcd(11111, 82) = 41, which is a factor of 11111.

[edit] References

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.

[edit] External links

2005, Stephen S. McMath

v • d • e Number-theoretic algorithms

Primality tests	AKS · APR · Ballie-PSW · ECPP · Fermat · Lucas–Lehmer · Lucas–Lehmer (Mersenne numbers) · Lucas–Lehmer–Riesel · Proth's theorem · Pépin's · Solovay-Strassen · Miller-Rabin · Trial division

Sieving algorithms	Sieve of Atkin · Sieve of Eratosthenes · Sieve of Sundaram · Wheel factorization

Integer factorization algorithms	CFRAC · Dixon's · ECM · Euler's · Pollard's rho · P - 1 · P + 1 · QS · GNFS · SNFS · rational sieve · Fermat's · Shanks' square forms · Trial division · Shor's algorithm

Other algorithms	Ancient Egyptian multiplication · Aryabhata · Binary GCD · Chakravala · Euclidean · Extended Euclidean · integer relation algorithm · integer square root · Modular exponentiation · Shanks-Tonelli

Italics indicate that algorithm is for numbers of special forms; bold indicates deterministic algorithm for primality tests.