Shanks's square forms factorization

Input: N, the integer to be factored, which must be neither a prime number nor a perfect square.

Output: a non-trivial factor of N.

The algorithm:

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

Repeat

$b_{i}=\left\lfloor {\frac {\lfloor {\sqrt {N}}\rfloor +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.

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

Repeat

$b_{i}=\left\lfloor {\frac {\lfloor {\sqrt {N}}\rfloor +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+1}=P_{i}$.

Then $\gcd(N,P_{i})$ is a non-trivial factor of $N$.

Example:

N=11111

P0=105 Q0=1 Q1=86

P1=67 Q1=86 Q2=77

P2=87 Q2=77 Q3=46

P3=97 Q3=46 Q4=37

P4=88 Q4=37 Q5=91

P5=94 Q5=91 Q6=25

Here Q6 is a perfect square

P0=104 Q0=5 Q1=59

P1=73 Q1=59 Q2=98

P2=25 Q2=98 Q3=107

P3=82 Q3=107 Q4=41

P4=82

Here P3=P4

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

Reference: 2005, Stephen S. McMath