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

Tenta vários valores para a , esperando que $a^{2}-N=b^{2}$ , seja um quadrado.

FermatFactor(N): // N deve ser impár
a ← ceil(sqrt(N))
b2 ← a*a - N
while b2 isn't a square: // Enquanto b2 não for um quadrado
a ← a + 1    // equivalente a: b2 ← b2 + 2*a + 1
b2 ← a*a - N //               a ← a + 1
endwhile
return a - sqrt(b2) // ou a + sqrt(b2)

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

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

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²	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:

FermatSieve(N, astart, aend, astep, modulus)
a ← astart
do modulus times: //vezes o modulo
b2 ← a*a - N
if b2 is a square, modulo modulus: //se b2 é quadrado, modulo do modulo
FermatSieve(N, a, aend, astep * modulus, NextModulus)
endif
a ← a + astep
enddo

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

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.^[1]

Outras melhorias[editar | editar código-fonte]

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.