Shanks's square forms factorization

Shanks's square forms factorization is a method for integer factorization devised by Daniel Shanks as an improvement on Fermat's factorization method.

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

A practical algorithm for finding pairs ${\displaystyle (x,y)}$ which satisfy ${\displaystyle x^{2}\equiv y^{2}{\pmod {N}}}$ 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 used a method similar to SQUFOF to factor ${\displaystyle (10^{17}-1)/9}$ ${\displaystyle =}$ ${\displaystyle 11111111111111111}$ ${\displaystyle =}$ ${\displaystyle 2071723\cdot 5363222357}$.[1]

Algorithm

Input: ${\displaystyle N}$, the integer to be factored, which must be neither a prime number nor a perfect square, and a small multiplier ${\displaystyle k}$.

Output: a non-trivial factor of ${\displaystyle N}$.

The algorithm:

Initialize ${\displaystyle P_{0}=\lfloor {\sqrt {kN}}\rfloor ,Q_{0}=1,Q_{1}=kN-P_{0}^{2}.}$

Repeat

${\displaystyle b_{i}=\left\lfloor {\frac {P_{0}+P_{i-1}}{Q_{i}}}\right\rfloor ,P_{i}=b_{i}Q_{i}-P_{i-1},Q_{i+1}=Q_{i-1}+b_{i}(P_{i-1}-P_{i})}$

until ${\displaystyle Q_{i+1}}$ is a perfect square at some even ${\displaystyle i+1}$.

Initialize ${\displaystyle b_{0}=\left\lfloor {\frac {P_{0}-P_{i}}{\sqrt {Q_{i+1}}}}\right\rfloor ,P_{0}=b_{0}{\sqrt {Q_{i+1}}}+P_{i},Q_{0}={\sqrt {Q_{i+1}}},Q_{1}={\frac {kN-P_{0}^{2}}{Q_{0}}}}$

Repeat

${\displaystyle b_{i}=\left\lfloor {\frac {P_{0}+P_{i-1}}{Q_{i}}}\right\rfloor ,P_{i}=b_{i}Q_{i}-P_{i-1},Q_{i+1}=Q_{i-1}+b_{i}(P_{i-1}-P_{i})}$

until ${\displaystyle P_{i}=P_{i-1}.}$

Then if ${\displaystyle f=\gcd(N,P_{i})}$ is not equal to ${\displaystyle 1}$ and not equal to ${\displaystyle N}$, then ${\displaystyle f}$ is a non-trivial factor of ${\displaystyle N}$. Otherwise try another value of ${\displaystyle k}$.

Shanks's method has time complexity ${\displaystyle O({\sqrt[{4}]{N}})}$.

Stephen S. McMath wrote a more detailed discussion of the mathematics of Shanks's method, together with a proof of its correctness.[2]

Example

Let ${\displaystyle N=11111,k=1}$

Cycle forward
${\displaystyle i}$ ${\displaystyle P_{i}}$ ${\displaystyle Q_{i}}$ ${\displaystyle b_{i}}$
${\displaystyle 0}$ ${\displaystyle 105}$ ${\displaystyle 1}$
${\displaystyle 1}$ ${\displaystyle 67}$ ${\displaystyle 86}$ ${\displaystyle 2}$
${\displaystyle 2}$ ${\displaystyle 87}$ ${\displaystyle 77}$ ${\displaystyle 2}$
${\displaystyle 3}$ ${\displaystyle 97}$ ${\displaystyle 46}$ ${\displaystyle 4}$
${\displaystyle 4}$ ${\displaystyle 88}$ ${\displaystyle 37}$ ${\displaystyle 5}$
${\displaystyle 5}$ ${\displaystyle 94}$ ${\displaystyle 91}$ ${\displaystyle 2}$
${\displaystyle 6}$ ${\displaystyle 25}$

Here ${\displaystyle Q_{6}=25}$ is a perfect square.

Reverse cycle
${\displaystyle i}$ ${\displaystyle P_{i}}$ ${\displaystyle Q_{i}}$ ${\displaystyle b_{i}}$
${\displaystyle 0}$ ${\displaystyle 104}$ ${\displaystyle 5}$ ${\displaystyle 2}$
${\displaystyle 1}$ ${\displaystyle 73}$ ${\displaystyle 59}$ ${\displaystyle 3}$
${\displaystyle 2}$ ${\displaystyle 25}$ ${\displaystyle 98}$ ${\displaystyle 1}$
${\displaystyle 3}$ ${\displaystyle 82}$ ${\displaystyle 107}$ ${\displaystyle 1}$
${\displaystyle 4}$ ${\displaystyle 82}$ ${\displaystyle 41}$ ${\displaystyle 4}$

Here ${\displaystyle P_{3}=P_{4}=82}$.

${\displaystyle gcd(11111,82)=41}$, which is a factor of ${\displaystyle 11111}$.

Thus, ${\displaystyle 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.[citation needed]

#include <inttypes.h>
#define nelems(x) (sizeof(x) / sizeof((x)[0]))

const int multiplier[] = {1, 3, 5, 7, 11, 3*5, 3*7, 3*11, 5*7, 5*11, 7*11, 3*5*7, 3*5*11, 3*7*11, 5*7*11, 3*5*7*11};

uint64_t SQUFOF( uint64_t N )
{
uint64_t D, Po, P, Pprev, Q, Qprev, q, b, r, s;
uint32_t L, B, i;
s = (uint64_t)(sqrtl(N)+0.5);
if (s*s == N) return s;
for (int k = 0; k < nelems(multiplier) && N <= UINT64_MAX/multiplier[k]; k++) {
D = multiplier[k]*N;
Po = Pprev = P = sqrtl(D);
Qprev = 1;
Q = D - Po*Po;
L = 2 * sqrtl( 2*s );
B = 3 * L;
for (i = 2 ; i < B ; i++) {
b = (uint64_t)((Po + P)/Q);
P = b*Q - P;
q = Q;
Q = Qprev + b*(Pprev - P);
r = (uint64_t)(sqrtl(Q)+0.5);
if (!(i & 1) && r*r == Q) break;
Qprev = q;
Pprev = P;
};
if (i >= B) continue;
b = (uint64_t)((Po - P)/r);
Pprev = P = b*r + P;
Qprev = r;
Q = (D - Pprev*Pprev)/Qprev;
i = 0;
do {
b = (uint64_t)((Po + P)/Q);
Pprev = P;
P = b*Q - P;
q = Q;
Q = Qprev + b*(Pprev - P);
Qprev = q;
i++;
} while (P != Pprev);
r = gcd(N, Qprev);
if (r != 1 && r != N) return r;
}
return 0;
}


References

1. ^ Lemmermeyer, F. (2013). "Václav Šimerka: quadratic forms and factorization". LMS Journal of Computation and Mathematics. 16: 118–129. doi:10.1112/S1461157013000065.
2. ^ "Daniel Shanks' Square Forms Factorization". 2004. CiteSeerX 10.1.1.107.9984. {{cite journal}}: Cite journal requires |journal= (help)