Congruence of squares

From Free net encyclopedia

In number theory, a congruence of squares is a congruence

<math>x^2\equiv y^2 \pmod{n}\hbox{ where }x\not\equiv \pm y\pmod{n}</math>.

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

<math>

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}. </math>

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.

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:

<math>6^2\equiv 1^2\pmod{35}</math>

with gcd(6 + 1, 35) = 7 and gcd(6 - 1, 35) = 5. These are the two non-trivial factors of 35.fr:Congruence de carrés