miniaturadaimagem|Pierre 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:
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.
O método básico
Tenta vários valores para a , esperando que , 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 , nos tentamos primeiro a é a raiz quadrada de arrendondando para o próximo inteiro, que é . Então, . 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 b2 125 282 441 b 11.18 16.79 21
A terceira tentativa produz o quadrado perfeito de 441. Então, , ,e o fatorial de é , e .
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, é o menor fator ≥ a raiz quadrada de N. E assim é o maior fator ≤ root-N. Se o procedimento achar , isso mostra que N é primo.
Para , onde c é o maior fator de sub raiz. , então o número de passos é aproximadamente .
Se N é primo (de modo que ), ele precisa de 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 a partir de 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 , mas também calcular b and . Começando a partir de , nos podemos criar a tabela:
a 48,433 48,434 48,435 48,436 b2 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 , 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 ; usando o Fermat método para fatores entre e . Isso da um "atalho" para a divisão comum, que é . No exemplo acima, com o "atalho" para a divisão comum é de 47830. Uma escolha razoável é 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 b2 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 , nem mesmo examinar todos os valores . Considere a tabela para : a 48,433 48,434 48,435 48,436 b2 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 por 10. Por esse exemplo, adicionando '-17' mod 20 (ou 3), 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, deve ser 1 mod 20, o que significa que é 1 ou 9 mod 10; isso produzira um b2 que terminara em 4 mod 20 e, se quadrado, terminara em 2 ou 8 mod 10.
Isto pode ser realizado com qualquer módulo. Usando a mesmo , modulo 16:Quadrado são 0, 1, 4, or 9 N mod 16 é5 assim só pode ser9 e deve ser3 ou 5 ou 11 ou 13 modulo 16modulo 9: Quadrado são 0, 1, 4, or 7 N mod 9 é7 assim só pode ser7 e deve ser4 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
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 () é conhecida, então o Número racional pode ser escolhido perto deste valor. , e os fatores são aproximadamente iguais: O método de Fermat, aplicado a Nuv, vai encontra-los rapidamente. Então e . (A não ser que c divide u ou d divide v.)
Geralmente, se a relação não é conhecida, vários 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 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 , 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.
Ver também Completamento de quadrados Fatoração polinomial Triângulo de Pascal Fator primo Fatoração
J. McKee, "Speeding Fermat's factoring method", Mathematics of Computation'', 68:1729-1737 (1999).
Ligações externas Fermat's factorization running time, at blogspot.in
Categoria:Teoria dos números Categoria:Pierre de Fermat Categoria:Algoritmos de fatorização de inteiros