Congruència de quadrats

En teoria de nombres, i més concretament en aritmètica modular una congruència de quadrats és una congruència que es fa servir normalment en els algorismes de factorització dels enters.

Deducció

Donat un enter positiu n, El Mètode de factorització de Fermat es basa a trobar nombres x, y que satisfacin la següent equació:

$x^{2}-y^{2}=n\,\!$

Llavors es pot factoritzar n = x² − y² = (x + y) (x − y). Però, aquest algorisme, a la pràctica és lent perquè cal cercar molts nombres, i només uns quants satisfan aquesta equació tan estricta. Però, n també es pot factoritzar si se satisfà una congruència de quadrats més feble.

$x^{2}\equiv y^{2}{\pmod {n}}{\hbox{, }}x\not \equiv \pm y{\pmod {n}}$.

És a dir la diferència dels quadrats ara ja no cal que sigui exactament igual a n sinó que n'hi ha prou que sigui un múltiple de n. A partir d'aquí es dedueix fàcilment

$x^{2}-y^{2}\equiv 0{\pmod {n}}{\hbox{, }}(x+y)(x-y)\equiv 0{\pmod {n}}$

Això vol dir que n divideix (x + y) (x − y). Però s'ha imposat que x ≠ ±y (mod n), per tant n no divideix ni (x+y) ni (x−y) tots sols. Així (x+y) i (x−y) tots dos contenen factors comuns propis (diferents d'1) amb n. Calculant el màxim comú divisor de (x + y, n) i el de (x − y, n) s'obtenen aquests factors; això es pot trobar de foma molt ràpida fent servir l'algorisme d'Euclides.

Les congruències de quadrats són molt útils en els algorismes de factorització dels enters. Aquesta congruència es fa servir de forma extensiva, per exemple en el garbell quadràtic, l'algorisme general del garbell del cos de nombres, la factorització amb fraccions contínues, etc.

Exemple

Si es considera n = 35. Es troba que

$\textstyle 6^{2}\equiv 36\equiv 1\equiv 1^{2}{\pmod {n}}$.

Per tant es pot factoritzar 35 amb Mcd(6 − 1, 35) = 5 i Mcd(6 + 1, 35) = 7.

Generalitzacions

També es pot fer servir una base de factorització per ajudar a trobar de forma més ràpida congruències de quadrats. I en comptes de buscar $\textstyle x^{2}\equiv y^{2}{\pmod {n}}$ directament, es busquen molts $\textstyle x^{2}\equiv y{\pmod {n}}$ on els y tenen factors primers petits, i es prova de multiplicar uns quants entre ells per tal d'obtenir un quadrat al cantó dret.