Método de fatoração de Fermat
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4b/Pierre_de_Fermat.png/220px-Pierre_de_Fermat.png)
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 N = 2345678917, mas também calcular b and a − b. 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 ser | 9 | |
e 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 só pode ser | 7 | |
e 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
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.[1]
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
Referências
- ↑ Lehman, R. Sherman (1974). «Factoring Large Integers». Mathematics of Computation. 28 (126): 637–646. doi:10.2307/2005940
- 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