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



Entón podemos factorizar n = x2 − y 2 = ( 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:




De aquí deducimos facilmente




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 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  directamente, atopamos moitas "relacións"  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

  .

Deste xeito, factorizamos como



 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





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.



obtendo a congruencia de cadrados



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



 Notas 


 Véxase tamén 

 Bibliografía 



 Outros artigos 
 Relación de congruencia.
 Aritmética modular
 Ligazóns externas 
 Quadratic Congruences Dušan Đukić.

Categoría:Teoría de números
Categoría:Wikipedia:Páxinas con traducións non revisadas