ALGÈBRE LINÉAIRE SUR LES

ℤ–MODULES ET LES ℤ_{K}–MODULES

Henri Cohen

Résumé.

Le but de ces exposés est d’expliquer les techniques de bases d’algèbre linéaire qui sont utilisées dans les calculs dans les corps de nombres. Contrairement à l’algèbre linéaire habituelle qui concerne des espaces vectoriels sur des corps, les algorithmes dont nous aurons besoin concernent des modules sur des anneaux, et en particulier des ℤ-modules ou plus généralement des ℤ_{K}-modules pour un anneau d’entiers de corps de nombres ℤ_{K}.

Certains des algorithmes sont très classiques (algorithme d’Hermite et de Smith), d’autres datent des années 1980 (algorithme LLL, algorithmes d’Hermite et de Smith modulaires), tandis que d’autres sont très récents (algorithmes d’Hermite et de Smith dans les anneaux de Dedekind).

Cet article est donc en trois parties. Dans la première partie, nous décrivons les algorithmes d’Hermite et de Smith. Dans la deuxième partie nous décrivons les algorithmes LLL. Enfin dans la troisième partie nous décrivons les algorithmes d’Hermite et de Smith dans les anneaux d’entiers de corps de nombres.

1. Algorithmes sur les ℤ-modules

1.1. Théorèmes de base

Dans cette partie, nous étudions un certain nombre d’algorithmes fondamentaux utilisés pour travailler avec des ℤ-modules, c’est à dire des groupes abéliens. Nous considérerons uniquement des ℤ-modules de type fini (c’est à dire possédant un système génerateur fini). Il y a essentiellement trois types d’algorithmes de nature assez différente que nous devons étudier : les algorithmes d’Hermite, de Smith, et LLL.

Rappelons les théorèmes de structure fondamentaux suivants, qui décrivent la structure des ℤ-modules de type fini.

Théorème 1.1. Soit M un ℤ-module de type fini. Soit

M_{tors} = {x ∈ M/ ∃n ∈ ℤ, n ≠ 0, nx = 0}

le sous-module de torsion de M. Alors (1) M_{tors} est un module fini.

(2) Il existe un sous-module N de M sans torsion (c’est à dire vérifiant N_{tors} =

{0}) tel que

M = M_{tors} ⊕ N .

Théorème 1.2.

(1) Pour qu’un ℤ-module de type fini M soit sans torsion, il faut et il suffit que ce soit un module libre.

(2) Tout sous-module d’un ℤ-module libre de type fini de rang n est libre de type fini de rang inférieur ou égal à n (le rang d’un module libre est évidemment sa dimension en tant que ℤ-module).

Avant d’énoncer les deux théorèmes suivants, de nature plus algorithmiques, il est utile d’introduire deux définitions.

Définition 1.3. Soit H = (h_{i,j}) une matrice carrée n × n. Nous dirons que H est sous forme normale d’Hermite (HNF) si elle vérifie les conditions suivantes.

(1) Pour tout i et j, h_{i,j} ∈ ℤ.

(2) H est une matrice triangulaire supérieure à diagonale positive. En d’autres termes, h_{i,j} = 0 pour i > j, et h_{i,i} > 0.

(3) Pour tout i < j, on a 0 ≤ h_{i,j} < h_{i,i}.

Définition 1.4. Soit S = (s_{i,j}) une matrice carrée n × n. Nous dirons que S est sous forme normale de Smith (SNF) si S est une matrice diagonale dont les termes diagonaux sont des entiers strictement positifs, et vérifient s_{i,i} | s_{j,j} pour tout couple (i, j) tel que i > j.

Nous pouvons maintenant énoncer les théorèmes de structure des ℤ-modules de type fini.

Théorème 1.5. Soit M un ℤ-module libre de rang n et soit N un sous-module de M (libre d’après le théorème 1.2) de même rang n.

(1) Soit e_{1}, …, e_{n} une ℤ-base de M. Il existe une unique ℤ-base f_{1}, …, f_{n} de N telle que la matrice H = (h_{i,j}) représentant les f_{j} sur la base e_{i} soit sous forme normale d’Hermite.

(2) Il existe une ℤ-base e_{1}, …, e_{n} de M et une ℤ-base f_{1}, …, f_{n} de N telle que la matrice S = (s_{i,j}) représentant les f_{j} sur la base e_{i} soit sous forme normale de Smith. La matrice S est déterminée de manière unique par les ℤ-modules M et N, et les coefficients diagonaux de S s’appellent les facteurs invariants du module quotient M/N.

En pratique, on utilise ce théorème de la manière suivante. Le module sanstorsion M étant donné, ainsi qu’une base e_{i} de M, a première partie du théorème permet de donner une représentation canonique de tous les sous-modules de M de rang maximal n. C’est ainsi que tous les modules sans torsion seront représentés.

Si maintenant W est un module de torsion de type fini, on peut toujours représenter W sous la forme W = M/N avec M et N modules sans torsion de rang n, et la deuxième partie du théorème donne donc une représentation canonique de W. Noter que avec les notations du théorème, on aura

W ≃ ⨁_{i=1}^{n} ℤ/s_{i,i}ℤ .

ALGÈBRE LINÉAIRE SUR LES ℤ–MODULES ET LES ℤ_{K}–MODULES 3

Toutefois, en algorithmique les isomorphismes non explicités sont interdits, et il faut en fait écrire :

W = ⨁_{i=1}^{n} ℤ/s_{i,i}ℤ\overline{e_{i}} ,

où \overline{e_{i}} désigne la classe de e_{i} modulo N.

1.2. Les algorithmes d’Hermite

Le but de ce paragraphe est de décrire explicitement les algorithmes qui sont utilisés pour trouver la HNF d’un ℤ-module sans torsion N de rang n.

En pratique, la situation sera la suivante. Sera donné un module libre M de rang n, ainsi qu’une ℤ-base e_{i} de M. Le module N sera alors connu par un système de gérateurs exprimés sur la base des e_{i}, en d’autres termes par une matrice A à n lignes et k colonnes, chaque colonne donnant les cooordonnées sur les e_{i} d’un générateur de M.

Nous nous autoriserons à effectuer des opérations élémentaires sur les colonnes de A qui ne changent pas le ℤ-module engendré par les colonnes de A. Nous pouvons donc par exemple permuter les colonnes de A, ou bien remplacer une colonne de A par cette colonne plus une combinaison linéaire à coefficients entiers des autres colonnes. Plus généralement nous pouvons multiplier A à droite par toute matrice à coefficients entiers de déterminant égal à ±1 (par abus de langage, nous dirons qu’une telle matrice est unimodulaire).

Nous pouvons reformuler la première partie du théorème 1.5 de la manière suivante.

Proposition 1.6. Soit A une matrice n × k à coefficients entiers. On suppose que A est de rang n (donc en particulier k ≥ n). Il existe une matrice unimodulaire U telle que les k − n premières colonnes de AU soient nulles, et les n dernières colonnes forment une matrice en HNF. Cette dernière matrice HNF est unique.

Nous allons démontrer l’assertion d’existence de cette proposition de façon algorithmique.

La manière la plus simple de démontrer cette proposition, et en même temps de donner un algorithme pour calculer la HNF, est de considérer le cas très particulier n = 1, k = 2. Dans ce cas, si A = [a, b], la proposition affirme qu’on peut trouver une matrice unimodulaire U telle que AU = [0, d] avec d > 0. Or soit d le PGCD de a et de b, u et v tels que au + bv = d, alors il est clair que la matrice

U = ( \begin{matrix}b/d & u \\ −a/d & v \end{matrix} )

convient.

Pour calculer la HNF d’une matrice n × k A = (a_{i,j}) avec n et k quelconque, on commence par le coin en bas à droite de A. Posons a = a_{n,k−1}, b = a_{n,k}, et soit U la matrice 2 × 2 ci-dessus. Si A_{j} désigne la j-ième colonne de A, la transformation [A_{k−1}, A_{k}] ← [A_{k−1}, A_{k}]U est unimodulaire, et introduit un 0 en position k − 1 sur la n-ième ligne. Procédant de cette façon de droite à gauche sur la dernière ligne, on voit que l’on peut ainsi annuler tous les coefficients de la dernière ligne, sauf a_{n,k} qui à la fin sera égal au PGCD de tous les coefficients de la dernière ligne.

Nous poursuivons avec la ligne n−1, en commencant cette fois par a = a_{n−1,k−2}, b = a_{n−1,k−1}. Et ainsi de suite. Quand on a fini de traiter la première ligne, il est clair que grâce à des transformations élémentaires nous avons amené A à une forme très voisine de celle voulue : les k − n premières colonnes sont nulles, et les n dernières forment une matrice triangulaire supérieure à diagonale positive. Il reste une réduction à faire sur les coefficients non nuls pour qu’ils vérifient 0 ≤ a_{i,j} < a_{i,i}, ce qui se fait de manière évidente de proche en proche (toujours de bas en haut et de droite à gauche) par des combinaisons linéaires de colonnes.

L’écriture formelle de l’algorithme est la suivante.

Algorithme 1.7. (Algorithme HNF ordinaire). Étant donnée A = (a_{i,j}) une matrice n × k de rang n, cet algorithme calcule une matrice U ∈ GL_{k}(ℤ) et une matrice H sous forme normale d’Hermite, tels que AU soit égal à une matrice ayant ses k − n premières colonnes nulles, et ses n dernières égales à la matrice H. Nous appellerons A_{j} (resp. U_{j}) les colonnes de A (resp. U).

1. [Initialisations] Poser i ← n, j ← k et soit U la matrice identité d’ordre k.

2. [Vérifier si zéro] Poser m ← j, et tant que m ≥ 1 et a_{i,m} = 0, poser m ← m − 1. Si m = 0, la matrice A n’est pas de rang n, donc imprimer un message d’erreur et terminer l’algorithme. Sinon, si m < j, échanger A_{m} et A_{j}, et échanger U_{m} et U_{j}.

3. [Boucle] Si m = 1, aller à 5. Sinon, poser m ← m − 1, et si a_{i,m} = 0, aller à 3.

4. [Bezout] (Ici a_{i,j} et a_{i,m} sont non nuls). En utilisant l’algorithme d’Euclide, calculer d = pgcd(a_{i,m}, a_{i,j}) ainsi que u et v tels que a_{i,m}u + a_{i,j}v = d. Puis poser (A_{m}, A_{j}) ← (a_{i,j}/dA_{m} − a_{i,m}/dA_{j}, uA_{m} + vA_{j}), (U_{m}, U_{j}) ← (a_{i,j}/dU_{m} − a_{i,m}/dU_{j}, uU_{m} + vU_{j}). Enfin, retourner à 3.

5. [Réductions finales pour la ligne i] Pour m = j + 1, …, m = n, soit q ← ⌊a_{i,m}/a_{i,j}⌋, et poser A_{m} ← A_{m} − qA_{j} and U_{m} ← U_{m} − qU_{j}.

6. [Terminé ?] Si i = 1, soit H la matrice formée par les n dernières colonnes de la matrice A modifiée, retourner les matrice U et H et terminer l’algorithme. Sinon, poser i ← i − 1, j ← j − 1 et revenir en 2.

L’algorithme ci-dessus est tout à fait raisonnable pour des petites valeurs de n et k, disons jusqu’à k = 10 environ. Quand n et k sont plus grands, il commence à apparaitre un phénomène qui rend l’algorithme quasiment inutilisable : l’explosion de la taille des coefficients. En effet, à chaque calcul de PGCD, on multiplie une colonne entière par une quantité dont la taille est du même ordre de grandeur que celle des coefficients de la matrice. Comme ceci est effectué environ O(kn) fois, on peut imaginer que la taille des coefficients devienne gigantesque, et c’est effectivement le cas en pratique. On peut ainsi trouver des matrices 20×20 dont les coefficients sont inférieurs à 10, et tels que les entiers intervenant dans les calculs intermédiaires aient plus de 5000 chiffres décimaux.

Il est donc nécéssaire de trouver de meilleurs algorithmes. Il en existe essentiellement de trois types différents : l’algorithme modulaire, l’algorithme de Havas et enfin la réduction d’Hermite “intelligente”.

L’idée de l’algorithme modulaire, due sous cette forme à Hafner et McCurley ([Haf-McCur]) est la suivante. Nous avons vu que le coefficient en bas à droite de la HNF de A est égal au PGCD des coefficients de la dernière ligne de A. De la même manière, il n’est pas difficile de montrer que le PGCD des mineurs 2 × 2 formés avec les deux dernières lignes de A est égal au produit des deux derniers termes diagonaux de la HNF de A, et ainsi de suite. A la fin du calcul, le produit des termes diagonaux de la HNF de A est égal à son déterminant (puisqu’une HNF est triangulaire), et c’est donc le déterminant du sous-résau de ℤ^{n} engendré par les colonnes de la matrice A initiale.

Si ce déterminant, ou même simplement un multiple D de ce déterminant, est connu, il suffit d’effectuer tous les calculs modulo D, ce qui évite bien entendu l’explosion des coefficients. Il n’est ensuite pas très difficile de récupérer la vraie forme normale d’Hermite par quelques PGCD supplémentaires. Formellement, ceci donne l’algorithme suivant, dont la démonstration est laissée au lecteur (voir [Coh1] p. 71 par exemple) :

Algorithme 1.8. (Algorithme HNF modulaire). Étant donnée A = (a_{i,j}) une matrice n × k de rang n, et un entier positif D multiple du déterminant du sous-ℤ-module de ℤ^{n} engendré par les colonnes de A, cet algorithme calcule la forme normale d’Hermite H = (h_{i,j}) de A. Nous utiliserons un vecteur colonne auxilliaire B, et nous désignerons par A_{j} (resp. H_{j}) les colonnes de A (resp. H).

1. [Initialisations] Poser i ← n, j ← k R ← D.

2. [Vérifier si zéro] Poser m ← j, et tant que m ≥ 1 et a_{i,m} = 0, poser m ← m − 1. Si m = 0, la matrice A n’est pas de rang n, donc imprimer un message d’erreur et terminer l’algorithme. Sinon, si m < j, échanger A_{m} et A_{j}.

3. [Boucle] Si m = 1, aller à 5. Sinon, poser m ← m − 1, et si a_{i,m} = 0, aller à 3.

4. [Bezout] (Ici a_{i,j} et a_{i,m} sont non nuls). En utilisant l’algorithme d’Euclide, calculer d = pgcd(a_{i,m}, a_{i,j}) ainsi que u et v tels que a_{i,m}u+a_{i,j}v = d avec u et v minimaux. Puis poser (A_{m}, A_{j}) ← (a_{i,j}/dA_{m} − a_{i,m}/dA_{j}, uA_{m} + vA_{j}) modulo R. Enfin, retourner à 3.

5. [Réductions finales pour la ligne i] En utilisant l’algorithme d’Euclide, calculer d = (a_{i,j}, R) ainsi que u et v tels que a_{i,j}u + Rv = d. Poser H_{i} ← uA_{j} mod R, et si h_{i,i} = 0, poser h_{i,i} ← R. Enfin pour m = i + 1, …,m = n, soit q ← ⌊h_{i,m}/h_{i,i}⌋, et poser H_{m} ← H_{m} − qH_{i}.

6. [Terminé ?] Si i = 1, retourner la matrice H et terminer l’algorithme. Sinon, poser i ← i − 1, j ← j − 1, R ← R/d et revenir en 2.

Pour pouvoir utiliser cet algorithme, il est donc nécéssaire de connaître une valeur convenable de D. Pour celà, même si la matrice n’est pas carrée, on peut effectuer un pivot de Gauss, et calculer rapidement le PGCD de quelques mineurs d’ordre n de la matrice A, ce qui donne un multiple (en général petit) du déterminant du réseau. Je ne donne pas l’algorithme en détail ici, mais je mentionne simplement qu’il s’éxécute rapidement en pratique.

De plus, dans beaucoup d’applications pratiques, une valeur convenable de D est connue.

On peut montrer que l’algorithme d’Hermite modulaire ci-dessus a un temps d’éxécution polynomial en n, k et la taille des coefficients de la matrice A, ce qui n’était pas le cas pour l’algorithme ordinaire à cause de l’explosion des coefficients. De plus, il n’est pas difficile, tout en conservant le caractère polynomial, d’obtenir également la matrice unimodulaire U.

L’algorithme d’Hermite modulaire peut s’utiliser pour des matrices ayant une centaine de lignes et de colonnes, mais commence à devenir très lent au delà.

Un deuxième type d’algorithme pour calculer la HNF est dû à G. Havas (voir [Hav-Maj]). Cet algorithme utilise un certain nombre de méthodes heuristiques destinées à s’assurer que les coefficients intermédiaires ne croissent pas trop vite. En conséquence, on ne peut pas démontrer que cet algorithme est rapide, mais en pratique il est remarquablement efficace. Toutefois, les méthodes heuristiques sont de nature assez techniques, et par manque de temps je n’en parlerai pas ici.

Le troisième type d’algorithme n’est utilisable que dans des circonstances relativement particulières : celle où la matrice A est creuse, c’est à dire possède peu de coefficients non nuls par ligne. Bien que ce soit un type particulier de matrices, ces matrices interviennent par exemple en permanence dans les algorithmes de calcul des groupes de classes, et donc il est utile d’étudier un peu les algorithmes correspondants.

Tout d’abord, une remarque : dans la réduction HNF stricto sensu, on ne s’autorise que des transformations de colonnes, c’est à dire la multiplication à droite par une matrice unimodulaire U. Nous pouvons, sans changer l’esprit de la notion de HNF, également autoriser des permutations de lignes. Ceci revient à permuter les éléments de la base e_{i}, ce qui est innocent, mais donne beaucoup plus de souplesse à la réduction HNF. Ceci est d’ailleurs déjà utilisé dans l’algorithme de Havas.

La réduction d’Hermite “intelligente” consiste en gros en quatre étapes. Dans une première étape, on regarde s’il existe une ligne de A ayant un unique coefficient non nul, égal à ±1 (s’il existe une ligne entièrement nulle, A n’est pas de rang n, ce qui est exclu). Si c’est le cas, après multiplication de la colonne correspondante par −1 si nécéssaire pour que le coefficient soit égal à 1, on échange lignes et colonnes pour que le coefficient 1 se retrouve en dernière ligne, dernière colonne. On ne considère plus ensuite que les n − 1 premières lignes et k − 1 premières colonnes, ce qui fait que de nouvelles lignes peuvent apparître qui n’ont qu’un unique coefficient non nul égal à ±1. On poursuit de cette manière tant qu’il existe des lignes aussi simples.

Dans une deuxième étape, on regarde s’il existe une ligne de A n’ayant que des coefficients nuls ou égaux à ±1. Pour une telle ligne, on effectue les opérations nécéssaires pour amener des zéros partout sauf un coefficient. Ces opérations ne sont que des additions ou soustractions de colonnes, et pas des multiplications. En particulier la taille des entiers qui interviennent reste petite, et peut bien sûr être très aisément controlée.

Dans une troisème étape, on utilise l’algorithme HNF ordinaire sur la matrice qui reste à traiter, mais en contrôlant la taille des coefficients pour que tous les calculs s’effectuent en simple précision.

Enfin, quand ceci n’est plus possible, il est nécéssaire de faire à la fois appel à la multiprécision et à l’algorithme d’Hermite modulaire pour terminer le travail. Toutefois la pratique montre que dans les problèmes courants où cette méthode de réduction “intelligente” est utilisée, la matrice à traiter par l’algorithme modulaire sera de taille beaucoup plus petite que la matrice initiale.

Noter que la HNF finale sera (par blocs) de la forme

( \begin{matrix}X & Y \\ 0 & I \end{matrix} ) ,

où X est une petite matrice carrée en HNF et I est une grande matrice identité.

1.3. Applications de la forme normale d’Hermite

La première application de la forme normale d’Hermite est le calcul de l’image et du noyau entier d’une matrice. Enonçons précisément le problème. Soit A une matrice n × k à coefficients entiers. La matrice A peut être considérée comme la matrice d’une application linéaire de ℚ^{k} dans ℚ^{n}, et en tant que telle elle possède une image et un noyau que l’on peut calculer sans difficulté par la méthode du pivot appliquée dans le corps ℚ.

Mais A peut aussi être considérée comme la matrice d’une application linéaire de ℤ^{k} dans ℤ^{n}. En tant que telle, elle possède aussi une image et un noyau qui, d’après le théorème 1.2 sont des ℤ-modules libres. Il est donc important de calculer des ℤ-bases de ces ℤ-modules. Ce sont les algorithmes d’Hermite qui vont nous donner la solution. D’ailleurs, d’une manière générale si on veut transposer à ℤ des algorithmes d’algèbre linéaire utilisés sur ℚ, il suffit presque toujours de remplacer “méthode du pivot” par “algorithme d’Hermite”.

Proposition 1.9. Soit A une matrice n × k de rang n, et soient U une matrice unimodulaire et H une matrice en HNF telles que AU = [0 H], comme celles fournies par l’algorithme 1.7. Alors les colonnes de H forment une base de l’image de A dans ℤ^{n}, et les k − n premières colonnes de U forment une base du noyau de A dans ℤ^{k}.

Démonstration. Puisque U est à coefficients entiers, il est clair que les colonnes de H sont des combinaisons linéaires à coefficients entiers des colonnes de A, donc appartiennent à l’image de A. Puisque H est triangulaire supérieure à diagonale strictement positive, les colonnes de H sont linéairement indépendantes. Enfin, comme U^{−1} est à coefficients entiers, l’équation A = [0 H]U^{−1} montre que les colonnes de A sont combinaison linéaires à coefficients entiers des colonnes de H, donc celles-ci forment bien une base de l’image de A.

L’équation AU = [0 H] montre que les k − n premières colonnes de U appartiennent au nayau de A. Comme U est inversible, elles sont linéairement indépendantes. Montrons qu’elles engendrent le noyau de A. Soit X tel que AX = 0. Posons

U^{−1}X = ( \begin{matrix}Y_{1} \\ Y_{2} \end{matrix} ) ,

où Y_{2} possède n composantes. On a donc

0 = AX = AUU^{−1}X = [0 H] ( \begin{matrix}Y_{1} \\ Y_{2} \end{matrix} ) = HY_{2} .

Comme H est de déterminant non nul, il en résulte que Y_{2} = 0, donc que U^{−1}X =

( \begin{matrix}Y_{1} \\ 0 \end{matrix} ), ou encore X = U ( \begin{matrix}Y_{1} \\ 0 \end{matrix} ) ce qui revient à dire que X est combinaison linéaire

à coefficients entiers des k − n premières colonnes de U, d’où la proposition. ⊓ ⊔

Grâce à la forme normale d’Hermite, nous pouvons également faire un certain nombre d’opérations entre sous-modules de rang maximal d’un module libre de type fini. Soit donc M un ℤ-module libre de rang n, e_{i} une base de M fixée une fois pour toutes. Nous pouvons représenter tout sous-module N de M de rang n par sa HNF sur la base e_{i}, qui est unique d’après le théorème 1.5. Les algorithmes d’Hermite vus ci-dessus nous permettent alors aisément de faire ce qui suit.

• Détermination d’une base. Etant donné un système de générateurs de N, l’image de la matrice donnant ces générateurs sur les e_{i} est une ℤ-base de N.

• Test d’égalité. Si N et N′ sont deux sous-modules de M, on a N = N′ si et seulement si leurs HNF sont égales.

• Somme de modules. Si N et N′ sont deux sous-modules donnés par leur HNF, la HNF de la matrice obtenue en concaténant les HNF de N et de N′ sera la HNF du module N + N′.

• Test d’inclusion. Si N et N′ sont deux sous-modules donnés par leur HNF, on peut tester si N′ ⊂ N en vérifiant que N + N′ = N.

• Test d’appartenance. Si N est un sous-module et X ∈ M, on peut tester si X ∈ N en vérifiant que N + ℤX = N, ce que l’on peut faire en utilisant un algorithme d’Hermite sur une matrice n × (n + 1). Il est toutefois plus rapide en général de vérifier que H^{−1}X est à coefficients entiers (H étant la HNF de N), car H est une matrice triangulaire donc le calcul de H^{−1}X s’effectue aisément.

• Produit de modules. Si le module M est muni d’une structure d’anneau (ce qui sera souvent le cas en théorie algébrique des nombres), on peut considérer le sous-module

NN′ = {∑_{i} n_{i}n′_{i}/ n_{i} ∈ N, n′_{i} ∈ N′} .

Si f_{j} (resp. f′_{m}) est la base HNF de N (resp. N′) alors les n^{2} éléments f_{j}f′_{m} forment un système générateur de NN′, et on peut donc calculer la HNF de NN′ en calculant la HNF d’une matrice n × n^{2}. Il est à noter que dès que n dépasse 20 environ, ceci devient très long.

Un cas particulier très important où ce calcul peut être considérablement accéléré est celui où M est un anneau commutatif et N et N′ des idéaux de M. Dans ce cas, il est facile de montrer la proposition suivante, laissée au lecteur.

Proposition 1.10. Soient N et N′ deux idéaux d’un anneau commutatif M libre de rang n sur ℤ. Soit (f_{j}) une ℤ-base de N et (f′_{m}) un M-système générateur de N′. Alors les f_{j}f′_{m} forment un ℤ-système générateur de NN′.

L’intérêt fondamental de cette proposition est que le cardinal d’un M-système générateur est en général beaucoup plus petit que celui d’un ℤ-système générateur. Si M est un anneau principal, on peut même prendre un M-système générateur ayant un seul élément. Dans le cas des corps de nombres, M sera un anneau de Dedekind et on pourra prendre un M-système générateur à deux éléments. Ceci signifie que l’on aura à calculer la HNF de matrices n × (2n) au lieu de n × n^{2}, ce qui est une amélioration considérable.

1.4. La forme normale de Smith

Les paragraphes précédents ont montré comment manipuler des ℤ-modules de type fini sans torsion, et donc libres. Dans ce paragraphe nous nous allons nous occuper au contraire des ℤ-modules G de type fini qui sont de torsion, et donc de cardinal fini. Un tel module G sera donné par un système de générateurs et par des relations entre ces générateurs. Comme G est abélien, il revient au même de dire que G est donné sous la forme M/N, où M et N sont des ℤ-modules libre de type fini et de même rang, disons n, tels que N ⊂ M.

D’après le théorème 1.5, il existe des bases (e_{i}) de M et (f_{j}) de N telles que la matrice des f_{j} sur les e_{i} soit une matrice S sous forme normale de Smith (SNF). La but des algorithmes de Smith est de trouver cette matrice S et les bases correspondantes.

Le principe de l’algorithme de Smith ordinaire est semblable à celui de l’algorithme d’Hermite, à la différence près que l’on s’autorise aussi bien à faire des combinaisons linéaires de colonnes (multiplication à droite par une matrice unimodulaire) que des combinaisons linéaires de lignes (multiplication à gauche par une matrice unimodulaire).

L’analogue algorithmique de la deuxième partie du théorème 1.5 est le suivant.

Proposition 1.11. Soit A une matrice n × n à coefficients entiers de rang n. Il existe deux matrices unimodulaires U et V telles que UAV soit une matrice SNF, et cette dernière matrice SNF est unique.

Nous allons démontrer l’assertion d’existence de cette proposition de manière algorithmique.

Nous procédons comme dans l’algorithme d’Hermite, de bas en haut et de droite à gauche, mais en s’autorisant des opérations élémentaires sur les colonnes et sur les lignes. Voyons ceci en détail.

Soient a et b deux entiers non tous deux nuls, soit d le PGCD de a et b, et u et v tels que au + bv = d. Nous allons utiliser les trois types de transformations unimodulaires suivantes. Tout d’abord

[0, d] = [a, b] ( \begin{matrix}b/d & u \\ −a/d & v \end{matrix} )

qui est celle utilisée dans l’algorithme d’Hermite, sa transposée

( \begin{matrix}0 \\ d \end{matrix} ) = ( \begin{matrix}b/d & −a/d \\ u & v \end{matrix} ) ( \begin{matrix}a \\ b \end{matrix} ) ,

et enfin la formule suivante

( \begin{matrix}ab/d & 0 \\ 0 & d \end{matrix} ) = ( \begin{matrix}bv/d & −au/d \\ 1 & 1 \end{matrix} ) ( \begin{matrix}a & 0 \\ 0 & d \end{matrix} ) ( \begin{matrix}b/d & u \\ −a/d & v \end{matrix} ) .

On procède alors comme suit. Appelons en permanence b l’élément de la dernière ligne et colonne de la matrice. Comme dans l’algorithme d’Hermite, en appliquant le premier type de transformation unimodulaire, on transforme la dernière ligne en une ligne de zéros, sauf b. Si b ne divise pas tous les éléments de sa colonne, on applique le deuxième type de transformation unimodulaire pour nettoyer la colonne. Ce faisant, on a détruit la nullité de la dernière ligne, mais en échange |b| a diminué puisque par hypothèse b ne divisait pas tous les éléments de sa colonne. On recommence donc à nettoyer sa ligne, et ainsi de suite. Puisque |b| diminue, ce procédé s’arrête, et les dernières lignes et colonnes sont alors nulles, sauf b sur la diagonale.

Maintenant on regarde les autres éléments de la matrice. S’il y en a un qui n’est pas divisibles par b, on applique le troisième type de transformation unimodulaire ci-dessus. Ceci détruit la nullité de la dernière ligne et colonne, mais diminue la valeur de b. Après un renettoyage des lignes et colonnes, |b| aura diminué et un élément de plus au moins de la matrice sera divisible par b. Il en résulte que le procédé s’arrête. On s’arrête de traiter b quand la dernière ligne et colonne sont nulles sauf l’élément diagonal b, et quand celui-ci divise tous les éléments de la matrice. On passe alors à la ligne et colonne précédente, et ainsi de suite.

Remarque. Il y a en fait un piège dans lequel il faut se garder ne ne pas tomber. Quand b divise a, il est nécéssaire de prendre u = 0, pour ne pas détruire la nullité de la ligne ou colonne. En fait nous pouvons nous assurer de l’unicité de u et v en exigeant −|a|/d < v signe(b) ≤ 0 et 1 ≤ u signe(a) ≤ |b|/d. Ce sont (au signe et effets de bord près) les valeurs minimum de u et v.

Bien que nous ayons démontré que l’algorithme se termine, au premier abord on peut avoir peur que le nombre d’étapes nécessaires soient très élevé puisque la nullité des colonnes et des lignes est souvent détruite. En fait il n’en est pas du tout ainsi, car après 2 ou 3 PGCD, le nombre b divisera en général toute la matrice. Par exemple, il faut se rappeler que même après un seul PGCD, la probabilité que b soit égal à 1 est égal à 6/π^{2}.

Nous écrivons l’algorithme formellement comme suit. Le troisème type de transformation unimodulaire est remplacée par une équivalente, mais plus simple pour l’algorithme. Nous utiliserons un compteur auxiliaire c qui nous permettra de savoir s’il a été nécéssaire de nettoyer la colonne courante.

Algorithme 1.12. (Algorithme SNF ordinaire). Étant donnée A = (a_{i,j}) une matrice n × n de rang n, cet algorithme calcule des matrices U et V dans GL_{n}(ℤ), et une matrice S sous forme normale de Smith, telles que UAV = S. Nous appellerons A_{j} (resp. V_{j}) les colonnes de A (resp. V), et A′_{i} (resp. U′_{i}) les lignes de A (resp. U).

1. [Initialiser i] Poser i ← n, soient U et V la matrice identité d’ordre n. Si n = 1, sortir U, V et S ← A et terminer l’algorithme.

2. [Initialiser j pour réduire la ligne] Poser j ← i, c ← 0.

3. [Vérifier si zéro] Si j = 1 aller à 5. Sinon, poser j ← j − 1, et si a_{i,j} = 0, aller à 3.

4. [Bezout] En utilisant l’algorithme d’Euclide, calculer (u, v, d) tels que ua_{i,i} + va_{i,j} = d = pgcd(a_{i,i}, a_{i,j}), avec u et v minimum (voir remarque ci-dessus). Poser B ← uA_{i} + vA_{j}, A_{j} ← (a_{i,i}/d)A_{j} − (a_{i,j}/d)A_{i}, A_{i} ← B, B ← uV_{i} + vV_{j}, V_{j} ← (a_{i,i}/d)V_{j} − (a_{i,j}/d)V_{i}, V_{i} ← B, et aller à 3.

5. [Initialiser j pour réduire la colonne] Poser j ← i.

6. [Zéro ?] Si j = 1 aller à 8. Sinon, poser j ← j − 1, et si a_{j,i} = 0 aller à 6.

7. [Bezout] En utilisant l’algorithme d’Euclide, calculer (u, v, d) tels que ua_{i,i} + va_{j,i} = d = pgcd(a_{i,i}, a_{j,i}), avec u et v minimum (voir remarque ci-dessus). Poser B ← uA′_{i} + vA′_{j}, A′_{j} ← (a_{i,i}/d)A′_{j} − (a_{j,i}/d)A′_{i}, A′_{i} ← B, B ← uU′_{i} + vU′_{j}, U′_{j} ← (a_{i,i}/d)U′_{j} − (a_{j,i}/d)U′_{i}, U′_{i} ← B, c ← c + 1 et aller à 6.

8. [Répéter l’étape i ?] Si c > 0 aller à 2.

9. [Vérifier le reste de la matrice] Poser b ← a_{i,i}. Pour 1 ≤ k, l < i, vérifier si b | a_{k,l}. Dès qu’un coefficient a_{k,l} n’est pas divisible par b, poser A′_{i} ← A′_{i} + A′_{k}, U′_{i} ← U′_{i} + U′_{k} et aller à 2.

10. [Etape suivante] (Ici tous les a_{k,l} avec 1 ≤ k, l < i sont divisibles par b). Si i = 2, sortir U, V, S ← A, et terminer l’algorithme. Sinon, poser i ← i − 1 et aller à 2.

Il existe également une variante modulaire de l’algorithme de Smith, qui est très facile à trouver en s’inspirant de l’algorithme d’Hermite modulaire. Toutefois, en pratique cet algorithme est beaucoup moins utile et nous ne le décrirons pas ici.

1.5. Application de la forme normale de Smith

L’application presque unique mais essentielle de la forme normale de Smith est la détermination de la structure des groupes abéliens finis G, c’est à dire des ℤmodules de torsion.

Habituellement, G sera donné par un système de générateurs g_{1}, …,g_{n}. En d’autres termes, l’application ϕ de M = ℤ^{n} dans G définie par ϕ((x_{1}, …, x_{n})) = x_{1}g_{1}+⋯+x_{n}g_{n} est surjective (nous notons temporairement G additivement). Si N est le noyau de ϕ, il est clair que ℤ^{n}/N ≃ G, où l’isomorphisme (qu’il faut toujours expliciter) est déduite de ϕ par passage au quotient.

Pour déterminer la structure de G il nous faut donc d’abord déterminer la structure de ℤ^{n}/N. Comme G est fini, N est un ℤ-module libre de rang n. On suppose que l’on connait un système de k générateurs de N, exprimés sur la base canonique de ℤ^{n}. Ce système forme une matrice entière A d’ordre n × k. On procède alors en trois étapes.

Dans une première étape, on utilise un algorithme d’Hermite pour trouver une ℤ-base de N (voir ci-dessus), exprimée sur la base canonique de ℤ^{n} par une matrice d’Hermite H.

Dans une deuxième étape, nous calculons grâce à l’algorithme de Smith deux matrices unimodulaires U et V telles que UHV = S soit sous forme normale de Smith. Il est à noter qu’en pratique on généralise la définition et l’algorithme de Smith aux matrices non carrées, et que ces deux premières étapes se réduisent alors à une seule. Toutefois dans ce cas il est absolument nécéssaire de choisir un algorithme de Smith plus performant que celui que nous avons donné.

Dans une troisième étape, on procède comme suit. Si ε_{1}, …,ε_{n} est la base canonique de ℤ^{n}, et si on pose

[e_{1}, …, e_{n}] = [ε_{1}, …, ε_{n}]U^{−1} ,

on a alors

[e_{1}, …, e_{n}]S = [ε_{1}, …, ε_{n}]HV .

Or puisque V est unimodulaire et qu’on multiplie à droite, la matrice HV représente aussi une base f_{1}, …,f_{n} de N sur la base canonique, et l’égalité ci-dessus montre que f_{i} = s_{i,i}e_{i}. Il en résulte que nous avons trouvé des bases adaptées de ℤ^{n} et de N, commme voulues par le Théorème 1.5.

D’après la discussion qui suit ce théorème, on a donc

ℤ^{n}/N = ⨁_{i=1}^{n}(ℤ/s_{i,i}ℤ)\overline{e_{i}} .

Enfin, nous devons transporter ce résultat sur le groupe G lui-même grâce à l’isomorphisme explicite que nous avons. Il est clair que l’on obtient le résultat suivant.

Proposition 1.13. Conservons toutes les notations ci-dessus. Posons

[h_{1}, …, h_{n}] = [g_{1}, …, g_{n}]U^{−1} ,

(où ceci doit être interprété convenablement si la loi de groupe abélien de G est notée multiplicativement). Soit m le plus grand indice i tel que s_{i,i} > 1 (rappelons que s_{n,n}|s_{n−1,n−1}| ⋯ |s_{1,1}). On a alors

G = ⨁_{i=1}^{m}(ℤ/s_{i,i}ℤ)h_{i} .

Toutefois, ceci n’est pas toujours satisfaisant. En effet, si l’on y prend pas garde, les coefficients de la matrice U^{−1} seront grands, ce qui peut considérablement ralentir le calcul des nouveaux générateurs h_{i}, et/ou donner des générateurs trop compliqués.

Il y a deux manières de remédier à cette situation. La première est d’utiliser des algorithmes heuristiques de G. Havas qui donnent des matrices U et U^{−1} ayant de très petits coefficients. Je n’en parlerai pas.

La deuxième consiste à remarquer que

[g_{1}, …, g_{n}]H = [0, …, 0] .

En effet, cette équation signifie exactement que les colonnes de H sont des relations entre les g_{i}, et donc appartiennent au sous-module N. Il en résulte qu’il est loisible de modifier les colonnes de U^{−1} en ajoutant une combinaison linéaire quelconque à coefficients entiers des colonnes de la matrice H de telle manière que les coefficients soient petits. Il est à noter que la nouvelle matrice ainsi obtenue ne sera plus nécéssairement dans GL_{n}(ℤ), mais conviendra pour le calcul des h_{i}. Evidemment, cette manière de faire ne change pas les h_{i}, mais peut considérablement améliorer le temps de calcul.

1.6. Exemple.

Nous souhaitons déterminer explicitement le groupe G = (ℤ/105ℤ)^{∗}. Bien entendu, ceci peut se faire directement, mais la méthode que nous allons utiliser peut s’appliquer dans des situations très générales.

On remarque tout d’abord que 105 = 3 · 5 · 7, donc

G ≃ (ℤ/3ℤ)^{∗} × (ℤ/5ℤ)^{∗} × (ℤ/7ℤ)^{∗} .

Toutefois, ceci n’est pas une réponse satisfaisante d’un point de vue algorithmique. D’ailleurs, il est pratiquement toujours interdit d’utiliser un d’isomorphisme non explicite en algorithmique.

Posons

H = (ℤ/3ℤ)^{∗} × (ℤ/5ℤ)^{∗} × (ℤ/7ℤ)^{∗} ,

et appelons q_{n} la surjection canonique de ℤ dans ℤ/nℤ. Il est clair que l’application ϕ de G dans H telle que

ϕ(q_{105}(x)) = (q_{3}(x), q_{5}(x), q_{7}(x))

est un isomorphisme. Il est toutefois également nécessaire en algorithmique d’expliciter l’isomorphisme réciproque. Or celui-ci est donné par le théorème des restes chinois. En effet, si u_{3}, u_{5}, u_{7} sont des entiers tels que u_{p} ≡ 1 (mod p) et u_{p} ≡ 0 (mod 105/p), on vérifie aisément que l’isomorphisme réciproque ϕ^{−1} est donné par

ϕ^{−1}(q_{3}(x_{3}), q_{5}(x_{5}), q_{7}(x_{7})) = q_{105}(u_{3}x_{3} + u_{5}x_{5} + u_{7}x_{7}) .

Une amélioration de l’ísomorphisme ci-dessus est donc l’égalité

G = G_{3} · G_{5} · G_{7} ,

où · désigne le produit de sous-groupes (toujours possible puisque G est abélien), et G_{p} désigne le sous-groupe de G image réciproque par ϕ des trois sous-groupes (ℤ/3ℤ)^{∗} × {1} × {1}, {1} × (ℤ/5ℤ)^{∗} × {1} et {1} × {1} × (ℤ/7ℤ)^{∗} de H.

Par l’algorithme d’Euclide, on calcule immédiatement que l’on peut choisir u_{3} = −35, u_{5} = 21 et u_{7} = 15. Comme (ℤ/3ℤ)^{∗} est engendré par la classe de 2 modulo 3, il en résulte que G_{3} est engendré par la classe de 2u_{3} + u_{5} + u_{7} ≡ −34 modulo 105, i.e. en abrégé G_{3} =< \overline{− 34} >. De même on trouve que G_{5} =< \overline{u_{3} + 2u_{5} + u_{7}} >=< \overline{22} > et G_{7} =< \overline{u_{3} + u_{5} + 3u_{7}} >=< \overline{31} >.

En résumé, nous avons montré que

G =< \overline{− 34} > · < \overline{22} > · < \overline{31} > .

Noter que ceci est une égalité, et pas un isomorphisme, et que les générateurs −34, 22 et 31 ne sont pas canoniques.

Nous n’avons pas encore complètement terminé. Si l’on souhaite la décomposition de G en ses facteurs invariants, nous devons maintenant appliquer l’algorithme de Smith.

Posons g_{1} = \overline{− 34}, g_{2} = \overline{22}, g_{3} = \overline{31}. Nous venons de montrer que les g_{1}, g_{2}, g_{3} sont des générateurs de G d’ordre exactement 2, 4 et 6 respectivement. En d’autres termes, G est isomorphe à ℤ^{3}/N, où N est le sous-module de ℤ^{3} engendré par 2e_{1}, 4e_{2} et 6e_{3} respectivement, les e_{i} désignant la base canonique de ℤ^{3}. Nous devons donc appliquer l’algorithme de Smith à la matrice

A = ( \begin{matrix}2 & 0 & 0 \\ 0 & 4 & 0 \\ 0 & 0 & 6 \end{matrix} ) .

Un calcul immédiat donne S = UAV avec S = ( \begin{matrix}12 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 2 \end{matrix} ), U = ( \begin{matrix}0 & −3 & 2 \\ 0 & 1 & −1 \\ 1 & 0 & 1 \end{matrix} )

et V = ( \begin{matrix}6 & 3 & 1 \\ −3 & −1 & 0 \\ −2 & −1 & 0 \end{matrix} ) (nous donnons la matrice V pour être complet, mais

nous n’en avons pas besoin). Comme U^{−1} = ( \begin{matrix}1 & 3 & 1 \\ −1 & −2 & 0 \\ −1 & −3 & 0 \end{matrix} ), on déduit de la

proposition 1.12 que G =< h_{1} > · < h_{2} > · < h_{3} > avec h_{1}, h_{2}, h_{3} d’ordres 12, 2 et 2 respectivement donnés par [h_{1}, h_{2}, h_{3}] = [g_{1}, g_{2}, g_{3}]U^{−1}, ce qui donne, tous calculs faits,

G =< \overline{− 37} > · < \overline{− 1} > · < \overline{− 34} > ,

où les éléments sont d’ordre 12, 2 et 2 respectivement.

2. Les algorithmes de réduction de réseaux.

Outre les algorithmes d’Hermite et de Smith, il existe un troisième type d’algorithme sur les ℤ-modules, dont le but est légèrement différent. Considérons tout d’abord un cas particulier. Soit N un sous-ℤ-module de rang n de ℤ^{n}. Il peut donc être donné par une matrice carrée n × n de rang n à coefficients entiers, dont les colonnes donnent les coefficients d’une base de N sur la base canonique de ℤ^{n}.

Rappelons que si N est seulement donné par un système générateur et pas par une base, l’un des algorithmes d’Hermite nous permet aisément de trouver une base.

Si A est la matrice sous forme normale d’Hermite donnant la base de N, l’expérience prouve qu’en pratique les coefficients de A sont très grands (plusieurs dizaines ou même centaines de chiffres), même quand N est un sous-module d’indice pas trop grand dans ℤ^{n}.

Ceci n’est pas satisfaisant, et il faut donc rechercher une base de N qui, à défaut d’être en HNF ou même triangulaire, aura des coefficients assez petits. C’est exactement le but des algorithmes de réduction de bases de ℤ-modules. Dans ce chapitre nous allons décrire le plus utile d’entre eux, l’algorithme LLL, du nom des auteurs de l’article dans lequel il est paru (Lenstra, Lenstra, Lovász, voir [LLL]).

2.1. La réduction de Gram-Schmidt.

L’idée de base de tous les algorithmes de réduction de réseaux est la remarque suivante : les vecteurs de base d’un réseau sont les plus courts possibles, quand ils sont presque orthogonaux. Avant de voir ceci, il est nécéssaire de rappeler la construction de Gram-Schmidt telle que nous allons nous en servir.

Proposition 2.1. Soit b_{i} une base d’un espace Euclidien E dont le produit scalaire est noté · . Posons par récurrence

b_{i}^{∗} = b_{i} − ∑_{1≤j<i} μ_{i,j}b_{j}^{∗} (1 ≤ i ≤ n) ,

où pour 1 ≤ j < i ≤ n on a posé

μ_{i,j} = \frac{b_{i} · b_{j}^{∗}}{b_{j}^{∗} · b_{j}^{∗}} .

(1) Les b_{i}^{∗} forment une base orthogonale (mais pas orthonormale) de E, b_{i}^{∗} est égal à la projection de b_{i} sur l’orthogonal de ∑_{j=1}^{i−1} ℝb_{j} = ∑_{j=1}^{i−1} ℝb_{j}^{∗}.

(2) La matrice M donnant les b_{i}^{∗} en termes des b_{i} est une matrice triangulaire supérieure dont les termes diagonaux sont égaux à 1.

(3) Si d est le déterminant de la matrice des b_{i} dans une base orthonormée quelconque de E, on a

d^{2} = ∏_{1≤i≤n} |b_{i}^{∗}|^{2} .

La démonstration de cette proposition est classique et immédiate par récurrence. On en déduit le corollaire suivant, appelé inégalité de Hadamard.

Corollaire 2.2. Soit B = (b_{i,j}) une matrice n × n. On a

| det(B)| ≤ ∏_{1≤i≤n} ( ∑_{1≤j≤n} |b_{i,j}|^{2})^{1/2}

avec égalité si et seulement si les colonnes de la matrice B sont othogonales deux à deux.

Démonstration. Soient b_{i} les vecteurs dont les coordonnées dans la base canonique de l’espace Euclidien E = ℝ^{n} sont les colonnes de la matrice B. Posons B_{i} = |b_{i}^{∗}|^{2}, où les b_{i}^{∗} sont donnés par la construction de Gram-Schmidt ci-dessus. Comme les b_{i}^{∗} sont orthogonaux, on a

|b_{i}|^{2} = b_{i} · b_{i} = B_{i} + ∑_{1≤j<i} μ_{i,j}^{2}B_{j} .

Soit M est la matrice donnant les b_{i}^{∗} en fonction des b_{i}, et posons B^{∗} = BM. La proposition ci-dessus entraine donc que

det(B)^{2} = det(B^{t}B) = det(B^{∗}^{t}B^{∗}) = ∏_{1≤i≤n} B_{i} ≤ ∏_{1≤i≤n} |b_{i}|^{2}

d’après l’égalité ci-dessus. Ceci n’est autre que le corollaire, et le cas d’égalité correspond à μ_{i,j} = 0 pour tout j < i, en d’autres termes à B^{∗} = B ce qui signifie bien que les colonnes de la matrice B sont orthogonales deux à deux. ⊓ ⊔

Soit donc L un réseau de ℝ^{n}, c’est à dire un sous-ℤ-module libre de ℝ^{n} de rang n. Soit b_{i} est une ℤ-base de L de matrice B dans la base canonique de ℝ^{n}. Il est clair que b′_{i} est une autre ℤ-base de L si et seulement si la matrice B′ des b′_{i} est de la forme B′ = BP avec P ∈ GL_{n}(ℤ), c’est à dire à coefficients entiers et de déterminant égal à ±1. En particulier, on voit que | det(B′)| = | det(B)| est donc une quantité indépendante de la base choisie, qui sera donc appelé le déterminant du réseau et noté d(L).

Il résulte du corollaire 2.2 ci-dessus que le produit des normes Euclidiennes des b_{i} est le plus petit possible quand les b_{i} sont orthogonaux (ou de maière équivalente si b_{i}^{∗} = b_{i}). Toutefois il n’est en général pas possible de rendre les vecteurs d’une ℤ-base exactement orthogonaux (noter que les b_{i}^{∗} sont combinaison linéaires des b_{j} à coefficients non entiers en général). Il faudra donc se contenter d’approximations de cette orthogonalité.

2.2. Description de l’algorithme LLL.

C’est ici où les divers algorithmes de réduction de réseaux divergent. L’idée de base de l’algorithme LLL (voir [LLL]) est de travailler seulement sur 2 vecteurs à la fois. En effet, dans le cas de deux vecteurs, on possède un algorithme de réduction optimal, du à Gauss.

L’idée de LLL est donc en gros la suivante. On commence par les deux premiers vecteurs b_{1} et b_{2} que l’on réduit, obtenant deux nouveaux vecteurs, qu’il est pratique de continuer à noter de la même manière (j’expliquerai plus loin comment se fait la réduction de deux vecteurs). On réduit ensuite le couple de vecteurs b_{2} (le nouveau) et b_{3}. En faisant ceci, le vecteur b_{2} a peut être été modifié, et il faut donc à nouveau s’occuper des vecteurs b_{1} et b_{2}. On s’occupe ensuite des vecteurs b_{2} et b_{3} (qui ont pu à nouveau être modifiés). On pourrait croire que ce procédé peut boucler indéfiniment, mais nous allons démontrer que ce n’est pas le cas, et en fait que cela va se stabiliser assez rapidement. On s’occupe ensuite des vectuers b_{3} et b_{4}, et ainsi de suite, jusqu’à ce que tous les couples b_{i}, b_{i+1} pour 1 ≤ i < n soient résuits.

Soyons maintenant plus précis.

Définition 2.3. Soit b_{1}, …,b_{n} une base d’un réseau L dans un espace Euclidien E, et soient b_{i}^{∗} et μ_{i,j} comme ci-dessus. Nous dirons que les b_{i} forment une base LLL réduite si les deux conditions suivantes sont satisfaites.

(1) Pour tout couple (i, j) tel que 1 ≤ j < i ≤ n, on a |μ_{i,j}| ≤ 1/2.

(2) Pour tout i tel que 2 ≤ i ≤ n on a

|b_{i}^{∗} + μ_{i,i−1}b_{i−1}^{∗}|^{2} ≥ \frac{3}{4}|b_{i−1}^{∗}|^{2}

ou de manière équivalente

|b_{i}^{∗}|^{2} ≥ (\frac{3}{4} − μ_{i,i−1}^{2}) |b_{i−1}^{∗}|^{2} .

L’algorithme LLL mentionné ci-dessus est le suivant.

Algorithme 2.4. (Algorithme LLL). Étant donnée une base b_{1}, …,b_{n} d’un rśeau L, cet algorithm transforme les vecteurs pour qu’ils deviennent une base LLL réduite de L.

1. [Gram-Schmidt] En utilisant les formules données ci-dessus, pour i = 1, …, i = n calculer pour tout j < i, μ_{i,j} ← b_{i} · b_{j}^{∗}/B_{j} puis b_{i}^{∗} = b_{i} − ∑_{1≤j<i} μ_{i,j}b_{j}^{∗} et B_{i} ← b_{i}^{∗} · b_{i}^{∗}. Si au cours de ce calcul l’un des B_{i} est égal à zéro, les b_{i} n’étaient pas linéairement indépendants, donc imprimer un message d’erreur et terminer l’algorithme. Sinon, poser k ← 2.

2. [Tester la condition LLL] Executer l’algorithme RED(k, k − 1) ci-dessous. Si B_{k} < (3/4−μ_{k,k−1}^{2})B_{k−1}, éxecuter l’algorithme ECH(k) ci-dessous, poser k ← max(2, k− 1) et aller à 2. Sinon, pour l = k − 2, k − 3, …, 1 éxecuter RED(k, l), puis poser k ← k + 1.

3. [Terminé ?] Si k ≤ n, aller à 2. Sinon, les b_{i} forment une base LLL réduite du réseau et terminer.

Algorithme RED(k, l). Si μ_{k,l} ≤ 0.5, terminer. Sinon, soit q = ⌊0.5 + μ_{k,l}⌋. Poser b_{k} ← b_{k} − qb_{l}, μ_{k,l} ← μ_{k,l} − 1, pour tout i tel que 1 ≤ i ≤ l − 1 poser μ_{k,i} ← μ_{k,i} − qμ_{l,i} et terminer.

Algorithme ECH(k). Echanger les vecteurs b_{k} et b_{k−1} et pour tout j tel que 1 ≤ j ≤ k − 2, échanger μ_{k,j} et μ_{k−1,j}. Puis, dans cet ordre, poser μ ← μ_{k,k−1}, B ← B_{k} + μ^{2}B_{k−1}, t ← B_{k−1}/B, μ_{k,k−1} ← μt, b ← b_{k−1}^{∗}, b_{k−1}^{∗} ← b_{k}^{∗} + μb, b_{k}^{∗} ← −μ_{k,k−1}b_{k}^{∗} + (B_{k}/B)b, B_{k} ← B_{k}t et B_{k−1} ← B. Enfin, pour tout i = k + 1, …, n, poser (dans cet ordre) t ← μ_{i,k}, μ_{i,k} ← μ_{i,k−1} − μt, μ_{i,k−1} ← t + μ_{k,k−1}μ_{i,k} et terminer l’algorithme.

Avant de poursuivre, notons qu’il ne faut pas être effrayé par la complexité apparente des deux sous-algorithmes : l’algorithme RED(k, l) consiste à remplacer b_{k} par b_{k} −qb_{l} pour une valeur optimale de q, le reste n’étant que la mise à jour des données de Gram-Schmidt. De la même manière, ECH(k) consiste à échanger b_{k} et b_{k−1}, le reste des instructions n’étant à nouveau qu’une mise à jour des données de Gram-Schmidt.

Démonstration. Il est facile de montrer qu’au début de l’étape 3 de l’algorithme LLL, les conditions LLL de la définition 2.3 sont satisfaites pour tout i ≤ k − 1. Il en résulte que si k > n (c’est à dire si k = n + 1), les b_{i} forment une base LLL rd́uite. Comme nous n’avons effectué que des opérations élémentaires sur les b_{i}, les b_{i} forment toujours une base du même réseau L, ce qui montre que le résultat de l’algorithme est correct.

Ce qui est moins évident est que l’algorithme se termine! De plus il est relativement rapide puisque nous allons voir qu’il prend un temps polynomial.

Pour 0 ≤ i ≤ n, posons

d_{i} = det((b_{r} · b_{s})_{1≤r,s≤i}) .

On vérifie facilement que

d_{i} = ∏_{1≤j≤i} B_{j} ,

où comme d’habitude on a posé B_{j} = |b_{j}^{∗}|^{2} = b_{j}^{∗} · b_{j}^{∗}.

En particulier on a d_{0} = 1, d_{i} > 0 et d_{n} = d(L)^{2}. Posons

D = ∏_{1≤i≤n−1} d_{i} .

Cette quantité ne peut être modifiée que si l’un des B_{i} se modifie, c’est à dire dans l’algorithme ECH. Mais dans cet algorithme les d_{i} sont inchangés pour i < k − 1 ainsi que pour i ≥ k. De plus, d’après la condition testée à l’étape 2 de l’algorithme LLL, d_{k−1} est multiplié par un facteur compris entre 0 et 3/4. Il en résulte que D est également multiplié par un tel facteur. Or un argument standard de compacité en géométrie des nombres montre que D est borné inférieurement par une constante strictement positive ne dépendant que du réseau L. Il en résulte que l’algorithme ECH ne sera éxecuté qu’un nombre fini de fois. Comme c’est uniquement à la sortie de l’éxecution de cet algorithme que k peut décroitre, l’algorithme doit se terminer. ⊓ ⊔

2.3. Commentaires sur l’algorithme LLL. Nous verrons ultérieurement les propriétés essentielles des bases LLL réduites

ainsi que des variantes de l’algorithme LLL. Dans le présent paragraphe, je veux faire un certain nombre de remarques d’ordre pratique concernant l’algorithme cidessus.

(1) Il est souvent utile, non seulement de transformer la base initiale b_{i} en une base LLL réduite, mais également de connaître la matrice de passage (de déterminant égal à ±1 donnant la nouvelle base en fonction de l’ancienne. Il est très facile d’ajouter aux algorithmes LLL, RED et ECH les instructions nécéssaires.

(2) En pratique, les b_{i} sont connus uniquement à travers la matrice de leurs produits scalaires respectifs (appelée matrice de Gram). Dans ce cas, les b_{i}^{∗} n’ont plus vraiment de sens explicite, et il est nécessaire de modifer les formules donnant les μ_{i,j} et les B_{i}. Les détails sont laissés au lecteur.

(3) Le fait d’avoir à mettre à jour en permanence tous les μ_{i,j} est coûteux. On peut dans une certaine mesure pallier à cet inconvénient en ne calculant les coefficients de Gram-Schmidt qu’au fur et à mesure où ils sont nécessaires.

(4) On peut montrer que la constante 3/4 utilisée dans la définition 2.3 et dans l’algorithme peut être remplacée par une constante arbitraire c telle que 1/4 < c < 1. Plus c est proche de 1, plus les vecteurs finaux seront courts, mais également plus l’algorithme prendra de temps. D’ailleurs, il est possible que la constante c = 1 convienne également, mais on ne sait pas dans ce cas montrer que l’algorithme se termine en temps polynomial, bien qu’il semble que ce soit le cas.

(5) Une possibilité de compromis est de faire varier au cours de l’algorithme la constante c mentionnée ci-dessus, en prenant c de plus en plus proche de 1 au fur et à mesure que k se rapproche de n.

(6) Il est possible de remplacer la condition B_{k} ≥ (3/4 − μ_{k,k−1}^{2})B_{k−1} par la condition B_{k} ≥ B_{k−1}/2, ce qui donne des résultats de qualité semblable.

(7) Si les b_{i} (ou leur matrice de Gram) sont à coefficients inexacts (réels flottants), il faut faire très attention dans la programmation de ces algorithmes. En effet, on peut rapidement atteindre la limite de la précision des données sans s’en apercevoir. Un cas particulier bien connu (correspondant essentiellement au cas n = 2 de l’algorithme LLL) est le développement en fraction continue d’un nombre réel : si le réel est donné à une certaine précision, il n’est pas clair à priori où il faut s’arrêter dans son développement en fractions continues. Cette instabilité numérique est la source essentielle des problèmes rencontrés lors de l’implantation en machine de l’algorithme LLL, du moins quand on désire traiter des nombres non nécéssairement

entiers.

(8) Pour que cet algorithme marche, il est indispensable que les b_{i} soient linéairement indépendants. Si ce n’est pas le cas, on aura un message d’erreur lors du calcul des coefficients de Gram-Schmidt. Nous verrons dans le paragraphe 2.5 comment modifier l’algorithme dans ce cas.

2.4. Propriétés des bases LLL réduites.

Les propriétés essentielles des bases LLL réduites peuvent se résumer dans le théorème suivant.

Théorème 2.5. Soit b_{1}, …, b_{n} une base LLL réduite d’un réseau L de déterminant d(L). On a alors.

(1)

d(L) ≤ ∏_{i=1}^{n} |b_{i}| ≤ 2^{n(n−1)/4}d(L) ,

(2)

|b_{j}| ≤ 2^{(i−1)/2}|b_{i}^{∗}|, si 1 ≤ j ≤ i ≤ n ,

(3)

|b_{1}| ≤ 2^{(n−1)/4}d(L)^{1/n} ,

(4) Pour tout x ∈ L non nul, on a

|b_{1}| ≤ 2^{(n−1)/2}|x| ,

(5) Plus généralement, si x_{1}, …, x_{t} ∈ L sont linéairement indépendants, on a

|b_{j}| ≤ 2^{(n−1)/2} max(|x_{1}|, …, |x_{t}|) pour 1 ≤ j ≤ t .

Démonstration. La première inégalité de (1) n’est autre que l’inégalité de Hadamard (corollaire 2.2). Puisque les b_{i} sont LLL réduits, on a B_{i} ≥ (3/4 − μ_{i,i−1}^{2})B_{i−1} ≥ B_{i−1}/2 puisque |μ_{i,i−1}| ≤ 1/2. Par récurrence, ceci implique que B_{j} ≤ 2^{i−j}B_{i} pour i ≥ j, donc que

b_{i} · b_{i} ≤ \frac{2^{i−1} + 1}{2}B_{i} ,

ce qui entraine la deuxième inégalité de (1) (avec même une meilleure constante).

En combinant les deux inégalités que nous venons de démontrer, on obtient que pour tout j ≤ i, on a b_{j} · b_{j} ≤ (2^{i−2} + 2^{i−j−1})B_{i}, ce qui implique (2).

Si on prend j = 1 dans (2) et que l’on effectue le produit de i = 1 à i = n, on obtient

|b_{1}|^{2n} ≤ 2^{n(n−1)/2} ∏_{1≤i≤n} B_{i} = 2^{n(n−1)/2}d(L)^{2} ,

ce qui montre (3).

Montrons (4). Puisque les b_{j} forment une base de L et que x ≠ 0, il existe i et des r_{j} ∈ ℤ tels que x = ∑_{1≤j≤i} r_{j}b_{j}, avec r_{i} ≠ 0. La construction des b_{i}^{∗} implique que l’on a également x = ∑_{1≤j≤i} s_{j}b_{j}^{∗} avec s_{j} ∈ ℝ, et de plus on a s_{i} = r_{i}. On a donc

|x|^{2} ≥ s_{i}^{2}B_{i} = r_{i}^{2}B_{i} ≥ B_{i}

puisque r_{i} est un entier non nul. D’après (2), on a donc

|x|^{2} ≥ B_{i} ≥ 2^{1−i}|b_{1}|^{2} ≥ 2^{1−n}|b_{1}|^{2} ,

d’où (4). On démontre (5) par une généralisation de cet argument. ⊓ ⊔

La propriété la plus importante d’une base LLL réduite est probablement la propriété (4) : le théorème ci-dessus montre que le premier vecteur d’une base LLL réduite est, en un sens précis, pas beaucoup plus grand que le plus petit vecteur non nul du résau. Or trouver un vecteur de plus petite norme dans un réseau est très difficile (tous les experts pensent qu’il est impossible de faire ceci en temps polynomial, et même en pratique cela peut prendre beaucoup de temps). Par contraste, vu l’existence de l’algorithme LLL qui est polynomial, il est relativement aisé de trouvé un vecteur de norme relativement petite.

D’ailleurs en pratique, il arrive souvent que b_{1} soit effectivement le plus petit vecteur non nul du réseau, mais bien sûr ce n’est pas toujours le cas.

Comme il a été signalé ci-dessus, on peut remplacer la constante 3/4 de la définition d’une base LLL-réduite par une constante c arbitraire vérifiant 1/4 < c < 1. Il est nécéssaire dans ce cas de modifier les constantes intervenant dans le théorème ci-dessus, et ceci est laissé au lecteur. On s’apercoit que la borne pour b_{1} devient meilleure quand c est proche de 1.

2.5. Variantes de l’algorithme LLL.

Il existe plusieurs variantes importantes de l’algorithme LLL, qui peuvent d’ailleurs se combiner. Dans ce paragraphe, nous en décrirons deux, à savoir l’algorithme LLL entier, et l’algorithme LLL appliqué à des vecteurs linéairement dépendants.

Il a été dit ci-dessus que, lorsque les b_{i} sont inexacts, il fallait faire attention aux pertes de précision lors de l’éxécution de l’algorithme LLL. Quand les b_{i} sont exacts, disons quand la matrice de Gram des produits scalaires b_{i} · b_{j} est à coefficients entiers, il y a deux manières de procéder. Soit on calcule les μ_{i,j}, b_{i}^{∗} et B_{i} de façon approchée, comme si les b_{i} étaient inexacts. Ceci a l’avantage de la rapidité, mais le désavantage déja mentionné du danger de perte de précision, difficile à controler.

Soit on fait tous les calculs exactement. Il est facile de voir que les μ_{i,j}, b_{i}^{∗} et B_{i} seront tous à coefficients rationnels, et donc les calculs exacts pourront se faire. Toutefois, les calculs avec les rationnels souffrent d’un grave défaut : il est nécéssaire de réduire les fractions que l’on trouve dans les calculs, ce qui conduit au calcul d’un très grand nombre de PGCD. L’algorithme devient alors beaucoup trop lent pour avoir une utilité pratique.

Toutefois, il y a un moyen d’effectuer tous les calculs en utilisant exclusivement des nombres entiers, et évitant tout calcul de PGCD. L’algorithme correspondant, que nous appelerons l’algorithme LLL entier, est plus lent que l’algorithme flottant, mais est parfaitement sûr, et il est tout à fait utilisable en pratique. Le principe de cet algorithme est basé sur la proposition suivante.

Proposition 2.6. Supposons que pour tout i et j, b_{i} · b_{j} ∈ ℤ, et posons comme ci-dessus

d_{i} = det((b_{r} · b_{s})_{1≤r,s≤i}) = ∏_{1≤j≤i} B_{j} .

Alors on a, pour tout i et tout j < i,

(1)

d_{i−1}B_{i} ∈ ℤ  et  d_{j}μ_{i,j} ∈ ℤ .

(2) Pour tout m tel que j < m ≤ i,

d_{j} ∑_{1≤k≤j} μ_{i,k}μ_{m,k}B_{k} ∈ ℤ .

Démonstration. Nous avons vu dans la démonstration du théorème 2.5 que d_{i} = ∏_{1≤k≤i} B_{k}. Il en résulte que d_{i−1}B_{i} = d_{i} ∈ ℤ. D’autre part soit j < i et posons

v = b_{i} − ∑_{1≤k≤j} μ_{i,k}b_{k}^{∗} = b_{i}^{∗} + ∑_{j<k<i} μ_{i,k}b_{k}^{∗} .

La deuxième égalité implique que b_{k}^{∗}v = 0 pour tout k tel que 1 ≤ k ≤ j. Puisque le ℝ-espace vectoriel engendré par les b_{k}^{∗} pour 1 ≤ k ≤ j est le même que celui engendré par les b_{k} pour 1 ≤ k ≤ j, on a donc aussi b_{k} · v = 0 pour tout k tel que 1 ≤ k ≤ j.

Pour la même raison, mais en considérant la première expression donnant v, on voit qu’il existe des nombres réels x_{k} tels que

v = b_{i} − ∑_{1≤k≤j} x_{k}b_{k} .

En termes matriciels, on peut donc écrire

( \begin{matrix}b_{1} · b_{1} & … & b_{1} · b_{j} \\ ⋮ & ... & ⋮ \\ b_{j} · b_{1} & … & b_{j} · b_{j} \end{matrix} ) ( x_{1} ; ⋮ ; x_{j} ) = ( b_{i} · b_{1} ; ⋮ ; b_{i} · b_{j} ) .

Puisque par définition le déterminant de la matrice de gauche est égal à d_{j}, il en résulte que les x_{k} sont de la forme x_{k} = m_{k}/d_{j} pour certains entiers m_{k}. De plus l’égalité

∑_{1≤k≤j} x_{k}b_{k} = ∑_{1≤k≤j} μ_{i,k}b_{k}^{∗}

projetée sur b_{j}^{∗} montre que x_{j} = μ_{i,j}, donc d_{j}μ_{i,j} = m_{j} ∈ ℤ, d’où (1).

D’après ce que nous venons de démontrer, d_{j}v est une combinaison linéaire des b_{k} à coefficients entiers, et donc appartient au réseau. Il résulte donc de l’intégralité de la matrice de Gram que d_{j}v · b_{m} ∈ ℤ pour tout m. En remplacant v par b_{i} − ∑_{1≤k≤j} μ_{i,k}b_{k}^{∗}, on obtient (2). ⊓ ⊔

Corollaire 2.7. Avec les mêmes hypothèses, posons λ_{i,j} = d_{j}μ_{i,j} pour j < i (donc λ_{i,j} ∈ ℤ), et λ_{i,i} = d_{i}. Fixons un j ≤ i, et définissons une suite u_{k} par u_{0} = b_{i} · b_{j}, et pour 1 ≤ k < j,

u_{k} = \frac{d_{k}u_{k−1} − λ_{i,k}λ_{j,k}}{d_{k−1}} .

Alors pour tout k < j on a u_{k} ∈ ℤ, et u_{j−1} = λ_{i,j}.

Démonstration. Par récurrence sur k, on vérifie immédiatement que

u_{k} = d_{k} (b_{i} · b_{j} − ∑_{1≤l≤k} \frac{λ_{i,l}λ_{j,l}}{d_{l}d_{l−1}} ) = d_{k} (b_{i} · b_{j} − ∑_{1≤l≤k} μ_{i,l}μ_{j,l}B_{l})

et la proposition montre que cette dernière expression est dans ℤ. D’autre part on voit facilement d’après l’expression ci-dessus que u_{j−1} = B_{j}d_{j−1}μ_{i,j} = d_{j}μ_{i,j} = λ_{i,j}, ce qui démontre le corollaire. ⊓ ⊔

Grâce à cette proposition et son corollaire, il est maintenant facile de modifier l’algorithme LLL et les sous-algorithmes RED et ECH pour qu’ils n’utilisent que des nombres entiers. Je laisse les détails au lecteur. (Voir [Coh2] si nécéssaire).

Une autre variante importante de l’algorithme LLL concerne le cas où les vecteurs b_{i} ne sont pas linéairement indépendants. Il arrivera alors un moment dans l’orthogonalisation de Gram-Schmidt où l’on trouvera B_{i} = 0, ce qui apparemment empêche toute possibilité de continuer. En fait, ce n’est pas grave du tout. En effet, Gram-Schmidt procède par projections des vecteurs sur le sous-espace engendré par les précédents. Si B_{i} = 0, celà signifie que le vecteur b_{i} est combinaison linéaire des précédents, donc que le sous-espace engendré ne varie pas, et on peut donc continuer. En d’autres termes, il suffit d’ignorer les indices pour lesquels B_{i} = 0.

Ceci donne les formules suivantes pour la réduction de Gram-Schmidt.

b_{i}^{∗} = b_{i} − ∑_{1≤j<i} μ_{i,j}b_{j}^{∗} (1 ≤ i ≤ n) ,

où pour 1 ≤ j < i ≤ n on a posé

μ_{i,j} = \{ \begin{matrix}\frac{b_{i} · b_{j}^{∗}}{B_{j}} & si B_{j} ≠ 0 \\ 0 si B_{j} = 0 \end{matrix} ,

et B_{i} = b_{i}^{∗} · b_{i}^{∗}.

A ce propos, une remarque importante doit être faite. Que signifie B_{i} = 0 quand les b_{i} ne sont pas donnés exactement ? De manière équivalente, que signifie le fait de dire que les b_{i} sont linéairement dépendants ? Le problème est intrinsèquement difficile, et je n’apporterai pas de solution sauf pour dire qu’il faut dans ce cas remplacer la condition B_{i} = 0 par B_{i} < ε, où ε est choisi en fonction de la précision des b_{i} (mais le choix précis n’est pas facile à faire).

L’algorithme est le suivant.

Algorithme 2.8. (Algorithme LLL pour des vecteurs linéairement dépendants). Étant donnée un système générateur b_{1}, …,b_{n} d’un réseau L, cet algorithm transforme les vecteurs et calcule le rang p du réseau L de telle façon que b_{i} = 0 pour 1 ≤ i ≤ n − p et les b_{i} pour n − p < i ≤ n forment une base LLL réduite de L. De plus, l’algorithme calcule une matrice H exprimant les nouveaux b_{i} en fonction des b_{i} initiaux. En particulier, les n − p premières colonnes H_{i} de H forment une base des relations entre les b_{i} initiaux, c’est à dire des vecteurs r = (r_{i}) tels que ∑_{1≤i≤n} r_{i}b_{i} = 0.

1. [Gram-Schmidt] En utilisant les formules données ci-dessus, pour i = 1, …, i = n calculer pour tout j < i, μ_{i,j} ← b_{i} · b_{j}^{∗}/B_{j} si B_{j} ≠ 0, μ_{i,j} ← 0 sinon, puis b_{i}^{∗} = b_{i} − ∑_{1≤j<i} μ_{i,j}b_{j}^{∗} et B_{i} ← b_{i}^{∗} · b_{i}^{∗}. Enfin, poser k ← 2 et H ← I_{n}, la matrice identité d’ordre n.

2. [Tester la condition LLL] Executer l’algorithme RED(k, k − 1) ci-dessus. Si B_{k} < (3/4−μ_{k,k−1}^{2})B_{k−1}, éxecuter l’algorithme ECHG(k) ci-dessous, poser k ← max(2, k− 1) et aller à 2. Sinon, pour l = k − 2, k − 3, …, 1 éxecuter RED(k, l), puis poser k ← k + 1.

3. [Terminé ?] Si k ≤ n, aller à 2. Sinon, soit r le nombre de vecteurs initiaux b_{i} qui sont égaux à zéro, sortir p ← n − r, les vecteurs b_{i} pour r + 1 ≤ i ≤ n (qui forment une base LLL réduite de L), la matrice H ∈ GL_{n}(ℤ), et terminer.

L’algorithme de réduction à utiliser est le même que celui utilisé dans l’algorithme LLL ordinaire. Par contre, l’algorithme d’échange doit être modifié comme suit.

Algorithme ECHG(k). Echanger les vecteurs b_{k} et b_{k−1}, H_{k} et H_{k−1}, et pour tout j tel que 1 ≤ j ≤ k − 2, échanger μ_{k,j} et μ_{k−1,j}. Puis, dans cet ordre, poser μ ← μ_{k,k−1} et B ← B_{k} + μ^{2}B_{k−1}. Si B = 0 (c’est à dire si B_{k} = μ = 0), échanger B_{k} et B_{k−1}, b_{k}^{∗} et b_{k−1}^{∗} et pour tout i ≥ k + 1 échanger μ_{i,k} et μ_{i,k−1}.

Si B_{k} = 0 et μ ≠ 0, poser B_{k−1} ← B, b_{k−1}^{∗} ← μb_{k−1}^{∗}, μ_{k,k−1} ← 1/μ, et pout tout i ≥ k + 1 poser μ_{i,k−1} ← μ_{i,k−1}/μ.

Enfin, si B_{k} ≠ 0, poser (dans cet ordre) t ← B_{k−1}/B, μ_{k,k−1} ← μt, b ← b_{k−1}^{∗}, b_{k−1}^{∗} ← b_{k}^{∗} + μb, b_{k}^{∗} ← −μ_{k,k−1}b_{k}^{∗} + (B_{k}/B)b, B_{k} ← B_{k}t et B_{k−1} ← B, puis, pour tout i ≥ k + 1 poser (dans cet ordre) t ← μ_{i,k}, μ_{i,k} ← μ_{i,k−1} − μt, μ_{i,k−1} ← t + μ_{k,k−1}μ_{i,k} et terminer l’algorithme.

Démonstration. La démonstration est tout à fait analogue à celle de l’algorithme et les détails sont laissés au lecteur. Je signale seulement que pour montrer que l’algorithme se termine, on pose

d_{k} = ∏_{i≤k,B_{i}≠0} B_{i} et D = ∏_{1≤k≤n,B_{k}≠0} d_{k} ∏_{1≤k≤n,B_{k}=0} 2^{k}

et on montre que D doit d’une part décroitre par un facteur au plus égal à 3/4 à chaque passage dans l’algorithme ECHG, et d’autre part que D est borné inférieurement. ⊓ ⊔

Il est bien entendu facile de combiner l’algorithme ci-dessus avec l’algorithme LLL entier.

2.6. Applications de l’algorithme LLL.

L’algorithme LLL et ses variantes possède un grand nombre d’applications. Dans ce paragraphe, nous en donnerons deux : la recherche du noyau et de l’image entière d’une matrice, et la recherche de relations linéaires entre nombres réels ou complexes.

Nous avons déja vu (proposition 1.9) que l’algorithme d’Hermite permet de trouver le noyau et l’image d’une matrice considérée comme application linéaire de ℤ^{k} dans ℤ^{n}. Il est clair que l’algorithme 2.8 (ou sa version n’utilisant que des entiers) permet de faire le même travail en utilisant une méthode assez différente. Voyons les avantages et les inconvénients de ces deux méthodes.

Tout d’abord, un mot sur les temps d’éxecution. Correctement programmé, en utilisant l’algorithme d’Hermite modulaire, la méthode utilisant l’algorithme d’Hermite prend un temps de l’ordre de O(n^{3}). L’algorithme LLL est en général plus lent, et une estimation raisonnable de son temps d’écution moyen est de l’ordre de O(n^{4}).

Si l’on cherche l’image (entière) d’une matrice ou d’une famille de vecteurs, il est inutile en général de conserver la matrice de transformation unimodulaire H, et on peut préférer utiliser Hermite. Toutefois les vecteurs de base qui seront obtenus peuvent être de grande taille, et il est souvent indispensable d’en réduire la taille au moyen de l’algorithme LLL. En conséquence, quand on ne veut calculer que l’image, il est raisonnable d’adopter le scénario suivant. Si le nombre de colonnes est beaucoup plus grand que le nombre de lignes, on commence par utiliser Hermite (modulaire), puis LLL. Sinon, on utilise directement l’algorithme LLL pour des vecteurs linéairement dépendants.

Si l’on cherche le noyau (entier), la situation est différente car il est indispensable de conserver la matrice de transformation unimodulaire H. Il est beaucoup plus facile de conserver cette matrice dans l’algorithme LLL modifié (qui la donne directement) que dans l’algorithme d’Hermite modulaire. On peut donc penser qu’il est préférable d’utiliser LLL. En fait, ce n’est pas le cas, car il existe un autre type d’algorithmes d’Hermite, dus essentiellement à G. Havas, qui utilisent des méthodes heuristiques permettant d’optimiser la taille des matrices de transformation unimodulaires H, et l’utilisation de ces algorithmes conduit à des temps d’éxecution sensiblement inférieurs aux autres, qu’ils soient Hermite modulaires ou LLL. Je réfère à [Hav-Maj] pour les détails.

Une deuxième application, très importante et spécifique de l’algorithme LLL est la recherche de relations linéaires à coefficients entiers entre nombres réels ou complexes.

Soient α_{1}, …, α_{n} des nombres réels. Nous souhaitons savoir s’il existe des entiers x_{i} tels que ∑_{i=1}^{n} x_{i}α_{i} = 0. Cette question est bien entendu mal posée, puisque les α_{i} ne sont donnés que de façon approchée, donc la somme ne pourra presque jamais être égale à zéro. On peut mieux poser la question en limitant la taille des x_{i}, et en se donnant une précision suffisamment grande sur les α_{i}. Voyons ce que nous pouvons faire dans cette direction.

Soit b_{i} le vecteur de ℝ^{n+1} dont la n+1-ième composante (dans la base canonique de ℝ^{n+1}) est Nα_{i} (où N est un grand nombre à choisir ultérieurement), dont la j-ième composante est égale à 1 pour j ≤ n, et les autres composantes égales à zéro. En d’autres termes, la matrice des b_{i} dans la base canonique est donnée par

B = ( \begin{matrix}1 & … & 0 \\ ⋮ & ... & ⋮ \\ 0 & … & 1 \\ Nα_{1} & … & Nα_{n} \end{matrix} ) .

Les vecteurs b_{i} étant évidemment linéairement indépendants sur ℝ engendrent donc un réseau L_{N} de rang n. Si x = ∑_{i} x_{i}b_{i} est un vecteur quelconque de L_{N}, on a

x = (x_{1}, …, x_{n}, N ∑_{i} x_{i}α_{i})^{t} .

Supposons que les α_{i} soient donnés avec une précision absolue inférieure à ϵ, et que l’on exige que |x_{i}| soit inférieur ou égaux à une constante X pour tout i. Demander ∑_{i} x_{i}α_{i} = 0 signifiera donc en pratique demander que

| ∑_{i} x_{i}α_{i}| < nXϵ ,

ce qui implique que

x · x < nX^{2} + N^{2}n^{2}X^{2}ϵ^{2} = n^{2}X^{2} (N^{2}ϵ^{2} + \frac{1}{n}) .

Appliquons donc l’algorithme LLL au réseau L_{N}. Grâce à cet algorithme, nous obtenons un petit vecteur y = (y_{1}, …, y_{n}, s), qui d’après le Theorème 2.5 vérifie pour tout vecteur x ∈ L_{N} comme ci-dessus :

|y| ≤ 2^{(n−1)/2}|x| < n2^{(n−1)/2}X\sqrt{N^{2}ϵ^{2} + \frac{1}{n}} .

En d’autres termes, nous avons prouvé le résultat suivant.

Proposition 2.9. Avec les notations ci-dessus, soit y = (y_{1}, …, y_{n}, s) le premier vecteur de la base LLL réduite du réseau L_{N}. Si ∑_{i} x_{i}α_{i} = 0 on a

max_{i} |x_{i}| ≥ \frac{|y|}{n2^{(n−1)/2}\sqrt{N^{2}ϵ^{2} + 1/n}} .

Réciproquement, si

|s| ≤ Nϵ ∑_{i} |y_{i}| ,

nous dirons que la relation ∑_{i} y_{i}α_{i} = 0 est satisfaite.

Ceci conduit donc à la méthode suivante. Nous choissons N au plus égal à ϵ^{−1}/\sqrt{n} et au mois égal à ϵ^{−1/2}, et on applique l’algorithme LLL au réseau L_{N}. Si le vecteur y trouvé par l’algorithme vérifie |s| ≤ Nϵ ∑_{i} |y_{i}|, nous donnons comme relation ∑_{i} y_{i}α_{i} = 0. Sinon, nous savons que si ∑_{i} x_{i}α_{i} = 0, on doit avoir

max_{i} |x_{i}| ≥ \frac{|y|}{n2^{(n−1)/2}\sqrt{N^{2}ϵ^{2} + 1/n}} .

Bien entendu, le choix de N gouverne la qualité de cette borne inférieure.

En pratique, cette application de l’algorithme LLL est beaucoup plus souvent utilisée dans sa version positive (i.e. existence d’une relation) que sa version négative.

Prenons un exemple. Soit θ = \sqrt{2} + \sqrt{3}. Nous savons que θ est racine d’un polynôme de degré 4, qu’il est facile de trouver par des moyens algébriques (en utilisant des résultants). Toutefois, on peut appliquer l’algorithme LLL à α_{i} = θ^{i−1} pour 1 ≤ i ≤ 5. Pour ϵ = 10^{−29}, toutes les valeurs de N entre 15 et 28 conviennent, et donnent le polynôme X^{4} − 10X^{2} + 1 comme polynôme minimal de θ.

La méthode ci-dessus peut aisément se généraliser pour trouver des relations de dépendance ℤ-linéaires entre des nombres complexes α_{i}. Il suffit pour celà de considérer des réseaux L_{N} dans ℝ^{n+2}, où les deux dernières lignes contiennent N fois les parties réelles et imaginaires des α_{i}. D’ailleurs, ceci n’a rien à voir avec la structure spécifique de ℂ, et on peut généraliser pour trouver des relations de ℤdépendance entre vecteurs appartenant à un espace vectoriel de (petite) dimension sur ℝ.

3. Algorithmes sur les ℤ_{K}-modules

Alors que les théories présentées ci-dessus sont maintenant tout à fait classiques (bien que l’algorithme LLL ne date que d’une quinzaine d’années), les algorithmes dont nous allons parler maintenant sont beaucoup plus récents. Ils sont apparus pour la première fois dans [Bos-Poh], et la formulation que nous donnons ici n’est pas encore parue.

Le but essentiel que nous poursuivons est de généraliser à l’anneau des entiers ℤ_{K} d’un corps de nombres les algorithmes de base utilisées sur ℤ. La raison principale qui conduit à faire ceci est la suivante. Supposons qu’un corps L soit défini comme une extension relative de corps de nombres, c’est à dire L = K[θ] pour un certain corps de nombres K. Des techniques standards permettent d’écrire L avec un élément primitif sur ℚ, comme L = ℚ[α]. Ceci est en général une très mauvaise idée, car on perd toute les structures d’extensions relatives. Il faut donc essayer de rester sur le corps de base K au lieu de redescendre à ℚ.

Toutefois, dès qu’on se pose le problème de la recherche d’une base d’entiers de L, plusieurs obstacles apparemment insurmontables apparaissent. Tout d’abord, ℤ_{L} n’est pas toujours un ℤ_{K}-module libre, pusique ℤ_{K} n’est plus un anneau principal en général. D’autre part les techniques d’algèbre linéaire sur ℤ décrites ci-dessus (Hermite, Smith, etc...) dépendent de manière essentielle du fait que ℤ est non seulement un anneau principal, mais même un anneau Euclidien avec un algorithme d’Euclide explicite. Or ceci n’est pas le cas en général pour ℤ_{K}.

Dans ce chapitre, nous allons brièvement expliquer comment surmonter les obstacles ci-dessus, et ainsi obtenir des algorithmes tout à fait satisfaisants pour les extensions relatives. Il y aura peu de démonstrations, référant à [Coh2] pour les détails.

3.1. Modules sur les anneaux de Dedekind.

Bien que l’anneau des entiers ℤ_{K} d’un corps de nombres ne soit pas un anneau principal en général, c’est quand même un anneau de Dedekind. Rappelons qu’il s’agit d’un anneau Noethérien, intégralement clos dans lequel tout idéal premier non nul est maximal. Les propriétés essentielles d’un anneau de Dedekind tiennent dans deux théorèmes. D’une part le théorème d’approximation, dont nous ne parlerons pas ici. D’autre part le théorème affirmant que l’ensemble des idéaux fractionnaires non nuls d’un anneau de Dedekind R forme un groupe pour la multiplication des idéaux. En particulier tout idéal I est inversible, et on a

I^{−1} = {x ∈ R/ xI ⊂ R} .

Le théorème suivant résume les propriétés des modules (que l’on supposera toujours de type fini) sur un anneau de Dedekind.

Theorème 3.1. Soit R un anneau de Dedekind de corps des fractions K, et soit M un R-module de type fini.

(1) Si

M_{tors} = {x ∈ M/ ∃a ∈ R, ax = 0}

est le sous-module de torsion de M, il existe un sous-module sans torsion N de M tel que

M = M_{tors} ⊕ N  et  N ≃ M/M_{tors} .

(2) Un R-module M de type fini est sans torsion si et seulement si M est un module projectif. Si V = MK est l’espace vectoriel engendré par M et si n = dim_{K}(V) est le rang de M, il existe des idéaux fractionnaires 𝔞_{i} et des éléments ω_{i} ∈ V tels que

M = 𝔞_{1}ω_{1} ⊕ 𝔞_{2}ω_{2} ⊕ ⋯ ⊕ 𝔞_{n}ω_{n} .

La classe du produit 𝔞 = 𝔞_{1}𝔞_{2} ⋯ 𝔞_{n} dans le groupe de classes de R ne dépend que du module M et s’appelle la classe de Steinitz de M. Le module M est un R-module libre si et seulement si sa classe de Steinitz est triviale.

(3) Soit M un module de torsion de type fini. Il existe des idéaux entiers 𝔡_{i} de R et des éléments ω_{i} ∈ M tels que

M = (R/𝔡_{1})ω_{1} ⊕ ⋯ ⊕ (R/𝔡_{n})ω_{n}

et 𝔡_{i−1} ⊂ 𝔡_{i} pour 2 ≤ i ≤ n.

Vu ce théorème, il est naturel de poser la définition suivante.

Définition 3.2. Soit M un R-module sans torsion de type fini et soit V = MK. Si les 𝔞_{i} sont des idéaux fractionnaires de R et ω_{i} des éléments de V, nous dirons que (ω_{i}, 𝔞_{i})_{1≤i≤k} forme un pseudo-système générateur de M si

M = 𝔞_{1}ω_{1} + ⋯ + 𝔞_{k}ω_{k} .

Nous dirons que c’est une pseudo-base de M si la somme est directe, c.a.d. si

M = 𝔞_{1}ω_{1} ⊕ ⋯ ⊕ 𝔞_{k}ω_{k} .

Notons que d’après le théorème 3.1, tout module de type fini sans torsion possède une pseudo-base.

Nous représenterons donc toujours les modules de type fini sans torsion par une pseudo-base. Pour faire ceci, il est nécesaire de savoir calculer et manipuler de telles pseudo-bases. Comme pour le cas R = ℤ, l’outil de base est l’algorithme d’Hermite, qui lui-même repose de manière essentielle sur l’algorithme d’Euclide. Nous allons maintenant voir qu’un tel algorithme existe.

3.2. L’algorithme d’Euclide étendu dans ℤ_{K}.

Pour un spécialiste, l’affirmation suivante peut paraître provocatrice, mais pourtant elle est vraie : tout anneau de Dedekind de la forme ℤ_{K} possède un algorithme d’Euclide étendu (ce qu’on appelle en France l’identité de Bezout au + bv = d) explicite, qui généralise exactement le cas des anneaux Euclidiens. Voyons pourquoi.

Proposition 3.3. Soit R un anneau de Dedekind, 𝔞 et 𝔟 deux idéaux de R, et a et b deux éléments non tous deux nuls de R. Posons 𝔡 = a𝔞 + b𝔟. Il existe u ∈ 𝔞𝔡^{−1} et v ∈ 𝔟𝔡^{−1} tels que au + bv = 1.

Démonstration. Si on multiplie l’égalité 𝔡 = a𝔞 + b𝔟 par 𝔡^{−1} on obtient a𝔞𝔡^{−1} + b𝔟𝔡^{−1} = R, ce qui démontre bien la proposition. ⊓ ⊔

Considérons le cas pariticulier où R est un anneau principal, et 𝔞 = 𝔟 = R. On a aR + bR = dR en posant d = pgcd(a, b), donc 𝔡 = dR, d’où 𝔡^{−1} = (1/d)R, et la proposition affirme donc qu’il existe u et v dans R/d tel que au + bv = 1, ce qui est exactement l’énoncé de l’identité de Bezout.

Dans le cas où R = ℤ_{K}, nous pouvons transformer l’affirmation d’existence en un algorithme grâce à la proposition suivante.

Proposition 3.4.. Soient I et J deux idéaux entiers de ℤ_{K} premiers entre eux, c’est à dire vérifiant I + J = ℤ_{K}. Il existe un algorithme qui trouve en temps polynomial α ∈ I et β ∈ J tel que α + β = 1.

Démonstration. Nous représenterons les idéaux I et J par leur forme normale d’Hermite H_{I} et H_{J} dans une base d’entiers de ℤ_{K}. Nous supposerons la base d’entiers choisie pour que son premier élément soit égal à 1 (on peut aisément se ramener à ce cas). Soit H la matrice à n lignes et 2n colonnes obtenue en concaténant les matrices H_{I} et H_{J}, où n = [K : ℚ]. La matrice H est la matrice d’un système générateur de I +J = ℤ_{K}. Il en résulte que la forme normale d’Hermite de H sera égale à la matrice identité. En d’autres termes, en utilisant l’un des algorithmes d’Hermite expliqués dans le chapitre 1, nous pouvons trouver une matrice unimodulaire U de rang 2n, telle que HU soit la concaténation d’une matrice n × n nulle et de la matrice identité d’ordre n. Mais alors si Z est la n + 1-ième ligne de U, on a HZ = [1, 0, …, 0]^{t} qui représente l’entier 1 d’après le choix de notre base d’entiers. Si l’on appelle X (resp. Y) les n premières (resp. dernières) composantes de Z, il est clair que H_{I}X représente un élément α ∈ I, H_{J}Y représente un élément β ∈ J, et α + β est représenté par HZ = [1, …, 0]^{t}, d’où la Proposition. ⊓ ⊔

Corollaire 3.5.. Soient 𝔞 et 𝔟 deux idéaux de ℤ_{K}, et a et b deux éléments non tous deux nuls de ℤ_{K}. Posons 𝔡 = a𝔞 + b𝔟. On peut trouver en temps polynomial u ∈ 𝔞𝔡^{−1} et v ∈ 𝔟𝔡^{−1} tels que au + bv = 1.

Démonstration. Il suffit de combiner les Propositions 3.3 et 3.4. ⊓ ⊔

Le corollaire ci-dessus est donc le remplacant exact de l’algorithme d’Euclide étendu, et comme il a déja été dit, même si ℤ_{K} est Euclidien, nous pouvons l’utiliser à la place de l’algorithme d’Euclide de ℤ_{K}.

Avant de passer à l’algorithme d’Hermite, il nous faut encore quelques résultats faciles (non pas que les résultats ci-dessus ne l’étaient pas!) dont la démonstration est laissée au lecteur (voir [Coh2]).

Proposition 3.6. Soit 𝔞, 𝔟, 𝔠, 𝔡 des idéaux fractionnaires de R = ℤ_{K}, et soient a, b, c, d des éléments de K. Posons e = ad − bc, et supposons que

𝔞𝔟 = e𝔠𝔡, a ∈ 𝔞𝔠^{−1}, b ∈ 𝔟𝔠^{−1}, c ∈ 𝔞𝔡^{−1}, d ∈ 𝔟𝔡^{−1} .

Enfin, soient x et y deux éléments d’un R-module M, et posons

( x′ y′) = ( x y) ( \begin{matrix}a & c \\ b & d \end{matrix} ) .

Alors

𝔞x + 𝔟y = 𝔠x′ + 𝔡y′ .

Corollaire 3.7. Soient 𝔞 et 𝔟 deux ideaux, a et b deux éléments de K non tous deux nuls, 𝔡 = a𝔞 + b𝔟 et u ∈ 𝔞𝔡^{−1}, v ∈ 𝔟𝔡^{−1} tels que au + bv = 1 fournis par le Corollaire 3.5.

Soient x et y deux éléments d’un R-module M, et posons

( x′ y′) = ( x y) ( \begin{matrix}b & u \\ −a & v \end{matrix} ) .

Alors

𝔞x + 𝔟y = 𝔞𝔟𝔡^{−1}x′ + 𝔡y′ .

3.3. L’algorithme d’Hermite dans ℤ_{K}.

Grâce aux résultats ci-dessus, il est maintenant facile d’écrire des algorithmes d’Hermite, d’Hermite modulaire ou de Smith dans l’anneau de Dedekind ℤ_{K}. Décrivons simplement l’algorithme d’Hermite le plus simple.

Nous partons d’un pseudo-système générateur (ω_{j}, 𝔞_{j}) d’un module M, où les ω_{j} sont représentés par une matrice A sur une base (e_{i}) de V = KM, et nous voulons trouver une pseudo-base de M. Nous travaillons sur la matrice A de manière analogue à l’algorithme d’Hermite. Dans celui-ci, on considère deux éléments a et b situés sur la même ligne, a étant en colonne j et b en colonne k. Grâce à Euclide étendu, si on pose d = P GCD(a, b) et u et v sont tels que au + bv = d, le remplacement de (A_{j}, A_{k}) par ((b/d)A_{j} − (a/d)A_{k}, uA_{j} + vA_{k}) conserve le module engendré par les colonnes de A, et remplace le couple (a, b) par le couple (0, d) (ici A_{j} désigne la j-ième colonne de A).

Dans le cas de ℤ_{K} et dans la même situation, le corollaire 3.5 ci-dessus appliqueé à a, b et aux idéaux 𝔞 = 𝔞_{j} et 𝔟 = 𝔞_{k} fournit 𝔡 = a𝔞 + b𝔟, u ∈ 𝔞𝔡^{−1} et v ∈ 𝔟𝔡^{−1} tels que au + bv = 1. On remplace alors

(A_{j}, A_{k}, 𝔞_{j}, 𝔞_{k}) par (bA_{j} − aA_{k}, uA_{j} + vA_{k}, 𝔞_{j}𝔞_{k}𝔡^{−1}, 𝔡) .

Ceci conserve le module ∑_{j} 𝔞_{j}A_{j} engendré par les colonnes de A (avec coefficients dans les idéaux correspondants), et remplace le couple (a, b) par le couple (0, 1). En procédant de cette façon de proche en proche, on démontre ainsi le théorème et l’algorithme suivant.

Théorème 3.8. (Forme Normale d’Hermite dans un anneau de Dedekind) Soient 𝔞_{j} une liste de k idéaux fractionnaires non nuls de R, et soit A = (a_{i,j}) une matrice n × k de rang n (donc telle que k ≥ n) à coefficients dans K. Soit A_{j} la j-ième colonne de A, et soit M le R-module engendré par les 𝔞_{j}A_{j}. Il existe k idéaux non nuls (𝔟_{j})_{1≤j≤k} et une matrice U = (u_{i,j}) de taille k × k satisfaisant les conditions suivantes. Posons 𝔞 = 𝔞_{1} ⋯ 𝔞_{k}, 𝔟 = 𝔟_{1} ⋯ 𝔟_{k}. Alors

(1) 𝔞 = det(U)𝔟.

(2) La matrice AU a la forme suivante :

AU = ( \begin{matrix}0 & 0 & … & 0 & 1 & ∗ & … & ∗ \\ 0 & 0 & … & 0 & 0 & 1 & … & ∗ \\ ⋮ & ⋮ & ... & ⋮ & ⋮ & ... & ... & ⋮ \\ 0 & 0 & … & 0 & 0 & … & 0 & 1 \end{matrix} )

où les k − n premières colonnes sont nulles.

(3) Si nous appelons ω_{j} les éléments correspondant aux colonnes non nulles de AU, et 𝔟′_{j} = 𝔟_{k−n+j} pour 1 ≤ j ≤ n, alors

M = 𝔟′_{1}ω_{1} ⊕ ⋯ ⊕ 𝔟′_{n}ω_{n} ,

en d’autres termes (ω_{j}, 𝔟′_{j}) est une pseudo-base de M.

(4) Les idéaux 𝔟′_{j} ci-dessus sont uniques, et la classe de Steinitz de M est la classe de ∏_{1≤j≤n} 𝔟′_{j}.

La formalisation de l’algorithme d’Hermite dans ℤ_{K} est la suivante.

Algorithme 3.9. (Algorithme d’Hermite dans ℤ_{K}). Etant donnés une matrice A = (a_{i,j}) de taille n × k et de rang n, ainsi que k idéaux fractionnaires 𝔞_{j} dans un corps de nombres K, cet algorithme calcule k idéaux 𝔟_{j} et une matrice U de taille k ×k telle que les conditions du théorème 3.8 soient réalisées. Nous appellerons A_{j} (resp. U_{j}) les colonnes de A (resp. de U).

1. [Initialisations] Poser i ← n, j ← k, et soit U la matrice identité d’ordre k.

2. [Vérifier si zéro] Poser m ← j, et tant que m ≥ 1 et a_{i,m} = 0, poser m ← m − 1. Si m = 0, la matrice A n’est pas de rang n, donc imprimer un message d’erreur et terminer l’algorithme. Sinon, si m < j, échanger A_{m} et A_{j}, 𝔞_{m} et 𝔞_{j}, et U_{m} et U_{j}.

3. [Mettre 1 sur la diagonale] Poser A_{j} ← A_{j}/a_{i,j}, U_{j} ← U_{j}/a_{i,j}, 𝔞_{j} ← a_{i,j}𝔞_{j} et poser m ← j. (Nous avons maintenant a_{i,j} = 1.)

4. [Boucle] Si m = 1, aller à 6. Sinon, poser m ← m − 1, et si a_{i,m} = 0, aller à 4.

5. [Bezout] (Ici a_{i,j} = 1 et a_{i,m} ≠ 0). En utilisant l’algorithme décrit dans le corollaire 3.5, poser 𝔡 = a_{i,m}𝔞_{m} + 𝔞_{j} et calculer u ∈ 𝔞_{m}𝔡^{−1} et v ∈ 𝔞_{j}𝔡^{−1} tels que a_{i,m}u + v = 1. Poser ensuite (A_{m}, A_{j}) ← (A_{m} − a_{i,m}A_{j}, uA_{m} + vA_{j}), (U_{m}, U_{j}) ← (U_{m} − a_{i,m}U_{j}, uU_{m} + vU_{j}) et (𝔞_{m}, 𝔞_{j}) ← (𝔞_{m}𝔞_{j}𝔡^{−1}, 𝔡). Enfin, aller à 4.

6. [Réductions finales pour la ligne i] Pour m = j+1, …, m = n, trouver q ∈ 𝔞_{m}𝔞_{j}^{−1} tel que a_{i,m} − q soit petit, et poser A_{m} ← A_{m} − qA_{j} et U_{m} ← U_{m} − qU_{j}.

7. [Terminé ?] Si i = 1, retourner la matrice U, la matrice A modifiée (c.a.d. AU avec les notations du théorème 3.8), et les idéaux modifiés 𝔞_{j} (c.a.d. 𝔟_{j} avec les notations du théorème 3.8) et terminer l’algorithme. Sinon, poser i ← i − 1, j ← j − 1 et revenir en 2.

Il resterait à expliquer ce qu’on entend dans l’étape 6 par a_{i,m} − q “petit”, mais toute définition est raisonnable. On peut d’ailleurs même se passer de faire ces réductions, au prix d’avoir des coefficients beaucoup plus grands.

Pour terminer, et comme il a déja été mentionné, je signale qu’il est facile de la même manière d’écrire un algorithme d’Hermite modulaire et un algorithme de Smith dans ℤ_{K}. Je réfère à [Coh2] pour les détails.

Bibliographie

[Bos-Poh] W. Bosma and M. Pohst, Computations with Finitely Generated Modules over Dedekind

Rings, Proceedings ISSAC’91 (1991), 151–156.

[Coh1] H. Cohen, A course in computational algebraic number theory, Graduate Texts in Maths, vol. 138, Springer-Verlag, 1993.

[Coh2] H. Cohen, Hermite and Smith Normal Form algorithms over Dedekind domains, submitted to Math. Comp..

[Haf-McCur] J. Hafner and K. McCurley, Asymptotically fast triangularization of matrices over

rings, SIAM J. Comput. 20 (1991), 1068–1083. [Hav-Maj] G. Havas and B. Majewski, Hermite Normal Form computation for integer matrices,

preprint.

[LLL] A.K. Lenstra, H.W. Lenstra and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), 515–534.

Laboratoire d’Algorithmique Arithmétique eXpérimentale, U.M.R. 9936 du C.N.R.S., Université Bordeaux I, 351 Cours de la Libération, 33405 TALENCE Cedex