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:
![{\displaystyle \exp \left(\left({\sqrt[{3}]{\frac {64}{9}}}+o(1)\right)(\ln n)^{\frac {1}{3}}(\ln \ln n)^{\frac {2}{3}}\right)=L_{n}\left[{\frac {1}{3}},{\sqrt[{3}]{\frac {64}{9}}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fcc5450b9f039008c0a728e15b6c66f24dafbb30)
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
