Saltar para o conteúdo

Campo de número de peneira geral

Origem: Wikipédia, a enciclopédia livre.
(Redirecionado de GNFS)

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

  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 de 1996). «A Tale of Two Sieves» (PDF). Notices of the AMS. 43 (12). pp. 1473–1485 

Referências

Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.