# Método de fatoração de Fermat

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:
    $N=a^{2}-b^{2}.$
A diferença é algebricamente fatorial $(a+b)(a-b)$; 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 $N=cd$ é a fatoração de N, então
    $N=\left({\frac {c+d}{2}}\right)^{2}-\left({\frac {c-d}{2}}\right)^{2}$
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.

## O método básico

Tenta vários valores para a , esperando que $a^{2}-N=b^{2}$, seja um quadrado.
Por exemplo, para fatorar $N=5959$, nos tentamos primeiro a é a raiz quadrada de $5959$ arrendondando para o próximo inteiro, que é $78$. Então, $b^{2}=78^{2}-5959=125$. Mas 125 não é quadrado então, a segunda tentativa é feita incrementando o valor de a em 1. A segunda tentativa também falha, por que novamente 282 não é quadrado.
| Tentativa: | 1 | 2 | 3 |
| a | 78 | 79 | 80 |
| b$^2$ | 125 | 282 | 441 |
| b | 11.18 | 16.79 | 21 |
A terceira tentativa produz o quadrado perfeito de 441. Então, $a=80$, $b=21$,e o fatorial de $5959$ é $a-b=59$, e $a+b=101$.
Suponha que N tem mais de dois fatores primos. Esse procedimento primeiro acha as fatorações com menores valores de a e b. Ou seja, $a+b$ é o menor fator ≥ a raiz quadrada de N. E assim $a-b=N/(a+b)$ é o maior fator ≤ root-N. Se o procedimento achar $N=1\cdot N$, isso mostra que N é primo.
Para $N=cd$, onde c é o maior fator de sub raiz. $a=(c+d)/2$, então o número de passos é aproximadamente $(c+d)/2-{\sqrt {N}}=({\sqrt {d}}-{\sqrt {c}})^{2}/2=({\sqrt {N}}-c)^{2}/2c$.
Se N é primo (de modo que $c=1$), ele precisa de $O(N)$ passos! Está é uma maneira ruim de provar primalidade. Mas se N é um fator próximo a sua raiz quadrada, o método funciona rapidamente. Mais precisamente, se c difere menos que ${\left(4N\right)}^{1/4}$ a partir de ${\sqrt {N}}$ o método requer somente um passo. Note que isso independe o tamanho de N.

## Fermat e divisão comum

Considere tentar o fator do número primo N = 2345678917, mas também calcular b and a − b. Começando a partir de ${\sqrt {N}}$, nos podemos criar a tabela:
| a | 48,433 | 48,434 | 48,435 | 48,436 |
| b$^2$ | 76,572 | 173,439 | 270,308 | 367,179 |
| b | 276.7 | 416.5 | 519.9 | 605.9 |
| a − b | 48,156.3 | 48,017.5 | 47,915.1 | 47,830.1 |
Na pratica, não se incomodaria com essa última linha, até b é um número inteiro. Mas observe que se N tem uma sub raiz com fator acima de $a-b=47830.1$, o método de fermat já teria achado.
A divisão comum teria tentando normalmente até 48,432; mas depois de quatro passos usando o método de Fermat, nos precisamos dividir somente até 47830, para achar o fator ou promover a primalidade.
Com surge o método fatorial combinado. Escolha alguns $c>{\sqrt {N}}$; usando o Fermat método para fatores entre ${\sqrt {N}}$ e $c$. Isso da um "atalho" para a divisão comum, que é $c-{\sqrt {c^{2}-N}}$. No exemplo acima, com $c=48436$ o "atalho" para a divisão comum é de 47830. Uma escolha razoável é $c=55000$ dando um "atalho" de 28937.
Neste sentido, o método de Fermat dá retornos decrescentes. Um certamente parar antes deste ponto:
| a | 60,001 | 60,002 |
| b$^2$ | 1,254,441,084 | 1,254,561,087 |
| b | 35,418.1 | 35,419.8 |
| a − b | 24,582.9 | 24,582.2 |

## Melhoria por Crivo

Não é necessário calcular todos os quadrados de base de $a^{2}-N$, nem mesmo examinar todos os valores $a$. Considere a tabela para $N=2345678917$:
| a | 48,433 | 48,434 | 48,435 | 48,436 |
| b$^2$ | 76,572 | 173,439 | 270,308 | 367,179 |
| b | 276.7 | 416.5 | 519.9 | 605.9 |
Pode-se dizer rapidamente que nenhum desses valores de b2 são quadrados. (Quadrados são sempre congruentes a 0, 1, 4, ou 9 modulo 16.) Os valores repetidos com cada aumento de $a$ por 10. Por esse exemplo, adicionando '-17' mod 20 (ou 3), $a^{2}-N$ produz 3, 4, 7, 8, 12, e 19 modulo 20 para esses valores. É evidente que só sera possível que seja quadrado a partir de 4. Assim, $a^{2}$ deve ser 1 mod 20, o que significa que $a$ é 1 ou 9 mod 10; isso produzira um b2 que terminara em 4 mod 20 e, se quadrado, $b$ terminara em 2 ou 8 mod 10.
Isto pode ser realizado com qualquer módulo. Usando a mesmo $N=2345678917$,
| modulo 16: | Quadrado são | 0, 1, 4, or 9 |
| | N mod 16 é | 5 |
| | assim $a^{2}$ só pode ser | 9 |
| | e $a$ deve ser | 3 ou 5 ou 11 ou 13 modulo 16 |
| modulo 9: | Quadrado são | 0, 1, 4, or 7 |
| | N mod 9 é | 7 |
| | assim $a^{2}$ só pode ser | 7 |
| | e $a$ deve ser | 4 ou 5 modulo 9 |
Geralmente escolhe uma potencia de primo diferente para cada modulo.
Dada uma seqüência de a-valores (start, end, and step) e um modulo, pode-se proceder da seguinte forma:
Mas a recursão é parado quando poucos a-valores restantes; que é, quando (aend-astart)/astep é pequena. também, porque a' passos é constante, pode-se calcular sucessivas b2 com adições.

## Melhoria de multiplicador

O método de Fermat funciona melhor quando existe um fator perto da raiz quadrada de N.
Se a proporção aproximada de dois fatores ($d/c$) é conhecida, então o Número racional $v/u$ pode ser escolhido perto deste valor. $Nuv=cv\cdot du$, e os fatores são aproximadamente iguais: O método de Fermat, aplicado a Nuv, vai encontra-los rapidamente. Então $\gcd(N,cv)=c$ e $\gcd(N,du)=d$. (A não ser que c divide u ou d divide v.)
Geralmente, se a relação não é conhecida, vários $u/v$ os valores podem ser julgados, e tentar fatorar cada resultado Nuv. R. Lehman desenvolveu uma maneira sistemática de fazer isso, de modo que o método de fermat unido a divisão comum pode fatorar N em $O(N^{1/3})$ time.

## Outras melhorias

As ideias fundamentais do método de Fermat são a base da crivo quadrático e crivo do corpo geral de números, os algoritmos mais conhecidos de fatoração grande de Número semiprimo, que são o "pior caso". As principais melhorias do crivo quadrático faz sobre o método de Fermat é que em vez de simplesmente encontrar um quadrado na seqüência de $a^{2}-n$, encontrar um subconjunto de elementos dessa seqüência cuja produto é um quadrado, e ele faz isso de uma maneira altamente eficiente. O resultado final é o mesmo: a diferença do quadrado mod n que, se não trivial, podem ser utilizados o fator de n.