Congruencia de cadrados

En teoría de números, unha **congruencia de cadrados** é unha congruencia que se usa habitualmente nos algoritmos de factorización de enteiros.

## Dedución 
Dado un número enteiro positivo *n*, o método de factorización de Fermat baséase en atopar números *x* e *y* que satisfagan a igualdade

: x^2 - y^2 = n

Entón podemos factorizar *n* = *x*2&#x2009;−&#x2009;*y* 2 = ( *x*&#x2009;+&#x2009;*y* )( *x*&#x2009;−&#x2009;*y*). Este algoritmo é lento na práctica porque necesitamos buscar moitos destes números, e só algúns satisfán a ecuación. No entanto, *n* tamén se pode factorizar se podemos satisfacer as condicións máis débiles de **congruencia de cadrados**:

: x^2 \equiv y^2 \pmod{n}
: x \not\equiv \pm y \,\pmod{n}

De aquí deducimos facilmente

: x^2 - y^2 \equiv 0 \pmod{n}
: (x + y)(x - y) \equiv 0 \pmod{n}

Isto significa que *n* divide o produto ( *x*&#x2009;+&#x2009;*y* )( *x*&#x2009;−&#x2009;*y*). A segunda condición non trivial garante que *n* non divide (*x*&#x2009;+&#x2009;*y*) nin (*x*&#x2009;−&#x2009;*y*) individualmente. Así (*x*&#x2009;+&#x2009;*y*) e (*x*&#x2009;−&#x2009;*y*) cada un contén algúns factores de *n*, mais non todos, e os máximos comúns divisores de (*x*&#x2009;+&#x2009;*y*, *n*) e de (*x*&#x2009;−&#x2009;*y*, *n*) daranos estes factores. Isto pódese facer rapidamente usando o algoritmo deEeuclides.

As congruencias de cadrados son moi útiles nos algoritmos de factorización de enteiros. E viceversa, debido a que atopar raíces cadradas módulo un número composto resulta ter un custo probabilístico de tempo polinómico equivalente a factorizar ese número, calquera algoritmo de factorización de enteiros pode usarse de forma eficiente para identificar unha congruencia de cadrados.

## Usando unha base de factores 
Unha técnica iniciada polo método de factorización de Dixon e mellorada pola factorización continua de fraccións, a criba cadrática e a criba xeral de corpos numéricos, é construír unha congruencia de cadrados utilizando unha base de factores.

En vez de buscar un par \textstyle x^2 \equiv y^2 \pmod n directamente, atopamos moitas "relacións" \textstyle x^2 \equiv y \pmod n onde os *y* só teñen factores primos pequenos (son números suaves), e multiplíquanse algúns deles para obter un cadrado no lado dereito.

O conxunto de pequenos primos no que *factoriza* chámase base de factores. Constrúese unha matriz lóxica onde cada fila describa un *y*, cada columna corresponde a un primo na base do factor e a entrada sexa a paridade (par ou impar) do número de veces que ese factor ocorre en *y*. O noso obxectivo é seleccionar un subconxunto de filas cuxa suma sexa a fila de ceros. Isto corresponde a un conxunto de valores *y* cuxo produto é un número cadrado, é dicir, un produto cuxa factorización só ten expoñentes pares. Os produtos dos valores *x* e *y* xuntos forman unha congruencia de cadrados.

Este é un problema clásico dun sistema de ecuacións lineares, e pódese resolver de forma eficiente mediante a eliminación de Gauss tan pronto como o número de filas supere o número de columnas. Moitas veces inclúense algunhas filas adicionais para garantir que existen varias solucións no espazo nulo da nosa matriz, no caso de que a primeira solución produza unha congruencia trivial.

## Exemplos 
### Factorizar 35 
Tomamos *n* = 35 e atopamos que

: \textstyle 6^2 = 36 \equiv 1 = 1^2 \pmod{35} .

Deste xeito, factorizamos como

:  \gcd( 6-1, 35 ) \cdot \gcd( 6+1, 35 ) = 5 \cdot 7 = 35

### Factorizar 1649 
Usando *n* =&#x2009;1649, como exemplo de atopar unha congruencia de cadrados construídos a partir dos produtos de non cadrados (véxase o método de factorización de Dixon), primeiro obtemos varias congruencias

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

Delas, a primeira e a terceira só teñen como factores primos pequenos, e un produto destes ten unha potencia par de cada primo pequeno e, polo tanto, é un cadrado.

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

obtendo a congruencia de cadrados

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

Entón, usando os valores de 80 e 114 como os nosos *x* e *y* dá factores

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

## Notas 
## Véxase tamén 
### Bibliografía 
* 
* 
* 
### Outros artigos 
* Relación de congruencia.
* Aritmética modular
### Ligazóns externas 
* Quadratic Congruences Dušan Đukić.