ArithmétiqueObjet mathématique · Glossaire
Crible du corps de nombre
Dans sa variante générale, le crible du corps de nombre (Number Field Sieve, NFS) est l'algorithme classique de référence pour factoriser les grands entiers sans forme particulière, lorsque les méthodes visant de petits facteurs ne suffisent pas. Il exploite la structure arithmétique d'extensions algébriques des rationnels pour trouver des congruences de carrés modulo le nombre à factoriser. Sa complexité sub-exponentielle en fait l'algorithme de référence pour ces entiers de grande taille et il détermine la sécurité pratique des cryptosystèmes RSA. Il a permis de factoriser des entiers de plusieurs centaines de chiffres.
Sommaire
Ce que vous allez apprendre
- Identifier les cinq grandes parties du NFS et leurs dépendances.
- Vérifier sur 77 comment une congruence de carrés livre les facteurs 7 et 11.
- Distinguer le NFS d’un crible de nombres premiers et d’une factorisation matricielle.
- Relier son coût sub-exponentiel à l’évaluation pratique des tailles de clés RSA.
En clair
Prenons un entier si grand que tester ses diviseurs un à un serait déraisonnable. Le crible du corps de nombre ne cherche pas directement ces diviseurs. Il collecte beaucoup de relations arithmétiques faciles à combiner, dans les entiers ordinaires et dans un corps de nombres.
Ces relations finissent par produire deux carrés ayant le même reste modulo l’entier étudié. Leur différence peut alors révéler, par un calcul de plus grand commun diviseur, un facteur qui n’est ni 1 ni l’entier lui-même.
Définition
Le crible du corps de nombre, ou Number Field Sieve (NFS), est une famille d’algorithmes classiques de factorisation destinée aux grands entiers. La variante générale s’applique à un entier composé sans forme particulière. Une variante spéciale profite d’une écriture algébrique favorable de l’entier.
Pour l’entier positif composé N à factoriser, la méthode choisit un polynôme et travaille en parallèle avec des entiers rationnels et des nombres algébriques. Un criblage retient des relations dont les quantités associées se décomposent sur de petites bases de facteurs. Une algèbre linéaire sur les parités combine ensuite assez de relations pour obtenir deux entiers X et Y tels que .
Comme N divise (X − Y)(X + Y), les nombres pgcd(X − Y, N) et pgcd(X + Y, N) peuvent livrer des facteurs non triviaux. Une congruence ne garantit toutefois pas le succès : si X est congru à Y modulo N, le premier pgcd vaut N ; si X est congru à −Y modulo N, le second vaut N. Elle peut donc échouer à produire un facteur propre. Pour les grands entiers généraux, le coût attendu du NFS est sub-exponentiel ; cette estimation, et non une preuve d’optimalité absolue, explique son rôle dans l’évaluation pratique des tailles de clés RSA.
De quoi c'est fait
Le NFS s’organise en six parties. La sélection polynomiale relie l’entier N à un corps de nombres. Les bases de facteurs fixent les petits éléments admis de chaque côté, rationnel et algébrique. Le criblage cherche des relations dont les deux quantités associées se décomposent sur ces bases.
La matrice de parités dépend des relations collectées : une combinaison dont chaque exposant total est pair prépare des carrés des deux côtés. L’extraction de racine carrée dépend à son tour de cette combinaison et ramène le résultat modulo N. Le calcul final de pgcd teste si la congruence obtenue sépare réellement N en facteurs. L’enchaînement relie ainsi les données algébriques au verdict entier, sans faire du dessin du pipeline une partie de la définition mathématique.
Un exemple, pas à pas
Voici un modèle réduit de l’étape finale, et non une exécution complète du NFS. Les données sont l’entier composé N = 77 et une congruence produite en amont avec X = 20 et Y = 13.
1. Calculer les carrés : 202 = 400 et 132 = 169.
2. Vérifier leur différence : 400 − 169 = 231 = 3 × 77. Les deux carrés ont donc le même reste, 15, modulo 77.
3. Calculer X − Y = 7, puis pgcd(7, 77) = 7.
4. Calculer X + Y = 33, puis pgcd(33, 77) = 11.
2. Vérifier leur différence : 400 − 169 = 231 = 3 × 77. Les deux carrés ont donc le même reste, 15, modulo 77.
3. Calculer X − Y = 7, puis pgcd(7, 77) = 7.
4. Calculer X + Y = 33, puis pgcd(33, 77) = 11.
Le résultat est la factorisation 77 = 7 × 11. Le contrôle est refaisable par multiplication : 7 × 11 vaut bien 77. Dans un calcul NFS réel, la difficulté essentielle consiste à produire X et Y à partir d’un très grand ensemble de relations ; l’extraction par pgcd est la conclusion courte du processus.
En pratique
Pour factoriser un entier général de très grande taille, les implémentations du NFS répartissent le criblage et la collecte de relations entre de nombreux calculs. Si l’entier possède une forme algébrique spéciale exploitable, la variante spéciale est préférée, car elle réduit le travail de sélection et de criblage.
Pour évaluer une clé RSA, on compare la taille du module aux ressources nécessaires à une factorisation par NFS. Cette estimation guide la taille des clés ; elle ne consiste pas à appliquer l’algorithme à chaque usage de RSA.
Pour un petit entier pédagogique comme 77, la division par de petits nombres premiers est plus directe. Le NFS devient pertinent lorsque cette approche élémentaire et les méthodes adaptées aux tailles intermédiaires ne correspondent plus à l’échelle du problème.
À ne pas confondre
Avec un crible de nombres premiers. Un crible classique, comme celui d’Ératosthène, énumère les nombres premiers jusqu’à une borne. Le NFS cherche les facteurs d’un entier donné en combinant des relations rationnelles et algébriques ; pour 77, l’objectif est d’obtenir 7 et 11, non la liste de tous les nombres premiers inférieurs à 77.
Avec la factorisation d’un polynôme ou d’une matrice. Ici, factoriser signifie écrire un entier comme produit de facteurs entiers. Décomposer 77 en 7 × 11 relève du NFS ; décomposer une matrice en facteurs LU ou QR pose un autre problème.
Avec le corps de nombres lui-même. Un corps de nombres est la structure algébrique utilisée par la méthode. Le crible du corps de nombre est l’algorithme qui exploite cette structure pour construire une congruence de carrés.
Limites et pièges
Congruence triviale. Si X ≡ Y ou X ≡ −Y modulo N, l’un des pgcd finaux peut être trivial ou égal à N, tandis que l’autre peut être un facteur propre, 1 ou N. La combinaison peut donc échouer à produire un facteur propre ; il faut alors former une autre combinaison de relations.
Petit facteur déjà visible. Si une division préliminaire trouve immédiatement un petit diviseur, lancer tout le NFS gaspille des ressources. Pour N = 77, tester 7 suffit ; l’exemple pas à pas sert uniquement à vérifier le mécanisme de congruence de carrés.
Entier de forme spéciale. Employer sans examen la variante générale peut masquer un gain important. Si N admet une représentation algébrique appropriée, il faut considérer le crible spécial du corps de nombre ; sinon, la variante générale reste le cadre de référence.
Portée de la complexité. « Sub-exponentiel » ne signifie ni polynomial ni instantané. Le temps et la mémoire croissent encore très vite avec le nombre de chiffres ; les records sur plusieurs centaines de chiffres reposent donc sur des calculs massifs, pas sur une garantie de facilité.
Pour aller plus loin
La factorisation replace le résultat recherché dans son cadre arithmétique, tandis que les corps de nombres éclairent la structure algébrique qui distingue le NFS des méthodes élémentaires.
La congruence modulo n détaille l’égalité de restes utilisée à l’étape finale. Le code RSA montre enfin pourquoi la difficulté pratique de factoriser de grands entiers a une portée cryptographique.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres