Shanks's square forms factorization

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: $N$, the integer to be factored, which must be neither a prime number nor a perfect square, and a small positive integer, $k$.

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

The algorithm:

Initialize $i=0,P\_0=\backslash lfloor\backslash sqrt\{kN\}\backslash rfloor,Q\_\{-1\}=1,Q\_0=kN-P\_0^2.$

Repeat

$i=i+1,b\_i=\backslash left\backslash lfloor\backslash frac\{P\_0+P\_\{i-1\}\}\{Q\_\{i-1\}\}\backslash right\backslash rfloor,P\_i=b\_iQ\_\{i-1\}-P\_\{i-1\},Q\_i=Q\_\{i-2\}+b\_i(P\_\{i-1\}-P\_i)$

until $Q\_i$ is a perfect square at some odd value of $i$.

Start the second phase (reverse cycle).

Initialize $b\_0=\backslash left\backslash lfloor\backslash frac\{P\_0-P\_i\}\{\backslash sqrt\{Q\_i\}\}\backslash right\backslash rfloor$, $Q\_\{-1\}=\backslash sqrt\{Q\_i\}$, and $P\_0=b\_0\backslash sqrt\{Q\_i\}+P\_i$, where $P\_0,\; P\_i$, and $Q\_\{i\}$ are from the previous phase. The $b\_0$ used in the calculation of $P\_0$ is the recently calculated value of $b\_0$.

Set $i=0$ and $Q\_0=\backslash frac\{kN-P\_0^2\}\{Q\_\{-1\}\}$, where $P\_0$ is the recently calculated value of $P\_0$.

Repeat

$i=i+1,b\_i=\backslash left\backslash lfloor\backslash frac\{P\_0+P\_\{i-1\}\}\{Q\_\{i-1\}\}\backslash right\backslash rfloor,P\_i=b\_iQ\_\{i-1\}-P\_\{i-1\},Q\_i=Q\_\{i-2\}+b\_i(P\_\{i-1\}-P\_i)$

until $P\_i=P\_\{i-1\}.${{cn|date=October 2023}}

Then if $f=\backslash 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$.{{cn|date=October 2023}}

Shanks' method has time complexity $O(\backslash sqrt[4]\{N\})$.{{Harvcol|Riesel|1994|p=189}}

Stephen S. McMath wrote

a more detailed discussion of the mathematics of Shanks' method,

together with a proof of its correctness.{{Cite CiteSeerX|title=Daniel Shanks' Square Forms Factorization| year=2004 |citeseerx = 10.1.1.107.9984}}

Let $N\; =\; 11111$

$Q\_\{-1\}=1$

border="1" class="wikitable" style="text-align:center; " !colspan="4" | Cycle forward
$i$ !$b\_\{i\}$ !$P\_\{i\}$ !$Q\_\{i\}$
$0$ |$$ |$105$ |$86$
$1$ |$2$ |$67$ |$77$
$2$ |$2$ |$87$ |$46$
$3$ |$4$ |$97$ |$37$
$4$ |$5$ |$88$ |$91$
$5$ |$2$ |$94$ |$25$

Here $Q\_\{5\}\; =\; 25$ is a perfect square, so the first phase ends.

For the second phase, set $Q\_\{-1\}\; =\; \backslash sqrt\{25\}\; =\; 5$. Then:

border="1" class="wikitable" style="text-align:center;" !colspan="4" | Reverse cycle
$i$ !$b\_\{i\}$ !$P\_\{i\}$ !$Q\_\{i\}$
$0$ |$2$ |$104$ |$59$
$1$ |$3$ |$73$ |$98$
$2$ |$1$ |$25$ |$107$
$3$ |$1$ |$82$ |$41$
$4$ |$4$ |$82$ |$$

Here $P\_\{3\}\; =\; P\_\{4\}\; =\; 82$, so the second phase ends. Now calculate $gcd(11111,\; 82)\; =\; 41$, which is a factor of $11111$.

Thus, $N\; =\; 11111\; =\; 41\; \backslash cdot\; 271$.

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

1. include
2. 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;

}

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

• 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