Congruence of squares

In number theory, a congruence of squares modulo an integer n is an equality

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

Such a relationship carries information useful in trying to factor the integer n: finding a congruence of squares modulo n is something sought after in integer factorization. There follows from it that

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

This means that n divides (x+y)(x−y) but not (x+y) or (x−y) alone, so both (x+y) and(x−y) contain factors of n. A simple gcd operation will extract a factor in most cases. The difficulty lies in finding x and y. This, incidentally, is what both the quadratic sieve and number field sieve do: set up a congruence of squares modulo n. This approach to factoring also shows that the problem of factoring can be reduced to the problem of finding square roots modulo n.

A case where a congruence of squares will not yield a factor is when only one of the pairs (x+y) or (x-y) shares a factor with n. This implies that the pair sharing factors with n is either equal to n or a multiple of n. The gcd of that pair and n thus will be n, and the gcd of n and the other pair is 1. In order for the congruence of squares to extract any factors, both pairs (x+y) and (x-y) must each share at least one factor with n.

Here is an example. Say n = 35. A perfect square close to 35 is 36, and, conveniently, 36 ≡ 1 (mod 35). Now 1 is also a perfect square. Thus we have our congruence:

$6^{2}\equiv 1^{2}{\pmod {35}}$

with gcd(6 + 1, 35) = 7 and gcd(6 - 1, 35) = 5. These are the two non-trivial factors of 35.