El algoritmo p + 1 de Williams

En teoría computacional de números , el algoritmo p + 1 de Williams   es un algoritmo de factorización de enteros , perteneciente a la familia de algoritmos de factorización de grupos algebraicos . Fue inventado por Hugh C. Williams en 1982.

Funciona bien si el número N que se va a factorizar contiene uno o más factores primos p tales que p + 1 sea suave , es decir, p + 1 contiene solo factores pequeños. Utiliza secuencias de Lucas para realizar la exponenciación en un campo cuadrático .

Es análogo al algoritmo p − 1 de Pollard   . De hecho, también puede encontrar p si p − 1 es suave, en cuyo caso degenera en una versión lenta del algoritmo de Pollard.  

Elija un número entero A mayor que 2 que caracterice la secuencia de Lucas :

${\displaystyle V_{0}=2,V_{1}=A,V_{j}=AV_{j-1}-V_{j-2}}$

donde todas las operaciones se realizan módulo N.

Entonces cualquier primo impar p divide${\displaystyle \gcd(N,V_{M}-2)}$siempre que M sea un múltiplo de${\displaystyle p-(D/p)}$, dónde ${\displaystyle D=A^{2}-4}$y${\displaystyle (D/p)}$es el símbolo jacobino .

Para diferentes valores de M calculamos${\displaystyle \gcd(N,V_{M}-2)}$y cuando el resultado no es igual a 1 o a N , hemos encontrado un factor no trivial de N.

Para encontrar un p con un p + 1 suave, requerimos que${\displaystyle (D/p)=-1}$, es decir, D debería ser un no residuo cuadrático módulo p . Pero como no conocemos p de antemano, puede ser necesario probar más de un valor de A antes de encontrar una solución. Si${\displaystyle (D/p)=+1}$Este algoritmo degenera en una versión lenta del algoritmo p − 1 de Pollard   . Esto ocurre el 50% de las veces.

x := B y := (B ^ 2 − 2) mod N para cada bit de M a la derecha del bit más significativo hacer si el bit es 1 entonces x := (x × y − B) mod N y := (y ^ 2 − 2) mod N demás y := (x × y − B) mod N x := (x ^ 2 − 2) mod N V := x

Con N =112729 y A =5, valores sucesivos de${\displaystyle V_{M}}$son:

V ₁ de seq(5) = V _1! de seq(5) = 5

V ₂ de seq(5) = V _2! de seq(5) = 23

V ₃ de seq(23) = V _3! de seq(5) = 12098

V ₄ de seq(12098) = V _4! de seq(5) = 87680

V ₅ de seq(87680) = V _5! de seq(5) = 53242

V ₆ de seq(53242) = V _6! de seq(5) = 27666

V ₇ de seq(27666) = V _7! de seq(5) = 110229.

En este punto, mcd(110229-2,112729) = 139, por lo que 139 es un factor no trivial de 112729. Nótese que p+1 = 140 = 2 ² × 5 × 7. El número 7! es el factorial más pequeño que es múltiplo de 140, por lo que el factor adecuado 139 se encuentra en este paso.

Utilizando otro valor inicial, por ejemplo A = 9, obtenemos:

V ₁ de seq(9) = V _1! de seq(9) = 9

V ₂ de seq(9) = V _2! de seq(9) = 79

V ₃ de seq(79) = V _3! de seq(9) = 41886

V ₄ de seq(41886) = V _4! de seq(9) = 79378

V ₅ de seq(79378) = V _5! de seq(9) = 1934

V ₆ de seq(1934) = V _6! de seq(9) = 10582

V ₇ de seq(10582) = V _7! de seq(9) = 84241

V ₈ de seq(84241) = V _8! de seq(9) = 93973

V ₉ de seq(93973) = V _9! de seq(9) = 91645.

En este punto, mcd(91645-2,112729) = 811, por lo que 811 es un factor no trivial de 112729. Nótese que p−1 = 810 = 2 × 5 × 3 ^4. El número 9! es el factorial más pequeño que es múltiplo de 810, por lo que el factor adecuado 811 se encuentra en este paso. El factor 139 no se encuentra esta vez porque p−1 = 138 = 2 × 3 × 23, que no es divisor de 9!.

Como se puede ver en estos ejemplos, no sabemos de antemano si el primo que se encontrará tiene un p+1 o p−1 suave.

Basándose en los algoritmos de factorización p − 1 de Pollard y p +1 de Williams , Eric Bach y Jeffrey Shallit desarrollaron técnicas para factorizar n de manera eficiente siempre que tenga un factor primo p tal que cualquier polinomio ciclotómico ^k Φ k ₍ p ) sea suave . ^{[ 3 ]} Los primeros polinomios ciclotómicos están dados por la secuencia Φ ₁ ( p ) = p −1, Φ ₂ ( p ) = p +1, Φ ₃ ( p ) = p ² + p +1 y Φ ₄ ( p ) = p ² +1.

• Williams, HC (1982), "Un método p+1 de factorización", Mathematics of Computation , 39 (159): 225–234 , doi : 10.2307/2007633 , JSTOR 2007633 , MR 0658227  

• Método de factorización P + 1 en Prime Wiki