L’ALGORITHME LLL SUR LES CORPS

DE NOMBRES ET APPLICATIONS

Henri Cohen et Huguette Napias

1. Introduction

La découverte de l’algorithme LLL en 1982 a été parmi les avancées algorithmiques les plus importantes de ces 20 dernières années. Cet algorithme a trouvé des applications dans des domaines extrêmement divers, souvent fort éloignés des mathématiques. L’une des raisons essentielles de son succès est qu’il permet d’approcher en temps polynomial la solution optimale de problèmes qui ne peut pas en général être trouvée en un temps raisonnable.

L’étude détaillée de l’algorithme montre que l’on travaille en fait sur des modules libres sur un anneau euclidien, qui possèdent en outre une structure d’espace euclidien (le mot euclidien n’ayant ici pas la même signification, bien que ce soit le même Euclide!). Dans le cas classique, on considère des réseaux M de dimension n, considérés comme plongés dans ℝ^{n} muni d’une forme quadratique définie positive. L’anneau euclidien est évidemment ℤ.

Il est tentant de vouloir généraliser ceci à d’autres modules. Citons deux applications immédiates parmi les nombreuses que l’on peut citer. La première application classique de LLL est la recherche de dépendances ℤ-linéaires entre nombres réels ou complexes. Par exemple, si l’on fournit le nombre

a = 5.841619252963778989528394936

à un LLL convenable, l’algorithme répond instantanément que a est racine de l’équation x^{4} − 36x^{2} + 64 = 0, et reconnait donc a = \sqrt{5} + \sqrt{13}. En remplacant l’anneau euclidien ℤ par l’anneau euclidien K[X] pour un corps K, on peut ainsi espérer obtenir un algorithme permettant de reconnaître des séries entières.

Comme deuxième application, citons l’algorithme POLRED expliqué par exemple dans [Coh-Dia]. Cet algorithme permet, en utilisant LLL, de trouver un “bon” polynôme pour définir un corps de nombres considéré comme extension absolue de ℚ. Il serait toutefois très utile de pouvoir disposer d’un tel algorithme pour une extension relative L/K de corps de nombres, car les calculs seraient beaucoup moins coûteux. La difficulté majeure provient ici du fait que les objets sont naturellement des ℤ_{K}-modules (où ℤ_{K} est l’anneau d’entiers de K), mais que ℤ_{K} n’est en général pas un anneau principal, et donc a fortiori pas un anneau euclidien.

Dans [Nap], le second auteur a montré comment on pouvait de manière relativement aisée, généraliser l’algorithme LLL au cas d’anneaux euclidiens autres que ℤ. Dans le présent article, nous montrons comment le généraliser quand on ne suppose même plus l’anneau de base euclidien ni même principal, en vue de généraliser l’algorithme POLRED ci-dessus. Nous nous plaçons donc dans le contexte des corps de nombres. Le plan de l’article est le suivant. Dans le §2, nous donnons une description détaillée du nouvel algorithme LLL. Cette description est largement inspirée de [Fie-Poh]. Dans le §3, nous donnons l’application à l’algorithme POLRED relatif. Enfin, dans le §4, nous donnons un exemple obtenu avec notre implémentation dans le système Pari.

2. L’algorithme LLL dans les corps de nombres

Soit K un corps de nombres de degré m sur ℚ, ayant r_{1} places réelles et 2r_{2} places complexes, avec r_{1} + 2r_{2} = m. Soit ℤ_{K} l’anneau des entiers de K, et soit M un ℤ_{K}-module sans-torsion de rang n. Un tel module possède une pseudo-base sur ℤ_{K} (voir [Coh2]), c’est à dire une famille (𝔞_{1}, b_{1}, …,𝔞_{n}, b_{n}), où les b_{i} sont des éléments de M ⊗ K et les 𝔞_{i} des idéaux fractionnaires de ℤ_{K}, tels que

M = ⨁_{1≤i≤n} 𝔞_{i}b_{i} .

Une telle pseudo-base n’est évidemment pas unique, et le but de l’algorithme LLL généralisé est de trouver une “bonne” base.

Les opérations élémentaires autorisées ne sont pas tout à fait du même type que dans le cas usuel, à cause de la présence des idéaux 𝔞_{i}. Plus précisément, si x et y sont des éléments d’une pseudo-base associés aux idéaux 𝔞 et 𝔟, et si on pose formellement

( \begin{matrix}x′ & y′ \\ 𝔠^{−1} & 𝔡^{−1} \end{matrix} ) = ( \begin{matrix}x & y \\ 𝔞^{−1} & 𝔟^{−1} \end{matrix} ) ( \begin{matrix}a & c \\ b & d \end{matrix} ) ,

alors nous pouvons remplacer (𝔞, x, 𝔟, y) par (𝔠, x′, 𝔡, y′) lorsque a ∈ 𝔞𝔠^{−1}, b ∈ 𝔟𝔠^{−1}, c ∈ 𝔞𝔡^{−1}, d ∈ 𝔟𝔡^{−1} et 𝔞𝔟 = (ad − bc)𝔠𝔡.

Dans [Coh2], nous donnons une généralisation de la forme normale d’Hermite (HNF) et de l’algorithme correspondant, au cas des pseudo-bases. Ceci a le grand avantage de donner une pseudo-base canonique d’un ℤ_{K}-module sans torsion M, et nous permet de travailler aisément avec de tels modules. (Nous donnons également une généralisation de la forme normale de Smith (SNF) et de l’algorithme correspondant, ce qui permet de travailler avec les modules de torsion.)

Notre but ici est toutefois différent. Nous voulons, non plus avoir une pseudobase canonique de M, mais plutôt une pseudo-base “petite” en un certain sens, ce qui conduit à vouloir généraliser l’algorithme LLL. Nous supposons connus l’algorithme LLL classique, tel qu’il est décrit par exemple dans [Coh].

Rappelons que cet algorithme commence par calculer une base orthogonale de Gram-Schmidt associée à la base initiale des b_{i}, en utilisant des constantes auxiliaires μ_{i,j} (qui mesurent les angles entre les b_{i}) et B_{i} (qui mesurent les normes des vecteurs de Gram associés aux b_{i}). Puis, l’algorithme modifie la base b_{i} pour se rapprocher de la base de Gram-Schmidt, d’une part en minimisant les μ_{i,j}, d’autre part en minimisant la croissance des B_{i} (ceci n’est qu’une description qualitative et approximative, et il faut bien sûr se référer à une description détaillée correcte).

Pour généraliser ceci, nous devons d’une part prendre en compte le fait que nos vecteurs b_{i} sont à coefficients dans un corps de nombres K (une fois choisie une K-base de M ⊗ K), et d’autre part le fait que nous n’avons pas vraiment une base, mais une pseudo-base, c’est à dire des idéaux 𝔞_{i}.

L’idée de Fieker et Pohst [Fie-Poh] est de remplacer les scalaires μ_{i,j} et B_{i} par des éléments de

E = ℝ^{r_{1}} × ℂ^{r_{2}} ,

où un élément de K est considéré comme un élément de E par son plongement canonique envoyant x sur le vecteur des (σ_{i}(x))_{1≤i≤r_{1}+r_{2}}.

L’espace E est un ℝ-espace vectoriel de dimension n, et c’est aussi une algèbre (avec multiplication composante par composante), avec l’involution induite par la conjugaison complexe. Noter aussi que nous avons deux fonctions importantes sur E qui sont d’une part la trace Tr définie par

Tr((x_{i})) = ∑_{1≤i≤r_{1}} x_{i} + ∑_{r_{1}+1≤i≤r_{1}+r_{2}}(x_{i} + \overline{x_{i}})

et la norme N définie par

N ((x_{i})) = ∏_{1≤i≤r_{1}} x_{i} ∏_{r_{1}+1≤i≤r_{1}+r_{2}}(x_{i}\overline{x_{i}})

toutes deux à valeurs dans ℝ.

Il est aussi nécessaire de remplacer les produits scalaires et formes quadratiques par produits scalaires et formes hermitiennes. En particulier, si x = (x_{j})_{1≤j≤m} et y = (y_{j})_{1≤j≤m} appartiennent à E^{m}, nous poserons

B(x, y) = ∑_{1≤j≤m} \overline{x_{j}}y_{j} ,

où le produit de \overline{x_{j}} et y_{j} se fait dans l’algèbre E. Ceci est à nouveau un élément de E, et B est une forme sesquilinéaire sur E^{m}.

Soit maintenant M un ℤ_{K}-module sans torsion de rang m muni d’une forme sesquilinéaire B à valeurs dans E. Nous pouvons si on le désire identifier M ⊗ K avec E^{m} en choisissant une K-base orthonormée.

Formellement, l’algorithme de réduction d’une pseudo-base de M s’écrit comme suit. Noter que la plupart des opérations à effectuer dans l’algorithme doivent être effectuées dans l’algèbre E.

Algorithme LLL relatif. Etant donnée une pseudo-base (𝔞_{i}, b_{i}) d’un ℤ_{K}-module de type fini sans torsion M et une forme sesquilinéaire B sur M à valeurs dans E comme ci-desus, cet algorithme calcule une nouvelle pseudo-base qui sera “réduite” pour B en un certain sens voisin du sens LLL habituel.

Étape 1. [Initialisation] Poser k ← 2, k_{max} ← 1, B_{1} ← B(b_{1}, b_{1}) et b_{1}^{∗} ← b_{1}.

Étape 2. [Gram-Schmidt incrémental] Si k ≤ k_{max}, aller à l’étape 3. Sinon, poser k_{max} ← k, b_{k}^{∗} ← b_{k} et pour j = 1 à j = k − 1 faire μ_{k,j} ← B(b_{j}^{∗}, b_{k})/B_{j}, b_{k}^{∗} ← b_{k}^{∗} − μ_{k,j}b_{j}^{∗}. Enfin, poser B_{k} ← B(b_{k}^{∗}, b_{k}^{∗}).

Étape 3. [Réduction préliminaire] Exécuter l’algorithme RED(k,k − 1) cidessous.

Étape 4. [Condition voisine de LLL] Si

Tr(B_{k} + \overline{μ_{k,k−1}}μ_{k,k−1}B_{k−1}) < \frac{3}{4} Tr(B_{k−1}) ,

executer l’algorithme ECH(k) ci-dessous, poser k ← max(2, k − 1) et retourner à l’étape 3.

Étape 5. [Réduction complète] Pour l = k − 2, ..., l = 1, exécuter l’algorithme RED(k,l) ci-dessous. Poser k ← k + 1.

Étape 6. [Terminé ?] Si k ≤ n, aller à l’étape 2, sinon sortir la nouvelle pseudo-base (𝔞_{i}, b_{i}) et terminer l’algorithme.

Les sous-algorithmes nécessaires sont les suivants.

Algorithme RED(k,l).

Étape 1. [Trouver un petit x] Trouver un x appartenant à l’idéal 𝔞_{l}𝔞_{k}^{−1} tel que Tr(\overline{(μ_{k,l} − x)}(μ_{k,l} − x)) soit minimal, ou du moins petit.

Étape 2. [Mise à jour] Si x = 0, terminer l’algorithme, sinon faire b_{k} ← b_{k} − xb_{l}, μ_{k,l} ← μ_{k,l} − x et pour i = 1 à i = l − 1 faire μ_{k,i} ← μ_{k,i} − xμ_{l,i} et terminer l’algorithme.

Algorithm ECH(k). Échanger b_{k} et b_{k−1}, 𝔞_{k} et 𝔞_{k−1}. Pour j = 1 à k − 2 échanger μ_{k,j} et μ_{k−1,j}. Puis, poser μ ← μ_{k,k−1}, B ← B_{k} + \overline{μ}μB_{k−1}, μ_{k,k−1} ← \overline{μ}B_{k−1}/B, 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−1}B_{k}/B et B_{k−1} ← B. Enfin, pour i = k + 1 à i = k_{max} faire t ← μ_{i,k}, μ_{i,k} ← μ_{i,k−1} − μt, μ_{i,k−1} ← t + μ_{k,k−1}μ_{i,k} et terminer l’algorithme.

Un certain nombre de remarques essentielles doivent être faites à propos de l’algorithme LLL présenté ci-dessus.

(1) Noter tout d’abord que les divisions par B_{j} dans l’algèbre E ont un sens, car il est facile de voir que les B_{j} sont inversibles dans E.

(2) La condition LLL a été remplacée par la condition

Tr(B_{k} + \overline{μ_{k,k−1}}μ_{k,k−1}B_{k−1}) < \frac{3}{4} Tr(B_{k−1}) ,

ce qui est effectivement une généralisation de la condition LLL habituelle. Toutefois, la canonicité qui était conservée grâce à l’utilisation de coefficients de Gram-Schmidt vectoriels (dans E) se trouve brisée, et cette condition n’est qu’une parmi plusieurs que l’on pourrait suggérer. On pourrait par exemple remplacer la trace par la norme.

(3) Dans cet algorithme, les idéaux 𝔞_{i} ne sont pas vraiment pris en compte (on est obligé d’en tenir compte dans l’algorithme RED simplement pour assurer de la légalité des opérations), et en particulier ils ne sont, ni utilisés dans la condition LLL, ni modifiés par l’algorithme (à part leur ordre bien sûr). On devrait donc modifier l’algorithme pour d’une part prendre en compte les idéaux 𝔞_{i} dans la condition LLL (ce qui est facile à faire, il suffit de conserver l’homogéneité, puisque seul le produit 𝔞_{i}b_{i} et non 𝔞_{i} et b_{i} séparément ont un sens), mais surtout pour permettre une modification des idéaux, en respectant les règles légales énoncées au début de ce paragraphe pour les opérations élémentaires. Nous ne savons pas pour l’instant comment réaliser celà de manière utile.

(4) L’étape 1 de l’algorithme RED est bien entendu délicate, et c’est pourquoi nous avons adopté une formulation approximative. Nous devons en un certain sens trouver un point d’un réseau (cette fois-ci au sens ordinaire, sur ℤ) le plus proche possible d’un point donné de l’espace ambiant. Ceci est bien sûr en général un problème trop difficile, mais une variante de l’algorithme LLL ordinaire permet de s’approcher raisonablement de la solution, d’autant plus que la dimension du réseau considéré est égale à [K : ℚ], donc petite en générale.

3. Application: L’algorithme POLRED relatif

Une première application de l’algorithme LLL relatif présenté ci-dessus est la possibilité de trouver des relations linéaires entre nombres complexes à coefficients dans un corps de nombres et plus seulement à coefficients dans ℚ. Par exemple, pour reprendre le nombre a = 5.841619252963778989528394936 donné au début, la méthode usuelle pour trouver des relations algébriques, mais utilisant l’algorithme LLL relatif, montre que a est racine du polynôme relatif

P (x) = x^{2} − 2x\sqrt{5} − 8 .

Toutefois, l’application principale dont nous souhaitons parler ici est la généralisation de l’algorithme POLRED de [Coh-Dia]. Rappelons que l’algorithme POL-RED a pour but de réduire les coefficients de polynômes définissant un corps de nombres. Plus précisément, il fonctionne de la manière suivante. Soit L un corps de nombres de degré m sur ℚ, défini par un polynôme unitaire irréductible P (X) ∈ ℤ[X], et soient (σ_{i})_{1≤i≤m} les m plongements de L dans ℂ. Si α est un entier algébrique appartenant à L, on pose

s(α) = ∑_{1≤i≤m} |σ_{i}(α)|^{2} .

Exprimant α sur une base d’entiers de L calculée une fois pour toutes, ceci définit une forme quadratique (non entière) appelée T_{2}, et en utilisant l’algorithme LLL nous pouvons calculer de petits vecteurs dans le réseau ℤ^{m} pour cette forme quadratique, et donc des entiers algébriques α tels que s(α) soit petit. Si de plus α est de degré exactement égal à m, on peut prendre le polynôme minimal de α comme polynôme de définition du corps L sur ℚ, et ses coefficients sont en général nettement plus petits que les coefficients du polynôme P initial.

Dans le cas relatif, nous procéderons de manière analogue. Soit K un corps de base de degré n sur ℚ, et L une extension de degré m de K défini par un polynôme irréductible unitaire relatif P (X) ∈ ℤ_{K}[X] (il est facile de se ramener à ce cas). Soient (σ_{i})_{1≤i≤m} les K-automorphismes de L, et (τ_{j})_{1≤j≤n} les plongements de K dans ℂ. Nous prolongerons les τ_{j} de manière arbitraire à la clôture galoisienne de L sur K, et nous noterons encore τ_{j} les prolongements. Les nm plongements de L dans ℂ sont alors les τ_{j} ∘ σ_{i}.

Si α est un entier algébrique de L, on aimerait poser à nouveau

s(α) = ∑_{1≤i≤m} |σ_{i}(α)|^{2} ∈ ℝ .

Toutefois, ceci ne prend pas en compte les τ_{j}. Il est donc beaucoup plus raisonnable de poser

s_{j}(α) = ∑_{1≤i≤m} |τ_{j}(σ_{i}(α))|^{2} ∈ ℝ et s(α) = (s_{j}(α))_{1≤j≤n} ∈ ℝ^{n} ,

puisque les τ_{j}(σ_{i}(α)) vont maintenant décrire tous les conjugués de α dans L. Noter que s_{j}(α) = s_{j+r_{2}}(α) pour j > r_{1}, et donc on peuit considérer s_{j} comme un élément de E. En écrivant α sur une pseudo-base d’entiers, ceci fournit donc une formme hermitienne sur ℤ_{L} à coefficients dans E, et nous pouvons donc appliquer l’algorithme LLL relatif présenté ci-dessus. Ceci conduit à l’algorithme POLRED relatif suivant.

Algorithme POLRED relatif. Etant donnés un corps de nombres K de degré n sur ℚ, une extension L de degré m de K donnée par un polynôme unitaire irréductible relatif P (X) ∈ ℤ_{K}[X], cet algorithme trouve des polynômes relatifs définissant la même extension L/K, mais dont les coefficients sont en général plus “petits”.

Étape 1. [Pseudo-base d’entiers] En utilisant l’algorithme Round 2 relatif décrit dans [CDO], calculer une pseudo-base d’entiers de L/K, c’est à dire une pseudo-base (𝔞_{i}, ω_{i}) tel que ℤ_{L} = ⨁ 𝔞_{i}ω_{i}.

Étape 2. [Matrice T2 relative] Calculer la matrice T_{2} ∈ M_{n}(E) de la forme sesquilinéaire induite sur ℤ_{L} par la forme hermitienne s(α) décrite ci-dessus, en exprimant α sur la pseudo-base d’entiers calculée à la première étape.

Étape 3. [LLL relatif] En utilisant l’algorithme LLL relatif décrit au paragraphe précédent, calculer des “petits” vecteurs pour la forme s, et les α ∈ ℤ_{L} correspondants.

Étape 4. [Terminer] Si, parmi les α trouvés il n’y en a aucun de degré relatif m = [L : K], imprimer un message d’erreur et terminer. Sinon, pour tous les α de degré relatif égal à m calculer le polynôme relatif minimal de α et sortir le polynôme dont les coefficients sont les plus petits, par exemple au sens de la norme L^{2} ou de la norme sup (on peut aussi sortir tous les polynômes de degré m obtenus), et terminer l’algorithme.

L’erreur qui peut se produire à l’étape 4 peut aussi exister dans le cas usuel, mais dans la pratique nous ne l’avons jamais rencontrée.

4. Exemple

Les algorithmes décrits ci-dessus ont été implémentés dans le système Pari, et ont des performances tout à fait correctes. Comme exemple tout à fait caractéristique de l’utilisation de l’algorithme POLRED relatif, nous décrivons un calcul qui a effectivement été utilisés dans [CDO2].

Soit K = ℚ(ζ) le corps des racines 8-ièmes de l’unité (où ζ est une racine primitive 8-ième de l’unité), et l’extension L/K défini par le polynôme

P (X) =X^{5} − 2X^{4} + (−ζ^{3} − ζ + 3)X^{3} + (17ζ^{3} + 17ζ − 2)X^{2}
+ (−22ζ^{3} − 22ζ + 48)X + (111ζ^{3} + 111ζ − 7) .

Ce polynôme est l’un de ceux que l’on obtient naturellement dans la recherche de l’équation d’une extention abélienne de K ramifiée seulement en un idéal premier au dessus de 11, en utilisant la théorie de Kummer.

Pour obtenir une équation réduite absolue, on pourrait calculer une équation absolue puis appliquer l’algorithme POLRED ordinaire. Comme expliqué ci-dessus, il est toutefois préférable (bien que non indispensable vu que les degrés sont petits) de procéder différemment. On applique d’abord l’algorithme POLRED relatif, ce qui fournit le nouveau polynôme relatif

Q(X) =X^{5} + (−2ζ^{3} − 2ζ + 1)X^{4} + (−7ζ^{3} − 7ζ − 8)X^{3}
+ (2ζ^{3} + 2ζ − 11)X^{2} − 13X + (−ζ^{3} − ζ − 15) ,

qui est visiblement plus simple que le polynôme initial, ce qu’on peut confirmer de diverses manières. On calcule maintenant un polynôme absolu correspondant (qu’il est inutile de donner ici, mais qui a des coefficients ayant 6 chiffres décimaux), puis on applique l’algorithme POLRED absolu (ou plus exactement une variante qui trouve un polynôme encore meilleur utilisant la même idée), pour obtenir finalement l’équation absolue

A(X) =X^{20} − 4X^{19} + 8X^{18} − 8X^{17} − X^{16} + 12X^{15} − 8X^{14}
− 16X^{13} + 43X^{12} − 44X^{11} + 24X^{10} − 12X^{9} + 24X^{8} − 44X^{7}
+ 48X^{6} − 36X^{5} + 21X^{4} − 12X^{3} + 8X^{2} − 4X + 1 ,

dont on constate que les coefficients sont très petits.

Le temps nécessaire à ce dernier algorithme POLRED absolu n’est pas du tout négligeable (une dizaine de minutes), mais aurait été supérieur d’environ 50% si l’on n’avait pas d’abord utilisé l’algorithme POLRED relatif, qui n’a nécessité qu’une trentaine de secondes. D’ailleurs, les améliorations de l’algorithme LLL relatif sur lequel cet algorithme est bâti, et qui ont été mentionnées au §2 ci-dessus, conduiraient probablement à un polynôme relatif encore meilleur que celui que nous avons trouvé. Noter que l’on peut pousser ce petit jeu encore plus loin. A partir du polynôme absolu A(X) obtenu ci-dessus, on peut calculer les polynômes relatifs correspondants, et on constate qu’ils sont encore plus simples que le polynôme relatif Q(X) que nous avons utilisé. L’un d’eux est par exemple

R(X) =X^{5} + (ζ^{3} − ζ^{2} − 1)X^{4} + (−ζ^{3} + ζ^{2} + ζ)X^{3}
+ (−ζ^{2} − 2ζ + 1)X^{2} + (ζ^{3} + ζ − 1)X − ζ^{3} .

Il serait intéressant de pouvoir obtenir ce polynôme directement par des moyens relatifs, et des recherches sont en cours sur ce problème, qui ne devrait pas être très difficile.

Bibliographie

[Coh] H. Cohen, A Course in Computational Algebraic Number Theory, Graduate Texts in Math., vol. 138, Springer-Verlag, 1993.

[Coh2] H. Cohen, Hermite and Smith Normal Form Algorithms over Dedekind Domains, Math. Comp., à paraître.

[Coh-Dia] H. Cohen et F. Diaz y Diaz, A polynomial reduction algorithm, Séminaire de théorie

des Nombres Bordeaux (Série 2) 3 (1991), 351–360.

[CDO] H. Cohen, F. Diaz y Diaz et M. Olivier, Algorithmic techniques for relative extensions of number fields, en préparation.

[CDO2] H. Cohen, F. Diaz y Diaz et M. Olivier, A table of totally complex number fields of small discriminant, en préparation.

[Fie-Poh] C. Fieker et M. Pohst, On Lattices over Number Fields, Lecture Notes in Computer

Science, vol. 1122, Springer-Verlag, 1996, pp. 133–139.

[Nap] H. Napias, A generalization of the LLL algorithm over Euclidean rings or orders (1996), Publication interne.