stringtranslate.com

Algoritmo p − 1 de Pollard

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]

Conceptos básicos

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.

Factores múltiples

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 .

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 falla
  1. Seleccione un límite de suavidad B
  2. definir (nota: puede que no sea necesario evaluar M explícitamente )
  3. Escoger aleatoriamente un entero positivo, a , que sea coprimo con n (nota: en realidad podemos fijar a , p. ej., si n es impar, entonces siempre podemos seleccionar a = 2, la selección aleatoria aquí no es imperativa)
  4. Calcular g = mcd( a M − 1, n ) (nota: la exponenciación se puede realizar módulo  n )
  5. si 1 < g < n entonces devuelve g
  6. Si g = 1 , seleccione una B mayor y vaya al paso 2 o devuelva el error.
  7. Si g = n , seleccione una B más pequeña y vaya al paso 2 o devuelva el error.

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.

Ejemplo

Si queremos factorizar el número n = 299.

  1. Seleccionamos B = 5.
  2. Por lo tanto M = 2 2 × 3 1 × 5 1 .
  3. Seleccionamos a = 2.
  4. g = mcd( a M − 1, n ) = 13.
  5. Como 1 < 13 < 299, devuelve 13.
  6. 299 / 13 = 23 es primo, por lo tanto está completamente factorizado: 299 = 13 × 23.

Métodos de elecciónB

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.

Variante de dos etapas

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 2B 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 −1H d n , ahorrando la necesidad de exponenciaciones.

Implementaciones

Véase también

Referencias

  1. ^ ¿Qué son los números primos fuertes y son necesarios para el sistema RSA?, RSA Laboratories (2007)