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 sólo 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 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 el grupo multiplicativo 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 q de Sophie Germain y, por lo tanto, mínimamente suaves. Estos números primos a veces se interpretan como "seguros para fines criptográficos", pero pueden no ser seguros ; en las recomendaciones actuales para números primos criptográficos fuertes ( por ejemplo , 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 primos suficientemente grandes son fuertes; Si un número primo utilizado con fines criptográficos resulta no ser fuerte, es mucho más probable que se deba a malicia que a un accidente de generación de números aleatorios . Esta terminología se considera obsoleta en 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 tan rápidamente como factores primos no seguros de tamaño similar, por lo que 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 números enteros un coprimo con p y para todos los números 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 algún límite B. Comience con una x aleatoria y reemplácela repetidamente por mientras w recorre esos poderes primarios. Verifique en cada etapa, o una vez al final si lo prefiere, 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 números primos pequeños, en cuyo punto el algoritmo Pollard p − 1 simplemente devuelve 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 -powersmooth. Si g = n en el paso 7, esto generalmente indica que todos los factores eran B -powersmooth, pero en casos raros podría indicar que a tenía un módulo n de orden pequeño . 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 más grandes de B hacen que funcione 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 . 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 tanto, 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 Pollard p − 1 una vez que los factores son grandes; ejecutando el método p − 1 hasta B = 2 32 se 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 , requerimos que todos menos uno de sus factores sean 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 una nueva
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 hacer 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 normalmente B 1 > 2 , d n son números pares. La distribución de los 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 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.
![{\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)