Editing Congruence of squares

{{Citations|date=January 2024}}
In [[number theory]], a '''congruence of squares''' is a [[modular arithmetic|congruence]] commonly used in [[integer factorization]] algorithms.

==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.

==Using a factor base==
A technique pioneered by [[Dixon's factorization method]] and improved by [[continued fraction factorization]], the [[quadratic sieve]], and the [[general number field sieve]], is to construct a congruence of squares using a [[factor base]].

Instead of looking for one pair <math>\textstyle x^2 \equiv y^2 \pmod n</math> directly, we find many "relations" <math>\textstyle x^2 \equiv y \pmod n</math> where the ''y'' have only small [[prime number|prime]] factors (they are [[smooth numbers]]), and multiply some of them together to get a [[square (algebra)|square]] on the right-hand side.

The set of small primes which all the ''y'' factor into is called the factor base.<!--The factor base generally includes -1 as well, a detail omitted here-->  Construct a [[logical matrix]] where each row describes one ''y'', each column corresponds to one prime in the factor base, and the entry is the parity (even or odd) of the number of times that factor occurs in ''y''.  Our goal is to select a subset of rows whose sum is the all-zero row.  This corresponds to a set of ''y'' values whose product is a square number, i.e. one whose factorization has only even exponents.  The products of ''x'' and ''y'' values together form a congruence of squares.

This is a classic [[system of linear equations]] problem, and can be efficiently solved using [[Gaussian elimination]] as soon as the number of rows exceeds the number of columns.<!--Not "equals"; that would only guarantee the trivial solution "choose no rows".-->  Some additional rows are often included to ensure that several solutions exist in the nullspace of our matrix, in case the first solution produces a trivial congruence.

A great advantage of this technique is that the search for relations is [[embarrassingly parallel]]; a large number of computers can be set to work searching different ranges of ''x'' values and trying to factor the resultant ''y''s.  Only the found relations need to be reported to a central computer, and there is no particular hurry to do so.  The searching computers do not even have to be trusted; a reported relation can be verified with minimal effort.

There are numerous elaborations on this technique.  For example, in addition to relations where ''y'' factors completely in the factor base, the "large prime" variant also collects "partial relations" where ''y'' factors completely except for one larger factor.  A second partial relation with the same larger factor can be multiplied by the first to produce a "complete relation".

==Examples==
===Factorize 35===
We take ''n''&nbsp;=&nbsp;35 and find that 

:<math>\textstyle 6^2 = 36 \equiv 1 = 1^2 \pmod{35}</math>. 

We thus factor as

:<math> \gcd( 6-1, 35 ) \cdot \gcd( 6+1, 35 ) = 5 \cdot 7 = 35</math>

===Factorize 1649===
Using ''n''&nbsp;=&thinsp;1649, as an example of finding a congruence of squares built up from the products of non-squares (see [[Dixon's factorization method]]), first we obtain several congruences

:<math>41^2 \equiv 32 = 2^5 \pmod{1649},</math>
:<math>42^2 \equiv 115 = 5 \cdot 23 \pmod{1649},</math>
:<math>43^2 \equiv 200 = 2^3 \cdot 5^2 \pmod{1649}.</math>

Of these, the first and third have only small primes as factors, and a product of these has an [[parity (mathematics)|even]] power of each small prime, and is therefore a square

:<math>32 \cdot 200 = 2^{5+3} \cdot 5^2 = 2^8 \cdot 5^2 = (2^4 \cdot 5)^2 = 80^2</math>

yielding the congruence of squares

:<math>32 \cdot 200 = 80^2 \equiv 41^2 \cdot 43^2 \equiv 114^2 \pmod{1649}.</math>

So using the values of 80 and 114 as our ''x'' and ''y'' gives factors

:<math>\gcd( 114-80, 1649 ) \cdot \gcd( 114+80, 1649 ) = 17 \cdot 97 = 1649.</math>

== See also ==
*[[Congruence relation]]

== References ==
<!--{{reflist}}-->
{{refbegin}}
* {{cite book |first=David M. |last=Bressoud |authorlink=David Bressoud |title=Factorization and Primality Testing |chapter=8. The Quadratic Sieve |year=1989 |isbn=0-387-97040-1 |series=Undergraduate Texts in Mathematics |publisher=Springer-Verlag |url=https://ndl.ethernet.edu.et/bitstream/123456789/23097/1/David%20M.%20Bressoud.pdf#page=115}}
* {{cite book |first=Hans |last=Reisel |title=Prime Numbers and Computer Methods for Factorization  |edition=2nd |series=Progress in Mathematics |volume=126 |year=1994 |isbn=0-8176-3743-5 |publisher=Birkhaüser}}
* {{cite book |first=Samuel S. Jr. |last=Wagstaff  |authorlink=Samuel S. Wagstaff Jr. |title=The Joy of Factoring |publisher=[[American Mathematical Society]] |series=Student mathematical library |volume=68 |location=Providence, RI |year=2013 |isbn=978-1-4704-1048-3 |pages=195–202}}
{{refend}}

<!--== External links ==-->

{{DEFAULTSORT:Congruence Of Squares}}
[[Category:Equivalence (mathematics)]]
[[Category:Integer factorization algorithms]]
[[Category:Modular arithmetic]]
[[Category:Squares in number theory]]