Crible spécial de corps de nombres (SNFS)

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 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.
  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Algorithme de factorisation par crible sur les corps de nombres sp%C3%A9cialis%C3%A9 ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Crible spécial de corps de nombres (SNFS) de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Crible général de corps de nombres (GNFS) — Algorithme de factorisation par crible sur les corps de nombres généralisé En mathématiques, le crible général de corps de nombres est l algorithme, fondé sur l arithmétique modulaire, pour la décomposition en produit de facteurs premiers le plus …   Wikipédia en Français

  • 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

  • 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 Généralisé — En mathématiques, le crible général de corps de nombres est l algorithme, fondé sur l arithmétique modulaire, pour la décomposition en produit de facteurs premiers le plus efficace connu. Il utilise étapes pour factoriser un nombre entier n (voir …   Wikipédia en Français

  • Algorithme de factorisation par crible sur les corps de nombres generalise — Algorithme de factorisation par crible sur les corps de nombres généralisé En mathématiques, le crible général de corps de nombres est l algorithme, fondé sur l arithmétique modulaire, pour la décomposition en produit de facteurs premiers le plus …   Wikipédia en Français

  • Algorithme de factorisation par crible sur les corps de nombres généralisé — En mathématiques, le crible général de corps de nombres, appelé aussi crible algébrique est l algorithme, fondé sur l arithmétique modulaire, pour la décomposition en produit de facteurs premiers le plus efficace des algorithmes classiques. Il… …   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

  • Liste Des Matières De La Théorie Des Nombres — Article détaillé : cryptologie. . Sommaire 1 Facteur (mathématiques) 2 Fractions 3 Arithmétique modulaire 4 …   Wikipédia en Français

  • Liste des matieres de la theorie des nombres — Liste des matières de la théorie des nombres Article détaillé : cryptologie. . Sommaire 1 Facteur (mathématiques) 2 Fractions 3 Arithmétique modulaire 4 …   Wikipédia en Français

Share the article and excerpts

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