Campo de número de peneira geral

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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[editar | editar código-fonte]

  1. L-notação é uma notação assintótica análoga à notação grande-O.[3]

Referências

  1. An Introduction to the General Number Field Sieve por Matthew E. Briggs em 17 de abril de 1998
  2. Número Geral campo peneira
  3. 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
  4. Pomerance, Carl (Dezembro 1996). «A Tale of Two Sieves» (PDF). Notices of the AMS. 43 (12). pp. 1473–1485 
Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.