Top Qs
Linha do tempo
Chat
Contexto
Algoritmo p + 1 de Williams
Da Wikipédia, a enciclopédia livre
Remove ads
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 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) |
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.
Remove ads
Referências
- 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
- P Plus 1 Factorization Method, MersenneWiki.
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads