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
[editar | editar a fonte]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 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
[editar | editar a fonte]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 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
[editar | editar a fonte]Factorizar 35
[editar | editar a fonte]Tomamos n = 35 e atopamos que
- .
Deste xeito, factorizamos como
Factorizar 1649
[editar | editar a fonte]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
[editar | editar a fonte]Véxase tamén
[editar | editar a fonte]Bibliografía
[editar | editar a fonte]- 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
[editar | editar a fonte]Ligazóns externas
[editar | editar a fonte]