Algoritmos

Algoritmos de factorización de enteros

 algoritmo p + 1 de Williams es un algoritmo de factorización de enteros, uno de la familia de algoritmos de factorización de grupos algebraicos. Fue inventado por Hugh C. Williams en 1982.

Este funciona bien si el número N a ser factorizado contiene uno o más factores primos p tales que

p + 1

es liso, i.e. p + 1 contiene únicamente factores pequeños. Este usa sucesiones de Lucas para realizar la exponenciación en un cuerpo cuadrático.

Es análogo al algoritmo p − 1 de Pollard.

Hugh Williams inventó el p método factorización 1 número entero en 1982 basado en John Pollard p método factorización -1 número entero; el p método 1 encuentra un factor de p cuando p es suave con respecto a una cota B . Hemos observado en un anterior ejercicio la estructura similar de de Pollard p -1 método y método de la curva elíptica de Lenstra, y Williams' p +1 acciones método la misma estructura de dos etapas; De Pollard p -1 método realiza multiplicaciones módulo p , método de curva elíptica de Lenstra realiza multiplicaciones sobre una curva elíptica, y Williams' p método 1 realiza multiplicaciones sobre un campo cuadrática utilizando secuencias de Lucas (similares a la cadena de Lucas en el Baillie-Wagstaff primality- las pruebas de ejercicio ). Una buena descripción de Williams' p método 1 se da en http://www.mersennewiki.org/index.php/P_Plus_1_Factorization_Method .

Williams' p método 1 utiliza el Lucas secuencia V ₀ = 2, V ₁ = A , V _j = A · V _j -1 - V _j -2 , con todas las operaciones de módulo N , donde A es un número entero mayor que 2. la multiplicación por sucesivas potencias de primera se lleva a cabo como en el de Pollard p algoritmo -1; Cuando todos los productos a la cota B se acumulan, el máximo común divisor de N y el resultado V _B - 2 puede ser un divisor de N si todos los factores de p 1 están a menos de B . Sin embargo, si A ² - 4 es un no residuo cuadrático de p , el cálculo fallará, por lo que varios intentos deben realizarse con diferentes valores de A antes de concluir que p 1 no está B -smooth.

Dada la adición fórmula V _m + n = V _m V _n - V _m - n la duplicación de fórmula y V _2m = V _m × V _m - 2, la multiplicación se realiza por medio de una secuencia de Lucas que calcula dos valores a la vez. Comenzando con el par V _kn y V _( k 1) n , y mirando a los bits en la representación binaria del multiplicador M , excluyendo el bit más significativo (que es siempre 1) y trabajando desde más significativo al menos significativo, calcular el par V _2KN , V _(2 k 1) n cuando el bit es cero y el par V _(2 k 1) n , V _{2 ( k 1) n} cuando el bit es uno.

La segunda etapa se encuentra factores que son B ₁ -smooth a excepción de un solo factor primordial en el intervalo B ₁ a B ₂ . Se puede hacer de una manera similar a la segunda etapa de la de Pollard p método -1, pero un poco de álgebra nos da una mejor segunda etapa. Suponiendo que V _n es el punto que sobrevive a la primera etapa, se multiplica el productos V _k - V _n para cada k divisible por 6 entre B ₁ y B ₂ , a continuación, tomar el máximo común divisor del producto con n para revelar el factor.

Su tarea consiste en escribir un programa que los factores de números enteros usando Williams p algoritmo 1. Cuando haya terminado, usted es bienvenido a leer o ejecutar una propuesta de solución, o para enviar su propia solución o discutir el ejercicio en los comentarios a continuación.

El algoritmo p − 1 de Pollard es un algoritmo de factorización de enteros en teoría de números, inventado por John Pollard en 1974. Es un algoritmo de propósito especial, lo que significa que es únicamente adecuado para enteros con factores de tipos específicos; es el ejemplo más simple de un algoritmo de factorización de grupos algebráicos.

Los factores que encuentra son aquellos para los que el número que precede el factor, p − 1, es potencia lisa; la observación esencial es que, trabajando en el grupo multiplicativo módulo un número compuesto N, también se trabaja en los grupos multiplicativos módulo todos los factores de N'. La existencia de este algoritmo permite también el concepto de primos fuertes, siendo primos para los cuales p − 1 tiene al menos un factor primo grande. Casi todos los números primos lo suficientemente grandes son fuertes; si un primo usado para propósitos criptográficos resultara ser no fuerte, es mucho más probable que fuera por malicia que a través de un error de generación de números aleatorios.

De Pollard  -Método

Descubrimiento de ECM de Lenstra se inspiró en Pollard  -method, que se describen en esta sección.

Definición 6 0,3 (potencia suave)   Dejar que   sea un número entero positivo. Si   es un número entero positivo con la descomposición en factores primos , entonces es -poder suave sipara todos . 

Por lo tanto es de potencia suave para , pero no está -POWER lisa (es -power liso).  

Vamos a utilizar el siguiente algoritmo, tanto en el Pollard  y métodos de factorización curva elíptica.

Algoritmo 6 0.3 (mínimo común múltiplo de los primeros  números enteros)   Dado un número entero positivo  , este algoritmo calcula el mínimo común múltiplo de los números enteros positivos de hasta  .

1. [Sieve] usando, por ejemplo, la criba de Eratóstenes (algoritmo  1.2.3 ), calcular una lista   de todos los números primos  .
2. [Multiplicar] Compute y la salida del producto . 

Prueba . Let . Entonces 

donde  es el mayor poder de  que satisface  . Dado que , tenemos .  

Dejar que   sea un número entero positivo que deseamos factor. Usamos el Pollard  -Método para buscar un factor no trivial de   la siguiente manera. Primero elegimos un entero positivo   , por lo general con un máximo de seis dígitos. Supongamos que hay un divisor primo   de   tal manera que  es  -poder suave. Tratamos de encontrar   mediante la siguiente estrategia. Si es un número entero no divisible por   entonces por el teorema  2.1.19 ,

Deje , y observar que nuestra suposición de que es -poder suave implica que , por lo 

Así

Si también entonces es un factor no trivial de  . Si , a continuación, para cada divisor de potencia principal de  . En este caso, repetir los pasos anteriores pero con una selección más pequeña de  o, posiblemente, una elección diferente de  . Además, es una buena idea para comprobar desde el principio si  no es una potencia perfecta , y si es así sustituir  por  . Formalizamos el algoritmo de la siguiente manera:    

Algoritmo 6 0,3 (Pollard  Method)   Dado un número entero positivo  y un salto  , este algoritmo intenta encontrar un factor no trivial  de  . (Cada primer  es probable que tenga la propiedad de que  es  -poder suave.)

1. [Compute mcm] El uso del algoritmo  6.3.2 para calcular . 
2. [Inicializar] Juego  .
3. [Power y mcd] Calcular y .  
4. [Terminado?] Si  o  , de salida  y terminar.
5. [Volver a intentar?] Si  (por ejemplo), reemplace  por  y vaya al paso 3 . Terminar de otra manera.

Para fijo   , Algoritmo  6.3.3 menudo se divide   cuando   es divisible por un número primo   tal que  es  -de potencia suave. Aproximadamente el 15% de los números primos   en el intervalo desde  y son tales que es -potencia suave, por lo que el método de Pollard con ya no casi el 85% del tiempo a la búsqueda de  números primos de dígitos en este rango (véase también el ejercicio  6 . 10 ). No analizaremos método de Pollard aún más, ya que se menciona aquí para establecer el escenario para el método de la curva elíptica factorización. 
Los siguientes ejemplos ilustran la Pollard  -method.

Ejemplo 6 0,3   En este ejemplo, Pollard funciona perfectamente. Let  . Tratamos de utilizar el Pollard  método con el  que dividir   . Tenemos ; teniendo tenemos

y

por lo que  es un factor de   .

Ejemplo 6 0,3   En este ejemplo, se reemplaza   por entero mayor. Let  . Con  y  tenemos

y Con , que tiene 

y

por lo que  es un factor no trivial de   .

Ejemplo 6 0,3   En este ejemplo, se reemplaza   por un número entero más pequeño. Let  . Supongamos  , por lo que , 

y , por lo que no obtienen un factor de  . Si reemplazamos  por el método de Pollard funciona: 

y , por lo dividimos  . 

Ejemplo 6 0,3   En este ejemplo,  no funciona, pero  lo hace. Let  . Supongamos  , por lo que , 

y , por lo que no obtienen un factor de  . Si reemplazamos por , entonces el método de Pollard funciona: 

y . Por lo tanto .  

algoritmo rho de Pollard es un algoritmo especializado de factorización de números enteros. Fue inventado por John Pollard en 1975. Es especialmente efectivo a la hora de factorizar números compuestos que tengan factores pequeños.

Ideas principales

El algoritmo rho se basa en el algoritmo de la liebre y la tortuga y en la observación de que (como ocurre en el problema del cumpleaños) dos números x e y son congruentes módulo p con probabilidad 0,5 tras haberse elegido aleatoriamente ${\displaystyle 1,177{\sqrt {p}}}$ números. Si p es factor de n, el número que se quiere factorizar, entonces ${\displaystyle 1<\operatorname {mcd} \left(|x-y|,n\right)\leq n}$, ya que p divide tanto a ${\displaystyle \left|x-y\right|}$ como a n.

El algoritmo rho emplea pues una función módulo n a modo de generador de una secuencia pseudoaleatoria. Hace funcionar una de las secuencias el doble de rápido que la otra, es decir, por cada iteración de una de las copias de la secuencia, la otra hace dos iteraciones. Sea x el estado actual de una secuencia e y el estado actual de la otra. En cada paso se toma el máximo común divisor (MCD) de |x − y| y n. Si este MCD llega a ser n, entonces finaliza el algoritmo con el resultado de fracaso, ya que esto significa que x = y y, por el algoritmo de la liebre y la tortuga, la secuencia ya ha completado su ciclo y seguir más allá sólo conseguiría repetir trabajo ya realizado.

El algoritmo

Entradas: n, el número que se desea factorizar; y f(x), una función pseudoaleatoria módulo n

Salidas: un factor no trivial de n, o bien un fracaso. (un factor trivial de n es n mismo o 1)

1. x ← 2, y ← 2; d ← 1
2. Mientras d = 1:
   1. x ← f(x)
   2. y ← f(f(y))
   3. d ← MCD(|x − y|, n)
3. Si d = n, devuelve fracaso.
4. De lo contrario, devuelve d.

Nótese que este algoritmo acabará en fracaso para todo n primo, pero también puede fallar para un n compuesto. En ese caso, se cambia la función f(x) y se intenta de nuevo.

Optimización

En 1980, Richard Brent publicó una versión del algoritmo más rápida. Empleó las mismas ideas fundamentales que Pollard pero un método distinto de detección de ciclos, reemplazando el algoritmo de la liebre y la tortuga por el algoritmo de Brent para la detección de ciclos.

Pollard y Brent introdujeron una mejora adicional. Observaron que si ${\displaystyle \operatorname {mcd} (a,n)>1}$, entonces también se cumple que ${\displaystyle \operatorname {mcd} (ab,n)>1}$ para cada entero positivo ${\displaystyle b}$. En particular, en lugar de computar ${\displaystyle \operatorname {mcd} (|x-y|,n)}$ en cada paso, basta definir ${\displaystyle z}$ como el producto de cien términos consecutivos de ${\displaystyle |x-y|}$ módulo n, para luego computar un solo ${\displaystyle \operatorname {mcd} (z,n)}$. Se obtiene un importante ahorro de tiempo, ya que se ven reemplazados 100 cálculos de un máximo común divisor por 99 multiplicaciones módulo ${\displaystyle n}$ y un solo ${\displaystyle \operatorname {mcd} }$. A veces se da lugar a un error en el algoritmo al introducir un factor repetido, por ejemplo, cuando ${\displaystyle n}$ es un cuadrado. Sin embargo, basta con volver atrás al cálculo anterior del ${\displaystyle \operatorname {mcd} }$, donde ${\displaystyle \operatorname {mcd} (z,n)=1}$, y a partir de ahí volver a usar el algoritmo rho original.

En la práctica

El algoritmo es muy rápido en la factorización de números que tienen factores pequeños. Por ejemplo, en un equipo de trabajo de 3 GHz, el algoritmo original halló el factor 274177 del sexto número de Fermat (18446744073709551617) en 26 milisegundos. Por contra, la variante de Richard Brent halló el mismo factor en sólo 5 milisegundos. Sin embargo, en el caso de un semiprimo del mismo número de cifras (10023859281455311421), el mismo equipo tardó 109 milisegundos en encontrar un factor con el algoritmo original, y 31 con la variante de Richard Brent.

Para f se elige un polinomio con coeficientes enteros. Los más comunes son de la forma

${\displaystyle f(x)=x^{2}+c{\hbox{ mod }}n,\,c\neq 0,-2.}$

El éxito más relevante del algoritmo rho ha sido la factorización del octavo número de Fermat, realizada por Pollard y Brent. Emplearon la variante de Brent, que halló un factor hasta entonces desconocido. La factorización completa de F₈ tardó dos horas en un UNIVAC 1100/42.

Ejemplo

Sea n = 8051 y f(x) = x² + 1 mód 8051.

i	xi	yi	MCD(|xi − yi|, 8051)
1	5	26	1
2	26	7474	1
3	677	871	97

97 es un factor no trivial de 8051. Otros valores de c pueden dar lugar al cofactor (83) en lugar de 97.

Complejidad

El algoritmo ofrece un equilibrio entre su tiempo de ejecución y la probabilidad de encontrar un factor.

Si n es producto de dos primos distintos de tamaño similar, al ejecutar el algoritmo en O(n^1/4 polylog(n)) iteraciones se obtiene un factor con probabilidad aproximadamente 0,5. (Nótese que ésta es una afirmación heurística, y que sigue abierto un análisis riguroso del algoritmo.)