Base de factores

Na teoría computacional de números, unha base de factores é un pequeno conxunto de números primos que se usan habitualmente como ferramenta matemática en algoritmos que implican unha gran criba de factores potenciais dun número enteiro dado.

Uso en algoritmos de factorización

Unha base de factores é un conxunto P relativamente pequeno de números primos distintos, ás veces xunto con -1.^[1] Digamos que queremos factorizar un número enteiro n. Xeramos, dalgún xeito, un gran número de pares de enteiros (x, y) para os que $x\neq \pm y$ , $x^{2}\equiv y^{2}{\pmod {n}}$ , e $x^{2}{\pmod {n}}{\text{ e }}y^{2}{\pmod {n}}$ pódese factorizar completamente sobre a base de factores escollida, é dicir, todos os seus factores primos están en P.

Na práctica, atópanse varios números enteiros x tal que $x^{2}{\pmod {n}}$ ten todos os seus factores primos na base de factores preescollida. Representamos cada expresión $x^{2}{\pmod {n}}$ como un vector dunha matriz con entradas enteiras estando os expoñentes dos factores na base de factores. As combinacións lineares das filas corresponden á multiplicación destas expresións. Unha relación de dependencia linear mod 2 entre as filas conduce a unha congruencia desexada $x^{2}\equiv y^{2}{\pmod {n}}$ . ^[2] Isto esencialmente reformula o problema nun sistema de ecuacións lineares, que se pode resolver usando numerosos métodos como a eliminación de Gauss; na práctica utilízanse métodos avanzados como o algoritmo de bloque de Lanczos, que aproveita certas propiedades do sistema.

Algoritmos

As bases de factores utilízanse, por exemplo, na factorización de Dixon, na criba cadrática e na criba xeral de corpos numéricos. A diferenza entre estes algoritmos son esencialmente os métodos utilizados para xerar candidatos (x, y). As bases de factores tamén se usan no algoritmo de cálculo do índice para calcular logaritmos discretos.^[3]

Notas

↑ Koblitz, Neal (1987). A Course in Number Theory and Cryptography. Springer-Verlag. p. 133. ISBN 0-387-96576-9.
↑ Trappe, Wade; Washington, Lawrence C. (2006). Introduction to Cryptography with Coding Theory (2nd ed.). Prentice-Hall. p. 185. ISBN 978-0-13-186239-5.
↑ Stinson, Douglas R. (1995). Cryptography / Theory and Practice. CRC Press. p. 171. ISBN 0-8493-8521-0.

Véxase tamén

Bibliografía

Outros artigos

Criba de Eratóstenes.

[1] Koblitz, Neal (1987). A Course in Number Theory and Cryptography. Springer-Verlag. p. 133. ISBN 0-387-96576-9.

[2] Trappe, Wade; Washington, Lawrence C. (2006). Introduction to Cryptography with Coding Theory (2nd ed.). Prentice-Hall. p. 185. ISBN 978-0-13-186239-5.

[3] Stinson, Douglas R. (1995). Cryptography / Theory and Practice. CRC Press. p. 171. ISBN 0-8493-8521-0.

[1]

[2]

[3]