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
- 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
- P Plus 1 Factorization Method, MersenneWiki.
| Control de autoridades |
|
|---|
Datos: Q4046134
Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.