Shanks's square forms factorization

Shanks' 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 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 divisors of are distributed between these two factors, so that calculation of the greatest common divisor 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, 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 .[1]

Algorithm

edit

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 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  [citation needed]

Then if   is not equal to   and not equal to  , then   is a non-trivial factor of  . Otherwise try another value of  .[citation needed]

Shanks' method has time complexity  .[2]

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

Example

edit

Let  

 

Cycle forward
       
     
       
       
       
       
       

Here   is a perfect square, so the first phase ends.

For the second phase, set  . Then:

Reverse cycle
       
       
       
       
       
     

Here  , so the second phase ends. Now calculate  , which is a factor of  .

Thus,  .

Example implementation

edit

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

edit
  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. ^ (Riesel 1994:189)
  3. ^ "Daniel Shanks' Square Forms Factorization". 2004. CiteSeerX 10.1.1.107.9984.
edit