Shanks' square forms factorization is a method for
integer factorization
In mathematics, integer factorization is the decomposition of a positive integer into a product of integers. Every positive integer greater than 1 is either the product of two or more integer factors greater than 1, in which case it is a comp ...
devised by
Daniel Shanks
Daniel Charles 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
Shan ...
as an improvement on
Fermat's factorization method.
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 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
are distributed between these two factors, so that calculation of the
greatest common divisor
In mathematics, the greatest common divisor (GCD), also known as greatest common factor (GCF), of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers , , the greatest co ...
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. Shanks programmed it on an
HP-65
The HP-65 is the first magnetic card-programmable handheld calculator. Introduced by Hewlett-Packard in 1974 at an MSRP of $795 (), it featured nine storage registers and room for 100 keystroke instructions. It also included a magnetic card ...
, made in 1974, which has storage for only nine digit numbers and allows only 100 steps/keystrokes of programming. There are versions of the algorithm that use little memory and versions that store a list of values that run more quickly.
In 1858, the Czech mathematician
Václav Šimerka used a method similar to SQUFOF to factor
.
Algorithm
Note This version of the algorithm works on some examples but often gets stuck in a loop.
This version does not use a list.
Input:
, 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 (mathematics), 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 ...
nor a
perfect square, and a small positive integer,
.
Output: a non-trivial factor of
.
The algorithm:
Initialize
Repeat
until
is a perfect square at some odd value of
.
Start the second phase (reverse cycle).
Initialize
,
, and
, where
, and
are from the previous phase. The
used in the calculation of
is the recently calculated value of
.
Set
and
, where
is the recently calculated value of
.
Repeat
until
Then if
is not equal to
and not equal to
, then
is a non-trivial factor of
. Otherwise try another value of
.
Shanks' method has time complexity
.
Stephen S. McMath wrote
a more detailed discussion of the mathematics of Shanks' method,
together with a proof of its correctness.
Example
Let
Here
is a perfect square, so the first phase ends.
For the second phase, set
. Then:
Here
, so the second phase ends. Now calculate
, which is a factor of
.
Thus,
.
Example implementation
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