Mostrar código-fonte de 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''', ({{langx|en|'''GNFS'''}}) é o mais eficiente [[algoritmo]] clássico, conhecido por [[Fatoração de inteiros|fatorar inteiros]] maiores do que 100 dígitos.<ref>[http://scholar.lib.vt.edu/theses/public/etd-32298-93111/materials/etd.pdf An Introduction to the General Number Field Sieve] por Matthew E. Briggs em 17 de abril de [[1998]]</ref>  O segundo melhor algoritmo clássico, conhecido por fatoração inteiro é o método de [[Fatoração da curva elíptica de Lenstra|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 [[Número primo|primo]] de <math>n</math>, o seu tempo de funcionamento depende do tamanho do divisor.<ref>[http://elmaxilab.com/definicao-abc/letra-n/numero-geral-campo-peneira.php Número Geral campo peneira]</ref>  [[Heurística|Heuristicamente]], a sua complexidade para fatorar um número inteiro <math>n</math> (composto de <math>\left\lfloor \log_2 n\right\rfloor + 1</math> bits) é da forma:

:<math>\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]</math>

em [[L-notação]]{{notaNT|L-notação é uma notação [[Análise assintótica|assintótica]] análoga à notação [[grande-O]].<ref>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</ref>}}, onde <math>ln</math> é o [[logaritmo natural]]<ref>{{citar jornal|último =Pomerance|primeiro =Carl|autorlink =Carl Pomerance|data=Dezembro de 1996|título=A Tale of Two Sieves|periodical=Notices of the AMS|volume=43|número=12|páginas=1473–1485|url=http://www.ams.org/notices/199612/pomerance.pdf|pontofinal=<!--None-->}}</ref>.

{{Notas}}
<references group="nt"/>
{{refbegin}}
{{Referências|group=nt}}
{{refend}}

{{Referências}}

{{Áreas da matemática}}
{{Esboço-matemática}}
{{Portal3|Tecnologias de informação|Matemática|Computação}}

[[Categoria:Teoria dos números| ]]
[[Categoria:Funções matemáticas]]
[[Categoria:Algoritmos| ]]
[[Categoria:Terminologia informática]]
[[Categoria:Ciência da computação]]
[[Categoria:Tecnologia da informação]]