The Congruence of squares reference article from the English Wikipedia on 24-Jul-2004 (provided by Fixed Reference: snapshots of Wikipedia from wikipedia.org)

Congruence of squares

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

.

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

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:

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

This is the "Congruence of squares" reference article from the English Wikipedia. All text is available under the terms of the GNU Free Documentation License. See also our Disclaimer.