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

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

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.

Notes et références

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

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de factorisation par crible sur les corps de nombres spécialisé de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Algorithme De Factorisation Par Crible Sur Les Corps De Nombres Spécialisé — 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,… …   Wikipédia en Français

  • Algorithme de factorisation par crible sur les corps de nombres specialise — Algorithme de factorisation par crible sur les corps de nombres spécialisé 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… …   Wikipédia en Français

  • Crible spécial de corps de nombres (SNFS) — Algorithme de factorisation par crible sur les corps de nombres spécialisé 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… …   Wikipédia en Français

  • Crible quadratique — L algorithme du crible quadratique est un algorithme de factorisation fondé sur l arithmétique modulaire. C est en pratique le plus rapide après le crible généralisé sur les corps de nombres, lequel est cependant bien plus compliqué, et n est… …   Wikipédia en Français

  • SNFS — Algorithme de factorisation par crible sur les corps de nombres spécialisé 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… …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”