El algoritmo p − 1 de Pollard es un algoritmo de factorización de números enteros basado en la teoría 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 cuales el número que precede al factor, p − 1, es uniforme en potencia ; 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 primos seguros , que son primos para los cuales p − 1 es dos veces un primo de Sophie Germain q y, por lo tanto, mínimamente suaves. Estos primos a veces se interpretan como "seguros para fines criptográficos", pero podrían ser inseguros : en las recomendaciones actuales para primos criptográficos fuertes ( por ejemplo , ANSI X9.31), es necesario pero no suficiente que p − 1 tenga al menos un factor primo grande. La mayoría de los primos suficientemente grandes son fuertes; si un primo usado para 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 se considera obsoleta por la industria de la criptografía: el método de factorización ECM es más eficiente que el algoritmo de Pollard y encuentra factores primos seguros con la misma rapidez que encuentra factores primos no seguros de tamaño similar, por lo tanto, el tamaño de p es el parámetro de seguridad clave, no la suavidad de p-1 . [1]
Sea n un entero compuesto con factor primo p . Por el pequeño teorema de Fermat , sabemos que para todos los enteros a coprimos con 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 múltiplo grande de p − 1 convirtiéndolo en un número con muchos factores primos; generalmente, tomamos el producto de todas las potencias primas menores que un límite B . Empezamos con una x aleatoria y la reemplazamos repetidamente por a medida que w recorre esas potencias primas. Verifica en cada etapa, o una vez al final si lo prefieres, si mcd( x − 1, n ) no es igual a 1.
Es posible que para todos los factores primos p de n , p − 1 sea divisible por primos pequeños, en cuyo punto el algoritmo p − 1 de Pollard simplemente devuelva n .
El algoritmo básico se puede escribir de la siguiente manera:
Si g = 1 en el paso 6, esto indica que no hay factores primos p para los cuales p-1 sea B -potencialmente uniforme. Si g = n en el paso 7, esto generalmente indica que todos los factores fueron B- potencialmente uniformes, pero en casos raros podría indicar que a tenía un orden pequeño módulo n . Además, 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 ) ; valores mayores de B hacen que se ejecute más lento, pero es más probable que produzcan un factor.
Si queremos factorizar el número n = 299.
Dado que el algoritmo es incremental, puede seguir ejecutándose con el límite en constante aumento.
Supongamos que p − 1, donde p es el factor primo más pequeño de n , se puede modelar como un número aleatorio de tamaño menor que √ n . Por el teorema de Dixon , la probabilidad de que el factor más grande de dicho número sea menor que ( p − 1) 1/ε es aproximadamente ε − ε ; por lo que existe 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 la curva elíptica es más rápido que el método p − 1 de Pollard 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.
A veces se utiliza una variante del algoritmo básico; en lugar de exigir que p − 1 tenga todos sus factores menores que B , exigimos que tenga todos menos uno de sus factores menores que algún B 1 , y el factor restante menor que algún 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 comprobar si mcd( Q , n ) produce un factor no trivial de n . Como antes, las exponenciaciones se pueden hacer 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 normalmente B 1 > 2 , d n son números pares. La distribución de números primos es tal que los 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 pueden 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.
![{\displaystyle Q=\prod _{{\text{primos}}q\in (B_{1},B_{2}]}(H^{q}-1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d707718b165c2175710c6ff2bd4b67e7f8ce548)