## Wednesday, August 1, 2018

### Congruence of squares - Wikipedia

Congruence of squares - Wikipedia

# Congruence of squares

In number theory, a congruence of squares is a congruence commonly used in integer factorization algorithms.

## ExamplesEdit

### Factorize 35Edit

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

### Factorize 1649Edit

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