Algoritmo p + 1 de Williams

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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.

Referencias[editar]

  • Williams, H. C. (1982), «A p+1 method of factoring», Mathematics of Computation 39 (159): 225–234, doi:10.2307/2007633 

Enlaces externos[editar]