Algoritmo p + 1 de Williams
Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. (Setembro de 2020) |
Em teoria algorítmica dos números, o algoritmo p + 1 de Williams é um algoritmo de fatorização de inteiros da família de algoritmos de fatorização de grupos algebraicos. Foi inventado por Hugh C. Williams em 1982.
Este algoritmo funciona bem se o número N a ser fatorizado contém um ou mais fatores primos p tais que:
- p + 1
é frágil, i.e. p + 1 contém unicamente fatores pequenos. Este usa sucessões de Lucas para realizar a exponenciação num corpo quadrático.
É análogo ao algoritmo p − 1 de Pollard.
Referências editar
- Williams, H. C. (1982), «A p+1 method of factoring», Mathematics of Computation, 39 (159): 225–234, MR 0658227, doi:10.2307/2007633
Ligações externas editar
- P Plus 1 Factorization Method, MersenneWiki.