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² − y ² = ( x + y )( x − 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 + y )( x − y). A segunda condición non trivial garante que n non divide (x + y) nin (x − y) individualmente. Así (x + y) e (x − y) cada un contén algúns factores de n, mais non todos, e os máximos comúns divisores de (x + y, n) e de (x − 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 coste 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 y 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 = 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

Bressoud, David M. (1989). "8. The Quadratic Sieve". Factorization and Primality Testing (PDF). Undergraduate Texts in Mathematics. Springer-Verlag. ISBN 0-387-97040-1.
Reisel, Hans (1994). Prime Numbers and Computer Methods for Factorization. Progress in Mathematics 126 (2nd ed.). Birkhaüser. ISBN 0-8176-3743-5.
Wagstaff, Samuel S. Jr. (2013). The Joy of Factoring. Student mathematical library 68. Providence, RI: American Mathematical Society. pp. 195–202. ISBN 978-1-4704-1048-3.

Outros artigos

Ligazóns externas

Quadratic Congruences Dušan Đukić.