El algoritmo p - 1 de Pollard es un algoritmo de factorización de enteros teórico de números , inventado por John Pollard en 1974. Es un algoritmo de propósito especial, lo que significa que solo es adecuado para números enteros con tipos específicos de factores; es el ejemplo más simple de un algoritmo de factorización de grupos algebraicos .
Los factores que encuentra son aquellos para los que el número que precede al factor, p - 1, es powersmooth ; la observación esencial es que, al trabajar en el grupo multiplicativo módulo un número compuesto N , también estamos trabajando en los grupos multiplicativos módulo todos los factores de N.
La existencia de este algoritmo conduce al concepto de números primos seguros , que son primos para los que p - 1 es dos veces un primo q de Sophie Germain y, por lo tanto, mínimamente suave. Estos números primos a veces se interpretan como "seguros para fines criptográficos", pero pueden no ser seguros ; en las recomendaciones actuales para primos fuertes criptográficos ( p . Ej., ANSI X9.31 ), es necesario, pero no suficiente, que p - 1 tenga al menos un número primo grande. factor. La mayoría de los números primos suficientemente grandes son fuertes; si un primo utilizado con fines criptográficos resulta no ser fuerte, es mucho más probable que sea por malicia que por un accidente de generación de números aleatorios . Esta terminología es considerada obsoleta por la industria de la criptografía: ECM hace que los números primos seguros sean tan fáciles de factorizar como los no seguros, por lo que el tamaño es el factor importante. [1]
Conceptos base
Sea n un entero compuesto con factor primo p . Por el pequeño teorema de Fermat , sabemos que para todos los enteros una primos entre sí a p y para todos los enteros positivos K :
Si un número x es congruente con 1 módulo un factor de n , entonces el mcd ( x - 1, n ) será divisible por ese factor.
La idea es hacer que el exponente sea un gran múltiplo de p - 1 convirtiéndolo en un número con muchos factores primos; Generalmente, se toma el producto de todos los poderes primos menores que un límite B . Comience con una x aleatoria y reemplácela repetidamente pormientras w atraviesa esos poderes primarios. Compruebe en cada etapa, o una vez al final si lo prefiere, si mcd ( x - 1, n ) no es igual a 1.
Múltiples factores
Es posible que para todos los factores primos p de n , p - 1 sea divisible por pequeños números primos, en cuyo punto el algoritmo Pollard p - 1 le da n nuevamente.
Algoritmo y tiempo de ejecución
El algoritmo básico se puede escribir de la siguiente manera:
- Entradas : n : un número compuesto
- Salida : un factor no trivial de n o fracaso
- seleccione un límite de suavidad B
- definir (nota: la evaluación explícita de M puede no ser necesaria)
- escoger al azar un primos entre sí a n (nota: en realidad podemos arreglar una , por ejemplo, si n es impar, entonces siempre se puede seleccionar un = 2, selección aleatoria aquí no es imprescindible)
- calcular g = mcd ( a M - 1, n ) (nota: la exponenciación se puede hacer módulo n )
- si 1 < g < n entonces devuelve g
- si g = 1 , seleccione una B más grande y vaya al paso 2 o devuelva la falla
- si g = n , seleccione una B más pequeña y vaya al paso 2 o devuelva la falla
Si g = 1 en el paso 6, esto indica que no hay factores primos p para los que p-1 es B -poderes suave. Si g = n en el paso 7, esto generalmente indica que todos los factores fueron B -powersuave, pero en casos raros podría indicar que a tenía un módulo n de orden pequeño . Por cierto, cuando los factores primos máximos de p-1 para cada factor primo p de n son todos iguales en algunos casos raros, este algoritmo fallará.
El tiempo de ejecución de este algoritmo es O ( B × log B × log 2 n ) ; los valores más altos de B lo hacen funcionar más lento, pero es más probable que produzcan un factor.
Ejemplo
Si queremos factorizar el número n = 299.
- Seleccionamos B = 5.
- Por tanto, M = 2 2 × 3 1 × 5 1 .
- Seleccionamos a = 2.
- g = mcd ( una M - 1, n ) = 13.
- Dado que 1 <13 <299, devuelve 13.
- 299/13 = 23 es primo, por lo que se factoriza completamente: 299 = 13 × 23.
¿Cómo elegir B ?
Dado que el algoritmo es incremental, puede seguir ejecutándose con el límite en constante aumento.
Suponga que p - 1, donde p es el factor primo más pequeño de n , puede modelarse como un número aleatorio de tamaño menor que √ n . Según el teorema de Dixon, la probabilidad de que el factor más grande de tal número sea menor que ( p - 1) 1 / ε es aproximadamente ε - ε ; por lo que hay una probabilidad de aproximadamente 3 −3 = 1/27 de que un valor B de n 1/6 produzca una factorización.
En la práctica, el método de curva elíptica es más rápido que el método Pollard p - 1 una vez que los factores son grandes; ejecutar el método p - 1 hasta B = 2 32 encontrará una cuarta parte de todos los factores de 64 bits y 1/27 de todos los factores de 96 bits.
Variante de dos etapas
A veces se utiliza una variante del algoritmo básico; en lugar de requerir que p - 1 tenga todos sus factores menores que B , requerimos que todos menos uno de sus factores sean menores que algunos B 1 , y el factor restante menor que algunos B 2 ≫ B 1 . Después de completar la primera etapa, que es la misma que el algoritmo básico, en lugar de calcular un nuevo
para B 2 y comprobando mcd ( a M ' - 1, n ) , calculamos
donde H = a M y verifique si mcd ( Q , n ) produce un factor no trivial de n . Como antes, las exponenciaciones se pueden realizar en módulo n .
Sean { q 1 , q 2 ,…} números primos sucesivos en el intervalo ( B 1 , B 2 ] y d n = q n - q n −1 la diferencia entre números primos consecutivos. Dado que típicamente B 1 > 2 , d n son números pares. La distribución de números primos es tal que d n serán todos relativamente pequeños. Se sugiere que d n ≤ ln 2 B 2. Por lo tanto, los valores de H 2 , H 4 , H 6 ,… ( mod n ) se puede almacenar en una tabla, y H q n se puede calcular a partir de H q n −1 ⋅ H d n , ahorrando la necesidad de exponenciaciones.
Implementaciones
- El paquete GMP-ECM incluye una implementación eficiente del método p - 1.
- Prime95 y MPrime , los clientes oficiales de Great Internet Mersenne Prime Search , utilizan una versión modificada del algoritmo p - 1 para eliminar posibles candidatos.
Ver también
Referencias
- ^ ¿Qué son los números primos fuertes y son necesarios para el sistema RSA? , Laboratorios RSA (2007)
- Pollard, JM (1974). "Teoremas de factorización y pruebas de primalidad". Actas de la Sociedad Filosófica de Cambridge . 76 (3): 521–528. Código Bib : 1974PCPS ... 76..521P . doi : 10.1017 / S0305004100049252 .
- Montgomery, PL; Silverman, RD (1990). "Una extensión FFT al algoritmo de factorización P - 1" . Matemáticas de la Computación . 54 (190): 839–854. Código Bibliográfico : 1990MaCom..54..839M . doi : 10.1090 / S0025-5718-1990-1011444-3 .
- Samuel S. Wagstaff, Jr. (2013). La alegría de la factorización . Providence, RI: Sociedad Matemática Estadounidense. págs. 138-141. ISBN 978-1-4704-1048-3.