Editing Congruence of squares (section)

==Derivation==
Given a positive [[integer]] ''n'', [[Fermat's factorization method]] relies on finding numbers ''x'' and ''y'' satisfying the [[equation|equality]]

:<math>x^2 - y^2 = n</math>

We can then factor ''n'' = ''x''<sup>2</sup>&thinsp;−&thinsp;''y''<sup>2</sup> = (''x''&thinsp;+&thinsp;''y'')(''x''&thinsp;−&thinsp;''y''). This algorithm is slow in practice because we need to search many such numbers, and only a few satisfy the equation. However, ''n'' may also be factored if we can satisfy the weaker '''congruence of squares''' conditions:

:<math>x^2 \equiv y^2 \pmod{n}</math>
:<math>x \not\equiv \pm y \,\pmod{n}</math>

From here we easily deduce
:<math>x^2 - y^2 \equiv 0 \pmod{n}</math>
:<math>(x + y)(x - y) \equiv 0 \pmod{n}</math>

This means that ''n'' [[divisor|divides]] the product (''x''&thinsp;+&thinsp;''y'')(''x''&thinsp;−&thinsp;''y'').  The second non-triviality condition guarantees that ''n'' does not divide (''x''&thinsp;+&thinsp;''y'') nor (''x''&thinsp;−&thinsp;''y'') individually.  Thus (''x''&thinsp;+&thinsp;''y'') and (''x''&thinsp;−&thinsp;''y'') each contain some, but not all, factors of ''n'', and the [[greatest common divisor]]s of (''x''&thinsp;+&thinsp;''y'', ''n'') and of (''x''&thinsp;−&thinsp;''y'', ''n'') will give us these factors.  This can be done quickly using the [[Euclidean algorithm]].

Most algorithms for finding congruences of squares do not actually guarantee non-triviality; they only make it likely.  There is a chance that a congruence found will be trivial, in which case we need to continue searching for another ''x'' and ''y''.

Congruences of squares are extremely useful in integer factorization algorithms.  Conversely, because finding [[Square root#In rings in general|square root]]s modulo a [[composite number]] turns out to be probabilistic polynomial-time equivalent to factoring that number, any integer factorization algorithm can be used efficiently to identify a congruence of squares.