CONGRUENCE OF SQUARES

In number theory, a 'congruence of squares' is a congruence commonly used in integer factorization algorithms.

Contents

Derivation

Example

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'' = ''x''² - ''y''² = (''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$
otequiv 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\}$
There is a good chance that ''n'' will have common factor(s) with (''x'' + ''y'') (''x'' - ''y''). Computing the greatest common divisors of (''x'' + ''y'', ''n'') and (''x'' - ''y'', ''n'') is enough to tell us whether we can extract a factorization from ''x'', ''y''; 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.

Example

We take ''n'' = 35. We find that
:$extstyle\; 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.