Congruence of squares
|
|
In number theory, a congruence of squares modulo an integer n is an equality
- <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.
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:
- <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.