View source for Shanks's square forms factorization

{{more footnotes|date=March 2015}}

'''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 <math>x</math> and <math>y</math> such that <math>x^2-y^2=N</math>, where <math>N</math> is the integer to be factored. An improvement (noticed by [[Maurice Kraitchik|Kraitchik]]) is to look for integers <math>x</math> and <math>y</math> such that <math>x^2\equiv y^2\pmod{N}</math>. Finding a suitable pair <math>(x, y)</math> does not guarantee a factorization of <math>N</math>, but it implies that <math>N</math> is a factor of <math>x^2-y^2=(x-y)(x+y)</math>, and there is a good chance that the [[prime divisor]]s of <math>N</math> are distributed between these two factors, so that calculation of the [[greatest common divisor]] of <math>N</math> and <math>x-y</math> will give a non-trivial factor of <math>N</math>.

A practical algorithm for finding pairs <math>(x,y)</math> which satisfy <math>x^2\equiv y^2\pmod{N}</math> 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 <math>(10^{17} - 1)/9</math> <math>=</math> <math>11111111111111111</math> <math>=</math> <math>2071723 \cdot 5363222357</math>.<ref>{{cite journal |last1=Lemmermeyer |first1=F. |title=Václav Šimerka: quadratic forms and factorization |journal=LMS Journal of Computation and Mathematics |date=2013 |volume=16 |pages=118–129 |doi=10.1112/S1461157013000065 |doi-access=free}}</ref>

==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''': <math>N</math>, the integer to be factored, which must be neither a [[prime number]] nor a [[Square number|perfect square]], and a small positive integer, <math>k</math>.

'''Output''': a non-trivial factor of <math>N</math>.

'''The algorithm:'''

Initialize <math>i=0,P_0=\lfloor\sqrt{kN}\rfloor,Q_{-1}=1,Q_0=kN-P_0^2.</math>

Repeat

<math>i=i+1,b_i=\left\lfloor\frac{P_0+P_{i-1}}{Q_{i-1}}\right\rfloor,P_i=b_iQ_{i-1}-P_{i-1},Q_i=Q_{i-2}+b_i(P_{i-1}-P_i)</math>

until <math>Q_i</math> is a perfect square at some odd value of <math>i</math>.

Start the second phase (reverse cycle).  

Initialize <math>b_0=\left\lfloor\frac{P_0-P_i}{\sqrt{Q_i}}\right\rfloor</math>, <math>Q_{-1}=\sqrt{Q_i}</math>, and <math>P_0=b_0\sqrt{Q_i}+P_i</math>, where <math>P_0, P_i</math>, and <math>Q_{i}</math> are from the previous phase. The <math>b_0</math> used in the calculation of <math>P_0</math> is the recently calculated value of <math>b_0</math>.

Set <math> i=0</math> and <math> Q_0=\frac{kN-P_0^2}{Q_{-1}}</math>, where <math>P_0</math> is the recently calculated value of <math>P_0</math>.

Repeat

<math>i=i+1,b_i=\left\lfloor\frac{P_0+P_{i-1}}{Q_{i-1}}\right\rfloor,P_i=b_iQ_{i-1}-P_{i-1},Q_i=Q_{i-2}+b_i(P_{i-1}-P_i)</math>

until <math>P_i=P_{i-1}.</math>{{cn|date=October 2023}}

Then if <math>f=\gcd(N,P_i)</math> is not equal to <math>1</math> and not equal to <math>N</math>, then <math>f</math> is a non-trivial factor of <math>N</math>. Otherwise try another value of <math>k</math>.{{cn|date=October 2023}}

Shanks' method has time complexity <math>O(\sqrt[4]{N})</math>.<ref>{{Harvcol|Riesel|1994|p=189}}</ref>

Stephen S. McMath wrote
a more detailed discussion of the mathematics of Shanks' method,
together with a proof of its correctness.<ref>{{Cite CiteSeerX|title=Daniel Shanks' Square Forms Factorization| year=2004 |citeseerx = 10.1.1.107.9984}}</ref>

==Example==

Let <math>N = 11111</math>

<math>Q_{-1}=1</math>

{| border="1" class="wikitable" style="text-align:center; "
 !colspan="4" | Cycle forward
 |-
 !<math>i</math>
 !<math>b_{i}</math>
 !<math>P_{i}</math>
 !<math>Q_{i}</math>
 |-
 |<math>0</math>
 |<math></math>
 |<math>105</math>
 |<math>86</math>
|-
 |<math>1</math>
 |<math>2</math>
 |<math>67</math>
 |<math>77</math>
|-
 |<math>2</math>
 |<math>2</math>
 |<math>87</math>
 |<math>46</math>
|-
 |<math>3</math>
 |<math>4</math>
 |<math>97</math>
 |<math>37</math>
|-
 |<math>4</math>
 |<math>5</math>
 |<math>88</math>
 |<math>91</math>
|-
 |<math>5</math>
 |<math>2</math>
 |<math>94</math>
 |<math>25</math>
|}

Here <math>Q_{5} = 25</math> is a perfect square, so the first phase ends.

For the second phase, set <math>Q_{-1} = \sqrt{25} = 5</math>.  Then:

{| border="1" class="wikitable" style="text-align:center;"
 !colspan="4" | Reverse cycle
 |-
 !<math>i</math>
 !<math>b_{i}</math>
 !<math>P_{i}</math>
 !<math>Q_{i}</math>
 |-
 |<math>0</math>
 |<math>2</math>
 |<math>104</math>
 |<math>59</math>
|-
 |<math>1</math>
 |<math>3</math>
 |<math>73</math>
 |<math>98</math>
|-
 |<math>2</math>
 |<math>1</math>
 |<math>25</math>
 |<math>107</math>
|-
 |<math>3</math>
 |<math>1</math>
 |<math>82</math>
 |<math>41</math>
|-
 |<math>4</math>
 |<math>4</math>
 |<math>82</math>
 |<math></math>
|}

Here <math>P_{3} = P_{4} = 82</math>, so the second phase ends. Now calculate <math>gcd(11111, 82) = 41</math>, which is a factor of <math>11111</math>.

Thus, <math>N = 11111 = 41 \cdot 271</math>.

==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. {{citation needed|date=May 2017}}

<syntaxhighlight lang="c">
#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;
}
</syntaxhighlight>

==References==
{{Reflist}}
*{{cite book
 | author = D. A. Buell
| title = Binary Quadratic Forms
| url = https://archive.org/details/binaryquadraticf0000buel
| url-access = registration
| publisher = Springer-Verlag
| year = 1989
| isbn=0-387-97037-1 }}
*{{cite book
| author = D. M. Bressoud
| authorlink = David Bressoud
| title = Factorisation and Primality Testing
| publisher = Springer-Verlag
| year = 1989
| isbn = 0-387-97040-1
| url-access = registration
| url = https://archive.org/details/factorizationpri0000bres
}}
* {{cite book
| last=Riesel | first=Hans | authorlink=Hans Riesel
| title=Prime Numbers and Computer Methods for Factorization
| publisher=Birkhauser
|edition = 2nd
| year=1994
| isbn=0-8176-3743-5 }}
* {{cite book | author =Samuel S. Wagstaff, Jr. | title=The Joy of Factoring | publisher=American Mathematical Society | location=Providence, RI | year=2013 | isbn=978-1-4704-1048-3 |url=http://www.ams.org/bookpages/stml-68 |author-link=Samuel S. Wagstaff, Jr. |pages=163–168 }}

== External links ==
* Daniel Shanks: [https://web.archive.org/web/20181201005104/https://www.usna.edu/Users/math/wdj/_files/documents/mcmath/shanks_analysis.pdf ''Analysis and Improvement of the Continued Fraction Method of Factorization''], (transcribed by S. McMath 2004)
* Daniel Shanks: [https://web.archive.org/web/20181130202030/https://www.usna.edu/Users/math/wdj/_files/documents/mcmath/shanks_squfof.pdf ''SQUFOF Notes''], (transcribed by S. McMath 2004)
* Stephen S. McMath: [https://web.archive.org/web/20181130202028/https://www.usna.edu/Users/math/wdj/_files/documents/mcmath/TridentFinal.pdf ''Parallel integer factorization using quadratic forms''], 2005
* S. McMath, F. Crabbe, D. Joyner: [https://web.archive.org/web/20200930034823/https://www.usna.edu/Users/cs/crabbe/papers/mcmath-IJPAM.pdf ''Continued fractions and parallel SQUFOF''], 2005
* Jason Gower, Samuel Wagstaff: [http://homes.cerias.purdue.edu/~ssw/squfof.pdf ''Square Form Factorisation''] [http://www.ams.org/journals/mcom/2008-77-261/S0025-5718-07-02010-8/S0025-5718-07-02010-8.pdf (Published)]
* [https://web.archive.org/web/20231003030532/http://colin.barker.pagesperso-orange.fr/lpa/big_squf.htm Shanks's SQUFOF Factoring Algorithm]
*[https://github.com/TilmanNeumann/java-math-library java-math-library]

{{number theoretic algorithms}}

[[Category:Integer factorization algorithms]]