En la teoría computacional de números , una base de factores es un pequeño conjunto de números primos que se usan comúnmente como una herramienta matemática en algoritmos que involucran un cribado extenso de factores potenciales de un entero dado.
Uso en algoritmos de factorización
Una base de factores es un conjunto relativamente pequeño de números primos distintos P , a veces junto con -1. [1] Supongamos que queremos factorizar un número entero n . Generamos, de alguna manera, una gran cantidad de pares de enteros ( x , y ) para los cuales, , y puede ser completamente factorizar más que el factor elegido de base, es decir, todos sus factores primos están en P .
En la práctica, se encuentran varios enteros x tales quetiene todos sus factores primos en la base de factores preseleccionada. Representamos a cada unoexpresión como vector de una matriz con entradas enteras como exponentes de factores en la base de factores. Las combinaciones lineales de las filas corresponden a la multiplicación de estas expresiones. Una relación de dependencia lineal mod 2 entre las filas conduce a una congruencia deseada. [2] Esto esencialmente reformula el problema en un sistema de ecuaciones lineales , que puede resolverse utilizando numerosos métodos como la eliminación gaussiana ; en la práctica se utilizan métodos avanzados como el algoritmo de bloque de Lanczos , que aprovechan determinadas propiedades del sistema.
Esta congruencia puede generar la trivial ; en este caso intentamos encontrar otra congruencia adecuada. Si los intentos repetidos de factorizar fallan, podemos volver a intentarlo usando una base de factores diferente.
Algoritmos
Las bases de factores se utilizan, por ejemplo, en la factorización de Dixon , el tamiz cuadrático y el tamiz de campo numérico . La diferencia entre estos algoritmos es esencialmente los métodos utilizados para generar candidatos ( x , y ). Las bases de factores también se utilizan en el algoritmo de cálculo de índices para calcular logaritmos discretos. [3]
Referencias
- ^ Koblitz, Neal (1987), Un curso de teoría de números y criptografía , Springer-Verlag, p. 133, ISBN 0-387-96576-9
- ^ Trappe, Wade; Washington, Lawrence C. (2006), Introducción a la criptografía con teoría de la codificación (2ª ed.), Prentice-Hall, p. 185, ISBN 978-0-13-186239-5
- ^ Stinson, Douglas R. (1995), Criptografía / Teoría y práctica , CRC Press, p. 171, ISBN 0-8493-8521-0