Campo de número de peneira geral
Na teoria dos números, um ramo da matemática, o campo de número de peneira geral, (em inglês: GNFS) é o mais eficiente algoritmo clássico, conhecido por fatorar inteiros maiores do que 100 dígitos.[1] O segundo melhor algoritmo clássico, conhecido por fatoração inteiro é o método de fatoração Lenstra curva elíptica. É melhor do que o campo de número de peneira geral quando factores são pequenos, uma vez que funciona olhando para valores normais da ordem do menor divisor primo de , o seu tempo de funcionamento depende do tamanho do divisor.[2] Heuristicamente, a sua complexidade para fatorar um número inteiro (composto de bits) é da forma:
em L-notação[nt 1], onde é o logaritmo natural[4].
Notas
- ↑ L-notação é uma notação assintótica análoga à notação grande-O.[3]
Referências
- ↑ An Introduction to the General Number Field Sieve por Matthew E. Briggs em 17 de abril de 1998
- ↑ Número Geral campo peneira
- ↑ Carl Pomerance, "Analysis and comparison of some integer factoring algorithms", In Mathematisch Centrum Computational Methods in Number Theory, Part 1, pp. 89-139, 1982, http://www.math.dartmouth.edu/~carlp/PDF/analysiscomparison.pdf
- ↑ Pomerance, Carl (Dezembro de 1996). «A Tale of Two Sieves» (PDF). Notices of the AMS. 43 (12). pp. 1473–1485
Referências
![]() | Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.
|
Portal das tecnologias de informação
Portal da matemática