Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] \| Liste Catégories \| Une page au hasard \| Pages liées

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

Le crible spécial de corps de nombres (SNFS) est un algorithme de décomposition en produit de facteurs premiers à but spécial. Le crible général de corps de nombres (GNFS) fut dérivé à partir de lui. Lorsque la locution "crible de corps de nombres" est utilisée sans qualification, elle réfère au GNFS.

Le crible spécial de corps de nombres est efficient pour les entiers de la forme r^e ± s, où r et s sont petits. Comme tel, il est idéal pour factoriser les nombres de Fermat.

Son temps d'exécution est de

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

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

Catégories: Wikipédia:ébauche | Algorithme | Théorie des nombres

This site support the Wikimedia Foundation. This Article originally from Wikipedia. All text is available under the terms of the