Método de fatoração de Fermat
De Wikipedia, a enciclopédia encyclopedia
O método de fatoração de Fermat, em homenagem a Pierre de Fermat, baseia-se na representação de um número inteiro ímpar, é representado pela diferença de dois quadrados:
A diferença é algebricamente fatorial ; se nenhum fator for igual a um, isso é uma fatoração apropriada para N.
Cada número ímpar tem uma única representação. De fato, se é a fatoração de N, então
Desde que N seja ímpar, então c e d também são impares, porque suas metades são inteiras. (Um múltiplo de quatro também é uma diferença de quadrados, desde que c e d também seja.)
Em sua forma mais simples, o método de Fermat pode ser ainda mais lento do que a divisão comum (no pior caso). No entanto, a combinação de divisão comum e do método de Fermat é mais eficaz do que qualquer outro.