Algorithme de factorisation par crible sur les corps de nombres spécialisé

Un article de Wikipédia, l'encyclopédie libre.
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

Le crible spécial de corps de nombres (SNFS) est un algorithme spécialisé de factorisation en nombres premiers. Lorsque la locution « crible de corps de nombres » est utilisée sans la mention spécial ou général, elle se réfère au GNFS, le crible général de corps de nombres.

Le crible spécial de corps de nombres est efficace pour les entiers de la forme re ± s, où r et s sont petits. Il est donc particulièrement recommandé pour factoriser les nombres de Fermat et les nombres de Mersenne.

Son temps d'exécution et sa complexité en notation de Laudau semble[1] être :

\Theta\left(\exp\left( \left(\frac{32}{9}n\right)^{\frac{1}{3}} (\log n)^{\frac{2}{3}} \right)\right).

Le SNFS a beaucoup été utilisé par NFSNET et d'autres pour factoriser les nombres du projet Cunningham.

[modifier] Notes et références

  1. ↑ Pour l'heure, ce n'est qu'une conjecture.
Autres langues