Algoritmo p + 1 de Williams

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa

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 | editar código-fonte]

  • 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 | editar código-fonte]