Congruence of squares

It is also possible to use factor bases to help find congruences of squares more quickly. Instead of looking for ${\displaystyle \textstyle x^{2}\equiv y^{2}{\pmod {n}}}$ from the outset, we find many ${\displaystyle \textstyle x^{2}\equiv y{\pmod {n}}}$ where the y have small prime factors, and try to multiply a few of these together to get a square on the right-hand side.

We take n = 35 and find that

${\displaystyle \textstyle 6^{2}=36\equiv 1\equiv 1^{2}{\pmod {35}}}$.

We thus factor as

${\displaystyle \gcd(6-1,35)\cdot \gcd(6+1,35)=5\cdot 7=35}$

Using n = 1649, as an example of finding a congruence of squares built up from the products of non-squares (see Dixon's factorization method), first we obtain several congruences

${\displaystyle 41^{2}\equiv 32{\pmod {1649}}}$

${\displaystyle 42^{2}\equiv 115{\pmod {1649}}}$

${\displaystyle 43^{2}\equiv 200{\pmod {1649}}}$

of these, two have only small primes as factors

${\displaystyle 32=2^{5}}$

${\displaystyle 200=2^{3}\cdot 5^{2}}$

and a combination of these has an even power of each small prime, and is therefore a square

${\displaystyle 32\cdot 200=2^{5+3}\cdot 5^{2}=2^{8}\cdot 5^{2}=(2^{4}\cdot 5)^{2}=80^{2}}$

yielding the congruence of squares

${\displaystyle 32\cdot 200=80^{2}\equiv 41^{2}\cdot 43^{2}\equiv 114^{2}{\pmod {1649}}}$

So using the values of 80 and 114 as our x and y gives factors

${\displaystyle \gcd(114-80,1649)\cdot \gcd(114+80,1649)=17\cdot 97=1649.}$