Crivo do corpo de números generalizado

Na teoria dos números, um ramo da matemática, o crivo do corpo de números generalizado, (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 ${\displaystyle n}$, o seu tempo de funcionamento depende do tamanho do divisor. Heuristicamente, a sua complexidade para fatorar um número inteiro ${\displaystyle n}$ (composto de ${\displaystyle \left\lfloor \log _{2}n\right\rfloor +1}$ 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]}$

em notação L,^{[nota 1]} onde ${\displaystyle \ln }$ é o logaritmo natural^[3].

Notas

Referências