Congruence of squares

From Wikipedia, the free encyclopedia

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

[edit] Derivation

Given a positive integer $\textstyle n$ , Fermat's factorization method relies on finding numbers $\textstyle x, y$ satisfying the equality

x 2 - y 2 = n

We can then factor $\textstyle n = x^2 - y^2 = (x + y)(x - y)$ . However, this algorithm is slow in practice because we need to search many such numbers, and only a few satisfy this strict equation. However, $\textstyle n$ can also be factored if we satisfy the weaker congruence of squares

$x^2 \equiv y^2 \pmod{n} \hbox{ , } x \not\equiv \pm y \pmod{n}$ .

From here we easily deduce

$x^2 - y^2 \equiv 0 \pmod{n} \hbox{ , } (x + y)(x - y) \equiv 0 \pmod{n}$

There is a good chance that $\textstyle n$ will have common factor(s) with $\textstyle (x + y)(x - y)$ . Computing the greatest common divisors of $\textstyle (x + y, n)$ and $\textstyle (x - y, n)$ is enough to tell us whether we can extract a factorization from $\textstyle x, y$ ; this can be done quickly using the Euclidean algorithm.