La Véritable Structure Mathématique du Crible Général du Corps de Nombres (GNFS)

L’objectif ultime du GNFS est de trouver $X, Y$ tels que $X^2 \equiv Y^2 \pmod N$. Pour y parvenir, les mathématiciens ont construit un pont entre le “monde des entiers réels” et le “monde des corps algébriques” . Ce pont est l’“homomorphisme”.

Phase 1 : Relier les mondes avec l’“Homomorphisme”

1. Sélection du polynôme et définition des racines

Pour un nombre composé géant $N$, on choisit un entier $m$ et un polynôme $f(x)$ tels que $f(m) \equiv 0 \pmod N$. (Exemple : on développe $N$ en base $m$ et on crée $f(x)$ à partir de ses coefficients. On suppose ici que $f(x)$ est irréductible sur le corps des rationnels $\mathbb{Q}$ (ne peut pas être factorisé davantage)).

Ensuite, on définit l’une des “racines complexes” de l’équation $f(x) = 0$ comme étant $\alpha$. Naturellement, $f(\alpha) = 0$. $\alpha$ n’est pas un entier, mais un nombre complexe impliquant des racines et des nombres imaginaires (un nombre algébrique).

2. Construction d’Anneaux (Rings) et d’Homomorphismes

Ici, on prépare deux “anneaux” mathématiques (des mondes où l’addition et la multiplication sont définies).

• Monde A : $\mathbb{Z}[\alpha]$ (L’anneau des entiers algébriques contenant $\alpha$) Un monde de nombres exprimés sous la forme $a + b\alpha + c\alpha^2 + \dots$.
• Monde B : $\mathbb{Z}/N\mathbb{Z}$ (L’anneau des restes modulo $N$) Un monde de congruences composé uniquement des entiers de $0$ à $N-1$.

Ici, on définit une application $\phi$ du Monde A vers le Monde B comme suit. $$\phi : \mathbb{Z}[\alpha] \to \mathbb{Z}/N\mathbb{Z}$$ $$\phi(\alpha) = m \pmod N$$

Cette application $\phi$ est une opération magique qui remplace exactement la variable $\alpha$ du Monde A par l’entier $m$ du Monde B. Ce $\phi$ possède une propriété extrêmement puissante appelée “Homomorphisme d’Anneau (Ring Homomorphism)” . L’homomorphisme est la propriété de “se téléporter dans un autre monde sans détruire la structure de l’addition et de la multiplication” . En d’autres termes, les équations suivantes sont vraies :

• $\phi(X \times Y) = \phi(X) \times \phi(Y)$
• $\phi(X^2) = \phi(X)^2$

Qu’est-ce que cela signifie ? Si nous pouvons créer le “carré ($\gamma^2$)” d’un élément complexe $\gamma$ dans le “Monde A (le monde de $\alpha$)”, et le téléporter dans le “Monde B (le monde des restes)” en utilisant $\phi$, la forme carrée $\phi(\gamma)^2$ est parfaitement préservée .

Phase 2 : L’Effondrement de la Factorisation Première et la Naissance des “Idéaux”

Dans le Monde A ($\mathbb{Z}[\alpha]$), on souhaite rassembler de nombreux éléments appropriés $(a - b\alpha)$ et les multiplier pour créer un “carré parfait (élément carré)”. Normalement, on procéderait à la “factorisation première” de chaque $(a - b\alpha)$ collecté et on les combinerait de manière à ce que les exposants des nombres premiers soient tous pairs (en résolvant avec des matrices) pour former un carré.

Cependant, ici, le mur désespérant de l’algèbre se dresse. Dans des mondes algébriques comme $\mathbb{Z}[\alpha]$, l’“unicité de la factorisation première (tout nombre peut être exprimé de manière unique comme un produit de nombres premiers)” enseignée au collège s’effondre .

(Exemple : Dans un certain monde algébrique, $6 = 2 \times 3$, mais en même temps $6 = (1+\sqrt{-5}) \times (1-\sqrt{-5})$, et on ne sait plus quels sont les vrais nombres premiers)

Si la factorisation n’est pas unique, le puzzle consistant à “compter le nombre de nombres premiers pour les rendre pairs” (la méthode du crible) est, en principe, impossible à exécuter.

Le Sauvetage de Kummer et Dedekind : les “Idéaux”

Ce qui a sauvé cet effondrement, c’est le concept d’ “Idéal (Ideal : nombre idéal)” créé par les mathématiciens du 19ème siècle. En pensant non pas à l’élément lui-même, mais à “l’ensemble des multiples (idéal)” généré par cet élément, la factorisation première est redevenue possible.

Dans l’anneau des entiers d’un corps algébrique $\mathcal{O}_K$ (un anneau plus complet contenant $\mathbb{Z}[\alpha]$), il est prouvé que même si un élément ne peut pas être factorisé de manière unique, “un idéal peut toujours être factorisé de manière unique comme le produit d’‘Idéaux Premiers ($\mathfrak{p}$)’” .

Par conséquent, dans le GNFS, au lieu de factoriser l’élément $(a - b\alpha)$ lui-même, on factorise l’idéal principal $\langle a - b\alpha \rangle$ qu’il génère en idéaux premiers .

Phase 3 : La Norme (Norm) et les Deux Cribles (Sieves)

Alors, comment savoir en quels idéaux premiers l’idéal $\langle a - b\alpha \rangle$ se décompose ? Ici on utilise une fonction appelée “Norme (Norm)” . La Norme est une fonction qui convertit des éléments complexes de corps algébriques en “entiers réels normaux $\mathbb{Z}$”.

La norme de l’élément $(a - b\alpha)$ est trouvée par un simple calcul polynomial $b^d f(a/b)$ ($d$ est le degré de $f(x)$).

D’après un théorème algébrique, on sait que “si la norme d’un certain idéal peut être complètement factorisée en petits nombres premiers (est friable), alors l’idéal d’origine peut également être complètement factorisé en petits idéaux premiers” .

Ainsi, pour un grand nombre de paires d’entiers $(a, b)$, le GNFS calcule les deux valeurs suivantes simultanément et ne collecte que les paires où les deux deviennent des “nombres friables (smooth numbers)” :

1. Crible Rationnel (Rational Sieve) : $a - bm$ (la valeur dans le monde réel)
2. Crible Algébrique (Algebraic Sieve) : $b^d f(a/b)$ (la norme dans le monde algébrique)

En collectant des dizaines de millions de paires $(a, b)$ où les deux sont friables, on résout les données de factorisation des idéaux premiers (combien d’idéaux premiers sont inclus) sous la forme d’une matrice géante (algèbre linéaire sur GF(2)) pour trouver un ensemble $S$ de paires tel que “multipliés ensemble, les exposants de tous les idéaux premiers deviennent pairs”.

Phase 4 : Les Deux “Obstacles” et le Groupe des Classes d’Idéaux

À partir du calcul matriciel, on a découvert qu’en multipliant tous les idéaux de $(a - b\alpha)$ appartenant à l’ensemble $S$, on obtient le carré d’un certain idéal $I$.

Cependant, ce n’est pas encore terminé. Le mur mathématique le plus profond et le plus difficile du GNFS se trouve ici.

Ce que nous voulons à la fin, ce n’est pas “le carré d’un idéal”, mais le “carré d’un élément ($\gamma^2$)” à substituer dans l’application $\phi$. Ce n’est pas parce que c’est devenu le carré d’un idéal que l’élément lui-même est nécessairement un carré. Il y a ici deux puissants obstacles mathématiques (Obstructions) .

Obstacle ① : La Barrière du Groupe des Classes d’Idéaux (Ideal Class Group)

L’idéal $I$ n’est pas toujours un “idéal généré par un seul élément (idéal principal)”. Il est impossible d’extraire un élément spécifique $\gamma$ d’un idéal qui n’est pas principal.

C’est ici qu’intervient le concept de “Groupe des Classes d’Idéaux (Class Group, $Cl_K$)” . Le groupe des classes d’idéaux est un groupe qui mesure “combien d’idéaux existent dans ce corps algébrique qui ne sont pas principaux (à quel point l’unicité de la factorisation est brisée)”. Même si $\prod \langle a - b\alpha \rangle$ devient $I^2$, si $I$ n’est pas l’élément neutre (idéal principal) dans le groupe des classes d’idéaux, il ne peut pas être ramené au carré d’un élément.

Obstacle ② : La Barrière du Groupe des Unités (Unit Group)

Supposons que, par chance, $I$ soit l’idéal principal $\langle \gamma \rangle$. Alors, on a $\prod \langle a - b\alpha \rangle = \langle \gamma^2 \rangle$. Vous pourriez penser : “Super, l’élément est aussi un carré !”, mais c’est une grosse erreur.

Le fait que des idéaux (ensembles de multiples) soient égaux ne signifie pas que les éléments sont parfaitement égaux. Il y aura toujours un décalage par une “Unité (Unit : un nombre dont l’inverse est aussi un entier. Comme 1 ou -1)” . En d’autres termes, l’équation réelle des éléments devient la suivante :

($u$ est un élément du groupe des unités $U_K$)

À moins que cette unité $u$ ne soit elle-même le carré de quelque chose, le côté gauche ne pourra jamais devenir le “carré parfait d’un élément”.

Phase 5 : La Magie d’Adleman “Caractères Quadratiques” (Quadratic Characters)

L’obstacle du groupe des classes d’idéaux et l’obstacle du groupe des unités. Comment surmonter ces deux-là ? C’est ici qu’intervient la brillante méthode des “Caractères Quadratiques (Quadratic Characters)” , introduzido par le cryptographe Leonard Adleman (le “A” de RSA) et d’autres.

Pour déterminer “si un certain élément est un carré parfait dans le corps algébrique”, on utilise la version pour corps algébriques du Symbole de Legendre (résidu quadratique). Dans cette matrice géante d’avant (le puzzle pour rendre pairs les comptes d’idéaux premiers), on ajoute furtivement quelques dizaines de conditions supplémentaires (colonnes) disant que “les caractères quadratiques pour certains idéaux premiers spéciaux $\mathfrak{q}$ doivent également tous être $1$ (pairs)” .

Lorsqu’on trouve un ensemble $S$ qui satisfait même à ces conditions supplémentaires par le calcul matriciel, des théorèmes profonds de la théorie algébrique des nombres garantissent que “l’obstacle du groupe des classes d’idéaux et l’obstacle du groupe des unités disparaîtront naturellement avec une probabilité écrasante” .

Avec cela, nous obtenons enfin la véritable équation.

Phase Finale : La Fusion des Mondes et l’Effondrement Cryptographique

Enfin, toutes les pièces du puzzle sont en place.

[Éléments dans le Monde Algébrique (Monde A)] $\gamma^2 = \prod (a - b\alpha)$ (On utilise un algorithme de racine carrée pour trouver $\gamma$)

[Éléments dans le Monde Réel (Monde des Nombres Rationnels)] $V^2 = \prod (a - bm)$ (Comme il s’agit d’une simple multiplication d’entiers, $V$ est trouvé normalement)

Maintenant, il est temps d’utiliser ce pont magique que nous avons construit au début, l’ homomorphisme $\phi$ . On téléporte l’élément $\gamma$ du Monde A vers le Monde B (le monde des restes de $N$) en utilisant $\phi$ (l’application où on remplace $\alpha$ par $m$).

D’autre part, on amène directement le $V$ construit dans le monde réel dans le monde des restes et on l’appelle $X$.

Grâce à la propriété de “préservation de structure” de l’homomorphisme, la relation carrée qui tenait dans le Monde A est parfaitement préservée dans le Monde B (le monde modulo $N$). De plus, puisque les paires originales $(a, b)$ ont été créées en correspondance sous les formes $a - b\alpha$ et $a - bm$, ces $X$ et $Y$ entrent en collision dans le monde modulo $N$ et produisent l’équation absolue suivante :

$$X^2 \equiv Y^2 \pmod N$$

Il ne reste plus qu’à prier pour que ces $X$ et $Y$ ne soient pas des solutions triviales ($X \equiv \pm Y$), et à calculer $\gcd(X - Y, N)$ .

S’il s’agit d’une solution non triviale, l’algorithme d’Euclide s’exécutera en 0,001 seconde, et les nombres premiers secrets $p$ et $q$, qui sont le cœur de la cryptographie RSA, seront imprimés sur l’écran de sortie.

Ceci est l’image complète du “Crible Général du Corps de Nombres (GNFS)” , l’essence des mathématiques modernes.