Algoritmo p + 1 de Williams

Carta Común · N.º 284139

En teoría de números computacional, el 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.

Leer en Wikipedia