Shanks's square forms factorization
   HOME

TheInfoList



OR:

Shanks's square forms factorization is a method for
integer factorization In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization. When the numbers are suf ...
devised by
Daniel Shanks Daniel Shanks (January 17, 1917 – September 6, 1996) was an American mathematician who worked primarily in numerical analysis and number theory. He was the first person to compute π to 100,000 decimal places. Life and education Shanks was b ...
as an improvement on
Fermat's factorization method Fermat's factorization method, named after Pierre de Fermat, is based on the representation of an odd integer as the difference of two squares: :N = a^2 - b^2. That difference is algebraically factorable as (a+b)(a-b); if neither factor equals one, ...
. The success of Fermat's method depends on finding integers x and y such that x^2-y^2=N, where N is the integer to be factored. An improvement (noticed by Kraitchik) is to look for integers x and y such that x^2\equiv y^2\pmod. Finding a suitable pair (x, y) does not guarantee a factorization of N, but it implies that N is a factor of x^2-y^2=(x-y)(x+y), and there is a good chance that the
prime divisor A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s of N are distributed between these two factors, so that calculation of the
greatest common divisor In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...
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 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. In 1858, the Czech mathematician
Václav Šimerka Václav Šimerka (20 December 1819 – 26 December 1887) was a Bohemian mathematician, priest, physicist, and philosopher. He wrote the first Czech text on calculus and is credited for discovering the first seven Carmichael numbers, from 561 to ...
used a method similar to SQUFOF to factor (10^ - 1)/9 = 11111111111111111 = 2071723 \cdot 5363222357.


Algorithm

Input: N, the integer to be factored, which must be neither a
prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
nor a
perfect square ''Perfect Square'' is a 2004 concert film of the alternative rock Musical ensemble, band R.E.M. (band), R.E.M., filmed on July 19, 2003, at the bowling green, Bowling Green in Wiesbaden, Germany. It was released by Warner Reprise Video on March 9, ...
, and a small multiplier k. Output: a non-trivial factor of N. The algorithm: Initialize P_0=\lfloor\sqrt\rfloor,Q_0=1,Q_1=kN-P_0^2. Repeat b_i=\left\lfloor\frac\right\rfloor,P_i=b_iQ_i-P_,Q_=Q_+b_i(P_-P_i) until Q_ is a perfect square at some even i+1. Initialize b_0=\left\lfloor\frac\right\rfloor,P_0=b_0\sqrt+P_i,Q_0=\sqrt,Q_1=\frac Repeat b_i=\left\lfloor\frac\right\rfloor,P_i=b_iQ_i-P_,Q_=Q_+b_i(P_-P_i) until P_i=P_. Then if f=\gcd(N,P_i) is not equal to 1 and not equal to N, then f is a non-trivial factor of N. Otherwise try another value of k. Shanks's method has time complexity O(\sqrt . Stephen S. McMath wrote a more detailed discussion of the mathematics of Shanks's method, together with a proof of its correctness.


Example

Let N = 11111, k = 1 Here Q_ = 25 is a perfect square. Here P_ = P_ = 82. gcd(11111, 82) = 41, which is a factor of 11111. Thus, N = 11111 = 41 \cdot 271


Example implementations

Below is an example of C function for performing SQUFOF factorization on unsigned integer not larger than 64 bits, without overflow of the transient operations. #include #define nelems(x) (sizeof(x) / sizeof((x) ) const int multiplier[] = ; uint64_t SQUFOF( uint64_t N )


References

* * * *


External links

* 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 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)

java-math-library
{{number theoretic algorithms Integer factorization algorithms