Algoritmo p + 1 de Williams
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, MR 0658227, doi:10.2307/2007633.
Enlaces externos editar
- P Plus 1 Factorization Method, MersenneWiki.
Datos: Q4046134
