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 n, Fermat's factorization method relies on finding numbers x, y satisfying the equality

x^2 - y^2 = n\,\!

We can then factor n = x2 − y2 = (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, 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}

This means that n divides (x + y) (x − y). However we have required that x ≠ ±y (mod n), so n divides neither (x+y) nor (x−y) alone. Thus (x+y) and (x−y) each contain proper factors of n. Computing the greatest common divisors of (x + y, n) and of (x − y, n) will give us these factors; this can be done quickly using the Euclidean algorithm.

Congruences of squares are extremely useful in integer factorization algorithms. This congruence is extensively used in, for example, the quadratic sieve, general number field sieve, continued fraction factorization, Dixon's factorization, and so on.

[edit] Example

We take n = 35. We find that

\textstyle 6^2 \equiv 36 \equiv 1 \equiv 1^2 \pmod{n}.

We can thus factor 35 as gcd(6 − 1, 35) = 5 and gcd(6 + 1, 35) = 7.

[edit] Further Example

We take n = 15. We find that

\textstyle 7^2 \equiv 49 \equiv 4 \equiv 2^2 \pmod{n}.

We can thus factor 15 as gcd(7 − 2, 15) = 5 and gcd(7 + 2, 15) = 3.

So 3 and 5 are factors of 15 (In this simple case, of course, these are the only two factors. This need not be the case).

Languages