Shanks' 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 $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 {N}}$ . 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 divisors of $N$ are distributed between these two factors, so that calculation of the greatest common divisor 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, 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.

Algorithm

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

Output: a non-trivial factor of $N$ .

The algorithm:

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

Repeat

$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 $Q_{i}$ is a perfect square at some even $i$ .

Initialize $b_{0}=\left\lfloor {\frac {P_{0}-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 {kN-P_{0}^{2}}{Q_{0}}}$

Repeat

$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 $P_{i}=P_{{i-1}}.$

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[ {4}]{N}})$ .

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

Let $N=11111,k=1$

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

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

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

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

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

Thus, $N=11111=41\cdot 271$

Implementations

The PSIQS Java package contains a SquFoF implementation.

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

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.
Riesel, Hans (1994). Prime numbers and computer methods for factorization (2nd ed.). Birkhauser. ISBN 0-8176-3743-5.
Samuel S. Wagstaff, Jr. (2013). The Joy of Factoring. Providence, RI: American Mathematical Society. pp. 163–168. ISBN 978-1-4704-1048-3.

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 McMath: Daniel Shanks’s Square Forms Factorization (Nov. 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)
Shanks' SQUFOF Factoring Algorithm

Number-theoretic algorithms
Primality tests	AKS test APR test Baillie–PSW Elliptic curve Pocklington Fermat Lucas Lucas–Lehmer Lucas–Lehmer–Riesel Proth's theorem Pépin's Quadratic Frobenius test Solovay–Strassen Miller–Rabin
Prime-generating	Sieve of Atkin Sieve of Eratosthenes Sieve of Sundaram Wheel factorization
Integer factorization	Continued fraction (CFRAC) Dixon's Lenstra elliptic curve (ECM) Euler's Pollard's rho p − 1 p + 1 Quadratic sieve (QS) General number field sieve (GNFS) Special number field sieve (SNFS) Rational sieve Fermat's Shanks' square forms Trial division Shor's
Multiplication	Ancient Egyptian Long Karatsuba Toom–Cook Schönhage–Strassen Fürer's
Discrete logarithm	Baby-step giant-step Pollard rho Pollard kangaroo Pohlig–Hellman Index calculus Function field sieve
Greatest common divisor	Binary Euclidean Extended Euclidean Lehmer's
Modular square root	Cipolla Pocklington's Tonelli–Shanks
Other algorithms	Chakravala Cornacchia LLL Integer square root Modular exponentiation Schoof's
Italics indicate that algorithm is for numbers of special forms

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.