**Entrée** Un polynôme $F \in K[X]$ de degré $n \ge 1$.

**Sortie** La factorisation séparable de $F$.

1. Appeler l'Algorithme 18.1 pour obtenir l'ensemble $L = \{(G_1, 1, m_1), \dots, (G_r, 1, m_r)\}$ des facteurs séparables de $F$ contenant toutes les racines de $F$ de multiplicité non divisible par $p$.

2. Calculer $C = F/(G_1^{m_1} \cdots G_s^{m_s})$ et construire $\tilde{C}$ tel que $\tilde{C}(X^p) = C(X)$.

3. Appeler récursivement le présent algorithme pour obtenir la factorisation séparable

$$ \tilde{L} = \{(G_{r+1}, q_{r+1}, m_{r+1}), \dots, (G_s, q_s, m_s)\} \text{ de } \tilde{C}. $$

4. Renvoyer $\{(G_1, 1, m_1), \dots, (G_r, 1, m_r)\} \cup \{(G_{r+1}, pq_{r+1}, m_{r+1}), \dots, (G_s, pq_s, m_s)\}$.

**Algorithme 18.3** – Algorithme de Gianni et Trager.

Comme $F'_1 = 0$ nous obtenons

$$ F' = F_1 \sum_{i=1}^{s} m_i G'_i G_i^{m_i-1} \frac{F_0}{G_i^{m_i}}, $$

alors, à l'étape (2) de l'algorithme, nous avons $C = F_1 \prod_{i=1}^{s} G_i^{m_i-1}$, et $G = \prod_{i=1}^{s} G_i$. Dans la première étape de la boucle nous obtenons $P = \prod_{i=1, m_i \ge 2}^{s} G_i$, $C = F_1 \prod_{i=1, m_i \ge 2}^{s} G_i^{m_i-2}$, et $G/P$ correspond aux $G_i$ pour lesquels $m_i = 1$. À la deuxième étape de la boucle nous avons

$$ P = \prod_{i=1, m_i \ge 3}^{s} G_i, \quad C = F_1 \prod_{i=1, m_i \ge 3}^{s} G_i^{m_i-3}, $$

et $G/P$ correspond aux $G_i$ pour lesquels $m_i = 2$. La preuve s'achève ainsi par récurrence comme pour l'algorithme de Musser. ■

En conservant les notations de la preuve, notons $F_0$ le facteur de $F$ composé des racines de multiplicité qui ne sont pas multiples de $p$ et posons $F_1 = F/F_0$. En introduisant $\tilde{F}_1(X^p) = F_1(X)$, le degré de $\tilde{F}_1$ est au plus celui de $F$ divisé par $p$, et nous pouvons donc calculer récursivement la factorisation séparable de $\tilde{F}_1$. Cette approche conduit à un algorithme dû à Gianni et Trager, présenté dans l'Algorithme 18.3.

**Proposition 18.12** L'Algorithme 18.3 est correct. Si $K$ est un corps, alors son coût est borné par $O(nM(n) \log n)$.

*Démonstration.* Par construction, les racines de $C$ ont une multiplicité divisible par $p$ donc $\tilde{C}$ est bien défini à l'étape (2). Comme $\tilde{L}$ est la factorisation séparable de $\tilde{C}$, alors $\{(G_{r+1}, pq_{r+1}, m_{r+1}), \dots, (G_s, pq_s, m_s)\}$ est la factorisation séparable de $C$. Comme
le degré de Č est borné par $n/p$, et que le calcul de C demande $O(M(n) \log n)$ opérations dans $\mathbb{K}$ par la Proposition 5.5, le coût total est borné par

$$O\left(\sum_{i \ge 1} \frac{n}{p^i} M\left(\frac{n}{p^i}\right) \log \frac{n}{p^i}\right) \subseteq O(nM(n) \log n). \quad \blacksquare$$

## Algorithme de Lecerf

L'extension de l'algorithme de Yun pour effectuer la factorisation séparable conduit à un coût arithmétique quasi-linéaire. Cette fin de section est assez technique et peut être omise en première lecture. Le point de départ est le lemme suivant :

**Lemme 18.13** Supposons $p > 0$, et soit F un polynôme unitaire de $\mathbb{K}[X]$. Il existe des uniques polynômes unitaires $S_0$ et $S_1$ de $\mathbb{K}[X]$ avec les propriétés suivantes :
— les facteurs irréductibles de $S_0$ sont séparables de multiplicité au plus $p-1$,
— $F(X) = S_0(X)S_1(X^p)$.

*Démonstration.* Le polynôme $S_0$ est défini par sa factorisation en irréductibles :

$$\text{firr}(S_0) = \{(G, m \text{ mod } p) \mid (G, m) \in \text{firr}(F), G \text{ est séparable et } m \text{ mod } p \neq 0\}.$$

Un facteur irréductible $G$ de $F/S_0$ est soit inséparable soit de multiplicité $m$ dans $F$ divisible par $p$. Par conséquent $F/S_0 \in \mathbb{K}[X^p]$ et nous définissons $S_1(X^p) = F(X)/S_0(X)$. ■

**Exemple 18.5** Avec l'Exemple 18.3 nous avons $S_0 = (X+2)X^2$ et $S_1 = (X+1)(X+2)$.

**Exemple 18.6** Avec l'Exemple 18.4 nous avons $S_0 = X + 2T$ et $S_1 = (X^2 + T)(X + 2T^3)^2(X + 2T)^3$.

Pour calculer la factorisation séparable de F nous commençons par celle de $S_0$.

**Lemme 18.14** Si l'Algorithme 18.2 est utilisé en caractéristique non nulle $p$, alors il renvoie la factorisation sans carré de $S_0$ tel que défini dans le Lemme 18.13. De plus sa complexité arithmétique reste en $O(M(n) \log n)$.

*Démonstration.* À l'étape (2) de l'algorithme nous avons :

$$U = \text{pgcd}(S_0, S'_0)S_1(X^p), \quad V = \frac{S_0}{\text{pgcd}(S_0, S'_0)}, \quad W = \frac{S'_0}{\text{pgcd}(S_0, S'_0)}.$$

Nous avons les mêmes valeurs de $V$ et $W$ en appelant l'algorithme directement avec $S_0$. Ensuite, nous laissons le soin au lecteur de vérifier à titre d'exercice que l'algorithme de Yun renvoie bien la factorisation sans carré de $S_0$, qui coïncide par ailleurs avec la factorisation séparable. Finalement l'analyse de complexité reste inchangée. ■
**Entrée** $F \in \mathbb{K}[X]$ de degré $n$, $fsc(S_0)$ et $fsep(S_1)$.

**Sortie** $fsep(F)$.

1. Si $S_1 \in \mathbb{K}$ alors renvoyer $\{(G_1, 1, m_1), \dots, (G_r, 1, m_r)\}$. Sinon initialiser $L$ avec la liste vide.

2. Pour tout $i \in \{1, \dots, r\}$ faire :

a. pour tout $j \in \{1, \dots, s\}$, calculer
   $R_{i,j}(X) = \tilde{G}_i(X) \mod H_j(X^{q_j})$,
   où $\tilde{G}_i$ est le polynôme défini par $\tilde{G}(X^p) = G_i(X)^p$;

b. pour tout $j \in \{1, \dots, s\}$, calculer
   $S_{i,j}(X) = \text{pgcd}(R_{i,j}(X), H_j(X^{q_j}))$;

c. pour tout $j \in \{1, \dots, s\}$, calculer
   $T_{i,j}(X) = G_i(X) \mod S_{i,j}(X^p)$;

d. pour tout $j \in \{1, \dots, s\}$, calculer
   $U_{i,j}(X) = \text{pgcd}(T_{i,j}(X), S_{i,j}(X^p))$,
   et adjoindre $(U_{i,j}, 1, m_i + pq_j n_j)$ à $L$ si $\text{deg}(U_{i,j}) \ge 1$;

e. calculer $V_i(X) = \prod_{j=1}^{s} U_{i,j}(X)$;

f. calculer $U_{i,0}(X) = G_i(X)/V_i(X)$
   et adjoindre $(U_{i,0}, 1, m_i)$ à $L$ si $\text{deg}(U_{i,0}) \ge 1$.

3. Pour tout $j \in \{1, \dots, s\}$ faire :

a. calculer $W_j(X^{q_j}) = \prod_{i=1}^{r} S_{i,j}(X)^{q_j}$;

b. calculer $U_{0,j}(X) = H_j(X)/W_j(X)$
   et adjoindre $(U_{0,j}, pq_j n_j)$ à $L$ si $\text{deg}(U_{0,j}) \ge 1$.

4. Renvoyer $L$.

**Algorithme 18.4** – Algorithme rapide de fusion des factorisations séparables.

Pour obtenir la factorisation séparable de $F$, nous commençons par calculer $fsc(S_0)$ et $S_1$ par l'algorithme précédent. Ensuite nous calculons récursivement $fsep(S_1)$, pour finalement fusionner ces factorisations et obtenir $fsep(F)$. Expliquons maintenant comment cette fusion peut être réalisée rapidement. Si

$$fsc(S_0) = \{(G_1, m_1), \dots, (G_r, m_r)\}, \quad fsep(S_1) = \{(H_1, q_1, n_1), \dots, (H_s, q_s, n_s)\},$$

alors nous commençons par calculer tous les $U_{i,j} = \text{pgcd}(G_i, H_j(X^{pq_j}))$ pour $i \in \{1, \dots, r\}$ et $j \in \{1, \dots, s\}$. Nous verrons que $(U_{i,j}, 1, m_i + pq_j n_j)$ est un élément de $fsep(F)$ dès que $\text{deg}(U_{i,j}) \ge 1$.

**Lemme 18.15** L'Algorithme 18.4 est correct et utilise $O(M(n) \log n)$ opérations arithmétiques dans $\mathbb{K}$.

*Démonstration.* Nous devons vérifier que la liste $L$ renvoyée par l'algorithme satisfait les propriétés $(S_1)$ à $(S_5)$ de la Définition 18.6. Pour tout $i \in \{1, \dots, r\}$ et tout $j \in \{1, \dots, s\}$ nous avons

$$R_{i,j}(X^p) = G_i(X)^p \mod H_j(X^{pq_j}), \quad S_{i,j}(X^p) = \text{pgcd}(G_i(X)^p, H_j(X^{pq_j})),$$
et par conséquent

$$
\begin{align*}
U_{i,j}(X) = \text{pgcd}(G_i(X), S_{i,j}(X^p)) &= \text{pgcd}(G_i(X), \text{pgcd}(G_i(X)^p, H_j(X^{pq_j}))) \\
&= \text{pgcd}(G_i(X), H_j(X^{pq_j})).
\end{align*}
$$

À la fin de l'étape (2), pour tout $i \in \{1, \dots, r\}$, il est clair que $G_i = \prod_{j=0}^{s} U_{i,j}$, et que les $U_{i,j}$ sont séparables et premiers entre eux. Dans l'étape (3) nous avons

$$
S_{i,j}(X)^{q_j} = \text{pgcd}(\tilde{G}_i(X)^{q_j}, H_j(X^{q_j})^{q_j}) = \text{pgcd}(\tilde{G}_i(X)^{q_j}, H_j(X^{q_j}))
$$

puisque les $\tilde{G}_i$ sont séparables par le Lemme 18.9. Par conséquent les $U_{0,j}$ sont bien
définis et nous avons

$$
W_j(X^{pq_j}) = \prod_{i=1}^{r} S_{i,j}(X^p)^{q_j} = \prod_{i=1}^{r} \text{pgcd}(G_i(X)^{pq_j}, H_j(X^{pq_j})) = \prod_{i=1}^{r} U_{i,j}(X)^{pq_j}.
$$

Nous en déduisons que $H_j(X^{pq_j}) = U_{0,j}(X^{pq_j}) \prod_{i=1}^r U_{i,j}(X)^{pq_j}$ est vrai pour tout $j \in \{1, \dots, s\}$. Nous pouvons récrire F en :

$$
\begin{align*}
F(X) = S_0(X)S_1(X^p) &= \left( \prod_{i=1}^{r} \prod_{j=0}^{s} U_{i,j}(X)^{m_i} \right) \prod_{j=1}^{s} \left( U_{0,j}(X^{pq_j})^{n_j} \prod_{i=1}^{r} U_{i,j}(X)^{pq_j n_j} \right) \\
&= \left( \prod_{i=1}^{r} \prod_{j=1}^{s} U_{i,j}(X)^{m_i + pq_j n_j} \right) \left( \prod_{i=1}^{r} U_{i,0}(X)^{m_i} \right) \left( \prod_{j=1}^{s} U_{0,j}(X^{pq_j})^{n_j} \right).
\end{align*}
$$

La factorisation renvoyée dans L satisfait bien (S₁). Les autres propriétés sont immé-
diatement satisfaites par construction.

Si $p \ge n+1$ alors $S_1 \in \mathbb{K}$, et l'algorithme ne fait rien. Nous pouvons donc supposer
à partir de maintenant que $p \le n$. Le coût suivant est une conséquence directe de la
super-additivité de M, de l'inégalité $r \le p-1$, et de $\deg(S_0) + p \deg(S_1) = n$. L'étape (2.a)
calcule des puissances $p$-ièmes et des réductions simultanées, totalisant ainsi

$$
O\left( \sum_{i=1}^{r} \deg(G_i) \log p + \sum_{i=1}^{r} \left( M(\deg(S_1)) \log s + M(\max(\deg(G_i), \deg(S_1))) \right) \right)
$$
$$
\subseteq O(\deg(S_0) \log d + pM(S_1) \log d + M(\deg(S_0))) \subseteq O(M(n) \log n).
$$

Le coût total des pgcd dans les étapes (2.b) tombe dans

$$
O\left( \sum_{i=1}^{r} \sum_{j=1}^{s} M(\deg(H_j(X^{q_j}))) \log(\deg(H_j(X^{q_j}))) \right) \subseteq O(pM(\deg(S_1)) \log n) \subseteq O(M(n) \log n).
$$

Le coût total des réductions simultanées des étapes (2.c) tombe dans

$$
\begin{align*}
& O\left( \sum_{i=1}^{r} \left( M(\deg(G_i)) + M\left( p \sum_{j=1}^{s} \deg(S_{i,j}) \right) \log n \right) \right) \\
& \subseteq O(M(\deg(S_0)) + M(p \deg(S_1)) \log n) \subseteq O(M(n) \log n).
\end{align*}
$$
Le coût total des étapes (2.d) est borné par

$$O\left(\sum_{i=1}^{r} \sum_{j=1}^{s} M(p \deg(S_{i,j})) \log n\right) \subseteq O(M(n) \log n).$$

Les étapes (2.e) et (2.f) coûtent

$$O\left(\sum_{i=1}^{r} M(\deg(G_i)) \log n\right) \subseteq O(M(n) \log n).$$

Finalement le coût de l'étape (3) est au plus

$$O\left(\sum_{j=1}^{s} M(\deg(H_j(X^{q_j}))) \log n\right) \subseteq O(M(n) \log n). \quad \blacksquare$$

**Exemple 18.7** Avec l'Exemple 18.3 nous entrons dans l'Algorithme 18.4 avec

$$fsc(S_0) = \{(X + 2, 1), (X, 2)\}, \quad fsep(S_1) = \{((X + 1)(X + 2), 1, 1)\},$$

et obtenons les valeurs suivantes pour les $U_{i,j}$ :

<table><tr><td>$i \setminus j$</td><td>0</td><td>1</td></tr><tr><td>0</td><td></td><td>X + 1</td></tr><tr><td>1</td><td>1</td><td>X + 2</td></tr><tr><td>2</td><td>X</td><td>1</td></tr></table>

**Exemple 18.8** Avec l'Exemple 18.4 nous entrons dans l'Algorithme 18.4 avec

$$fsc(S_0) = \{(X + 2X, 1)\}, \quad fsc(S_1) = \{(X^2 + T, 1, 1), (X + 2T^3, 1, 2), (X + 2T^3, 3, 1)\},$$

et obtenons les valeurs suivantes pour les $U_{i,j}$ :

<table><tr><td>$i \setminus j$</td><td>0</td><td>1</td><td>2</td><td>3</td></tr><tr><td>0</td><td></td><td>X<sup>2</sup> + T</td><td>1</td><td>X + 2T<sup>3</sup></td></tr><tr><td>1</td><td>1</td><td>1</td><td>X + 2T</td><td>1</td></tr></table>

Finalement les résultats de cette section se résument comme suit :

**Théorème 18.16** La factorisation séparable d'un polynôme $F \in K[X]$ de degré $n$ peut être calculée au moyen de $O(M(n) \log n)$ opérations dans $K$.

*Démonstration.* La preuve est une conséquence directe des Lemmes 18.14 et 18.15, et de la borne $\sum_{k \ge 0} M(n/p^k) \log(n/p^k) \in O(M(n) \log n)$. ■
**Entrée** $(G, q) \in S \times B$.

**Sortie** $(H, h) \in K[X] \times B$ avec $H$ irréductible tel que $H^h = \Phi^{-1}(G, q)$.

1. Poser $\tilde{G} = G$ et $h = 1$.

2. Tant que $\tilde{G}(X^p)$ est une puissance $p$-ième et tant que $h < q$, remplacer $\tilde{G}$ par la racine $p$-ième de $\tilde{G}(X^p)$, et multiplier $h$ par $p$.

3. Renvoyer $(\tilde{G}(X^{q/h}), h)$.

Algorithme 18.5 – Calcul de l'inverse de la fonction de déflation.

**Entrée** Un polynôme $F \in K[]$ de degré $n \ge 1$.

**Sortie** $\text{firr}(F)$.

1. Calculer la factorisation séparable $fsep(F)$ de $F$.

2. Pour chaque $(G, q, m) \in fsep(F)$ calculer la factorisation irréductible de $G$.

3. Renvoyer

$$ \bigcup_{(G,q,m) \in fsep(F)} \{(H(X^{q/h}), hm) \mid H^h = \Phi^{-1}(\tilde{G}, q), \text{ pour chaque facteur irréductible } \tilde{G} \text{ de } G\} $$

Algorithme 18.6 – Réduction de la factorisation au cas séparable.

## 18.5 Réduction à la factorisation des polynômes séparables

Une fois la factorisation séparable effectuée nous verrons dans les chapitres suivants comme réaliser la factorisation irréductible de chacun des facteurs séparables dans les situations courantes. Nous finissons donc ce chapitre en expliquant comment le problème de la factorisation irréductible se réduit au cas des polynômes séparables.

Nous supposons que $K$ dispose d'une opération élémentaire permettant d'extraire une racine $p$-ième, et expliquons, dans l'Algorithme 18.5, comment implémenter l'inverse de la fonction de déflation $\Phi^{-1}$.

**Lemme 18.17** L'Algorithme 18.5 est correct et coûte $O(\deg(G)\log_p q)$ extractions de racines $p$-ièmes de $K$.

*Démonstration.* Les quantités $\tilde{G}$ est $h$ calculées par l'algorithme coïncident avec celles de la preuve de la Proposition 18.8. ■

Dans l'Algorithme 18.6 nous supposons disposer d'un algorithme de factorisation irréductible pour les polynômes séparables.

**Proposition 18.18** L'Algorithme 18.6 est correct. Il effectue des factorisations irreducibles de polynômes séparables de $K[X]$ dont la somme des degrés est au
plus *n*, ainsi que $O(M(n) \log n)$ opérations arithmétiques dans $\mathbb{K}$ et $O(n)$ extractions de racines *p*-ièmes dans $\mathbb{K}$.

*Démonstration.* Le coût de la première étape vient du Théorème 18.16, et le coût de la dernière étape du lemme précédent. ■

## Notes

Cette partie sur la factorisation des polynômes est adaptée des notes d'un cours donné à l'occasion des *Journées Nationales de Calcul Formel* en 2013 [Lec13].

La recherche des racines d'un polynôme à une variable et plus généralement la factorisation de tels polynômes en irréductibles trouve ses origines dans des temps très anciens des mathématiques. Un bref historique a été donné par von zur Gathen [Gat06]. Une présentation plus détaillée sur la factorisation des polynômes se trouve dans les sections « Notes » des chapitres de la partie III de son livre avec Gerhard [GG03]. Nous fournirons des éclairages historiques plus précis dans les chapitres suivants. Précisons néanmoins dès maintenant que la plupart des logiciels de calcul formel offrent des fonctions pour factoriser les entiers et les polynômes. Le logiciel MAGMA propose une implémentation efficace couvrant tous les cas habituels [Ste05]. Parmi les logiciels libres, de nombreux cas particuliers de factorisation sont disponibles dans NTL, PARI/GP, SAGE, SINGULAR, et plus récemment dans MATHEMAGIX.

Concernant la factorisation sans carré, l'algorithmé original de Musser remonte à 1971 [Mus71]. Son extension à la factorisation séparable est due à Gianni et Trager [GT96].

L'algorithmé de Yun [Yun76] a été étendu à la factorisation séparable par Lecerf [Lec08]. Par ailleurs, lorsque $\mathbb{K}$ est parfait, cette extension coïncide essentiellement avec l'algorithmé de factorisation sans carré proposé par Knuth [Knu97, Section 4.6.3, Exercise 36] et von zur Gathen et Gerhard [GG03, Exercise 14.30].

La preuve du Théorème 18.10 utilise l'existence de la factorisation irréductible. Pour une autre preuve constructive le lecteur pourra consulter celle du livre de Mines et alii [MRR88, Chapter VI, Theorem 6.3].

Le fait qu'il existe des corps effectifs de caractéristique non nulle tels que l'extraktion de racines *p*-ièmes ne soit pas calculable a été établi par Fröhlich et Shepherdson en 1956 [FS56, Section 7]. Une autre preuve est esquissée par von zur Gathen [Gat84, Remark 5.10].

## Bibliographie

* FS56 FRÖHLICH, A. et J. C. SHEPHERDSON (1956). « Effective procedures in field theory ». In : *Philosophical Transactions of the Royal Society A*, vol. 248, p. 407-432.

* Gat06 GATHEN, Joachim von zur (2006). « Who was who in polynomial factorization ». In : *ISSAC'06 : International Symposium on Symbolic and Algebraic Computation*. ACM Press, p. 1-2.

* Gat84 — (1984). « Hensel and Newton methods in valuation rings ». In : *Mathematics of Computation*, vol. 42, n°166, p. 637-661.
GG03 GATHEN, Joachim von zur et Jürgen GERHARD (2003). *Modern computer algebra*. 2ᵉ éd. Cambridge University Press.

GT96 GIANNI, P. et B. TRAGER (1996). « Square-free algorithms in positive characteristic ». In : *Applicable Algebra in Engineering, Communication and Computing*, vol. 7, n°1, p. 1–14.

Knu97 KNUTH, Donald E. (1997). *The art of computer programming*. 3ᵉ éd. Vol. 2 : Seminumerical Algorithms. Computer Science and Information Processing. Addison-Wesley Publishing Co.

Lec08 LECERF, Grégoire (2008). « Fast separable factorization and applications ». In : *Applicable Algebra in Engineering, Communication and Computing*, vol. 19, n°2, p. 135–160.

Lec13 — (2013). « Factorisation des polynômes à plusieurs variables (Cours no. II) ». In : *Journées nationales de calcul formel*. Éd. par G. CHÈZE, P. BOITO, C. PERNET et M. Safey el DIN. Vol. 3. Les cours du CIRM n°1. Cedram, p. 1–85. url : http://ccirm.cedram.org/ccirm-bin/fitem?id=CCIRM_2013_3_1_A2_0.

MRR88 MINES, Ray, Fred RICHMAN et Wim RUITENBURG (1988). *A course in constructive algebra*. Universitext. Springer-Verlag.

Mus71 MUSSER, David R. (1971). « Algorithms for polynomial factorization ». Thèse de doctorat. Univ. of Wisconsin : C.S. Department.

Ste05 STEEL, Allan (2005). « Conquering inseparability : primary decomposition and multivariate factorization over algebraic function fields of positive characteristic ». In : *Journal of Symbolic Computation*, vol. 40, n°3, p. 1053–1075.

Yun76 YUN, David Y. Y. (1976). « On square-free decomposition algorithms ». In : *SYMSAC'76 : ACM Symposium on Symbolic and Algebraic Computation*. Yorktown Heights, New York, United States : ACM, p. 26–35.
<figure><img src="image_52.png" /></figure>
# 19. Factorisation des polynômes à une variable sur un corps fini

## Résumé

Les algorithmes de factorisation des polynômes dépendent fortement du corps de leurs coefficients. Il est alors naturel de commencer avec le cas des corps finis. Dans ce chapitre nous présentons les algorithmes historiques qui sont encore très largement utilisés en pratique. Grâce aux résultats du chapitre précédent nous pouvons supposer que le polynôme à factoriser est séparable.

## 19.1 Corps finis, quelques rappels

Nous commençons par rappeler quelques résultats élémentaires de théorie des groupes dont nous avons besoin.

### Préliminaires : groupes commutatifs finis, arithmétique

Soit $G$ un groupe commutatif fini, noté multiplicativement (dans la suite, $G$ sera le groupe $F_q^* = F_q \setminus \{0\}$, $F_q$ étant un corps fini à $q$ éléments). L'ordre d'un élément $a$ de $G$ est le plus petit entier positif non nul $\gamma$ tel que $a^{\gamma} = 1$. Dans la suite nous utiliserons les résultats suivants :

**Lemme 19.1** L'ordre de tout élément divise le cardinal $card(G)$ de $G$, et donc $a^{card(G)} = 1$ pour tout $a$ de $G$.

*Démonstration.* L'ensemble des puissances de $a$ est un sous-groupe de $G$, de cardinal $\gamma$. On utilise alors le théorème de Lagrange, qui dit que le cardinal d'un sous-groupe de $G$ divise $card(G)$. ■
**Lemme 19.2** Soit $\gamma$ le ppcm des ordres des éléments de G. Alors, il existe un élément d'ordre $\gamma$; en particulier, $\gamma$ divise card(G).

**Lemme 19.3** Soient $p, m, n$ trois entiers positifs, avec $p \ge 2$. Si $p^m - 1$ divise $p^n - 1$ alors $m$ divise $n$.

*Démonstration.* En écrivant $n = qm+r$, avec $0 \le r < m$, nous avons $p^r = p^n \bmod (p^m-1)$, donc $p^r = 1 \bmod (p^m-1)$. Puisque $r < m$, nous déduisons que $p^r = 1$ et donc $r = 0$. ■

## Corps finis

L'exemple le plus simple de corps fini, noté $\mathbb{F}_p$, est un quotient de la forme $\mathbb{Z}/p\mathbb{Z}$, où $p$ est un nombre premier. Attendu qu'un tel corps ne contient pas de sous-corps propre, il est dit premier.

Soit ensuite P un polynôme irréductible de $\mathbb{F}_p[X]$, de degré $d$. Alors, $K = \mathbb{F}_p[X]/(P)$ est également un corps ; puisque $1, X, \dots, X^{d-1}$ forment une base de $K$ comme espace vectoriel sur $\mathbb{F}_p$, le cardinal de $K$ est $p^d$. Si nous prenons un autre polynôme irréductible P de degré $d$ nous obtenons un autre corps fini isomorphe à $K$. Un corps fini à $q = p^d$ éléments est noté $\mathbb{F}_q$. En admettant l'existence de polynômes irréductibles de n'importe quel degré à coefficients dans $\mathbb{F}_p$, il est aisé de construire n'importe quel corps fini de cardinal $p^d$ quelle que soit la valeur de $d$. La proposition suivante montre que $\mathbb{F}_q$ correspond à l'ensemble des racines de $X^q - X$. Le groupe multiplicatif des éléments non nuls de $\mathbb{F}_q$ est noté $\mathbb{F}_q^*$. Son cardinal est $q-1$.

**Proposition 19.4** Pout tout $a$ dans $\mathbb{F}_q^*$, nous avons $a^{q-1} = 1$ et $X^q - X = \prod_{a \in \mathbb{F}_q} (X-a)$.

*Démonstration.* Pour tout $a$ dans $\mathbb{F}_q^*$, le Lemme 19.1 nous donne $a^{q-1} = 1$. Par conséquent $a^q = a$ pout tout $a$ de $\mathbb{F}_q$, nul ou pas. Ceci montre que le polynôme $X^q - X$ s'annule sur tous les éléments de $\mathbb{F}_q$, donc $\prod_{a \in \mathbb{F}_q} (X-a)$ divise $X^q - X$. Comme les deux polynômes sont unitaires et de même degré, ils sont égaux. ■

**Corollaire 19.5** Pour tout $i = 1, \dots, p-1$, le coefficient binomial $\binom{p}{i}$ est divisible par $p$.

*Démonstration.* Rappelons que ce coefficient binomial est le coefficient de $X^i$ dans $(X+1)^p$. La proposition précédente entraîne les égalités

$$ 
\begin{aligned}
X^p - X &= \prod_{a \in \mathbb{F}_p} (X-a) = \prod_{a \in \mathbb{F}_p} (X-a+1) \\
&= \prod_{a \in \mathbb{F}_p} ((X+1)-a) = (X+1)^p - (X+1).
\end{aligned}
$$

On en déduit que $(X+1)^p = X^p + 1$, qui est ce que l'on voulait montrer. ■

Le corollaire suivant est, d'une manière ou d'une autre, à la base de la plupart des résultats « arithmétiques » sur les corps finis.
**Corollaire 19.6** Soit F un polynôme quelconque dans $\mathbb{F}_q[X]$ et soit A le quotient $\mathbb{F}_q[X]/(F)$ (qui n'est pas nécessairement un corps). L'application, dite de Frobenius,

$$ \phi_F: \begin{array}{ccc} A & \to & A \\ a & \mapsto & a^q \end{array} $$

est $\mathbb{F}_q$-linéaire.

*Démonstration.* Soient $\lambda$ dans $\mathbb{F}_q$ et $a, b$ dans A. L'égalité $\phi_F(\lambda a) = \lambda \phi(a)$ est une conséquence de la Proposition 19.4, appliquée à $\mathbb{F}_q$. L'égalité $\phi_F(a+b) = \phi_F(a) + \phi_F(b)$ est une conséquence du corollaire précédent, en développant le produit $(a+b)^q$. ■

Voyons quelques conséquences de ce corollaire.

**Proposition 19.7** Pour tous $c_0, \dots, c_n$ dans $\mathbb{F}_q$, nous avons l'égalité suivante :

$$ \left( \sum_{i=0}^{n} c_i X^i \right)^q = \sum_{i=0}^{n} c_i X^{iq}. $$

*Démonstration.* Il s'agit d'une conséquence facile de la Proposition 19.4 et du Corollaire 19.5. ■

**Proposition 19.8** Pour tout $e \ge 1$, le polynôme $X^{q^e} - X$ est le produit des polynômes unitaires et irréductibles de $\mathbb{F}_q[X]$ dont le degré divise $e$.

*Démonstration.* Soit F un polynôme irréductible de $\mathbb{F}_q[X]$ de degré $n$ divisant $e$, et soit $K$ le quotient $\mathbb{F}_q[X]/(F)$. Soit ensuite $x$ la classe de X dans $K$; la Proposition 19.4 appliquée à $x$ montre que $x^{q^n-1} = 1$ donc $x^{q^n} = x$, d'où $x^{q^e} = x$. Par conséquent F divise $X^{q^e} - X$.

Réciproquement, soit F un facteur irréductible de degré $n$ de $X^{q^e} - X$; il faut montrer que $n$ divise $e$. Soit $K$ le quotient $\mathbb{F}_q[X]/(F)$ et soit $x$ l'image de X dans $K$. Puisque $F(x) = 0$, alors $x^{q^e} - x$ est nul. Pour tous $\lambda_i$ dans $\mathbb{F}_q$, nous avons alors les égalités suivantes :

$$ \left( \sum_i \lambda_i x^i \right)^{q^e} = \sum_i \lambda_i (x^i)^{q^e} = \sum_i \lambda_i (x^{q^e})^i = \sum_i \lambda_i x^i, $$

la première égalité s'obtenant en appliquant $n$ fois le Corollaire 19.6. Donc tout élément de $K$ est racine de $X^{q^e} - X$, de sorte que tout élément non nul de $K$ est racine de $X^{q^e-1} - 1$.

Soit maintenant $\gamma$ l'exposant du groupe $K \setminus \{0\}$, c'est-à-dire le ppcm des ordres de ses éléments; d'après le Lemme 19.2, $\gamma$ divise card($K \setminus \{0\}$) = $q^n - 1$. Par ailleurs, par définition, tout élément non nul de $K$ annule $X^\gamma - 1$, ce qui implique $\gamma \ge q^n - 1$, et donc $\gamma = q^n - 1$. Le Lemme 19.2 montre ensuite qu'il existe un élément $a$ d'ordre $q^n - 1$.
dans $K \setminus \{0\}$. De $a^{q^e-1} = 1$, on déduit que $q^n - 1$ divise $q^e - 1$. Le Lemme 19.3 permet alors de conclure que $n$ divise $e$.

À ce stade, on sait donc que les facteurs irréductibles de $X^{q^e} - X$ sont exactement les polynômes irréductibles de degré $n$, et a ses coefficients dans le corps fini $\mathbb{F}_q$, avec $q = p^d$. Nous noterons $F_1, \dots, F_r$ les facteurs irréductibles unitaires de $F$, que nous cherchons à calculer, de sorte que $F = F_1 \cdots F_r$.

## 19.2 Algorithme de Berlekamp

Nous commençons par présenter des algorithmes de factorisation, attribués à Berlekamp. À partir de maintenant, le polynôme $F$ à factoriser est supposé unitaire, séparable, de degré $n$, et a ses coefficients dans le corps fini $\mathbb{F}_q$, avec $q = p^d$. Nous noterons $F_1, \dots, F_r$ les facteurs irréductibles unitaires de $F$, que nous cherchons à calculer, de sorte que $F = F_1 \cdots F_r$.

### Réduction à l'algèbre linéaire

En vertu du Corollaire 19.6, l'application

$$ \begin{array}{rcl} \psi_F : & \mathbb{F}_q[X]/(F) & \rightarrow \mathbb{F}_q[X]/(F) \\ & G & \mapsto G^q - G \end{array} $$

est une application $\mathbb{F}_q$-linéaire. L'étude du noyau de $\psi_F$ va permettre de factoriser $F$, à partir de la proposition suivante :

**Proposition 19.9** Un polynôme $G$ de degré au plus $n-1$ est dans le noyau de $\psi_F$ si, et seulement si, $G$ est une constante modulo chaque $F_i$.

*Démonstration.* Par la Proposition 19.4, le polynôme $X^q - X$ se factorise dans $\mathbb{F}_q$, et donc dans $\mathbb{F}_q[X]/(F_i)$, sous la forme $\prod_{a \in \mathbb{F}_q} (X - a)$. Puisque $\mathbb{F}_q[X]/(F_i)$ est un corps contenant $\mathbb{F}_q$, un élément $b \in \mathbb{F}_q[X]/(F_i)$ est une racine de $X^q - X$ si et seulement s'il annule un des facteurs $X - a$, donc si, et seulement si, $a \in \mathbb{F}_q$. ■

En notant $\hat{F}_i = F/F_i$, nous pouvons maintenant observer que les

$$ B_i = (\hat{F}_i F'_i / F') \mod F $$

pour $i$ de 1 à $r$ satisfont la propriété suivante : $B_i \mod F_j$ vaut 1 si $j = i$ et 0 sinon. Il s'ensuit que les $B_i$ forment une base du noyau de $\psi_F$. Un polynôme $G$ dans le noyau de $\psi_F$ est donc nécessairement une combinaison linéaire sur $\mathbb{F}_q$ de la forme $G = \sum_{i=1}^n b_i B_i$. La proposition précédente donne déjà un moyen de calculer le nombre $r$ de facteurs irréductibles de $F$. La proposition suivante donne une méthode pour en déduire un scindage non trivial de $F$.

**Proposition 19.10** Si $G$ est non constant dans le noyau de $\psi_F$, alors les constantes $G \mod F_i$ se sont pas toutes identiques.
**Entrée** F séparable de degré $n$ dans $\mathbb{F}_q[X]$.

**Sortie** Un facteur non trivial de F si F n'est pas irréductible.

1. Calculer la matrice de l'application $\psi_F$.

2. Si le rang de $\psi_F$ est $n-1$ alors renvoyer le fait que F est irréductible.

3. Choisir un polynôme $G$ de degré au plus $n-1$ et non constant dans le noyau de $\psi_F$.

4. Calculer les pgcd$(F, G-a)$ pour toutes les valeurs de $a$ dans $\mathbb{F}_q$, jusqu'à trouver un scindage non trivial de F.

**Algorithme 19.1** – Algorithme déterministe de Berlekamp.

*Démonstration.* Puisque tous les $F_i$ sont distincts et irréductibles, par le théorème des restes chinois, nous avons un isomorphisme

$$ \mathbb{F}_q[X]/(F) = \mathbb{F}_q[X]/(F_1) \times \cdots \times \mathbb{F}_q[X]/(F_r), $$

donné par

$$ G \mod F \mapsto (G \mod F_1, \dots, G \mod F_r). $$

Les $F_i$ étant irréductibles, chaque $\mathbb{F}_q[X]/(F_i)$ est un corps. Dans la représentation « produit de corps », l'application $\psi_F$ s'écrit bien sûr :

$$ (G_1, \dots, G_r) \mapsto (G_1^q - G_1 \mod F_1, \dots, G_r^q - G_r \mod F_r). $$

Si tous les $G_i = G \mod F_i$ sont les mêmes, alors nécessairement $G = G_i$ pout tout $i$, car le degré de $G$ est plus petit que $F$. En particulier, $G$ devrait être constant, ce qui est contraire à nos hypothèses. ■

## Algorithme déterministe

La clé de l'algorithme déterministe de Berlekamp réside dans ce résultat :

**Proposition 19.11** Soit $G$ comme dans la proposition précédente. Il existe $a$ dans $\mathbb{F}_q$ tel que $\text{pgcd}(F, G-a)$ est un diviseur non trivial de $F$.

*Démonstration.* Pour $a$ quelconque dans $\mathbb{F}_q$, nous avons l'égalité $\text{pgcd}(F, G-a) = \prod_i F_i$, où le produit est pris sur tous les $F_i$ tels que $F_i$ divise $G-a$, c'est-à-dire tels que $G \mod F_i = a$. Puisqu'il existe au moins deux valeurs distinctes pour les $G \mod F_i$ et que chacune d'entre elles donne un diviseur de $F$, ces diviseurs sont stricts. ■

Dans la suite de ce chapitre nous notons $\theta > 2$ un exposant réalisable pour la multipli-cation de matrices sur $\mathbb{F}_q$, tel que défini dans le Chapitre 8.

**Proposition 19.12** L'Algorithme 19.1 calcule un facteur non trivial de F au moyen d'au plus $O(n^\theta + (q+n)M(n)\log n)$ opérations arithmétiques dans $\mathbb{F}_q$.
Démonstration. Le premier pas consiste à calculer la matrice de l'application $\psi_F$ dans la base $1, X, \dots, X^{n-1}$. On commence par calculer $X^q \mod F$ : cela demande $O(\log q)$ opérations modulo F, soit $O(M(n) \log q)$ opérations dans $\mathbb{F}_q$. Ensuite, il faut calculer $(X^2)^p = (X^p)^2, (X^3)^p = (X^p)^3, \dots$, ce qui se fait en $n$ multiplications modulo F, soit $O(nM(n))$ opérations en tout.

L'algèbre linéaire coûte $O(n^\theta)$. Une fois obtenu un vecteur du noyau, chaque essai de pgcd coûte $O(M(n) \log n)$ opérations, et il faut en faire au plus $q$. ■

Pour trouver la factorisation complète, il suffit d'itérer le procédé, ce qui entraîne a priori un surcoût de $n$. En fait, il n'y a pas besoin de refaire de l'algèbre linéaire, mais seulement de parcourir tous les vecteurs d'une base du noyau de $\psi_F$, de sorte que le coût total de la factorisation est

$$O(n^{\theta} + qnM(n) \log n)$$

opérations de $\mathbb{F}_q$. Nous avons alors montré le résultat suivant :

**Proposition 19.13** Un polynôme F séparable de $\mathbb{F}_q[X]$ de degré $n$ peut être factorisé en effectuant au plus $O(n^\theta + qnM(n) \log n)$ opérations de $\mathbb{F}_q$.

La complexité de cet algorithme est linéaire en $q$, ce qui le rend rapidement impracticable, dès lors que $q$ atteint quelques milliers. Par ailleurs, supposer F séparable n'est pas restrictif ici puisque les techniques du chapitre précédent permettent de se ramener facilement à ce cas.

À l'heure actuelle, on ne connaît pas d'algorithme de factorisation déterministe de complexité polynomiale, c'est-à-dire en $n$ et $\log q$. Nous présenterons dans la suite des algorithmes probabilistes de coûts moyens polynomiaux.

## Algorithme probabiliste

L'algorithme probabiliste de Berlekamp repose essentiellement sur les même ingrédients que la version déterministe précédente. Supposons $p$ impair, c'est-à-dire autre que 2. L'entier $q-1$ est alors divisible par 2 et la puissance $(q-1)/2$ d'un élément de $\mathbb{F}_q$ vaut soit $-1$ soit 1. Sur l'ensemble des éléments non nuls il y a autant de telles puissances valant $-1$ que 1. Donc si $G$ est pris comme une combinaison linéaire non nulle des vecteurs d'une base fixe du noyau de $\psi_F$, alors on peut attendre que

$$G^{(q-1)/2} = \sum_{i=1}^{r} b_i^{(q-1)/2} B_i^{(q-1)/2}$$

ait quelques possibles valeurs $b_i^{(q-1)/2}$ qui valent 0, et la plupart des autres qui valent $-1$ ou $1$ à peu près en même proportion. Du coup, il est possible que $\text{pgcd}(G, F)$ soit un facteur non trivial de F, mais en général ce n'est pas le cas et on examine $\text{pgcd}(G^{(q-1)/2} - 1, F)$. Ce dernier polynôme est souvent un facteur non trivial de F contenant une quantité proche de $r/2$ facteurs irréductibles en moyenne. Nous formaliserons davantage cette description de l'algorithme dans les paragraphes suivants. Lorsque $p=2$, l'entier $q-1$ n'est pas divisible par 2 et la technique que nous venons
**Entrée** $F \in \mathbb{F}_q[x]$ séparable de degré $n$, et une base $G_1, \dots, G_r$ du noyau de l'endomorphisme de Frobenius $\psi_F$.

**Sortie** Les facteurs irréductibles $F_1, \dots, F_r$ de F.

1. Si $r=1$ alors renvoyer F.

2. Choisir des éléments $g_1, \dots, g_r$ dans $\mathbb{F}_q$ à l'aide d'un générateur aléatoire, et calculer $G = g_1 G_1 + \dots + g_r G_r$.

3. Si $H_1 = \text{pgcd}(F, G)$ n'est pas constant alors aller à l'étape (6).

4. Calculer $H = G^{\frac{q-1}{2}} - 1 \text{ mod } F \text{ si } p \text{ est impair,}$
   et $H = \text{Tr}_d(G) \text{ mod } F \text{ si } p = 2$.

5. Si $H_1 = \text{pgcd}(F, H)$ est constant alors retourner à l'étape (2).

6. Calculer $H_2 = F/H_1$.

7. Calculer une base $G_{1,1}, \dots, G_{r_1,1}$ des
   $(G_i F' \text{ mod } F)/(H'_1 H_2) \text{ mod } H_1 \text{ pour } i \in \{1, \dots, r\}$.

8. Calculer une base $G_{1,2}, \dots, G_{r_2,2}$ des
   $((G_i F' \text{ mod } F)/(H_1 H'_2) \text{ mod } H_2 \text{ pour } i \in \{1, \dots, r\})$.

9. Renvoyer la réunion des facteurs obtenus par les appels récursifs avec $H_1, G_{1,1}, \dots, G_{r_1,1}$, d'une part, puis $H_2, G_{1,2}, \dots, G_{r_2,2}$ d'autre part.

Algorithme 19.2 – Deuxième partie de l’algorithme probabiliste de Berlekamp.

d'ébaucher ne s'applique plus. Il est alors d'usage de faire appel à la construction
suivante un peu plus coûteuse en calculs :

**Définition 19.1** Si $p = 2$, le polynôme de la $d$-ième trace sur $\mathbb{F}_2$ est $\text{Tr}_d(X) = X^{2^{d-1}} + X^{2^{d-2}} + \dots + X^4 + X^2 + X + 1 \in \mathbb{F}_{2d}[X]$.

**Lemme 19.14** Tout $a \in \mathbb{F}_{2^d}$ vérifie $\text{Tr}_d(a) \in \mathbb{F}_2$ et $\text{card}(\text{Tr}_d^{-1}(0)) = \text{card}(\text{Tr}_d^{-1}(1)) = 2^{d-1}$.

*Démonstration.* Puisque $X^{2^d} + X = \text{Tr}_d^2(X) + \text{Tr}_d(X) = \text{Tr}_d(X)(\text{Tr}_d(X) + 1)$ nous avons bien $\text{Tr}_d(a) \in \mathbb{F}_2$. Nous obtenons ainsi le fait que $\text{Tr}_d$ a toutes ses $2^{d-1}$ racines dans $\mathbb{F}_{2^d}$. ■

**Exercice 19.1** Si $p = 2$, si F est un polynôme de degré $n$ dans $\mathbb{F}_q[X]$, et si G est un polynôme de degré au plus $n-1$, montrer que $\text{Tr}_d(G) \text{ mod } F$ peut se calculer au moyen de $dM(n)$ opérations dans $\mathbb{K}$. ■

La première partie de l’algorithme probabiliste de Berlekamp est le calcul d’une base $G_1, \dots, G_r$ du noyau de $\psi_F$. La deuxième partie, résumée dans l’Algorithme 19.2, consiste à calculer tous les facteurs irréductibles de F à partir de cette base. Rappelons que le coût moyen d’un algorithme pour une entrée donnée est la moyenne des coûts sur toutes les exécutions possibles.
**Proposition 19.15** L'Algorithme 19.2 est correct et nécessite au plus

$$O(n^{\theta} \log r + (r + \log n + \log q)M(n) \log r)$$

opérations dans $\mathbb{F}_q$ en moyenne.

*Démonstration.* Si $pgcd(F, G)$ à l'étape (2) n'est pas constant alors il s'agit d'un facteur non trivial de F. Si $p$ est impair, les facteurs irréductibles de $H_1$ à l'étape (5) sont les $F_i$ tels que $G^{(q-1)/2} \mod F_i$ vaut 1.

Nous avons vu que chaque $r$-uplet $(g_1, \dots, g_r)$ est en bijection avec un $r$-uplet $(b_1, \dots, b_r)$ de $\mathbb{F}_q^r$ satisfaisant $G = \sum_{i=1}^r b_i B_i$. Sur les $q^r$ valeurs possibles du $r$-uplet $(b_1, \dots, b_r), (q-1)^r$ d'entre elles sont dans $(\mathbb{F}_q^*)^r$. Donc pour $q^r-1-(q-1)^r$ un scindage non trivial de F est trouvé dès l'étape (3). Si $p$ est impair, les $r$-uplets $(b_1^{(q-1)/2}, \dots, b_r^{(q-1)/2})$ sont équi-distribués dans $\{1, 1\}^r$. Seuls les deux tels uplets constants sur les $2^r$ possibles ne conduisent pas à un scindage non trivial de F à l'étape (5). La proportion d'uplets qui ne conduisent pas à un scindage non trivial est donc

$$\frac{1 + (q-1)^r/2^{r-1}}{q^r} \le 1/2.$$

Le nombre moyen d'uplets à essayer est donc borné par une constante. Autrement dit, l'algorithme arrive rapidement à l'étape (6) en moyenne.

À partir de l'identité

$$(B_i F' \mod F)/(H_1'H_2) \equiv (F/F_i)/(H_1'H_2) \equiv (H_1/F_i)H_1' \mod H_1,$$

nous voyons que $(B_i F' \mod F)/(H_1'H_2)$ est dans le noyau de $\psi_{H_1}$ pour tout $i \in \{1, \dots, r\}$, et que les $G_{i,1}$ forment bien un ensemble générateur du noyau de $\psi_{H_1}$. Il en va de même concernant $H_2$. Par conséquent l'algorithme fonctionne correctement. Nous laissons le soin au lecteur de traiter le cas particulier où $p=2$.

L'étape (2) coûte $O(rn)$ opérations. L'étape (4) coûte $O(M(n) \log q)$ opérations. Les étapes (3), (5), et (6) utilisent $O(M(n) \log n)$ opérations. Ensuite, les étapes (7) et (8) nécessitent $O((r + \log n)M(n) + n^\theta)$ opérations en faisant appel au Théorème 8.4. Le nombre d'opérations total en moyenne avant d'entrer dans les appels récursifs est donc $O(n^\theta + (r + \log n + \log q)M(n))$.

Considérons maintenant l'arbre des appels récursifs. Au début, à la racine, le degré du polynôme en entrée est $n$. Si $r \ge 2$, à la profondeur 1 de cet arbre, il y a deux nœuds correspondant à $H_1$ et $H_2$ trouvés par l'algorithme. La somme des degrés de $H_1$ et $H_2$ est $n$. Il est aisé de constater qu'à une profondeur donnée la somme des degrés de tous les polynômes à factoriser est toujours au plus $n$. De part la super-additivité de M, le coût total des calculs propres à tous les nœuds d'une même profondeur est donc $O(n^\theta + (r + \log n + \log q)M(n))$ opérations dans $\mathbb{F}_q$. Il reste à montrer que la profondeur moyenne de l'arbre des appels récursifs est $O(\log r)$ pour conclure l'analyse de complexité.

Considérons le cas où $p$ est impair. Notons $\ell$ la variable aléatoire représentant la profondeur de l'arbre, et $E(\ell)$ la moyenne des profondeurs. Si $P(\ell \ge h)$ représente la
**Entrée** F séparable dans $\mathbb{F}_q[X]$.

**Sortie** La factorisation irréductible de F.

1. Calculer, dans la base $1, X, \dots, X^{n-1}$, la matrice de l'endomorpisme de Frobenius $\psi_F$.

2. Calculer une base $G_1, \dots, G_r$ du noyau de $\psi_F$.

3. Appeler l'Algorithme 19.2 avec $F, G_1, \dots, G_r$ et renvoyer la factorisation obtenue.

**Algorithme 19.3** – Algorithme probabiliste de Berlekamp.

probabilité que la profondeur soit au moins $h$, alors

$$E(\ell) = \sum_h h(\mathcal{P}(\ell \le h) - \mathcal{P}(\ell \le h + 1)) = \sum_h \mathcal{P}(\ell \ge h).$$

La probabilité que deux facteurs $i < j$ qui sont dans le même nœud à la profondeur $h-1$ le reste à la profondeur $h$ est $1/q^2+1/2$. Elle correspond aux possibilités suivantes pour $(b_i, b_j) : (0,0), (b_i, b_j) \in (\mathbb{F}_q^*)^2$ avec $b_i^{(q-1)/2} = b_j^{(q-1)/2}$. Par conséquent, la probabilité que deux facteurs $i < j$ soient dans le même nœud jusqu'à la profondeur $h$ est $(1/q^2+1/2)^h$. En prenant la somme de toutes ces probabilités sur toutes les paires $i < j$, on déduit que la probabilité $\mathcal{P}(\ell \ge h)$ que tous les facteurs de F n'aient pas été découvertes à la profondeur $h-1$ est au plus $r^2(1/q^2+1/2)^{h-1} \le r^2(3/4)^{h-1}$. Finalement nous déduisons la borne souhaitée :

$$\sum_h \mathcal{P}(\ell \le h) \le \sum_{h \le (2 \log h)/\log(3/4)} \mathcal{P}(\ell \le h) + \sum_{h > (2 \log h)/\log(3/4)} \mathcal{P}(\ell \le h) = O(\log r).$$

À nouveau, nous laissons l'étude du cas $p = 2$ en exercice.

<figure><img src="image_53.png" /></figure>

Nous obtenons finalement une version probabiliste de l'algorithme de Berlekamp dans l'Algorithme 19.3.

**Proposition 19.16** L'Algorithme 19.3 est correct et utilise en moyenne

$$O(n^{\theta} \log n + (n + \log q)M(n) \log n)$$

opérations dans $\mathbb{F}_q$.

*Démonstration.* Le fait que l'algorithme est correct provient de la Proposition 19.15. Le coût de la première étape est dans $O((n + \log q)M(n))$. L'étape (2) effectue $O(n^\theta)$ opérations par le Théorème 8.4. Le reste du coût provient essentiellement de la proposition précédente.

<figure><img src="image_54.png" /></figure>

## 19.3 Algorithme de Cantor et Zassenhaus

Une composante commune à de nombreux algorithmes de factorisation sur les corps finis est la suite des itérés de Frobenius $(\Phi_i)_{i \ge 0}$, relative à F définie par $\Phi_i =$
**Entrée** F dans $\mathbb{F}_q[X]$ de degré $n$.

**Sortie** La factorisation $E_1, \dots, E_n$ par degrés des facteurs irréductibles de F.

1. Calculer $\Phi_0, \dots, \Phi_n$.

2. Pour chaque $i$ de 1 à $n$, calculer $E_i = \text{pgcd}(\Phi_i - X, F)$ puis remplacer F par $F/E_i$.

3. Renvoyer $E_1, \dots, E_n$.

**Algorithme 19.4** – Algorithme de factorisation par degrés.

$X^{q^i}$ mod F. D'une façon naïve, les $n+1$ premiers itérés $\Phi_0, \dots, \Phi_n$ peuvent être calculés en utilisant $O(nM(n)\log q)$ opérations dans $\mathbb{F}_q$.

La dépendance du coût du calcul des itérés de Frobenius peut être diminuée en considérant l'opération de composition modulaire définie comme le calcul de $G \circ H$ mod F pour G et H deux polynômes de degré au plus $n-1$. Nous pouvons calculer $\Phi_1$ en $O(M(n)\log q)$ opérations puis obtenir $\Phi_{i+1}$ comme $\Phi_1 \circ \Phi_i$ mod F. Avec cette idée, pour calculer les $n+1$ premiers itérés, il existe une technique spécifique exploitant l'évaluation et interpolation rapide d'un polynôme en plusieurs points du Chapitre 5, et donnant le résultat suivant :

**Proposition 19.17** Avec les notations précédentes, une fois $\Phi_1$ connu, les polynômes $\Phi_0, \dots, \Phi_l$, pour $l \le n$, peuvent être calculés avec $O(M(n)^2 \log n \log l)$ opérations dans $\mathbb{F}_q$.

*Démonstration.* L'évaluation de $\Phi_i$ en $\Phi_1, \dots, \Phi_i$ mod F fournit les polynômes $\Phi_{i+1}, \dots, \Phi_{2i}$. Le coût total découle alors de la Proposition 5.6. ■

L'algorithme de Cantor et Zassenhaus comporte deux étapes. La première consiste à décomposer F en un produit de polynômes $\prod_{i \ge 1} E_i$ où chaque $E_i$ ne comporte que des facteurs irréductibles de degré exactement $i$. Nous parlons alors de factorisation par degrés des facteurs. La deuxième étape consiste à factoriser individuellement chaque $E_i$ en irréductibles.

**Proposition 19.18** L'Algorithme 19.4 est correct et nécessite

$$O(M(n)(M(n)\log^2 n + \log q))$$

opérations dans $\mathbb{F}_q$.

*Démonstration.* La formule utilisée pour calculer $E_i$ repose sur la Proposition 19.8. Le coût total provient directement de la proposition précédente. ■

Notons que l'algorithme précédent ne fait pas intervenir de valeurs aléatoires. L'étape suivante consiste à supposer que F est le produit de $r$ polynômes irréductibles de degré exactement $n/r$.
**Entrée** F séparable de degré *n* ayant tous ses facteurs irréductibles de degré *n/r*.

**Sortie** La factorisation irréductible $F_1, \dots, F_r$ de F.

1. Si $r = 1$ alors renvoyer F.

2. Répéter :

a. choisir un polynôme $G$ de degré au plus $n-1$ d'une façon aléatoire;

b. calculer $H_1 = \text{pgcd}(F, G)$. Si $H_1$ n'est pas constant alors aller à l'étape (3);

c. calculer $H = G^{\frac{q^{n/r}-1}{2}} \bmod F$ si $p$ est impair et $H = \text{Tr}_{kn/r}(G) \bmod F$ si $p=2$;

d. calculer $H_1 = \text{pgcd}(F, H-1)$;

e. si $H_1$ n'est pas constant alors aller à l'étape (3).

3. Calculer $H_2 = F/H_1$ et appeler récursivement la fonction sur $H_1$ et $H_2$ et renvoyer la réunion des facteurs.

Algorithme 19.5 – Algorithme de factorisation en équi-degré.

**Proposition 19.19** L'Algorithme 19.5 est correct et effectue

$$O(nM(n) \log q \log n)$$

opérations dans $\mathbb{F}_q$ en moyenne. Ce coût tombe dans

$$O(M(n)^2 \log^3 n + M(n) \log q \log n)$$

lorsque $p$ est impair.

*Démonstration.* En notant $\hat{F}_i = F/F_i$, nous avons précédemment observé que les $B_i = (\hat{F}_i F'_i / F') \bmod F$ pour $i$ de 1 à $r$ satisfont la propriété suivante : $B_i \bmod F_j$ vaut 1 si $j = i$ et 0 sinon.

Si $G$ est un polynôme de degré au plus $n-1$, il s'écrit d'une unique façon sous la forme $\sum_{i=1}^{r} C_i(X)B_i(X)$ avec $C_i(X) \in \mathbb{F}_q[X]$ de degré au plus $n/r-1$, par le théorème des restes chinois. Du coup $G^{(q^{n/r}-1)/2} \equiv C_i^{(q^{n/r}-1)/2} \bmod F_i$ vaut assez rarement 0, et plus fréquemment soit $-1$ soit 1 dans la même proportion. Donc $H_1$ définit bien un scindage non trivial de $F$ en général. Le résultat renvoyé par l'algorithme est donc correct. Nous laissons le soin au lecteur d'adapter la preuve de l'algorithme probabiliste de Berlekamp pour prouver que la profondeur moyenne des appels récursifs est dans $O(\log n)$.

Le coût du calcul de $H$ à l'étape (2) peut se faire en $O(nM(n) \log q)$. Les autres opérations totalisent un coût dans $O(M(n) \log n)$. Lorsque $p$ est impair il est intéressant de procéder comme suit. En notant $m = n/r$ et $\alpha = H \bmod F$, comme

$$\frac{q^m - 1}{2} = (q^{m-1} + q^{m-2} + \cdots + q + 1) \frac{q-1}{2},$$
nous pouvons calculer $\alpha^{\frac{q^{m}-1}{2}} = (\alpha^{q^{m-1}} \cdots \alpha^{q}\alpha)^{\frac{m-1}{2}}$ grâce à la proposition 19.17. ■

Nous arrivons au résultat principal de cette section :

**Théorème 19.20** Un polynôme de degré $n$ dans $\mathbb{F}_q[x]$ peut être factorisé avec un nombre moyen d'opérations dans $\mathbb{F}_q$ dans $\tilde{O}(n^2 \log q)$. Ce coût tombe dans $\tilde{O}(n^2 + n \log q)$ si $p$ est impair.

*Démonstration.* Il s'agit d'une conséquence des Propositions 19.18 et 19.19, en utilisant une fonction de multiplication $M(n)$ dans $\tilde{O}(n)$. ■

## Notes

La présentation choisie ici est inspirée du Chapitre 14 du livre de von zur Gathen et Gerhard [GG03]. Le calcul des itérés de Frobenius constitue une brique importante en ce qui concerne les performances pratiques. Les algorithmes décrits dans ce chapitre sont essentiellement ceux utilisés en pratique à ce jour. Ils peuvent être encore un peu améliorés et adaptés pour la recherche des racines, pour tester l'irréductibilité, ou bien encore pour construire des polynômes irréductibles de degré donné. Les analyses détaillées des aspects probabilistes ont d'abord été effectuées par Flajolet et Steyaert [FS82], puis complétées par Flajolet, Gourdon, et Panario [FGP01]. Comme autres livres sur les corps finis et leurs applications, le lecteur pourra être intéressé par consulter celui de Mullen et Panario [MP13], ou bien celui de Shoup [Sho09].

Les premières techniques connues de factorisation des polynômes à coefficients dans un corps fini remontent aux travaux de Gauss en 1798, Galois en 1830, et Arwins en 1918. Les premiers algorithmes performants ont été formalisés par Berlekamp [Ber67; Ber70], Zassenhaus [Zas69], puis Cantor et Zassenhaus [CZ81]. Ils regroupent les principales idées mathématiques que nous avons présentées ici.

En 1998, Kaltofen et Shoup [KS98] ont relié le problème de factorisation à celui de la composition modulaire, et ont obtenu une borne de complexité en $O(d^{1,815} \log q)$, en terme du nombre d'opérations effectuées dans $\mathbb{F}_q$. Sur un corps fini, Kedlaya et Umans ont ensuite conçu un algorithme de composition modulaire ayant un coût binaire quasi-linéaire [KU08], permettant de déduire un algorithme de factorisation sur $\mathbb{F}_q[X]$ ayant un coût binaire moyen dans $(d^{1,5} + d \log q)^{1+o(1)} \log q$, ce qui représente la meilleure borne de complexité asymptotique connue à ce jour. Malheureusement cette approche ne semble pas plus efficace que l'algorithme de Cantor et Zassenhaus pour les tailles de problèmes que l'on peut traiter avec les ordinateurs actuels.

La conception d'algorithmes déterministes en temps polynomial est toujours un sujet de recherche actif. Un algorithme de coût sous-exponentiel a été conçu par Evdokimov en 1994 [Evd94]. Des solutions partielles sont données dans des cas particuliers, selon les propriétés du polynômes ou bien du corps fini, dans les travaux de Moenck [Moe77], Camion [Cam83], Schoof [Sch85], von zur Gathen [Gat87], Mignotte et Schnorr [MS88], Rónyai [Rón89; Rón92], Shoup [Sho90; Sho91b], Huang [Hua91], Žrałek [Žra10], Grenet, van der Hoeven et Lecerf [GHL15a; GHL15b].
Bibliographie

Ber67 BERLEKAMP, E. R. (1967). « Factoring polynomials over finite fields ». In : *Bell System Technical Journal*, vol. 46, p. 1853-1859.

Ber70 — (1970). « Factoring polynomials over large finite fields ». In : *Mathematics of Computation*, vol. 24, p. 713-735.

Cam83 CAMION, Paul (1983). « A deterministic algorithm for factorizing polynomials of $F_q[X]$ ». In : *Combinatorial mathematics (Marseille-Luminy, 1981)*. Vol. 75. North-Holland Math. Stud. North-Holland, Amsterdam, p. 149-157.

CZ81 CANTOR, David G. et Hans ZASSENHAUS (1981). « A new algorithm for factoring polynomials over finite fields ». In : *Mathematics of Computation*, vol. 36, n°154, p. 587-592.

Evd94 EVDOKIMOV, Sergei (1994). « Factorization of polynomials over finite fields in subexponential time under GRH ». In : *Algorithmic number theory (Ithaca, NY, 1994)*. Vol. 877. Lecture Notes in Computer Science. Springer-Verlag, p. 209-219.

FGP01 FLAJOLET, P., X. GOURDON et D. PANARIO (2001). « The complete analysis of a polynomial factorization algorithm over finite fields ». In : *Journal of Algorithms*, vol. 40, n°1, p. 37-81.

FS82 FLAJOLET, Philippe et Jean-Marc STEYAERT (1982). « A branching process arising in dynamic hashing, trie searching and polynomial factorization ». In : *Automata, Languages and Programming*. Éd. par M. NIELSEN et E. SCHMIDT. Vol. 140. Lecture Notes in Computer Science. Springer-Verlag, p. 239-251.

Gat87 GATHEN, Joachim von zur (1987). « Factoring polynomials and primitive elements for special primes ». In : *Theoretical Computer Science*, vol. 52, n°1-2, p. 77-89.

GG03 GATHEN, Joachim von zur et Jürgen GERHARD (2003). *Modern computer algebra*. 2e éd. Cambridge University Press.

GHL15a GRENET, Bruno, Joris van der HOEVEN et Grégoire LECERF (2015). « Deterministic root finding over finite fields using Graeffe transforms ». In : *Applicable Algebra in Engineering, Communication and Computing*, vol. 27, n°3, p. 237-257.

GHL15b — (2015). « Randomized root finding over finite FFT-fields using tangent Graeffe transforms ». In : *ISSAC'15 : International Symposium on Symbolic and Algebraic Computation*. Éd. par D. ROBERTZ. ACM Press, p. 197-204.

Hua91 HUANG, Ming-Deh A. (1991). « Generalized Riemann hypothesis and factoring polynomials over finite fields ». In : *Journal of Algorithms*, vol. 12, n°3, p. 464-481.

KS98 KALTOFEN, Erich et Victor SHOUP (1998). « Subquadratic-time factoring of polynomials over finite fields ». In : *Mathematics of Computation*, vol. 67, n°223, p. 1179-1197.

KU08 KEDLAYA, Kiran S. et Christopher UMANAS (2008). « Fast modular composition in any characteristic ». In : *FOCS'08 : IEEE Conference on Foundations of Computer Science*. Washington, DC, USA : IEEE Computer Society, p. 146-155.
Moe77 MOENCK, Robert T. (1977). « On the efficiency of algorithms for polynomial factoring ». In : Mathematics of Computation, vol. 31, p. 235-250.

MP13 MULLEN, Gary L. et Daniel PANARIO (2013). *Handbook of finite fields*. Discrete Mathematics and Its Applications. Chapman et Hall/CRC.

MS88 MIGNOTTE, Maurice et Claus SCHNORR (1988). « Calcul déterministe des racines d'un polynôme dans un corps fini ». In : *Comptes Rendus des Séances de l'Académie des Sciences. Série I. Mathématique*, vol. 306, n°12, p. 467-472.

Rón89 RÓNYAI, L. (1989). « Factoring polynomials modulo special primes ». In : *Combinatorica. An International Journal on Combinatorics and the Theory of Computing*, vol. 9, n°2, p. 199-206.

Rón92 RÓNYAI, Lajos (1992). « Galois groups and factoring polynomials over finite fields ». In : *SIAM Journal on Discrete Mathematics*, vol. 5, n°3, p. 345-365.

Sch85 SCHOOF, René (1985). « Elliptic curves over finite fields and the computation of square roots mod $p$ ». In : *Mathematics of Computation*, vol. 44, n°170, p. 483-494.

Sho09 SHOUP, Victor (2009). *A computational introduction to number theory and algebra*. 2e éd. Cambridge University Press.

Sho90 — (1990). « On the deterministic complexity of factoring polynomials over finite fields ». In : *Information Processing Letters*, vol. 33, n°5, p. 261-267.

Sho91b — (1991). « A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic ». In : *ISSAC'91 : International Symposium on Symbolic and Algebraic Computation*. Éd. par S. M. WATT. ACM Press, p. 14-21.

Zas69 ZASSENHAUS, Hans (1969). « On Hensel factorization I ». In : *Journal of Number Theory*, vol. 1, n°1, p. 291-311.

Źra10 ŹRAŁEK, Bartosz (2010). « Using partial smoothness of $p-1$ for factoring polynomials modulo $p$ ». In : *Mathematics of Computation*, vol. 79, p. 2353-2359.
# 20. Réduction de réseaux et algorithme LLL

## Résumé

La recherche de vecteurs courts dans un réseau est la clé de voûte des algorithmes modernes de factorisation des polynômes à coefficients rationnels en temps polynomial. Et plus généralement la réduction des réseaux joue désormais un rôle majeur dans de nombreuses applications. Nous consacrons ce chapitre à l'algorithme classique LLL, nommé d'après les initiales de ses concepteurs A. Lenstra, H. Lenstra et L. Lovász.

## 20.1 Réseaux et vecteurs courts

On appelle réseau de $\mathbb{Z}^n$ un $\mathbb{Z}$-module $\sum_{i=1}^n \mathbb{Z}v_i$ engendré par des vecteurs $v_i$ linéairement indépendants sur $\mathbb{Z}$. Il n'est habituellement pas requis que le nombre de tels générateurs corresponde à la dimension $n$. Néanmoins, ce cas particulier étant suffisant pour les applications de cet ouvrage, nous n'aborderons pas le cas général.

Ce chapitre est consacré au problème du calcul de vecteurs « courts » dans un réseau donné : par exemple, le réseau engendré par les vecteurs (6,4) et (8,4) contient le vecteur plus court (2,0), comme illustré dans la Figure 20.1. Ici, court s'entend pour la norme euclidienne définie par $||x|| = (x_1^2 + \dots + x_n^2)^{1/2}$, pour $x \in \mathbb{R}^n$.

La recherche d'un vecteur de norme minimale dans un réseau donné s'avère être un problème difficile, et plus précisément NP-difficile. Il est donc naturel de relâcher la contrainte de minimalité et de considérer le problème approché à un facteur près. Malheureusement, en tolérant un facteur constant tel que $\sqrt{2}$, cette recherche reste NP-difficile. Le problème devient polynomial dès qu'on autorise le facteur d'approximation à croître suffisamment avec la dimension $n$ du réseau.

Ce chapitre est consacré à l'algorithme LLL qui, pour une base $v_1, \dots, v_n$ d'un réseau L, calcule un vecteur $u$ approximant les plus courts vecteurs du réseau à un
<figure><img src="image_55.png" /><figcaption>FIGURE 20.1 – Réseau engendré par les vecteurs (6, 4) et (8, 4).</figcaption></figure>

facteur au plus $2^{(n-1)/2}$.

**Théorème 20.1** Donnée une base $v_1, \dots, v_n$ d'un réseau $L \subseteq \mathbb{Z}^n$, on peut calculer un vecteur $u$ de ce réseau satisfaisant

$$ \|u\| \le 2^{(n-1)/2} \min\{\|v\| \mid v \in L, v \ne 0\}, $$

en $\tilde{O}(n^5 \log^2 A)$ opérations binaires, où $A = \max_{1 \le i \le n} \|v_i\|$.

L'utilisation de l'algorithme LLL à la factorisation des polynômes à coefficients rationnels fera l'objet du chapitre suivant. Mentionnons ici d'autres applications de nature historique :

- la mise en évidence de la faiblesse de générateurs pseudo-aléatoires;

- le cassage d'un crypto-système basé sur le problème du sac-à-dos;

- la recherche de dépendances linéaires entre nombres donnés par des approximations numériques.

Dans les paragraphes suivants nous détaillons ces deux dernières applications d'une façon informelle.

## Cassage du crypto-système de Merkle et Hellman

Merkle et Hellman ont proposé en 1978 un crypto-système basé sur le problème du sac-à-dos. Ce crypto-système devait nécessiter des calculs moins lourds que le désormais célèbre système RSA.

L'idée de Merkle et Hellman est la suivante. Bob se dote d'une clé secrète constituée d'une famille d'entiers positifs $b_1, \dots, b_n$, telle que chaque $b_i$ soit supérieur à la somme des précédents, d'un multiplicateur $c$, et d'un autre entier $m > b_1 + \dots + b_n$. Il rend public les restes positifs $a_i$ de $cb_i$ modulo $m$, pour chaque $1 \le i \le n$. Quand Alice veut lui envoyer le message constitué de la suite de bits $(x_1, \dots, x_n)$, elle construit la somme $s = x_1a_1 + \dots + x_na_n$ qui constitue le message chiffré. Bob n'a plus qu'à multiplier par l'inverse de $c$ modulo $m$ pour obtenir $x_1b_1 + \dots + x_nb_n$, et en déduire les $x_i$ pour $i$ décroissant de $n$ à 1.

Le problème sur lequel s'appuie ce crypto-système, celui du sac-à-dos, consiste
précisément à décider l'existence des $x_i \in \{0,1\}$ tels que $s = x_1a_1 + \cdots + x_na_n$. Ce problème est NP-complet en l'absence d'hypothèse sur la famille des $a_i$. Mais dans le cas présent, l'origine des $a_i$ crée une faiblesse cryptographique. Considérons les vecteurs $(0,...,0,1,0,...,0,-a_i) \in \mathbb{Z}^{n+1}$, où 1 est en i-ième position, pour $i \in \{1,...,n\}$, ainsi que le vecteur $(0,...,0,s)$. Tous ces vecteurs sont « longs », puisque de norme de l'ordre de $m$, mais le réseau qu'ils engendrent contient le vecteur $(x_1,...,x_n,0)$, lequel est manifestement très court. Pour des valeurs pratiques de $n$, l'algorithme LLL permet donc de déchiffrer les messages assez rapidement.

## Relations de dépendance entre constantes numériques

Étant donnés $n$ nombres réels non nuls, $r_1,...,r_n$, une relation de dépendance linéaire à coefficients entiers entre ces réels est une relation de la forme

$$c_1 r_1 + \cdots + c_n r_n = 0$$

pour des coefficients $c_i$ entiers non tous nuls. Lorsqu'on se donne une approximation rationnelle de chaque réel $r_i$, ou mieux, la possibilité d'obtenir autant de chiffres décimaux que souhaité, la recherche des vecteurs courts dans un réseau permet la détermination de relations de dépendance linéaire entre les $r_i$. Pour cela, on considère les combinaisons linéaires à coefficients entiers des vecteurs lignes de la matrice

$$V = \begin{pmatrix} 1 & 0 & \cdots & 0 & a_1 \\ 0 & 1 & \cdots & 0 & a_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & a_{n-1} \\ 0 & 0 & \cdots & 0 & a_n \end{pmatrix},$$

où chaque $a_i$ est une troncature entière de $Nr_i$ pour un grand entier $N$ (par exemple, $N$ est une grande puissance de 10). Un vecteur court est alors de la forme

$$u = (c_1, \dots, c_{n-1}, c_1 a_1 + \dots + c_n a_n) \approx (c_1, \dots, c_{n-1}, N(c_1 r_1 + \dots + c_n r_n)).$$

En particulier,

$$|c_1 r_1 + \dots + c_n r_n| \approx |N^{-1}(c_1 a_1 + \dots + c_n a_n)| \le N^{-1} \|u\|$$

se doit d'être petit, ce qui fait de

$$c_1 r_1 + \cdots + c_n r_n = 0$$

un bon candidat pour une relation de dépendance entre les $r_i$. Bien qu'un tel argument ne constitue pas une preuve, la preuve formelle de relation entre constantes a dans un bon nombre de cas été grandement facilitée une fois que la bonne relation a pu être découverte expérimentalement par cette méthode.

Donnons un exemple. Disons que des arguments théoriques donnent la certitude que le nombre

$$\alpha = \int_{0}^{\infty} \frac{\sqrt{x} \ln^5 x}{(1-x)^5} dx$$
peut se représenter comme l'évaluation en $\pi$ d'une fonction polynomiale à coefficients rationnels. Il s'agit de trouver une dépendance linéaire entre

$$1, \pi, \dots, \pi^d, \alpha$$

pour un degré de polynôme $d$ à déterminer. Tout système de calcul formel généraliste connaît des approximations pour $\pi$ et permet de calculer aisément une approximation numérique de $\alpha$. On prend donc par exemple $a_1 = N = 10^{20}$, $a_2 = 314159265358979323846 \approx N\pi$, ..., $a_7 = 96138919357530443703022 \approx N\pi^6$, $a_{10} = -1669947371922907049619 \approx N\alpha$ pour construire la matrice V. Les normes des vecteurs lignes de cette matrice sont toutes supérieures à $N = 10^{20}$. Par l'algorithme LLL, on trouve une base du même réseau de vecteurs, dont le premier vecteur ligne,

$$u = (c_1, \dots, c_{n-1}, c_1 a_1 + \dots + c_n a_n) = (0, 0, -120, 0, -140, 0, 15, 66),$$

est de norme inférieure à 200, tous les autres vecteurs de base étant de norme supérieure à 380. Il est aisé de déduire $c_n = -24$, en soustrayant $c_1 a_1 + \dots + c_{n-1} a_{n-1}$ à la dernière coordonnée de $u$ et en divisant par $a_n$, d'où la relation linéaire

$$\alpha = \int_{0}^{\infty} \frac{\sqrt{x} \ln^5 x}{(1-x)^5} dx = \frac{5\pi^2}{24}(3\pi^4 - 28\pi^2 - 24),$$

que l'on peut ensuite prouver être exacte.

## Polynôme minimal de nombres algébriques

Donnons nous une approximation numérique d'un nombre réel $r$ qu'on a de bonnes raisons de penser être une racine d'un polynôme $P$ de degré $d$ à coefficients rationnels. La détermination heuristique de $P$ peut se voir comme la recherche d'une relation de dépendance linéaire sur des approximations numériques rationnelles de

$$1, r, \dots, r^d.$$

Dès lors qu'on dispose d'une borne supérieure sur le degré $d$ de $P$, on peut donc employer la méthode précédente. Par exemple, soit à déterminer si

$$r \approx 0,26625264629019611453024776557584454817650128610395\dots$$

est algébrique. En testant les relations jusqu'à $d = 6$ et pour $N = 10^{20}$, on trouve le vecteur court

$$u = (1, 0, 0, -54, 0, 0, -8),$$

de norme inférieure à 60, tous les autres vecteurs calculés étant de normes supérieures à 250. On en déduit alors $c_7 = 54$, ce qui conduit au polynôme $P(X) = 54X^6 - 54X^3 + 1$.

## 20.2 Le procédé d'orthogonalisation de Gram-Schmidt

L'algorithme LLL exploite le procédé d'orthogonalisation de Gram-Schmidt qui, partant d'une base $v_1, \dots, v_n$ d'un espace vectoriel sur $\mathbb{Q}$, calcule une base orthogonale
$v_1^*,...,v_n^*$ du même espace vectoriel par la méthode décrite dans les paragraphes suivants.

Le contexte de cette méthode est celui de l'espace vectoriel $\mathbb{Q}^n$ muni du produit scalaire euclidien $(x,y) \mapsto (x|y) = x_1y_1 + \cdots + x_ny_n$ qui a servi à définir la norme euclidienne par $\|x\|^2 = (x|x)$. Rappelons que les vecteurs $x$ et $y$ sont dits orthogonaux lorsque leur produit scalaire est nul, et que l'orthogonal d'un ensemble $S \subset \mathbb{Q}^n$ est l'ensemble noté $S^\perp$ des vecteurs orthogonaux à tous les éléments de $S$. On introduit les espaces vectoriels emboîtés $V_i = \mathbb{Q}v_1 \oplus \cdots \oplus \mathbb{Q}v_i$. La projection orthogonale sur $V_i$ est le projecteur linéaire sur $V_i$ parallèlement à $V_i^\perp$. On définit alors $v_i^*$ comme la projection orthogonale de $v_i$ sur $V_{i-1}^\perp$ (donc parallèlement à $(V_{i-1}^\perp)^\perp$, qui n'est autre que $V_{i-1}$).

Les considérations qui précèdent définissent uniquement les $v_i^*$ à partir des $v_i$ comme suit :

$$v_i^* = v_i - \sum_{j=1}^{i-1} \mu_{i,j} v_j^* \quad \text{où} \quad \mu_{i,j} = \frac{(v_i | v_j^*)}{(v_j^* | v_j^*)}.$$

La quantité $\mu_{i,j}$ correspond à l'unique valeur garantissant l'orthogonalité entre $v_i^*$ et $v_j^*$ quand $j < i$. Après avoir posé $\mu_{i,i} = 1$ et $\mu_{i,j} = 0$ quand $j > i$, on obtient la matrice triangulaire inférieure

$$M = (\mu_{i,j}) = \begin{pmatrix} 1 & & & 0 \\ & \ddots & & \\ \mu_{i,j} & & \ddots & \\ & & 1 & \end{pmatrix},$$

vérifiant la relation

$$M \begin{pmatrix} v_1^* \\ \vdots \\ v_n^* \end{pmatrix} = \begin{pmatrix} v_1 \\ \vdots \\ v_n \end{pmatrix}.$$

En particulier, les espaces vectoriels sur $\mathbb{Q}$ engendrés par les $v_i$ d'une part et par les $v_i^*$ d'autre part sont les mêmes.

Soit maintenant un vecteur non nul $v$ du réseau engendré par les $v_i$, qui s'écrit donc $v = \lambda_1 v_1^* + \cdots + \lambda_n v_n^*$ pour des entiers $\lambda_i$ non tous nuls. En passant au carré de la norme on obtient

$$\|v\|^2 = \sum_{i=1}^{n} \lambda_i^2 \|v_i^*\|^2 \geq \min_{1 \leq i \leq n} \|v_i^*\|^2.$$

À ce stade, nous aurions trouvé des vecteurs parmi les plus courts, si ce n'est que les $v_i^*$ sont généralement à coefficients rationnels et donc hors du réseau. Il n'en reste pas moins que l'algorithme LLL qui va suivre s'appuie sur ce procédé d'orthogonalisation de sorte à contrôler des transformations de la base du réseau. À un niveau intuitif, plus une base de réseau est « orthogonale », plus elle est à même de contenir un vecteur court. Cette heuristique se justifie par la notion de déterminant d'un réseau : étant donnée une base $v_1,...,v_n$ d'un réseau, le déterminant de cette famille, c'est-à-dire le déterminant de la matrice $^t(v_1,...,v_n)$ obtenue en plaçant les vecteurs lignes $v_i = (v_{i,1},...,v_{i,n})$ les uns au dessus des autres, est, au signe près, invariant par changement de base de $\mathbb{Z}^n$. En effet, soit $w_1,...,w_n$ une autre base du même réseau. Il existe alors une matrice $U$ à coefficients entiers, admettant un inverse
à coefficients entiers, tel que $^t(v_1, ..., v_n) = U^t(w_1, ..., w_n)$. En passant aux déterminants, on a que $\det(U)$ vaut $\pm 1$, donc que $^t(v_1, ..., v_n)$ et $^t(w_1, ..., w_n)$ ont même déterminant au signe près. Toujours au signe près, ce déterminant n'est autre que le volume du parallélépipède construit en s'appuyant sur les $v_i$. Les côtés de ce parallélépipède sont d'autant plus courts que ce parallélépipède est orthogonal.

Une base $v_1, ..., v_n$ d'un réseau est dite *réduite* lorsque les orthogonalisés $v_i^*$ des $v_i$ par le procédé de Gram-Schmidt satisfonnent $\|v_i^*\|^2 \le 2\|v_{i+1}^*\|^2$ pour tout $i$ entre 1 et $n-1$. En particulier, $\|v_1\|^2 = \|v_1^*\|^2 \ge 2^{i-1}\|v_i^*\|$. Les inégalités suivantes s'ensuivent pout tout vecteur non nul $v$ du réseau :

$$ \|v\| \ge \min_{1 \le i \le n} \|v_i^*\| \ge \min_{1 \le i \le n} 2^{-(i-1)/2} \|v_1\| \ge 2^{-(n-1)/2} \|v_1\|. $$

Autrement dit, le premier élément d'une base réduite est un vecteur court, au sens où pour tout $v$ non nul du réseau on a $\|v_1\| \le 2^{(n-1)/2}\|v\|$.

## 20.3 L'algorithme LLL

Pour un réel $x$, on note $\lceil x \rceil$ l'entier le plus proche de $x$ (par défaut, l'entier immédiatement inférieur si $x$ est un demi-entier). LLL est présenté dans l'Algorithme 20.2. Le reste du chapitre est essentiellement dédié à la preuve du théorème suivant, qui implique immédiatement le Théorème 20.1.

**Théorème 20.2** L'Algorithme 20.2 est correct et a pour coût binaire

$$ \tilde{O}(n^5 \log^2 A), $$

$$ \text{où } A = \max_{1 \le i \le n} \|v_i\|. $$

Pour commencer, illustrons l'algorithme sur l'exemple donné par les deux vecteurs $v_1 = (6, 4)$ et $v_2 = (8, 4)$ de $\mathbb{Z}^2$. Après les étapes (1) et (2), on a $w_1^* = v_1$, $w_2^* = v_2 - \frac{16}{13}v_1 = (\frac{8}{13}, -\frac{12}{13})$, et

$$ N = \begin{pmatrix} 1 & 0 \\ \frac{16}{13} & 1 \end{pmatrix}, $$

de sorte que $N^t(w_1^*, w_2^*) = {}^t(w_1, w_2)$. Comme $\lceil \frac{16}{13} \rceil = 1$, la transformation, dite de réduction, de l'étape (3.a) revient à multiplier $N$ et $^t(w_1, w_2)$ à gauche par la matrice $\begin{pmatrix} 1 & 0 \\ -1 & 1 \end{pmatrix}$. Les vecteurs $w_1$ et $w_2$ deviennent (6, 4) et (2, 0), et la nouvelle valeur pour $N$ est

$$ N = \begin{pmatrix} 1 & 0 \\ \frac{3}{13} & 1 \end{pmatrix}. $$

On a la relation

$$ N\begin{pmatrix} 6 & 4 \\ \frac{8}{13} & -\frac{12}{13} \end{pmatrix} = \begin{pmatrix} 6 & 4 \\ 2 & 0 \end{pmatrix}, $$

qui montre que $w_1^*, w_2^*$ reste l'orthogonalisé de $w_1, w_2$.

En arrivant à l'étape (3.b), les normes à considérer vérifient $\|w_1^*\|^2 = 52 > 2\|w_2^*\|^2 = 32/13$, ce qui provoque l'échange des valeurs de $w_1$ et $w_2$. Nous pouvons vérifier sur
**Entrée** Des vecteurs $v_1, \dots, v_n$ de $\mathbb{Z}^n$ engendrant un réseau L.

**Sortie** Une base réduite $w_1, \dots, w_n$ de L.

1. Initialiser $w_i$ à $v_i$ pour chaque $i$ de 1 à $n$.

2. Initialiser $w_1^*, \dots, w_n^*$ et $N = (v_{i,j})$ avec les orthogonalisés de Gram-Schmidt $w_1^*, \dots, w_n^*$ de $w_1, \dots, w_n$ et la matrice M des $\mu_{i,j}$, de sorte que $N^t(w_1^*, \dots, w_n^*) = t(w_1, \dots, w_n)$.

3. Pour $i$ à partir de 2, tant que $i \le n$, faire :

a. pour $j$ de $i-1$ à 1, remplacer $w_i$ par $w_i - [v_{i,j}]w_j$ et remplacer $v_{i,k}$ par $v_{i,k} - [v_{i,j}]v_{j,k}$ pour $1 \le k \le j$;

b. si $i \ge 2$ et si $\|w_{i-1}^*\|^2 > 2\|w_i^*\|^2$,

i. poser $\alpha = v_{i,i-1}$, et calculer

$$\beta = v_{i,i-1} \|w_{i-1}^*\|^2 / (\|w_i^*\|^2 + v_{i,i-1}^2 \|w_{i-1}^*\|^2),$$

ii. remplacer simultanément $w_{i-1}^*$ et $w_i^*$ par $w_i^* + \alpha w_{i-1}^*$ et $w_{i-1}^* - \beta(w_i^* + \alpha w_{i-1}^*)$,

iii. permuter les valeurs de $w_{i-1}$ et $w_i$,
ainsi que les lignes $i-1$ et $i$ de N,

iv. pour tout $i-1 \le k \le n$, remplacer simultanément $v_{k,i-1}$ et $v_{k,i}$ par $\beta v_{k,i-1} + (1-\alpha\beta)v_{k,i}$ et $v_{k,i-1} - \alpha v_{k,i}$.

v. décrémenter $i$,

sinon incrémenter $i$.

4. Renvoyer $w_1, \dots, w_n$.

**Algorithme 20.2 – Algorithme de réduction de réseau LLL.**

cette exemple que les formules de l'étape (3.b) correspondent à la mise à jour de l'orthogonalisé de Gram-Schmidt de $w_1, w_2$, puisque l'on obtient à la fin de cette étape : $\beta = 3$, $w_2^* = (0,4)$, et

$$N = \begin{pmatrix} 1 & 0 \\ 3 & 1 \end{pmatrix}$$

de sorte que

$$N \begin{pmatrix} 2 & 0 \\ 0 & 4 \end{pmatrix} = \begin{pmatrix} 2 & 0 \\ 6 & 4 \end{pmatrix}. \qquad (20.1)$$

La valeur de $i$ passe alors de 2 à 1. On repasse ensuite par (3.a) et (3.b) mais sans rien faire, et $i$ revient à 2. Comme $\lceil 3 \rceil = 3$, une nouvelle réduction est effectuée à la nouvelle étape (3.a) : on multiplie alors à gauche les deux membres de (20.1) par $\begin{pmatrix} 1 & 0 \\ -3 & 1 \end{pmatrix}$. On obtient de la sorte la relation suivante :

$$\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 2 & 0 \\ 0 & 4 \end{pmatrix} = \begin{pmatrix} 2 & 0 \\ 0 & 4 \end{pmatrix}.$$

Comme $\|w_1^*\|^2 = 4 \le 2\|w_2^*\|^2 = 32$, l'algorithme termine en renvoyant la base réduite $w_1 = (2,0)$ et $w_2 = (0,4)$.
## 20.4 Preuve de l’algorithme LLL

Nous commençons par prouver que l’algorithme est correct et termine bien. Ensuite nous prouvons qu’il effectue $O(n^4 \log A)$ opérations arithmétiques dans $\mathbb{Q}$. Enfin, nous analysons la taille des nombres rationnels intervenant dans les calculs, de sorte à déduire la borne sur sa complexité binaire donnée dans le Théorème 20.2.

### Correction

À l'entrée de la boucle (3), $w_1^*,...,w_n^*$ est l'orthogonalisé de Gram-Schmidt de $w_1,...,w_n$ et N est la matrice M des $\mu_{i,j}$ qui satisfait $M^t(w_1^*,...,w_n^*) = {}^t(w_1,...,w_n)$. Observons d'abord que cette propriété est préservée à chaque sortie du corps de boucle.

Il est clair qu'il en est ainsi après la transformation de l'étape (3.a) puisque N reste triangulaire supérieure de diagonale 1 et satisfait

$$ N^t(w_1^*,...,w_n^*) = {}^t(w_1,...,w_n). \quad (20.2) $$

Quant à l'étape (3.b), on veut montrer que l'orthogonalisation est mise à jour après l'échange des vecteurs $w_{i-1}$ et $w_i$. Notons $u_1,...,u_n$ la base

$$ w_1,...,w_{i-2},w_i,w_{i-1},w_{i+1},...,w_n $$

du réseau obtenue après cet échange, et $u_1^*,...,u_n^*$ son orthogonalisé. On a les égalités entre espaces vectoriels $\mathbb{Q}w_1 \oplus \cdots \oplus \mathbb{Q}w_k = \mathbb{Q}u_1 \oplus \cdots \oplus \mathbb{Q}u_k$, pour $k \in \{1,...,n\} \setminus \{i-1\}$. Ainsi, les vecteurs orthogonalisés $u_k^*$ et $w_k^*$ sont clairement égaux lorsque $k \neq i-1, i$. Pour $k=i-1$, on déduit de

$$ w_i = w_i^* + \alpha w_{i-1}^* + \mu_{i,i-2} w_{i-2}^* + \cdots + \mu_{i,1} w_1^* $$

que $u_{i-1}^* = w_i^* + \alpha w_{i-1}^*$ et donc

$$ u_{i-1} = u_{i-1}^* + \mu_{i,i-2} u_{i-2}^* + \cdots + \mu_{i,1} u_1^* $$

Ensuite on prétend que $u_i^* = w_{i-1}^* - \beta(w_i^* + \alpha w_{i-1}^*)$, avec

$$ \beta = \frac{\beta \|w_{i-1}^*\|^2}{\|w_i^*\|^2 + \beta^2 \|w_{i-1}^*\|^2} $$

Ce vecteur est orthogonal à $u_1^*,...,u_{i-2}^*$, et on vérifie que

$$ (u_i^* | u_{i-1}^*) = (w_{i-1}^* | w_i^* + \alpha w_{i-1}^*) - \beta \|w_i^* + \alpha w_{i-1}^*\|^2 = \alpha \|w_{i-1}^*\|^2 - \beta (\|w_i^*\|^2 + \alpha^2 \|w_{i-1}^*\|^2) = 0. $$

Puis, à partir de

$$ w_{i-1} = w_{i-1}^* + \mu_{i-1,i-2} w_{i-2}^* + \cdots + \mu_{i-1,1} w_1^* $$

on obtient

$$ u_i = u_i^* + \beta u_{i-1}^* + \mu_{i-1,i-2} u_{i-2}^* + \cdots + \mu_{i-1,1} u_1^* $$

Pour $k \ge i+1$, on utilise

$$ w_{i-1}^* = u_i^* + \beta u_{i-1}^*, \quad w_i^* = -\alpha u_i^* + (1-\alpha\beta)u_{i-1}^* $$
de sorte que

$$w_k = w_k^* + \mu_{k,k-1} w_{k-1}^* + \dots + \mu_{k,1} w_1^*$$

se récrit en

$$u_k = u_k^* + \mu_{k,i+1} u_{i+1}^* + (\mu_{k,i-1} - \alpha \mu_{k,i}) u_i^* + (\beta \mu_{k,i-1} + (1-\alpha\beta)\mu_{k,i}) u_{i-1}^* + \mu_{k,i-2} u_{i-2}^* + \dots + \mu_{k,1} w_1^*$$

Donc à la sortie de l'étape (3.b), les $w_i^*$ sont bien les orthogonalisés des $w_i$ et la relation (20.2) est conservée.

Un second invariant respecté par la même boucle (3) est la suite d'inégalités

$$\|w_1^*\|^2 \le 2\|w_2^*\|^2, \dots, \|w_{i-2}^*\|^2 \le 2\|w_{i-1}^*\|^2.$$

Cet invariant est bien satisfait à l'entrée de la boucle (3), pour $i = 2$. Puis, la stratégie de l'étape (3.b) est d'incrémenter $i$ seulement si la suite d'inégalités peut se prolonger par $\|w_{i-1}^*\|^2 \le 2\|w_i^*\|^2$, ou au contraire de décrémenter $i$ lorsque $w_{i-1}^*$ est modifié. Par conséquent, si une exécution de l'algorithme sort de la boucle (3), la base renvoyée est bien réduite. Il nous reste donc prouver maintenant que l'algorithme termine.

## Terminaison

Pour montrer la terminaison de algorithme, on commence par observer que seule l'étape (3.b) modifie les $w_i^*$. On va montrer que l'échange et la mise à jour durant cette étape réduit $\|w_{i-1}^*\|^2$, et on va associer à ces normes une quantité entière qui décroît. Le nombre d'échanges ne pourra donc être que fini.

Lors d'un passage dans l'étape (3.b) avec $i \ge 2$ et $\|w_{i-1}^*\|^2 > 2\|w_i^*\|^2$, notons à nouveau $u_1, \dots, u_n$ la base du réseau obtenue après l'échange de $w_{i-1}$ et $w_i$. La formule $w_{i-1}^* = w_i^* + \alpha w_{i-1}^*$ implique

$$\|u_{i-1}^*\|^2 = \|w_i^*\|^2 + \alpha^2 \|w_{i-1}^*\|^2 < \|w_{i-1}^*\|^2/2 + (1/2)^2 \|w_{i-1}^*\|^2 = \frac{3}{4} \|w_{i-1}^*\|^2, \quad (20.3)$$

en utilisant le fait que l'étape (3.a) a forcé la relation $\alpha = \mu_{i,i-1} \le 1/2$. Aussi on vérifie que la formule $u_i^* = w_{i-1}^* - \beta(w_i^* + \alpha w_{i-1}^*)$ implique

$$\begin{align} \|u_i^*\|^2 &= \|w_{i-1}^*\|^2 + \beta^2 \|w_i^* + \alpha w_{i-1}^*\|^2 - 2(w_{i-1}^* | \beta(w_i^* + \alpha w_{i-1}^*) ) \tag{20.4} \\ &= (1 - \alpha\beta) \|w_{i-1}^*\|^2 < \|w_{i-1}^*\|^2. \end{align}$$

On introduit la matrice de Gram $G_i$ des vecteurs $w_1, \dots, w_i$ comme la matrice de taille $i \times i$ dont l'entrée $(k,l)$ est le produit scalaire $(w_k | w_l)$. C'est donc une matrice de $\mathbb{Z}^{i \times i}$, qui s'exprime aussi comme le produit

$$G_i = {}^t(w_1, \dots, w_i)(w_1, \dots, w_i).$$

Puisque le bloc $M_i$ de taille $i \times i$ en haut à gauche dans la matrice M est encore triangulaire inférieur de diagonale 1, on a

$$d_i = \det(M_i{}^t(w_1, \dots, w_i)^t (M_i{}^t(w_1^*, \dots, w_i^*)) = \|w_1^*\|^2 \dots \|w_i^*\|^2.$$

Le variant qui va s'avérer adéquat est le produit $D = d_1 \cdots d_{n-1}$, de nouveau un entier strictement positif. Lors d'un échange à l'étape (3.b), nous venons de prouver
que $d_{i-1}$ est divisé par au moins 4/3. Comme les autres $d_j$ restent inchangés, alors D est divisé par au moins 4/3, tout en restant entier strictement positif. Il ne peut donc y avoir qu'un nombre fini d'échanges lors d'une exécution de l'algorithme.

Considérons les nombres *e* d'échanges en (3.b) et *f* de passages en (3.b) qui incrémentent *i*. En observant ces valeurs à chaque entrée de la boucle (3), on a l'invariant $i = 2 - e + f$. Chaque passage dans la boucle (3) incrémente l'un ou l'autre de ces deux nombres. Mais comme le nombre *e* ne peut croître indéfiniment, le nombre *f* doit ultimement ne plus cesser de croître, et *i* avec, ce jusqu'à la valeur $i = n + 1$ qui provoque la fin de la boucle. L'algorithme termine donc.

## Complexité arithmétique

Au début de l'algorithme, le nombre D qui vient d'être introduit pour montrer la terminaison vaut

$$D_{\text{initial}} = \|v_1^*\|^{2(n-1)} \|v_2^*\|^{2(n-2)} \cdots \|v_{n-1}^*\|^2.$$

Mais chaque $v_i^*$ étant alors une certaine projection de l'entrée $v_i$, on a

$$D_{\text{initial}} \le \|v_1\|^{2(n-1)} \|v_2\|^{2(n-2)} \cdots \|v_{n-1}\|^2 \le A^{n(n-1)}.$$

Après *e* échanges en (3.b), on a l'encadrement $1 \le D \le (3/4)^e D_{\text{initial}}$, d'où la borne supérieure $e \le n(n-1) \log_{4/3} A$.

Notons $e_{\text{final}}$ et $f_{\text{final}}$ les valeurs finales de *e* et *f*, en fin d'exécution. On vient de prouver la relation $e_{\text{final}} = O(n^2 \log A)$. Par ailleurs l'invariant sur *i* donne $n + 1 = 2 - e_{\text{final}} + f_{\text{final}}$, d'où $v_{\text{final}} = O(n^2 \log A)$. Comme l'orthogonalisation initiale se fait en $O(n^3)$ opérations arithmétiques dans $\mathbb{Q}$, et que chacune des étapes (3.a) et (3.b) se fait en $O(n^2)$ telles opérations arithmétiques, la complexité arithmétique totale de l'algorithme LLL est

$$O(n^3) + (e_{\text{final}} + v_{\text{final}})O(n^2) = O(n^4 \log A).$$

## Complexité binaire

Il nous reste à analyser la taille des entiers intervenant dans l'algorithme. Nous allons montrer qu'elle reste dominée par $O(n \log A)$, ce qui achèvera la preuve du Théorème 20.2.

### Coût de l'orthogonalisation

Commençons par borner la taille des rationnels intervenant lors du procédé d'orthogonalisation. Notons $K = M^{-1}$ et notons $\kappa_{i,j}$ les entrées de K. Il s'agit d'une matrice triangulaire inférieure avec des 1 sur la diagonale. Pour tout $1 \le i \le n$, on a

$$w_i^* = w_i + \kappa_{i,i-1} w_{i-1} + \cdots + \kappa_{i,1} w_1.$$

En prenant les produits scalaires par $w_j$ pour $1 \le j \le i - 1$ on obtient

$$0 = (w_i, w_j) + \kappa_{i,i-1} (w_{i-1}, w_j) + \cdots + \kappa_{i,1} (w_1, w_j),$$

ce qui donne la relation

$$G_{i-1}^{t}(\kappa_{i,1}, \dots, \kappa_{i,i-1}) + t((w_i, w_1), \dots, (w_i, w_{i-1})) = 0, \quad (20.5)$$
qui représente $(\kappa_{i,1}, \dots, \kappa_{i,i-1})$ comme solution d'un système linéaire.

Pour analyser l'étape (2) de l'algorithme il suffit d'utiliser le fait que les normes $||v_i|| = ||w_i||$ sont au plus A. Le système linéaire (20.5) est inversible car le déterminant de $G_{i-1}$ est $d_{i-1} \ge 1$. Par les formules de Cramer, on déduit déjà que $d_{i-1} \kappa_{i,j}$ est un entier, pour tout $1 \le j \le i$. Par conséquent $d_{i-1} w_i^* \in \mathbb{Z}^n$ et $||w_i^*|| \ge 1/\sqrt{d_{i-1}}$. Ensuite on peut borner les $\mu_{i,j}$ comme suit :

$$|\mu_{i,j}| = \frac{(w_i, w_j^*)}{||w_j^*||^2} \le \frac{||w_i||}{||w_j^*||} \le \sqrt{d_{j-1}} ||w_i|| \le A^i. \quad (20.6)$$

Il s'ensuit que la taille des entiers intervenant dans l'étape (2) est bornée par $O(n \log A)$. Le coût binaire de cette étape est donc $O(n^4 \log A)$.

## Taille des entiers dans la boucle principale

Grâce à (20.3) et (20.4), nous savons que les normes des $||w_i^*||$ restent bornées par A tout au long de l'algorithme, et que $d_i \le A^i$. Commençons par majorer les normes des $w_i$ au long de l'exécution. À partir de

$$||w_i||^2 = ||w_i^*||^2 + \mu_{i,i-1}^2 ||w_{i-1}^*||^2 + \dots + \mu_{i,i-1}^2 ||w_{i-1}^*||^2$$

nous avons

$$||w_i|| \le \sqrt{i} A \max_{1 \le j \le i} \mu_{i,j}.$$

Lorsqu'on entre dans l'étape (3.a), la borne (20.6) garantit que les entiers des $\mu_{i,j}$ sont au plus $A^i$ et donc que

$$||w_i|| \le \sqrt{i} A^{i+1}.$$

Lorsque $|v_{i,j}| \ge 1/2$, on remplace $v_{i,k}$ par $v_{i,k} - \lceil v_{i,j} \rceil \mu_{j,k}$ au cours de l'étape (3.a), alors $|v_{i,k}|$ croît au plus de

$$\lceil v_{i,k} \rceil \mu_{j,k} \le (v_{i,j} + \frac{1}{2}) \frac{1}{2} \le v_{i,j},$$

lorsque $k < j$, comme $|v_{j,l}| \le 1/2$. Lorsque $j = k$, on a $|v_{i,j}| \le 1/2$. Donc les entiers $v_{i,j}$ restent bornés par (2A)$^i$. Par conséquent, les tailles des entiers dans les étapes (3.a) restent en $O(n \log A)$. Lorsqu'on quitte l'étape (3.a), tous les $v_{i,j}$ sont au plus $1/2$ lorsque $j < i$, et donc $||w_i|| \le \sqrt{i} A$.

Enfin, lors de l'étape (3.b), il est clair que les entiers restent aussi de taille $O(n \log A)$, ce qui achève l'étude de la complexité binaire de l'algorithme LLL.

## Bornes sur la base réduite

En complément, nous donnons les bornes suivantes, qui nous seront utiles dans le prochain chapitre :

**Proposition 20.3** La base $w_1, \dots, w_n$ renvoyée par l'Algorithme 20.2 satisfait la propriété suivante : $||w_j||^2 \le 2^{i-1} ||w_i^*||^2$, pour tout $1 \le j \le i \le n$.
Démonstration. Comme $w_1, \dots, w_n$ est une base réduite, on a $\|w_j^*\|^2 \le 2^{i-j}\|w_i^*\|^2$. Par ailleurs, à la sortie de l'algorithm, les entrées sous la diagonale de N sont au plus 1/2 en valeur absolue. La relation (20.2) implique donc

$$ \begin{aligned} \|w_j\|^2 &\le \|w_j^*\|^2 + \frac{1}{4} (\|w_{j-1}^*\|^2 + \dots + \|w_1^*\|^2) \\ &\le \left(2^{i-j} + \frac{1}{4}(2^{i-j+1} + \dots + 2^{i-1})\right) \|w_i^*\|^2 \le 2^{i-1} \|w_i^*\|^2. \end{aligned} \quad \blacksquare $$

Notes

La théorie des réseaux remonte aux travaux d'Hermite [Pic05] et à l'algorithm de réduction de Lagrange pour la dimension deux [Lag73; Lag75]. L'algorithm LLL a été découvert par A. Lenstra, H. Lenstra et L. Lovász en 1982 [LLL82]. Le présent chapitre suit la version décrite dans le Chapitre 16 du livre de von zur Gathen et Gerhard [GG03]. La preuve que le calcul du plus court vecteur d'un réseau est NP-difficile est due à Ajtai en 1998 [Ajt98].

En pratique, il est conseillé de modifier l'Algorithm 20.2 de sorte à ne pas calculer les $w_i^*$, mais seulement les $\|w_i^*\|^2$. Aussi pour améliorer significativement les performances, il ne faut pas effectuer les calculs avec des nombres rationnels, car les calculs de pgcd nécessaires pour maintenir les numérateurs et dénominateurs premiers entre eux sont très coûteux. On préfère donc programmer une version qui sépare habilement numérateurs et dénominateurs, en utilisant le procédé d'orthogonalisation décrit par Erlingsson, Kaltofen et Musser [EKM96]. D'autres variantes, avec des meilleures bornes de complexité, ont été proposées par plusieurs auteurs, dont Kaltofen [Kal83], Schönhage [Sch84], Koy et Schnorr [KS01; Sch88a]. La qualité de la base obtenue par les divers procédés a été étudiée par Schnorr [Sch03; Sch87].

Pour améliorer davantage la complexité de l'algorithm LLL, il faut commencer par observer que les $\lceil \mu_{i,i-1} \rceil$ dépendent juste des bits de poids fort de $\mu_{i,i-1}$. On peut donc utiliser une arithmétique numérique en virgule flottante pour accélérer les calculs, et conserver les matrices unimodulaires de changement de base plutôt que les bases intermédiaires. Toute la difficulté pratique repose sur le choix de bonnes stratégies pour bénéficier au maximum de la double précision IEEE 754, native dans de nombreux processeurs. Pour bien faire fonctionner cette technique il faut aussi relâcher la condition de réduction. Ces idées ont été introduites par Schnorr en 1988 [Sch88a], puis améliorées avec Euchner [SE94] : elles ont conduit à la borne de complexité $O(n^4(n + \log A)^2 \log A)$, et à une implantation très efficace. Puis, dans cette veine, l'algorithm L$^2$, conçu par Nguyen et Stéhlé [NS05; NS09], a atteint la borne $(n^3(n + \log A) \log A) \tilde{O}(n)$ en utilisant une précision qui dépend juste linéairement de n. Maintenant, le meilleur algorithme connu, appelé L$^1$ est dû à Novocin, Stéhlé et Villard en 2011 [NSV11], et a pour coût $O(n^{5+\epsilon} \log A + n^{\theta+1+\epsilon}(\log A)^{1+\epsilon})$, où $\theta \le 3$ est un exposant réalisable de l'algèbre linéaire (au sens du Chapitre 8), et $\epsilon > 0$ est une constante réelle qui peut être fixée arbitrairement petite.
Bibliographie

Ajt98 AJTAI, Miklós (1998). « The shortest vector problem in L2 is NP-hard for randomized reductions ». In : Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing. STOC '98. Extended abstract. New York, NY, USA : ACM, p. 10–19.

EKM96 ERLINGSSON, Úlfar, Erich KALTOFEN et David MUSSER (1996). « Generic Gram–Schmidt orthogonalization by exact division ». In : Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation. ISSAC'96. New York, NY, USA : ACM, p. 275–282.

GG03 GATHEN, Joachim von zur et Jürgen GERHARD (2003). Modern computer algebra. 2e éd. Cambridge University Press.

Kal83 KALTOFEN, Erich (1983). « On the complexity of finding short vectors in integer lattices ». In : Computer Algebra : EUROCAL'83, European Computer Algebra Conference London, England, March 28–30, 1983 Proceedings. Éd. par J. A. HULZEN. Berlin, Heidelberg : Springer Berlin Heidelberg, p. 236–244.

KS01 KOY, Henrik et Claus Peter SCHNORR (2001). « Segment LLL-Reduction of Lattice Bases ». In : Cryptography and Lattices : International Conference, CaLC 2001 Providence, RI, USA, March 29–30, 2001 Revised Papers. Éd. par Joseph H. SILVERMAN. Berlin, Heidelberg : Springer Berlin Heidelberg, p. 67–80.

Lag73 LAGRANGE, Joseph Louis, comte de (1773). « Recherches d'arithmétique ». In : Nouveaux Mémoires de l'Académie Royale des Sciences et Belles-Lettres de Berlin, p. 265–312.

Lag75 — (1775). « Recherches d'arithmétique ». In : Nouveaux Mémoires de l'Académie Royale des Sciences et Belles-Lettres de Berlin, p. 323–356.

LLL82 LENSTRA, A. K., H. W. LENSTRA Jr. et L. Lovász (1982). « Factoring polynomials with rational coefficients ». In : Mathematische Annalen, vol. 261, n°4, p. 515–534.

NS05 NGUYÊN, Phong Q. et Damien STEHLÉ (2005). « Floating-point LLL revisited ». In : Proceedings of Advances in Cryptology, EUROCRYPT 2005 : 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22-26, 2005. Éd. par Ronald CRAMER. Berlin, Heidelberg : Springer Berlin Heidelberg, p. 215–233.

NS09 NGUYEN, Phong Q. et Damien STEHLÉ (2009). « An LLL algorithm with quadratic complexity ». In : SIAM Journal on Computing, vol. 39, n°3, p. 874–903.

NSV11 NOVOCIN, Andrew, Damien STEHLÉ et Gilles VILLARD (2011). « An LLL-reduction algorithm with quasi-linear time complexity ». In : Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing. STOC '11. Extended abstract. New York, NY, USA : ACM, p. 403–412.

Pic05 PICARD, Émile, éd. (1905). Œuvres de Charles Hermite. Gauthier-Villars.

Sch03 SCHNORR, Claus Peter (2003). « Lattice reduction by random sampling and birthday methods ». In : STACS 2003 : 20th Annual Symposium on Theoretical Aspects of Computer Science Berlin, Germany, February 27 – March 1,
2003 *Proceedings*. Éd. par Helmut ALT et Michel HABIB. Berlin, Heidelberg : Springer Berlin Heidelberg, p. 145-156.

Sch84 SCHÖNHAGE, Arnold (1984). « Factorization of univariate integer polynomials by diophantine approximation and an improved basis reduction algorithm ». In : *Automata, Languages and Programming : 11th Colloquium Antwerp, Belgium, July 16-20, 1984*. Éd. par Jan PAREDAENS. Berlin, Heidelberg : Springer Berlin Heidelberg, p. 436-447.

Sch87 SCHNORR, C. P. (1987). « A hierarchy of polynomial time lattice basis reduction algorithms ». In : *Theoretical Computer Science*, vol. 53, n°2-3, p. 201-224.

Sch88a — (1988). « A more efficient algorithm for lattice basis reduction ». In : *Journal of Algorithms*, vol. 9, n°1, p. 47-62.

SE94 SCHNORR, C. P. et M. EUCHNER (1994). « Lattice basis reduction : improved practical algorithms and solving subset sum problems ». In : *Mathematical Programming*, vol. 66, n°1, p. 181-199.
# 21. Factorisation des polynômes à une variable sur les rationnels

## Résumé

La factorisation des polynômes à coefficients des nombres rationnels repose sur trois résultats fondamentaux : une borne sur la taille des coefficients des facteurs, l'algorithme de Newton-Hensel, et l'algorithme de réduction LLL. L'idée principale consiste à calculer la factorisation irréductible à coefficients $p$-adiques à une précision suffisante, pour un nombre $p$ bien choisi. Ensuite il reste à deviner comment les facteurs $p$-adiques se recombinent en les facteurs rationnels.

Tout au long de ce chapitre F désigne le polynôme de degré $n$ de $Q[X]$ que nous souhaitons factoriser. Son coefficient de tête, c'est-à-dire de degré $n$, est noté $ct(F)$.

Le contenu d'un polynôme de $Z[X]$ est défini comme le pgcd de ses coefficients, et sa partie primitive correspond au quotient par son contenu. Rappelons le résultat classique général d'arithmétique suivant, que nous admettrons :

**Proposition 21.1** — Lemme de Gauss sur les contenus. Soit $A$ est un anneau factoriel, le contenu du produit de deux polynômes de $A[X]$ est égal au produit de leurs contenus.

**Théorème 21.2** — Lemme de Gauss sur les polynômes irréductibles. Soient $A$ un anneau factoriel, et $K$ son corps de fractions. Un polynôme non constant de $A[X]$ est irréductible si, et seulement, s'il est primitif et irréductible dans $K[X]$.

*Démonstration.* Soit $F$ un polynôme non constant de $A[X]$. Il est nécessairement primitif. S'il se factorise dans $K[X]$, alors il existe des polynômes $F_1$ et $F_2$ primitifs de $A[X]$, et un élément $c$ de $A$, tels que $cF = F_1F_2$. La proposition précédente implique
que $c$ est une unité. Cela prouve le sens direct de l'énoncé. La réciproque est quant à elle immédiate. ■

Ici, la conséquence pratique de ce théorème est de réduire la factorisation de $\mathbb{Z}[X]$ à celle d'un contenu dans $\mathbb{Z}$ et celle d'un polynôme primitif dans $\mathbb{Q}[X]$.

La factorisation dans $\mathbb{Z}[X]$ semble donc mathématiquement proche de celle dans $\mathbb{Q}[X]$. Seulement, à l'heure actuelle, du point de vue de la complexité, nous ne connaissons toujours pas d'algorithme pour factoriser les entiers en temps polynomial. Nous n'aborderons pas cette question dans cet ouvrage. Néanmoins, une fois tout risque de confusion maintenant levé, il sera plus pratique de considerer que le polynôme à factoriser est à coefficients entiers et primitif. Les factorisations dans $\mathbb{Z}[X]$ et $\mathbb{Q}[X]$ coïncident alors. Dans la section suivante nous présentons un premier algorithme très simple de coût exponentiel qui conduit à une borne raisonnable sur les tailles des coefficients des facteurs irréductibles, que nous améliorerons ensuite.

## 21.1 Bornes sur les coefficients des facteurs

Dans cette section $F(X) = f_nX^n + f_{n-1}X^{n-1} + \dots + f_1X + f_0$ représente un polynôme primitif de $\mathbb{Z}[X]$ de degré $n$.

### Borne naive

Si $G \in \mathbb{Z}[X]$ est un facteur propre de $F$, c'est-à-dire non constant et primitif, de degré au plus $m \le n-1$, alors, pour tout entier $i \in \{0, \dots, m\}$, nécessairement $G(i)$ divise $F(i)$. Cette simple remarque fournit un algorithme pour trouver un tel facteur $G$ ou bien montrer qu'il n'en existe pas, et prouver ainsi que $F$ est irréductible :

1. Évaluer $F$ en tous les points de $\{0, \dots, m\}$.

2. Énumérer tous les vecteurs $(b_0, \dots, b_m)$ de $\mathbb{Z}^m$ tels que $b_i$ divise $F(i)$ pour tout $i \in \{0, \dots, m\}$.

3. Pour chaque tel vecteur $(b_0, \dots, b_m)$, interpoler le polynôme $G$ de degré au plus $m$ tel que $G(i) = b_i$ pour tout $i \in \{0, \dots, m\}$. Si $G$ est non constant dans $\mathbb{Z}[X]$, et divise $F$, alors c'est un facteur propre de $F$.

Le coût de cette méthode dans le pire des cas est bien exponentiel. Néanmoins elle conduit à un premier résultat concernant la taille des coefficients des facteurs de $F$. Notons $\|F\|_{\infty}$ la quantité $\max_{i \in \{0, \dots, n\}} |f_i|$.

**Proposition 21.3** Soit $F$ un polynôme primitif de $\mathbb{Z}[X]$ de degré $n$, et soit $G$ un facteur propre de $F$ de degré $m \le n-1$. Alors $\|G\|_{\infty} \le (m+1)(n+1)m^{n+2m}\|F\|_{\infty}$.

*Démonstration.* À partir de la formule d'interpolation de Lagrange nous avons

$$G(X) = \sum_{i=0}^{m} G(i) \prod_{j=0, j \neq i}^{m} \frac{X-j}{i-j},$$
et déduisons la majoration suivante :

$$
\|G\|_{\infty} \le \left( \max_{i \in \{0, \dots, m\}} |G(i)| \right) \left\| \sum_{i=0}^{m} \prod_{j=0, j \ne i}^{m} (X+j) \right\|_{\infty} \le (m+1) m^{2m} \max_{i \in \{0, \dots, m\}} |G(i)|.
$$

La conclusion provient de

$$
\max_{i \in \{0, \dots, m\}} |G(i)| \le \max_{i \in \{0, \dots, m\}} |F(i)| \le (n+1) m^n \|F\|_{\infty}.
$$

<figure><img src="image_56.png" /></figure>

La taille des coefficients de G est donc au plus la taille de ceux de F plus O(n log n).

**Exemple 21.1** Avec $F = X^{105} - 1 = (X-1)(X^2+X+1)(X^4+X^3+X^2+X+1)(X^6+X^5+
X^4+X^3+X^2+X+1)(X^8-X^7+X^5-X^4+X^3-X+1)(X^{12}-X^{11}+X^9-X^8+X^6-X^4+
X^3-X+1)(X^{24}-X^{23}+X^{19}-X^{18}+X^{17}-X^{16}+X^{14}-X^{13}+X^{12}-X^{11}+
X^{10}-X^8+X^7-
X^6+X^5-X+1)(X^{48}+X^{47}+X^{46}-X^{43}-X^{42}-2X^{41}-X^{40}-X^{39}+X^{36}+
X^{35}+X^{34}+
X^{33}+X^{32}+X^{31}-X^{28}-X^{26}-X^{24}-X^{22}-X^{20}+X^{17}+X^{16}+X^{15}+X^{14}+
X^{13}+X^{12}-
X^9-X^8-2X^7-X^6-X^5+X^2+X+1)$, la taille des coefficients du dernier facteur
dépasse légèrement celle de F.

Borne de Landau–Mignotte

Dans la suite de ce chapitre la borne donnée dans la Proposition 21.3 sera suffisante pour obtenir un algorithme de factorisation en temps polynomial. En pratique il est néanmoins utile d'avoir des bornes plus précises. Pour ce faire, nous utiliserons la norme $\|\cdot\|_2$, définie par

$$
\|F\|_2 = (|f_n|^2 + \dots + |f_0|^2)^{1/2}.
$$

L'idée pour borner plus finement la taille des coefficients d'un facteur de F est de
considérer la mesure de Mahler de F(X) = f_n Π_{i=1}^n (X - φ_i) ∈ C[X] \ {0}, notée M(F), et
définie par

$$
M(F) = |f_n| \prod_{i=1}^{n} \max(1, |\varphi_i|).
$$

Ici les racines $\varphi_i$ ne sont pas nécessairement distinctes puisque F n'est pas supposé sans
carré. Cette fonction M est multiplicative : si F = GH, alors nous avons visiblement
M(F) = M(G)M(H).

Dans un premier temps nous allons montrer $M(F) \le \|F\|_2$. Notons que cette borne
est immédiate si toutes les racines de F sont de module au plus 1, puisque dans ce
cas on a $M(F) = \text{ct}(F) \le \|F\|_2$. Pour se ramener à ce cas nous utilisons le polynôme
auxiliaire

$$
H(X) = \text{ct}(F) \bar{\varphi}_{m+1} \cdots \bar{\varphi}_n (X - \varphi_1) \cdots (X - \varphi_m) (X - \bar{\varphi}_{m+1}^{-1}) \cdots (X - \bar{\varphi}_n^{-1}),
$$

où les racines $\varphi_1, \dots, \varphi_n$ de F sont ordonnées par modules croissants, et où $m \in \{0, \dots, n\}$ est défini par $0 < |\varphi_1| \le \dots \le |\varphi_m| < 1 \le |\varphi_{m+1}| \le \dots \le |\varphi_n|$. Ce polynôme H a toutes ses racines de modules au plus 1, et donc $M(H) = \text{ct}(H) \le \|H\|_2$. De plus, la construction de H est faite pour avoir $M(H) = M(F)$.
**Proposition 21.4** Pour tout polynôme F de $\mathbb{C}[X]$, on a $M(F) \le \|F\|_2$.

*Démonstration.* Avec ce que nous venons de voir à propos de H, il nous reste à prouver
$\|F\|_2 = \|H\|_2$. Soit $\omega$ une racine primitive de l'unité d'ordre $n+1$ dans $\mathbb{C}$. La transformée
de Fourier associée à $\omega$,

$$
F \mapsto (F(1), F(\omega), \dots, F(\omega^n)),
$$

définit un changement de base dans l'espace des polynômes de degré au plus $n$. Le
Lemme 2.7 nous garantit que ce changement de base est orthogonal, et que les vecteurs
de la nouvelle base ont pour norme $1/\sqrt{n+1}$. Par conséquent on a

$$
\|F\|_2^2 = \frac{1}{n+1} \sum_{i=0}^{n} |F(\omega^i)|^2.
$$

En utilisant la formule similaire pour H, et en vérifiant que l'on a $|F(\omega^i)|^2 = |H(\omega^i)|^2$
pour tout $i$, on obtient bien $\|F\|_2 = \|H\|_2$. ■

Les formules classiques reliant les coefficients de F à ses racines mènent alors à :

**Proposition 21.5** Si G est un facteur de degré *m* de F, alors

$$
\|G\|_2 \le 2^m \mathrm{M}(G) \le 2^m \left| \frac{\mathrm{ct}(G)}{\mathrm{ct}(F)} \right| \|F\|_2.
$$

Démonstration. Si $g_i$ est le coefficient de degré $i$ de $G$ et si $\varphi_1, \dots, \varphi_m$ sont les racines de $G$ classées par ordre de croissant de module, alors on a $|g_i| \le |g_m| (\binom{m}{i}) |\varphi_{i+1}| \cdots |\varphi_m| \le (\binom{m}{i}) M(G)$. De l'inégalité $\sum_{i=0}^m (\binom{m}{i})^2 \le (\sum_{i=0}^m \binom{m}{i})^2 = 2^{2m}$ nous déduisons $\|G\|_2 \le 2^m M(G)$. La preuve s'achève donc en utilisant $M(G) \le \left| \frac{g_m}{f_n} \right| M(F)$ et la proposition précédente.

Nous déduisons le théorème suivant appelé borne de Landau–Mignotte.

**Théorème 21.6** Si $G \in \mathbb{Z}[X]$ est un facteur de $F \in \mathbb{Z}[X]$ de degré $m$, alors

$$
\| \mathrm{ct}(F)G / \mathrm{ct}(G) \|_{\infty} \le \sqrt{n+1} 2^m \|F\|_{\infty}.
$$

*Démonstration.* Il s'agit juste de combiner les inégalités $\|G\|_\infty \le \|G\|_2$, et $\|F\|_2 \le \sqrt{n+1}\|F\|_\infty$ avec la proposition précédente.

■

Borne de Mahler

En réutilisant le polynôme auxiliaire H de la sous-section précédente, nous pou-
vons aussi obtenir l'inégalité suivante due à Mahler, qui nous sera utile pour l'algo-
rithme de van Hoeij présenté en Section 21.4.
**Théorème 21.7** Pour tout $F \in \mathbb{C}[X]$ degré $n$, on a $M(F') \le nM(F)$.

*Démonstration.* Le polynôme $H$ a toutes ses racines dans le disque unité ouvert. Par le classique théorème de Gauss-Lucas (rappelé dans le Lemme 21.9 ci-dessous), les racines de $H'(X)$ sont dans l'enveloppe convexe de celles de $H(X)$, et donc dans le disque unité ouvert. On a ainsi $M(H') = nM(H)$. Comme $M(H) = M(F)$, il suffit de prouver $M(F') \le M(H')$.

Si $|x| \ge 1$ et $i \ge m+1$, alors on vérifie l'inégalité $|x - \varphi_i| \le |\bar{\varphi}_i x - 1|$, en constatant qu'elle est équivalente à

$$ (x - \varphi_i)(\bar{x} - \bar{\varphi}_i) \le (\bar{\varphi}_i x - 1)(\varphi_i \bar{x} - 1), $$

qui se récrit en $0 \le |\varphi_i|^2|x|^2 - |x|^2 - |\varphi_i|^2 + 1 = (|\varphi_i|^2 - 1)(|x|^2 - 1)$. Pour tout $|x| \ge 1$, on a donc $|F(x)| \le |H(x)|$. En d'autres termes, si $u \in \mathbb{C}$ est de module $|u| > 1$, alors les racines de $F(X) - uH(X)$ sont toutes dans le disque unité ouvert. Par le théorème de Gauss-Lucas, les racines de $F'(X) - uH'(X)$ sont donc aussi dans le disque unité ouvert. Par conséquent, pour tout $x \in \mathbb{C}$ n'annulant pas $H'$, si $u = F'(x)/H'(x)$ est de module strictement plus grand que 1, alors $x$ est un zéro de $F'(X) - uH'(X)$ et donc dans le disque unité ouvert. Autrement dit, on vient de prouver $|F'(x)| \le |H'(x)|$ pour tout $|x| \ge 1$. Le lemme suivant assure alors que $M(F') \le M(H')$. ■

**Lemme 21.8** Si $F$ et $G$ sont deux polynômes de $\mathbb{C}[X]$ tels que $|F(x)| \le |G(x)|$ pour tout $x$ de module 1, alors $M(F) \le M(G)$.

*Démonstration.* On considère le résultant $\mathrm{Res}(F(X), X^k - 1)$. La formule de Poisson vue dans le Théorème 6.5 conduit à l'identité

$$ \mathrm{ct}(F)^k \prod_{F(x)=0} (x^k - 1) = (-1)^{kn} \prod_{x^k=1} F(x), $$

qui implique

$$ |\mathrm{ct}(F)| \prod_{F(x)=0} |x^k - 1|^{1/k} = \prod_{x^k=1} |F(x)|^{1/k}. $$

En faisant de même pour $G$, et en utilisant l'hypothèse $|F(x)| \le |G(x)|$, on déduit

$$ |\mathrm{ct}(F)| \prod_{F(x)=0} |x^k - 1|^{1/k} \le |\mathrm{ct}(G)| \prod_{G(x)=0} |x^k - 1|^{1/k}. $$

Si $|x| < 1$, alors $|x^k - 1|^{1/k}$ converge vers 1 lorsque $k$ tend vers l'infini. Si $|x| > 1$ alors $|x^k - 1|^{1/k}$ converge vers $|x|$. Si ni $F$ ni $G$ n'ont de racine de module 1 alors on en déduit $M(F) \le M(G)$.

Par hypothèse, les racines de $G$ qui sont sur le cercle unité annulent aussi $F$. En divisant $F$ et $G$ par le polynôme annulateur unitaire de ces racines, par la multipli-cativité de $M$, on se ramène au cas où $G$ n'a pas de racine de module 1. Ensuite on prend $\alpha$ réel au voisinage de 1 de sorte que $F(\alpha X)$ n'admet aucune racine de module
1 lorsque $\alpha > 1$. Quitte à restreindre le voisinage pour $\alpha$, il existe un voisinage réel pointé à gauche de 1 qui contient des valeurs $\beta$ telles que $\beta F(\alpha x) \le G(x)$ pour tout $x$ de module 1. On a alors $M(\beta F(\alpha X)) \le M(G)$. On peut enfin faire tendre $\alpha$ vers 1 puis $\beta$ vers 1 dans cette dernière inégalité pour conclure la preuve du lemme. ■

**Lemme 21.9 — Gauss-Lucas.** Les racines de la dérivée d'un polynôme $F \in \mathbb{C}[X]$ non constant sont dans l'envelope convexe des racines de F.

*Démonstration.* Si $F(X) = \text{ct}(F) \prod_{i=1}^n (X - \varphi_i)$, alors la dérivée logarithmique de F est

$$ \frac{F'}{F} = \sum_{i=1}^{n} \frac{1}{X - \varphi_i}. $$

Soit $\psi$ est une racine de $F'$. Le résultat est immédiat si $\psi$ est aussi racine de F. Sinon on a

$$ \sum_{i=1}^{n} \frac{1}{\psi - \varphi_i} = 0, $$

qui implique

$$ \sum_{i=1}^{n} \frac{\bar{\psi} - \bar{\varphi}_i}{|\psi - \varphi_i|^2} = 0, $$

et donc

$$ \psi \sum_{i=1}^{n} \frac{1}{|\psi - \varphi_i|^2} = \sum_{i=1}^{n} \frac{\varphi_i}{|\psi - \varphi_i|^2}. $$

Autrement dit, $\psi$ est un barycentre des $\varphi_i$.

<figure><img src="image_57.png" /></figure>

<figure><img src="image_58.png" /></figure>

La définition de la mesure de Mahler peut sembler *a priori* artificielle. En fait, une définition plus naturelle est la formule suivante :

$$ \log M(F) = \frac{1}{2\pi} \int_{0}^{2\pi} \log |F(e^{i\theta})| d\theta. $$

L'équivalence des deux définitions fait habituellement appel à des résultats classiques d'analyse complexe, mais on peut aussi y parvenir en adaptant les arguments utilisés dans la preuve du Lemme 21.8. En effet, nous avons vu que si F n'a pas de racine sur le cercle unité, alors le membre de gauche de l'identité

$$ |\text{ct}(F)| \prod_{F(x)=0} |x^k - 1|^{1/k} = \prod_{x^k=1} |F(x)|^{1/k}, $$

converge vers $M(F)$. Par ailleurs, le logarithme du membre de droite vaut

$$ \sum_{x^{k}=1} \frac{1}{k} \log |F(x)| $$
et converge donc vers

$$ \frac{1}{2\pi} \int_{0}^{2\pi} \log|F(e^{i\theta})|d\theta $$

lorsque $k$ tend vers l'infini. Enfin pour traiter le cas où $F$ a des racines sur le cercle unité, il suffit de reprendre l'argument de déformation utilisé à la fin de la preuve du lemme.

## Borne d'Hadamard

Afin de borner des résultats comme $\mathrm{Res}(F, F')$, nous utilisons le résultat classique suivant :

**Proposition 21.10** — **Borne d'Hadamard.** Si $V$ est une matrice carrée de taille $n \times n$ à coefficients dans $\mathbb{R}$, alors $|\mathrm{det}(V)| \le \|v_1\|_2 \cdots \|v_n\|_2$, où $v_i$ représente la $i$-ième ligne de $V$.

*Démonstration.* Le procédé d'orthogonalisation de Gram-Schmidt, vu dans le chapitre précédent, appliqué aux vecteurs $v_1, \dots, v_n$, fournit des vecteurs orthogonaux $v_1^*, \dots, v_n^*$ et une matrice $M$ triangulaire inférieure de diagonale unitaire tels que $\|v_i^*\|_2 \le \|v_i\|_2$ pour tout $i$, et

$$ M \begin{pmatrix} v_1^* \\ \vdots \\ v_n^* \end{pmatrix} = \begin{pmatrix} v_1 \\ \vdots \\ v_n \end{pmatrix}. $$

Par conséquent le déterminant de $V$ est égal à $\|v_1^*\|_2 \cdots \|v_n^*\|_2 \le \|v_1\|_2 \cdots \|v_n\|_2$. ■

**Corollaire 21.11** Si $F$ et $G$ sont deux polynômes de degrés respectifs $n$ et $m$ à coefficients réels, alors $|\mathrm{Res}(F, G)| \le \|F\|_2^m \|G\|_2^n$. ■

*Démonstration.* Il suffit d'appliquer la proposition précédente à la matrice de Sylvester des polynômes $F$ et $G$, définie au Chapitre 6. ■

## 21.2 Factorisation sans carré

Nous abordons maintenant la complexité binaire de la factorisation sans carré d'un polynôme primitif $F$ de $\mathbb{Z}[X]$. La méthode présentée ici consiste à calculer la factorisation sans carré de $F$ modulo $p$ pour suffisamment de nombres premiers $p$, puis à utiliser la méthode des restes chinois pour reconstruire la factorisation sans carré de $F$ dans $\mathbb{Z}[X]$. Nous commençons par étudier la complexité du calcul de nombres premiers.

### Calcul de nombres premiers

Le premier ingrédient technique nécessaire est le calcul de nombres premiers plus petits qu'un entier $k$ fixé. Le second ingrédient est un encadrement du produit des nombres premiers inférieurs à $k$.
**Lemme 21.12** L'ensemble des nombres premiers inférieurs ou égaux à *k* peut se calculer en coût binaire $O(k \log^2 k) = \tilde{O}(k)$.

*Démonstration.* La borne de complexité découle de l'utilisation de la méthode classiquement appelée *crible d'Ératosthène*. On initialise un vecteur de booléens avec vrai de taille *k* + 1 : la *i*-ième entrée indiquera à la fin de l'algorithme si l'entier *i* est premier. On met les entrées 0 et 1 à faux. Le premier entier *p* dont l'entrée est vrai est 2, et on marque faux tous les multiples stricts de *p* à partir de *p*². On prend ensuite pour *p* l'entier suivant marqué vrai, en l'occurrence 3, et on marque faux tous les multiples stricts de *p* à partir de *p*². On prend ensuite pour *p* l'entier suivant marqué vrai, et on continue de la même façon. De la sorte, *p* est toujours premier. Il suffit de s'arrêter dès que $p > \sqrt{k}$. Le coût binaire de cette méthode est donc

$$O\left(\sum_{\substack{2 \le p \le \sqrt{k} \\ p \text{ premier}}} \frac{k}{p} \log k\right) = O\left((k \log k) \sum_{2 \le i \le k} \frac{1}{i}\right).$$

Cette dernière somme est majorée par

$$\sum_{2 \le i \le k} \frac{1}{i} \le \sum_{2 \le i \le k} \int_{i-1}^{i} \frac{1}{t} dt \le \int_{1}^{k} \frac{1}{t} dt = O(\log k),$$

ce qui nous donne le coût binaire annoncé $O(k \log^2 k)$.

<figure><img src="image_59.png" /></figure>

**Lemme 21.13** Lorsque *k* est suffisamment grand on a

$$\left(\frac{3}{2}\right)^k \le \prod_{\substack{2 \le p \le k \\ p \text{ premier}}} p \le 4^{k-1}.$$

*Démonstration.* Commençons par la majoration. L'inégalité se vérifie directement pour $k = 2,3$, puis nous entamons une récurrence sur *k*. Bien entendu, nous pouvons nous ramener à *k* impair de la forme $2m + 1$, et supposer la borne valable pour *m* à la place de *k*.

On décompose le produit

$$\prod_{\substack{2 \le p \le 2m+1 \\ p \text{ premier}}} p \quad \text{en} \quad A = \prod_{\substack{2 \le p \le m \\ p \text{ premier}}} p \quad \text{et} \quad B = \prod_{\substack{m+1 \le p \le 2m+1 \\ p \text{ premier}}} p.$$

Par récurrence on a justement $A \le 4^{m-1}$. Ensuite on remarque que B divise le nombre combinatoire $\binom{2m+1}{m}$. Puis pour borner ce nombre on fait appel à la formule du binôme de Newton

$$(1+1)^{2m+1} = \sum_{i=0}^{2m+1} \binom{2m+1}{i},$$
qui donne $B \le \binom{2m+1}{m} \le 2^{2m+1}$, et donc $AB \le 4^{2m-1/2} \le 4^{k-1}$.

Pour la minoration, on commence par observer que la multiplicité de $p$ dans $i \in \{m+1, \dots, 2m\}$ est au plus $\log_p(2m)$, et comme il n'y a qu'au plus $1+\log_p m$ multiples de $p$ dans $m+1, \dots, 2m$, alors la multiplicité de $p$ dans $C_n = (2m)(2m-1)\cdots(m+1)/m!$ est au plus $(1+\log_p m)\log_p(2m)$. De plus, si $\sqrt{2m} < p \le 2m$, alors cette multiplicité est au plus 1 : en effet la multiplicité de $p$ dans $i \le 2m$ est au plus 1, le nombre de multiples de $p$ dans $1, \dots, m$ est $\lfloor \frac{m}{p} \rfloor$ et le nombre de multiples de $p$ dans $m+1, \dots, 2m$ est au plus $1+\lfloor \frac{m}{p} \rfloor$. On déduit

$$C_n \le \left( \prod_{\substack{2 \le p \le \sqrt{2m} \\ p \text{ premier}}} p^{(1+\log_p m)\log_p(2m)} \right) \left( \prod_{\substack{\sqrt{2m} < p \le 2m \\ p \text{ premier}}} p \right) \le (2m)^{(1+\log_2 m)\sqrt{2m}} \prod_{\substack{2 \le p \le 2m \\ p \text{ premier}}} p.$$

Comme $C_n = \binom{2m}{m} \ge \binom{2m}{i}$ pour tout $0 \le i \le 2m$, l'identité

$$(1+1)^{2m} = \sum_{i=0}^{2m} \binom{2m}{i} \le 2 + \sum_{i=1}^{2m-1} \binom{2m}{i} \le 2m \binom{2m}{m},$$

implique alors $C_n \ge 4^m/(2m)$. Donc on a

$$\prod_{\substack{2 \le p \le 2m \\ p \text{ premier}}} p \ge \frac{2^{2m}}{(2m)^{1+(\log_2(2m))\sqrt{2m}}}$$

et la conclusion provient de

$$\prod_{\substack{2 \le p \le k \\ p \text{ premier}}} p \ge \frac{2^k}{(k+1)^{1+(\log_2(k+1))\sqrt{k+1}}} \ge \left(\frac{3}{2}\right)^k,$$

pour $k$ suffisamment grand. La constante $\frac{3}{2}$ est arbitraire ici : n'importe quel nombre inférieur strict à 2 convient. ■

## Méthode par restes chinois

Nous avons défini au Chapitre 18 la factorisation sans carré de F, notée fsc(F), comme l'ensemble des paires $(Q, m)$, où Q est le produit des facteurs sans carré primitifs de F de multiplicité $m \ge 1$. Un entier $p$ sera dit *compatible* avec la factorisation sans carré de F lorsque la factorisation sans carré de F mod $p$ coïncide avec $\{(Q \mod p, m) \mid (Q, m) \in \text{fsc(F)}\}$. Nous commençons par deux lemmes techniques.

**Lemme 21.14** Soit F un polynôme de $\mathbb{Z}[X]$. Un nombre premier $p$ divise Res(F, F') si et seulement s'il divise ct(F) ou si $\text{Res}(F \mod p, F' \mod p) = 0 \mod p$.
*Démonstration.* Nous avons vu au Chapitre 6, que si A et B sont deux polynômes en la variable X de degrés respectifs *m* et *n*,

$$
A(X) = a_m X^m + \dots + a_1 X + a_0 \quad \text{et} \quad B(X) = b_n X^n + \dots + b_1 X + b_0,
$$

le résultant de A et B peut être calculé comme le déterminant de la matrice de
Sylvester, carrée de taille *m* + *n* suivante

$$
\text{Syl}(A, B) =
\begin{pmatrix}
a_m & \cdots & a_1 & a_0 \\
\vdots & & \vdots & \vdots \\
a_m & \cdots & a_{m-1} & a_0 \\
b_n & \cdots & b_1 & b_0 \\
\vdots & & \vdots & \vdots \\
b_n & \cdots & b_{n-1} & b_0
\end{pmatrix}
$$

En considérant Res(F, F') comme le déterminant de la matrice de Sylvester de F
et F', nous vérifions que si ct(F) mod *p* ≠ 0, alors Res(F, F') mod *p* est proportionnel sur
Fp à Res(F mod *p*, F' mod *p*). Par ailleurs, on observe aisément que Res(F, F') s'annule
modulo *p* lorsque ct(F) s'annule modulo *p*.
■

**Lemme 21.15** Soit *p* un nombre premier supérieur ou égal à *n* + 1. Notons *G* = *pgcd(F, F')* et *H* = *F/G* la partie sans carré de *F*. Les conditions suivantes sont équivalentes :

— *p* est compatible avec la factorisation sans carré de *F*;

— *p* ne divise pas Res(H, H');

— *p* ne divise pas ct(F) et deg(pgcd(F mod *p*, F' mod *p*)) = deg G.

*Démonstration.* Commençons par remarquer que l'hypothèse *p* ≥ *n* + 1 assure que les factorisations séparable et sans carré de F mod *p* coïncident.

La partie sans carré H de F n'est autre que le produit des facteurs sans carré de F,
c'est-à-dire $H = \prod_{(Q,m) \in \text{fsc}(F)} Q$. À partir de la dérivation $H' = \sum_{(Q,m) \in \text{fsc}(F)} Q'(H/Q)$,
et des propriétés multiplicatives du résultant énoncées dans le Théorème 6.5 et le
Corollaire 6.6, on obtient :

$$
\begin{align*}
\mathrm{Res}(H, H') &= \prod_{(Q,m) \in \mathrm{fsc}(F)} \mathrm{Res}(Q, H') \\
&= \prod_{(Q,m) \in \mathrm{fsc}(F)} \mathrm{ct}(Q)^* \mathrm{Res}(Q, Q'(H/Q)) \\
&= \pm \prod_{(Q,m) \in \mathrm{fsc}(F)} \mathrm{ct}(Q)^* \mathrm{Res}(Q, Q') \mathrm{Res}(Q, H/Q),
\end{align*}
$$

où ct(Q)* représente un puissance de ct(Q) qu'il n'est pas nécessaire d'expliciter ici. Le
fait que *p* soit compatible signifie d'une part que les facteurs Q mod *p* sont séparables
pour tout (Q, *m*) de fsc(F), et que d'autre part ces Q mod *p* sont premiers entre eux
deux à deux. Par la propriété de spécialisation du résultant vue dans le Lemme 21.14, cela est bien équivalent au fait que $p$ ne divise pas $\text{Res}(H, H')$.

Si $p$ ne divise pas $\text{Res}(H, H')$, alors $\text{ct}(H) \mod p$ et $\text{Res}(H \mod p, H' \mod p)$ sont non nuls par la propriété de spécialisation du résultant, ce qui signifie que $H \mod p$ est séparable : c'est donc la partie sans carré de $F \mod p$. On peut voir que les degrés de $\text{pgcd}(F \mod p, F' \mod p)$ et $G$ coïncident bien grâce à la formule suivante et au fait que $p$ ne divise aucune multiplicité $m$ :

$$ \text{pgcd}(F \mod p, F' \mod p) = $$

$$ \text{pgcd}\left( H \mod p, \sum_{(Q,m) \in \text{fsc}(F)} m(Q' \mod p)(H/Q \mod p) \right) \prod_{(Q,m) \in \text{fsc}(F)} (Q \mod p)^{m-1}. $$

Inversement, supposons que $p$ divise $\text{Res}(H, H')$. Si $p$ ne divise pas $\text{ct}(F)$, alors il ne divise pas $\text{ct}(H)$ et donc $\text{Res}(H \mod p, H' \mod p)$ est nul, ce qui implique que

$$ \text{pgcd}(H \mod p, H' \mod p) = \text{pgcd}\left( H \mod p, \sum_{(Q,m) \in \text{fsc}(F)} (Q' \mod p)(H/Q \mod p) \right) $$

est non constant. Comme ce dernier $\text{pgcd}$ coïncide avec

$$ \text{pgcd}\left( H \mod p, \sum_{(Q,m) \in \text{fsc}(F)} m(Q' \mod p)(H/Q \mod p) \right), $$

il s'ensuit que $\text{pgcd}(F \mod p, F' \mod p)$ est de degré strictement plus grand que $\text{deg} G$, ce qui conclut la preuve. ■

La stratégie pour obtenir $\text{fsc}(F)$ est la suivante : on calcule $\text{fsc}(F \mod p)$ pour suffisamment de valeurs de nombres premiers $p \ge n+1$ de sorte qu'on puisse d'une part déterminer ceux qui sont compatibles, et d'autre part qu'il y ait suffisamment de compatibles pour pouvoir reconstruire les facteurs par la méthode des restes chinois. Les détails sont donnés dans l'Algorithmme 21.1.

**Proposition 21.16** L'Algorithmme 21.1 est correct, de coût binaire $\tilde{O}(n^2 \log \|F\|_\infty)$.

*Démonstration.* Par la Proposition 6.2, le degré $d$ de $G = \text{pgcd}(F, F')$ correspond à la dimension du noyau de la matrice de Sylvester de $F$ et $F'$. Il existe donc un mineur $M$ non nul de taille $2n-1-d$ de cette matrice tel que, si $p$ ne divise ni $M$ ni $\text{ct}(F)$, alors le degré de $\text{pgcd}(F \mod p, F' \mod p)$ est égal à $d$. Par le Lemme 21.15, un tel $p \ge n+1$ est alors compatible avec la factorisation sans carré de $F$.

Il nous faut maintenant prouver que l'ensemble $E$ déterminé par l'algorithme permet bien de reconstruire les facteurs sans carré de $F$. D'une part, la borne d'Hadamard vue en Proposition 21.10 nous donne

$$ |\text{ct}(F)M| \le n^n \|F\|_2^{2n} \le n^{2n} \|F\|_\infty^{2n}. $$
**Entrée** $F \in \mathbb{Z}[X]$, séparable et primitif de degré $n$.

**Sortie** La factorisation sans carré de $F$.

1. Calculer le premier entier $k$ tel que

$$ (3/2)^k > 2 \cdot 8^n \sqrt{n+1} n^{2n} \|F\|_{\infty}^{2n+1}. $$

2. Calculer tous les nombres premiers $\leq k$.

3. Pour tout nombre premier $p$ entre $n+1$ et $k$, calculer $\text{fsc}(F \text{ mod } p)$.

4. Sélectionner l'ensemble $E$ des nombres premiers $p$ entre $n+1$ et $k$ tels que la partie sans carré de $F \text{ mod } p$ soit de degré maximal.

5. Notons $Q_{p,m}$ le facteur sans carré de multiplicité $m$ de $F \text{ mod } p$.
Pour chaque multiplicité $m$, calculer l'unique polynôme $Q_m$ de $\mathbb{Z}[X]$ satisfaisant $Q_m = \text{ct}(F)Q_{m,p}/\text{ct}(Q_{m,p}) \text{ mod } p$ pour tout $p \in E$ et $\|Q_m\|_{\infty} \leq \sqrt{n+1} 2^n \|F\|_{\infty}$.

6. Remplacer les $Q_m$ par leurs parties primitives et renvoyer la liste des paires $(Q_m, m)$.

**Algorithme 21.1** – Factorisation sans carré dans $\mathbb{Q}[X]$.

D'autre part le Théorème 21.6 de Landau-Mignotte permet de borner la taille des coefficients de tout facteur $Q$ primitif de $F$ par la formule suivante :

$$ \|\text{ct}(F)Q/\text{ct}(Q)\|_{\infty} \leq \sqrt{n+1} 2^n \|F\|_{\infty}. $$

En prenant pour $k$ le premier entier tel que

$$ (3/2)^k > 2 \cdot 8^n \sqrt{n+1} n^{2n} \|F\|_{\infty}^{2n+1}, $$

alors on a nécessairement

$$ \prod_{\substack{n+1 \leq p \leq k \\ p \text{ premier}}} p > 2 |\text{ct}(F)M| \|\text{ct}(F)Q/\text{ct}(Q)\|_{\infty}, $$

en utilisant les bornes pour $|\text{ct}(F)M|$ et $\|\text{ct}(F)Q/\text{ct}(Q)\|_{\infty}$ que nous venons de voir, ainsi que le Lemme 21.13. Par conséquent, parmi tous les calculs de $\text{fsc}(F \text{ mod } p)$ pour tout $n+1 \leq p \leq k$, on rencontre au moins un premier $p$ compatible. Cela justifie que l'algorithme détermine bien le degré de la partie sans carré de $F$, et sélectionne ainsi tous les nombres premiers $p$ compatibles. De plus, le choix de $k$ garantit aussi que le produit des nombres premiers de $E$ est deux fois supérieur à tous les coefficients des $\text{ct}(F)Q/\text{ct}(Q)$, pour tout facteur sans carré $Q$ de $F$.

En notant $\eta = \|\text{ct}(F)Q/\text{ct}(Q)\|_{\infty}$ et $\pi = \prod_{p \in E} p$, on a une injection naturelle de $\{-\eta, \dots, \eta\}$ dans $\mathbb{Z}/\pi\mathbb{Z}$. Un coefficient $c$ de $\text{ct}(F)Q/\text{ct}(Q)$ est envoyé dans $\{0, \dots, \eta\}$ s'il est
positif ou nul, et dans {$\pi - \eta, \dots, \pi - 1$} sinon. La condition $\pi > 2\eta$ assure que ces deux ensembles sont disjoints. L'utilisation des restes chinois à l'étape (5) permet donc bien de reconstruire les polynômes ct(F)Q/ct(Q). L'algorithme est correct.

Le coût binaire des étapes (1) et (2) est $\tilde{O}(n \log ||F||_\infty)$, par le Lemme 21.12. Les calculs multimodulaires et des restes chinois dans les étapes (4) et (5) ont coût $\tilde{O}(n^2 \log ||F||_\infty)$, par la Proposition 5.3. Pour les calculs des factorisations sans carré, on utilise le Théorème 18.16, qui reflète dans le présent cas le seul coût de l'Algorithmme 18.2 de Yun, puisque $p \ge n+1$. L'étape (3) totalise un coût binaire $\tilde{O}(n^2 \log ||F||_\infty)$. Les parties primitives de la dernière étape s'obtiennent en coût $\tilde{O}(n(n+\log ||F||_\infty))$. ■

## 21.3 Algorithme par remontée et recombinaison

Sans perte de généralité, à parir de maintenant, nous pouvons supposer F sans carré. Si $p$ est un nombre premier qui ne divise pas Res(F, F'), alors nous allons montrer qu'il existe une unique factorisation irréductible de F dans $\mathbb{Z}/p^\sigma\mathbb{Z}[X]$ pour chaque entier $\sigma \ge 1$. Lorsque $\sigma = 1$, il s'agit de la factorisation de F mod $p$, c'est-à-dire dans $\mathbb{F}_p[X]$, qui peut être calculée avec les algorithmes du Chapitre 19. Dans un premier temps nous allons montrer comment étendre cette factorisation pour n'importe quelle valeur de $\sigma$. Nous verrons que les facteurs de F dans $\mathbb{Z}/p^{\sigma+1}\mathbb{Z}[X]$ prolongent ceux dans $\mathbb{Z}/p^\sigma\mathbb{Z}[X]$. Nous parlerons alors de *remontée* des facteurs de F modulo $p$.

Ensuite, si $G \in \mathbb{Z}[X]$ divise F, alors les facteurs irreductibles de G dans $\mathbb{Z}/p^\sigma\mathbb{Z}[X]$ forment un sous-ensemble de ceux de F dans $\mathbb{Z}/p^\sigma\mathbb{Z}[X]$. Cette remarque nous mène alors à tester les produits de tous les sous-ensembles de facteurs de F dans $\mathbb{Z}/p^\sigma\mathbb{Z}[X]$, lorsque $\sigma$ est suffisamment grand. C'est l'étape dite de *recombinaison*.

### Choix de $p$

Pour choisir un premier $p$ qui ne divise pas Res(F, F'), il est plus efficace d'utiliser le lemme suivant plutôt que de calculer Res(F, F') puis de le réduire modulo $p$. Pour des raisons de complexité, nous sommes intéressés à avoir le plus petit nombre premier $p$ qui ne divise pas Res(F, F').

**Proposition 21.17** La recherche du plus petit nombre premier $p$ qui ne divise pas Res(F, F') peut s'effectuer en $\tilde{O}(n^2 \log ||F||_\infty)$ opérations binaires. De plus, ce nombre premier est borné par $\tilde{O}(n \log ||F||_\infty)$.

*Démonstration.* Par le Corollaire 21.11, la valeur absolue de Res(F, F') est au plus $||F||_2^{n-1}||F'||_2^n$. En prenant pour $k$ le premier entier plus grand que

$$ \log(||F||_2^{n-1}||F'||_2^n) = \tilde{O}(n \log ||F||_\infty), $$

on calcule alors tous les nombres premiers inférieurs à $k$ et on cherche le plus petit d'entre eux qui ne divise pas Res(F, F'). Si aucun nombre premier ne convient, alors on double $k$ et on cherche parmi les nouveaux nombres premiers. Le Lemme 21.13 nous assure que l'algorithme s'arrête avec $k$ borné par $\tilde{O}(n \log ||F||_\infty)$. Le Lemme 21.12 nous garantit que le calcul des nombres premiers inférieurs à $k$ est quasi-linéaire en $k$.

Avec l'algorithme rapide utilisant l'arbre des sous-produits du Chapitre 5 (voir Théorème 5.3), on peut calculer F mod $p$ pour tout nombre premier $p \le k$ en temps
quasi-linéaire. Ensuite pour chaque $p$ qui ne divise pas $\text{ct}(F)$ on calcule le discriminant de $F$ mod $p$ en temps $\tilde{O}(n \log p)$. Au total on obtient un coût binaire $\tilde{O}(n^2 \log \|F\|_\infty)$. ■

## Remontée de Newton-Hensel

Dans cette sous-section, $\mathbb{A}$ représente un anneau commutatif avec une unité, $I$ est un idéal propre de $\mathbb{A}$, et $F$ est un polynôme de $\mathbb{A}[X]$ de coefficient de tête noté $\text{ct}(F)$, qui est supposé inversible modulo $I$. Le lemme suivant est une forme du lemme de Hensel, mais avec le point de vue calculatoire de l'itération de Newton.

**Lemme 21.18** Supposons $\text{Res}(F, F')$ inversible modulo $I$. Si $g \in \mathbb{A}[X]$ divise $F$ modulo $I$ et que $\text{ct}(g) = 1$, alors il existe un unique polynôme $\mathfrak{G}$ congru à $g$ modulo $I$, unitaire et divisant $F$ modulo $I^2$.

*Démonstration.* Posons $\mathfrak{h} = F/g$. Nous cherchons deux polynômes $\mathfrak{G}$ et $\mathfrak{H}$ congrus respectivement à $g$ et $\mathfrak{h}$ modulo $I$, avec $\mathfrak{G}$ unitaire, et tels que $F = \mathfrak{G}\mathfrak{H}$ mod $I^2$. Cette dernière équation se récrit en $F = g\mathfrak{h} + g(\mathfrak{H} - \mathfrak{h}) + \mathfrak{h}(\mathfrak{G} - g)$ mod $I^2$. En prenant les restes de la division par $g$ nous obtenons $\text{rem}(F, g) = \text{rem}(\mathfrak{h}(\mathfrak{G} - g), g)$ mod $I^2$. Puisque le discriminant de $F$ est inversible modulo $I$, le résultant de $g$ et $\mathfrak{h}$ est inversible modulo $I$, et donc $\mathfrak{h}$ est inversible modulo $g$ dans $(\mathbb{A}/I^2)[X]$. En notant $u$ son inverse, nous en déduisons la formule suivante :

$$ \mathfrak{G} = g + \text{rem}(uF, g) \mod I^2. \quad \blacksquare $$

Comme $F' = g'\mathfrak{h} + g\mathfrak{h}' \mod I$, alors $\mathfrak{h} = F'/g' \mod g \mod I$ et nous obtenons la formule

$$ \mathfrak{G} - g = \frac{g'}{F'} F \mod g \mod I^2, $$

et par conséquent un algorithme pour calculer $\mathfrak{G}$. Une partie importante du calcul consiste à évaluer $F$ et $F'$ modulo $g$ et $I^2$ comme dans le cas de l'opérateur de Newton.

En fait, comme $F$ mod $g$ a tous ses coefficients dans $I$, il est suffisant de connaître l'inverse de $F'$ modulo $g$ à la précision $I$. Lorsque $I$ est maximal, $\mathbb{A}/I$ est un corps et nous pouvons obtenir cet inverse à partir de l'algorithme du pgcd étendu. En général, l'inverse $\mathfrak{u}$ de $F'$ modulo $\mathfrak{G}$ à la précision $I^2$ peut être déduit de l'inverse $\mathfrak{u}$ de $F'$ à la précision $I$ par la formule suivante :

$$ \mathfrak{u} = \mathfrak{u} - \mathfrak{u}(\mathfrak{u}F' - 1) \mod \mathfrak{G}, $$

puisque $\mathfrak{u}F' = 1 - (\mathfrak{u}F' - 1)^2 = 1 \mod \mathfrak{G} \mod I^2$. Cette méthode est résumée dans l'Algorithme 21.2.

**Proposition 21.19** Soient $\mathbb{A} = \mathbb{Z}$ et $I = (p)$ avec $p$ premier. À partir d'une décomposition $F = \text{ct}(F)\mathfrak{f}_1 \cdots \mathfrak{f}_s$ modulo $p$, avec des $\mathfrak{f}_i$ unitaires, nous pouvons calculer la decomposition $F = \text{ct}(F)\mathfrak{f}_1 \cdots \mathfrak{f}_s$ modulo $p^\sigma$ telle que $\mathfrak{f}_i = \mathfrak{f}_i \mod p$ pour tout $i \in \{1, \dots, m\}$, en temps $O(\mathbb{M}_{\mathbb{Z}}(\sigma \log p)M(d) \log d)$.

*Démonstration.* Il suffit d'appliquer successivement l'Algorithme 21.2 pour arriver en précision $p^2, p^4, \dots$ jusqu'à dépasser $p^\sigma$. Le coût découle principalement de la
**Entrée** $F \in \mathbb{A}[X]$, et $f_1, \dots, f_s$ unitaires dans $(\mathbb{A}/I)[X]$ tels que $F = \text{ct}(F)f_1 \cdots f_s$ dans $(\mathbb{A}/I)[X]$.

**Sortie** $F_1, \dots, F_s$ unitaires dans $(\mathbb{A}/I^2)[X]$ tels que $F = \text{ct}(F)F_1 \cdots F_s$ dans $(\mathbb{A}/I^2)[X]$ et $F_i = f_i \bmod I$ pour tout $i$.

1. Calculer $F \bmod f_1, \dots, F \bmod f_s$ et $F' \bmod f_1, \dots, F' \bmod f_s \bmod I^2$.

2. Calculer $r_1 = f'_1 F^F \bmod f_1, \dots, r_s = f'_s F^F \bmod f_s \bmod I^2$.

3. Renvoyer $f_1 + r_1, \dots, f_s + r_s$.

**Algorithme 21.2** – Remontée de Hensel simultanée.

Proposition 5.6, auquel il faut ajouter le coût pour obtenir les inverses de $F'$ mod $f_i$ pour tout $i$, c'est-à-dire $O(M_{\mathbb{Z}}(\sigma \log p)M(d) \log d)$.

**Proposition 21.20** Soient $\mathbb{K}$ un corps, $\mathbb{A} = \mathbb{K}[t]$ et $I = (t)$. À partir d'une décomposition $F = \text{ct}(F)f_1 \cdots f_s \bmod t$, avec des $f_i$ unitaires, nous pouvons calculer la decomposition $F = \text{ct}(F)F_1 \cdots F_s \bmod t^\sigma$ telle que $F_i = f_i \bmod t$ pour tout $i \in \{1, \dots, m\}$, en utilisant $O(M(\sigma)M(d) \log d)$ opérations arithmétiques dans $\mathbb{K}$.

*Démonstration.* La preuve est similaire à la précédente.

Chaque élément $a$ de $\mathbb{Z}/p^\sigma\mathbb{Z}$ s'écrit de façon unique en base $p$ sous la forme $\sum_{i=0}^{\sigma-1} a_i p^i$, avec les $a_i$ dans $\{0, \dots, p-1\}$. En s'inspirant de la construction des anneaux des séries formelles, on peut faire tendre $\sigma$ vers l'infini et définir l'anneau des *entiers p-adiques*, noté $\mathbb{Z}_p$, comme l'ensemble des limites des tels développements en base $p$. Les éléments sont de la forme $\sum_{i=0}^{+\infty} a_i p^i$. Les factorisations de $F$ dans $\mathbb{Z}/p^\sigma\mathbb{Z}$ convergent donc vers l'unique factorisation irréductible *p-adique* de $F$ dans $\mathbb{Z}_p[X]$.

**Exemple 21.2** Avec $F(X) = X^4 - 1$, on peut prendre $p = 5$. Les facteurs irréductibles dans $\mathbb{Z}/p^\sigma\mathbb{Z}[X]$ sont $X+1, X+2, X+3$ et $X+4$. Avec $\sigma = 10$, on a $F_1(X) = X+1+O(p^{10})$, $F_2(X) = X+2+p+2p^2+p^3+3p^4+4p^5+2p^6+3p^7+3p^9+O(p^{10})$, $F_3(X) = X+3+3p+2p^2+3p^3+p^4+2p^6+p^7+4p^8+p^9+O(p^{10})$, $F_4(X) = X+4+4p+4p^2+4p^3+4p^4+4p^5+4p^6+4p^7+4p^8+4p^9+O(p^{10})$.

## Recombinaison des facteurs *p*-adiques

Notons $F_1, \dots, F_s$ les facteurs irréductibles unitaires de $F$ dans $\mathbb{Z}/p^\sigma\mathbb{Z}$, de sorte que $F = \text{ct}(F)F_1 \cdots F_s$. Si $G \in \mathbb{Z}[X]$ est un diviseur propre et primitif de $F$, alors il existe un sous-ensemble $E$ de $\{1, \dots, s\}$ tels que $G(X) = \text{ct}(G) \prod_{e \in E} F_e$. Comme il n'est pas souhaitable de factoriser $\text{ct}(F)$ dans $\mathbb{Z}$ de sorte à énumérer toutes les valeurs possibles pour $\text{ct}(G)$, on va examiner $H(X) = \text{ct}(F)G(X)/\text{ct}(G) = \text{ct}(F) \prod_{e \in E} F_e$. Il s'agit d'un polynomial de $\mathbb{Z}[X]$ dont les normes des coefficients sont au plus $\eta = \sqrt{n+1} 2^m \|F\|_\infty$ par le Théorème 21.6.
**Entrée** $F \in \mathbb{Z}[X]$, séparable et primitif.

**Sortie** Les facteurs irréductibles de F.

1. Trouver le plus petit nombre premier $p$ qui ne divise pas $\text{Res}(F, F')$.

2. Déterminer le premier entier $\sigma$ tel que $p^{\sigma} > 2\eta$, avec $\eta = \sqrt{n+1} 2^n ||F||_{\infty}$.

3. Calculer les facteurs unitaires irréductibles $f_1, \dots, f_s$ de F dans $\mathbb{Z}/p\mathbb{Z}[X]$.

4. Remonter la factorisation irréductible $f_1, \dots, f_s$ de F dans $\mathbb{Z}/p^{\sigma}\mathbb{Z}[X]$ à l'aide de l'Algorithmme 21.2.

5. Initialiser S avec $\{1, \dots, s\}$, puis T avec $\{\}$, et L avec la liste vide.

6. Parcourir les sous-ensembles E non vides de S par cardinal croissant au plus $(s - \text{card}(T))/2$ et disjoints de T :

a. calculer $\text{ct}(F) \prod_{e \in E} F_e$ modulo $p^{\sigma}$, puis sa préimage H dans $\mathbb{Z}[X]$;

b. calculer la partie primitive G de H;

c. si G divise F alors l'insérer dans L, remplacer T par $T \cup E$, et F par $F/G$.

7. Si $\text{deg}(F) \ge 1$ alors insérer F dans L.

8. Renvoyer L.

**Algorithme 21.3** – Méthode naïve de factorisation par remontée et recombinaison.

On fixe maintenant $\sigma$ au premier entier tel que

$$p^{\sigma} > 2\eta = \sqrt{n+1} 2^{m+1} ||F||_{\infty}.$$

De cette manière, on a une injection

$$\{-\eta, \dots, \eta\} \hookrightarrow \mathbb{Z}/p^{\sigma}\mathbb{Z}.$$

Un coefficient $h_i$ de H est envoyé dans $\{0, \dots, \eta\}$ s'il est positif ou nul, et dans $\{-\eta + p^{\sigma}, \dots, p^{\sigma} - 1\}$ sinon. La condition $p^{\sigma} > 2\eta$ assure que ces deux ensembles sont disjoints. Par conséquent à partir de $\text{ct}(F) \prod_{e \in E} F_e$ calculé modulo $p^{\sigma}$ on peut reconstruire le polynôme $H(X) = \text{ct}(F)G(X)/\text{ct}(G)$, puis déduire G comme la partie primitive de H. Cette approche conduit à l'Algorithmme 21.3.

**Proposition 21.21** L'Algorithmme 21.3 est correct et a pour coût binaire

$$\tilde{O}(2^n \log ||F||_{\infty}).$$

*Démonstration.* Avec $p = \tilde{O}(n \log ||F||_{\infty})$ tel que spécifié dans la Proposition 21.17, la Proposition 19.13 permet de réaliser la factorisation de l'étape (3) de façon déterministe en $\tilde{O}(n^3 + pn^2) = \tilde{O}(n^3 \log ||F||_{\infty})$ opérations binaires. Ensuite, le coût de l'étape (4) est quasi-linéaire, grâce à la Proposition 21.19.
Pour le calcul de H, on construit l'arbre des sous-produits présenté dans la Section 5.4 de sorte que la Proposition 5.5 implique un coût binaire quasi-linéaire. Pour le calcul du contenu de H on peut utiliser successivement n fois l'algorithme rapide de pgcd, pour obtenir aussi un coût quasi-linéaire. Pour tester si G divise F on peut calculer F/G dans $\mathbb{Z}/p^\sigma\mathbb{Z}[X]$ puis la préimage Q de ce quotient dans $\mathbb{Z}[X]$ et enfin vérifier que F est égal à GQ. De cette manière le coût est quasi-linéaire.

Enfin, le nombre de candidats G à construire et tester dans l'étape (6), tant que F et S ne changent pas, est borné par le nombre de sous-ensembles de $S \setminus T$ de cardinal au plus $(s - \text{card}(T))/2$, c'est-à-dire $2^{s-\text{card}(T)}-1$. ■

Prendre pour $p$ le plus petit nombre premier qui ne divise pas $\text{Res}(F, F')$ est une bonne stratégie pour l'analyse de la complexité, mais ce n'est pas le meilleur choix en pratique, où il vaut mieux que $p$ soit de taille proche de celle d'un registre, c'est-à-dire 32 ou 64 bits avec les processeurs actuels.

**Exemple 21.3** Avec $F(X) = X^4 - 1$, et $p = 5$, comme dans l'Exemple 21.2, on a $\eta = 16\sqrt{5} < 36$, et il est suffisant de prendre $\sigma = 3$. Avec $E = \{1\}$, on obtient que $G(X) = H(X) = X + 1$ est un facteur irréductible de F. Ensuite $E = \{2\}$ donne $G(X) = H(X) = X + 57$ qui ne divise pas F. Avec $E = \{3\}$, on a $G(X) = H(X) = X - 59$ qui ne divise pas F. Avec $E = \{4\}$, on a $G(X) = H(X) = X - 1$ qui divise F. Le dernier facteur irréductible de F est donc $X^2 + 1$, obtenu avec $E = \{2, 3\}$.

R

L'Algorithmme 21.3 peut être amélioré. Déjà, lorsque F et T changent à l'étape (6), il est inutile de reconsidérer les ensembles E déjà traités. Ensuite, à chaque tel changement on peut recalculer une nouvelle précision $\sigma$, plus petite. Aussi on peut se contenter de chercher les facteurs irréductibles G de degrés au plus $d/2$. S'il n'existe pas de tels facteurs alors F est irréductible. Enfin le test de divisibilité de F par G doit être optimisé de sorte à détecter au plus vite la non-divisibilité, qui est le cas le plus fréquent rencontré au cours de l'algorithme. Par exemple on peut montrer que G ne divise pas F modulo un nombre premier $p' \neq p$. En pratique il est aussi intéressant d'essayer plusieurs valeurs de $p$ à l'étape (1), de sorte à minimiser le nombre $s$ de facteurs $p$-adiques. En général on observe souvent que $s$ est plutôt petit par rapport à $n$. Du coup cet algorithme est raisonnablement efficace, tant que $s$ ne dépasse pas la vingtaine. Néanmoins il existe certains cas extrêmes où $n = O(s)$, comme dans l'exemple suivant.

**Exemple 21.4** Soit $p_i$ le i-ième nombre premier pour $i \ge 1$. Le m-ième polynôme de Swinnerton-Dyer est défini par

$$S_m(X) = \prod (X \pm \sqrt{2} \pm \sqrt{3} \pm \sqrt{5} \pm \cdots \pm \sqrt{p_m}),$$

où le produit est pris sur les $2^m$ possibilités de signes + et -. Le degré de $S_m$ est $n = 2^m$. Ces polynômes peuvent être calculés numériquement (par exemple avec une arithmétique d'intervalle pour garantir le calcul) ou bien avec une cascade de résultats, comme par exemple : $S_2(X) = \text{Res}_{z_2}(\text{Res}_{z_1}(X - z_1 - z_2, z_1^2 - 2), z_2^2 - 3)$. Par cette dernière formule nous constatons que $S_m$ a tous ses coefficients dans $\mathbb{Z}$ et qu'il est unitaire. Par des arguments classiques de théorie de Galois, nous
savons que $S_m$ est irréductible dans $\mathbb{Z}[X]$. Par ailleurs, si $p$ est un nombre premier alors $\mathbb{F}_{p^2}$ contient toutes les racines carrées modulo $p$. Par conséquent $S_m(X)$ se factorise en facteurs de degrés 1 ou 2 modulo $p$. Le temps pour retrouver les recombinaisons des facteurs $p$-adiques est donc exponentiel en $n$. Avec $m = 3$, on a $S_3(X) = X^8 - 40X^6 + 352X^4 - 960X^2 + 576$. La factorisation modulo $p = 2$ est $X^8$, modulo $p = 3$ on a $(X^2 + 1)^2 X^4$, modulo $p = 5$ on a $(X^2 + 1)^2 X^4$, modulo $p = 7$ on a $(X^2 + 6X + 3)(X^2 + X + 6)(X^2 + 6X + 6)(X^2 + X + 3)$, etc.

Dans certaines situations, comme celles rencontrées au Chapitre 16, on souhaite connaître les racines entières ou rationnelles d'un polynôme $F$ de $\mathbb{Z}[X]$. Il n'est alors pas utile de calculer toute la factorisation irréductible de $F$ mais seulement ses facteurs de degré 1. À cet effet l'Algorithme 21.3 peut être naturellement simplifié pour conduire à la complexité suivante :

**Proposition 21.22** Le calcul des racines dans $\mathbb{Q}$ d'un polynôme $F$ de $\mathbb{Z}[X]$, primitif et séparable, de degré $n$ peut se faire en coût binaire $\tilde{O}(n^2 \log \|F\|_{\infty})$.

*Démonstration.* Il s'agit tout simplement de restreindre l'Algorithme 21.3 à ne chercher que les facteurs de degré 1, ce qui correspond à ne considérer que des sousensembles $E$ de cardinal 1 dans l'étape (6). Par conséquent, dans l'étape (3) on peut se contenter de ne calculer que les facteurs linéaires de $F$ modulo $p$. Cela peut être fait en évaluant $F$ sur tous les points de $\mathbb{Z}/p\mathbb{Z}$. Comme $p = \tilde{O}(n \log \|F\|_{\infty})$, l'algorithme d'évaluation multipoint du Théorème 5.1 permet d'effectuer cette tâche au moyen de $\tilde{O}(n \log \|F\|_{\infty})$ opérations dans $\mathbb{Z}/p\mathbb{Z}$, ce qui donne un coût binaire $\tilde{O}(n \log \|F\|_{\infty})$. La complexité découle de l'analyse faite dans la preuve de la proposition précédente. ■

## 21.4 Algorithme de van Hoeij

Nous présentons dans cette section un algorithme de factorisation déterministe fonctionnant en temps polynomial. Comme pour l'algorithme précédent, nous commençons par calculer une factorisation $p$-adique, mais jusqu'à une précision plus élevée de sorte à pouvoir résoudre le problème de recombinaison en temps polynomial, au moyen de l'algorithme LLL du chapitre précédent. L'idée clé est la suivante : si $F$ se factorise en $F_1 \cdots F_r$ alors l'égalité

$$F' = F \frac{F_1'}{F_1} + \cdots + F \frac{F_r'}{F_r}$$

permet, d'une certaine façon, de « linéariser » le problème.

### Dérivées logarithmiques

Continuons à supposer que $p$ est un nombre premier qui ne divise pas $\text{Res}(F, F')$, et notons $F_1, \dots, F_s$ les facteurs $p$-adiques unitaires de $F$ en précision $\sigma$. Pour chaque facteur irréductible $F_i$ de $F$ on définit le vecteur $\mu_i \in \{0, 1\}^s$ par l'égalité

$$F_i = \text{ct}(F_i) F_1^{\mu_{i,1}} \cdots F_s^{\mu_{i,s}} + O(p^{\sigma}).$$
En prenant la dérivée logarithmique et en multipliant par F les deux membres de cette égalité, nous obtenons :

$$F_{\frac{F'}{F_i}} = \mu_{i,1} F_{\frac{F'_1}{F_1}} + \dots + \mu_{i,s} F_{\frac{F'_s}{F_s}} + O(p^{\sigma}).$$

On doit donc chercher des entiers $\ell_1, \dots, \ell_s$ aussi petits que possible tels que

$$\ell_1 F_{\frac{F'_1}{F_1}} + \dots + \ell_s F_{\frac{F'_s}{F_s}}$$

soit un polynôme à coefficients des entiers pas trop grands modulo $p^{\sigma}$. Dans un premier temps il nous faut donc borner la taille des coefficients de tels polynômes lorsqu'ils sont de la forme $FG'/G$, avec $G$ un diviseur de $F$ dans $\mathbb{Z}[X]$. En utilisant successivement la Proposition 21.5, la multiplicativité de la mesure de Mahler $M$, le Théorème 21.7, puis la Proposition 21.4, on obtient :

$$\begin{aligned} \|FG'/G\|_2 &\le 2^{n-1} M(FG'/G) = 2^{n-1} M(F/G)M(G') \\ &\le n 2^{n-1} M(F/G)M(G) = n 2^{n-1} M(F) \le n 2^{n-1} \|F\|_2. \end{aligned}$$

À partir de maintenant on prend pour $\tau$ le premier entier tel que $p^{\tau} > n 2^n \|F\|_2$. Ainsi, pour tout $i \in \{1, \dots, r\}$, on peut reconstruire $F_{\frac{F'}{F_i}}$ à partir de sa projection dans $\mathbb{Z}/p^{\tau}\mathbb{Z}[X]$.

### Troncatures signées

Si $\mathfrak{a} = \sum_{i \ge 0} a_i p^i$ est un nombre $p$-adique, nous notons $\lceil \mathfrak{a} \rceil^{\sigma}$ l'entier $\sum_{i=0}^{\sigma-1} a_i p^i$. On définit aussi le reste signé dans la division par $p^{\tau}$ l'entier $r = \sum_{i=0}^{\tau-1} a_i p^i$ si $r \le p^{\tau}/2$, et $r - p^{\tau}$ sinon. On définit alors $\lfloor \mathfrak{a} \rfloor_{\tau}$ comme l'entier $p$-adique $(\mathfrak{a} - r)/p^{\tau}$, de sorte que

$$\mathfrak{a} = \lfloor \mathfrak{a} \rfloor_{\tau} p^{\tau} + r \quad \text{avec} \quad r \in \left\lfloor -\frac{p^{\tau}}{2}, \frac{p^{\tau}}{2} \right\rfloor.$$

Enfin on utilisera la notation $[\mathfrak{a}]_{\tau}^{\sigma} = \lceil \lfloor \mathfrak{a} \rfloor_{\tau} \rceil^{\sigma}$, qui satisfait $\mathfrak{a} = [\mathfrak{a}]_{\tau}^{\sigma} p^{\tau} + r + O(p^{\sigma})$.

Lorsqu'il est positif, un nombre entier $c$ peut simplement être vu comme un entier $p$-adique en considérant son écriture en base $p$. Lorsqu'il est négatif, son image dans $\mathbb{Z}_p$ peut être obtenue comme l'opposé de l'image de $-c$. Par exemple avec $p = 5$, l'image de $-7$ est $3 + 3p + 4p^2 + 4p^3 + 4p^4 + 4p^5 + \dots$. Dans la suite, l'écriture $[c]_{\tau}^{\sigma}$ représentera $[\mathfrak{a}]_{\tau}^{\sigma}$ en prenant pour $\mathfrak{a}$ l'image de $c$ dans $\mathbb{Z}_p$. Aussi, si $\mathfrak{Q} = \sum_{i=0}^{d} \mathfrak{Q}_i X^i \in \mathbb{Z}_p[X]$, alors on notera, par extension, $[\mathfrak{Q}]_{\tau}^{\sigma} = \sum_{i=0}^{d} [\mathfrak{Q}_i]_{\tau}^{\sigma} X^i \in \mathbb{Z}[X]$.

La fonction $[\cdot]_{\tau}^{\sigma}$ n'est pas additive à cause des retenues. Si $\mathfrak{a}_1, \dots, \mathfrak{a}_n$ sont des entiers $p$-adiques, et si $\ell_1, \dots, \ell_n$ sont des entiers positifs ou négatifs, alors on peut écrire

$$[\ell_1 \mathfrak{a}_1 + \dots + \ell_n \mathfrak{a}_n]_{\tau}^{\sigma} = [\ell_1 \mathfrak{a}_1]_{\tau}^{\sigma} + \dots + [\ell_n \mathfrak{a}_n]_{\tau}^{\sigma} + \epsilon + O(p^{\sigma}),$$

avec $\epsilon \in \mathbb{Z}$ borné par $|\epsilon| \le (\ell_1 + \dots + \ell_n)/2$.
Construction du réseau

Posons $m = s + n$ et considérons le réseau L de $\mathbb{Z}^m$ engendré par les lignes de la
matrice

$$
\left(
\begin{array}{c@{\quad}c}
1 & [\mathbb{G}_{1,0}]_{\tau}^{\sigma} \cdots [\mathbb{G}_{1,d-1}]_{\tau}^{\sigma} \\
\vdots & \vdots \\
1 & [\mathbb{G}_{s,0}]_{\tau}^{\sigma} \cdots [\mathbb{G}_{s,d-1}]_{\tau}^{\sigma} \\
\multicolumn{2}{c}{p^{\sigma-\tau}} \\
\multicolumn{2}{c}{\vdots} \\
\multicolumn{2}{c}{p^{\sigma-\tau}}
\end{array}
\right), \qquad (21.1)
$$

où $\mathbb{G}_{i,j}$ représente le coefficient de degré $j$ de $F_{\mathcal{F}_i}^{F'_i}$. Pour expliquer en quoi cette
construction est pertinente, commençons par montrer que L contient des vecteurs
« courts » provenant des facteurs irréductibles de $F$. Par le choix de $\tau$ on sait que

$$
\left[ \mu_{i,1} F_{\frac{F_1}{F}} + \dots + \mu_{i,s} F_{\frac{F_s}{F}} \right]_{\tau} = O(p^{\sigma}),
$$

et donc pour toute valeur de $\sigma \ge \tau$ on obtient

$$
\left[ \mu_{i,1} F_{\frac{F_1'}{F_1}} + \dots + \mu_{i,s} F_{\frac{F_s'}{F_s}} \right]_{\tau}^{\sigma} = O(p^{\sigma-\tau}),
$$

ce qui fournit un polynôme $\epsilon_i \in \mathbb{Z}[X]$ de norme $\|\epsilon_i\|_{\infty} \leq s/2$, tel que

$$
\mu_{i,1} \left[ F \frac{F_1'}{F_1} \right]_{\tau}^{\sigma} + \cdots + \mu_{i,s} \left[ F \frac{F_s'}{F_s} \right]_{\tau}^{\sigma} + \delta_i p^{\sigma-\tau} = \epsilon_i,
$$

où $\delta_i \in \mathbb{Z}[X]$ accumule les retenues à partir de la précision $\sigma - \tau$. Par conséquent on vient de montrer que les vecteurs $(\mu_{i,1}, \dots, \mu_{i,s}, \epsilon_{i,0}, \dots, \epsilon_{i,n-1})$, notés plus simplement $(\mu_i, \epsilon_i)$, sont dans L. Ils peuvent être qualifiés de « courts » puisqu'ils ont pour norme

$$
\|(\mu_i, \epsilon_i)\|_2 \le \sqrt{s + n(s/2)^2}.
$$

Posons $\eta = \sqrt{s + n(s/2)^2}$, et définissons W comme le réseau engendré par

$(\mu_1, \epsilon_1), \dots, (\mu_r, \epsilon_r),$

de sorte que W ⊆ L. L'étape suivante de la méthode de factorisation consiste à calculer
une base de W à partir de L.

Réduction du réseau

Nous notons $w_1, \dots, w_m$ la base réduite de L obtenue en utilisant l'Algorithmme 20.2 de réduction LLL du chapitre précédent. Nous souhaitons pouvoir en déduire les $\mu_i$ dès que $\sigma$ est suffisamment grand. Nous introduisons ensuite

$$
t = \min\{i \mid \|v_j^*\|_2 > \eta, \forall j > i\}.
$$

Le lemme suivant permet de restreindre L à un sous-réseau $\tilde{L}$ qui contient toujours W.
**Lemme 21.23** Si $v$ est un vecteur de L de norme $\|v\|_2 \le \eta$, alors il appartient au réseau $\mathcal{L}$ engendré par $w_1, \dots, w_t$. En particulier on a $W \subseteq \mathcal{L}$.

*Démonstration.* Notons $i \le m$ le plus petit entier tel que $v$ soit dans réseau engendré par $w_1, \dots, w_i$. Par définition du procédé d'orthogonalisation de Gram-Schmidt, c'est aussi le premier entier tel que $v$ est dans l'espace vectoriel engendré par $w_1^*, \dots, w_i^*$, de sorte que

$$v = \ell_i w_i + \dots + \ell_1 w_1 = \ell_i' w_i' + \dots + \ell_1' w_1',$$

avec $\ell_i' = \ell_i \ge 1$. Par conséquent $\|v\|_2 \ge \|w_i\|_2$, et nécessairement $i \le t$. ■

## Reconstruction des facteurs

Par définition de $t$, on a $\|w_i^*\|_2 \le \eta$. Par ailleurs, la Proposition 20.3 nous donne $\|w_i\|_2^2 \le 2^{t-1}\|w_t^*\|_2^2$ pour tout $i \le t$. Par conséquent, pour tout $i \le t$, on a

$$\|w_i\|_2 \le 2^{(t-1)/2} \eta \le 2^{(m-1)/2} \eta.$$

Fixons maintenant un indice $i \le t$ et examinons $w_i$. Fixons ensuite un indice $j$ de $w_i$ tel que $w_{i,j} \ne 0$. Il existe un unique entier $k$ tel que $\mu_{k,j} = 1$. On construit alors le vecteur

$$\tilde{w}_i = w_i - w_{i,j}(\mu_k, \epsilon_k),$$

qui satisfait $\tilde{w}_{i,j} = 0$ et a pour norme

$$\|\tilde{w}_i\|_2 \le \|w_i\|_2 + \|w_i\|_2 \eta \le 2^{(m-1)/2}(1+\eta)\eta.$$

Comme $\tilde{w}_i$ est dans le réseau L, on a

$$\tilde{w}_{i,1} \left[ F \frac{F_1'}{F_1} \right]_{\tau}^{\sigma} + \dots + \tilde{w}_{i,s} \left[ F \frac{F_s'}{F_s} \right]_{\tau}^{\sigma} = \phi_i + O(p^{\sigma-\tau}),$$

avec $\phi_i$ un polynôme de $\mathbb{Z}[X]$ de degré au plus $n-1$ et de norme

$$\|\phi_i\|_2 \le \|\tilde{w}_i\|_2 \le 2^{(m-1)/2}(1+\eta)\eta.$$

On considère ensuite le polynôme

$$\mathfrak{H}_i = \tilde{w}_{i,1} F \frac{F_1'}{F_1} + \dots + \tilde{w}_{i,s} F \frac{F_s'}{F_s},$$

et on écrit

$$[\mathfrak{H}_i]_{\tau}^{\sigma} = \tilde{w}_{i,1} \left[ F \frac{F_1'}{F_1} \right]_{\tau}^{\sigma} + \dots + \tilde{w}_{i,s} \left[ F \frac{F_s'}{F_s} \right]_{\tau}^{\sigma} + \psi_i + O(p^{\sigma-\tau}),$$

avec $\psi_i$ un polynôme de $\mathbb{Z}[X]$ de degré au plus $n-1$ et de norme

$$\|\psi_i\|_{\infty} \le (|\tilde{w}_{i,1}| + \dots + |\tilde{w}_{i,s}|)/2 \le \sqrt{n} \|\tilde{w}_i\|_2/2 \le \sqrt{n} 2^{(m-3)/2} (1+\eta)\eta.$$
On écrit ensuite

$$
\mathcal{H}_i = [\mathcal{H}_i]^\sigma p^\tau + \rho_i + O(p^\sigma) = (\phi_i + \psi_i) p^\tau + \rho_i + O(p^\sigma)
$$

avec $\|\rho_i\|_{\infty} \le p^{\tau/2}$. On pose $H_i = (\phi_i + \psi_i)p^{\tau} + \rho_i$. Il s'agit d'un polynôme de $\mathbb{Z}[X]$ de
norme

$$
\|H_i\|_{\infty} \le \left( \left(1 + \frac{\sqrt{n}}{2}\right)^2 \frac{(m-1)/2}{(1+\eta)\eta} + \frac{1}{2} \right) p^{\tau},
$$

et tel que $H_i = \mathcal{H}_i + O(p^\sigma)$. On pose

$$
\theta = \sqrt{n} \left( \left( 1 + \frac{\sqrt{n}}{2} \right)^2 \frac{(m-1)/2}{(1+\eta)\eta} + \frac{1}{2} \right) p^{\tau}
$$

de manière à avoir $\|H_i\|_2 \le \theta$.

Comme $\mathcal{F}_j$ divise $\mathcal{H}_i$ et $\mathcal{F}$ à la précision $p^\sigma$, alors le résultant $R_i = \text{Res}(\mathcal{H}_i, \mathcal{F})$ vaut $O(p^\sigma)$. On utilise par ailleurs le Corollaire 21.11

$$
|R_i| \le \|H_i\|_2^n \|F\|_2^{n-1} \le \Theta^n \|F\|_2^{n-1}.
$$

La condition $p^{\sigma} > 2|R_i|$ garantit alors que $R_i = 0$. Par conséquent $G_k$ divise $H_i$, ce qui implique que $w_{i,l} = w_{i,j}$ pour tout indice $l$ tel que $\mu_{k,l} = 1$. En faisant de même avec les autres valeurs de $j$ on déduit que, pour tout $i \le t$, $\tilde{w}_i$ est dans l'espace engendré par $\mu_1, \dots, \mu_r$. On vient donc de prouver que $L' = W$.

Pour retrouver les $\mu_i$ à partir de $w_1, \dots, w_t$, on peut peut calculer la forme échelonnée sur $\mathbb{Q}$ de la matrice obtenue en mettant les $w_i$ en lignes les uns au dessus des autres. Nous renvoyons le lecteur au Chapitre 8 pour les détails.

Synthèse de l’algorithme

Le méthode de factorisation est résumée dans l'Algorithme 21.4.

**Théorème 21.24** L'Algorithme 21.4 de factorisation est correct et requiert
$\tilde{O}(n^7(n + \log \|F\|_\infty)^2)$ opérations binaires.

Démonstration. Nous venons de voir tout au long de cette section que l'algorithme est correct. Il nous reste à analyser sa complexité. Le coût des étapes de (1) à (5) s'analyse comme pour l'Algorithme 21.3 : il est borné par $O(n^3 \log \|F\|_\infty)$, car $\tau \log p = \tilde{O}(n + \log \|F\|_\infty)$, et $\sigma \log p = \tilde{O}(n^2 + n \log \|F\|_\infty)$.

La construction de la matrice de l'étape (6) requiert $\tilde{O}(n^2 \sigma \log p)$ opérations, ce
qui est dominé par la réduction du réseau par LLL qui coûte ensuite $\tilde{O}(n^5 (\sigma \log p)^2) =
\tilde{O}(n^5 (n^2 + n \log \|F\|_\infty)^2)$. Le calcul de la forme échelonnée est négligeable dans ce
cas particulier. Enfin la reconstruction des facteurs peut se faire en temps quasi-
linéaire.
■

R Lorsque s est petit il est intéressant d'utiliser l'Algorithme 21.3 naïf de recombi-
naison. Aussi, avant d'utiliser l'algorithme de van Hoeij, il est utile de tester si
**Entrée** F ∈ Z[X], séparable et primitif.

**Sortie** Les facteurs irréductibles de F.

1. Trouver le plus petit nombre premier $p$ qui ne divise pas $\text{Res}(F, F')$.

2. Déterminer le premier entier $\tau$ tel que $p^{\tau} > n2^n \|F\|_2$.

3. Déterminer le premier entier $\sigma$ tel que $p^{\sigma} > 2\theta^n \|F\|_2^{n-1}$,
avec $\theta = \sqrt{n}\left(\left(1 + \frac{\sqrt{n}}{2}\right)2^{\frac{(m-1)}{2}}(1 + \eta)\eta + \frac{1}{2}\right)p^{\tau}$.

4. Calculer les facteurs unitaires irréductibles $f_1, \dots, f_s$ de F dans $\mathbb{Z}/p\mathbb{Z}[X]$.

5. Remonter la factorisation irréductible $f_1, \dots, f_s$ de F dans $\mathbb{Z}/p^\sigma \mathbb{Z}[X]$ à l'aide de l'Algorithme 21.2.

6. Construire la matrice (21.1) définissant le réseau L.

7. Utiliser l'Algorithme 20.2 du chapitre précédent pour obtenir une base réduite notée $w_1, \dots, w_m$, avec $m = s + n$.

8. Calculer $t = \min\{i \mid \|v_j^*\|_2 > \eta, \forall j > i\}$, puis la base échelonnée sur $\mathbb{Q}$ de $(w_{1,1}, \dots, w_{1,s}), \dots, (w_{t,1}, \dots, w_{t,s})$, qui n'est autre que $\mu_1, \dots, \mu_r$ à une permutation près.

9. Pour chaque $i \in \{1, \dots, r\}$, calculer $F_i$ comme la partie primitive de la préimage (signée) dans $\mathbb{Z}[X]$ de $\text{ct}(F)F_1^{\mu_{i,1}} \dots F_s^{\mu_{i,s}}$.

10. Renvoyer $F_1, \dots, F_r$.

**Algorithme 21.4 – Algorithme de factorisation de van Hoeij.**

certains facteurs $p$-adiques sont déjà des projections de facteurs rationnels. On peut en plus éventuellement tester tous les produits de deux facteurs $p$-adiques. La borne $\sigma$ pour la précision nécessaire pour que l'algorithme fonctionne est souvent surévaluée en pratique. Il est donc utile de commencer avec une précision $\approx 2\tau$, de tester si l'on trouve des facteurs, et, si non, de doubler la précision et recommencer la réduction de réseau. On peut prouver le critère d'arrêt suivant : chaque vecteur de la base échelonnée de l'étape (8) ne contient que des 0 et 1 et conduit à un diviseur de F.

Enfin, on peut essayer de ne garder que quelques colonnes sur les $n$ dernières, de sorte à accélérer la réduction de réseau. Dès qu'une factorisation de F est trouvée on peut ensuite redémarrer l'algorithme sur chacun des facteurs.

**Exemple 21.5** Prenons pour F le produit des polynômes de Swinnerton-Dyer d'indices 2 et 3 :

$$F(X) = X^{12} - 50X^{10} + 753X^8 - 4520X^6 + 10528X^4 - 6720X^2 + 576.$$

Le plus petit nombre premier $p$ qui ne divise pas le discriminant de F est $p = 11$. La factorisation de F modulo $p$ est

$$(X^2 + 2X + 10)(X^2 + 7X + 2)(X^2 + 10X + 1)(X^2 + X + 1)(X^2 + 9X + 10)(X^2 + 4X + 2).$$
On a donc $s = 6$, $\tau = 9$, $\eta \approx 10,7$, $\theta \approx 10^{15}$ et $\sigma = 217$. Après reduction du réseau L, on a $\|w_1^*\| \approx 1,4$, $\|w_2^*\| \approx 2,0$, et les autres $\|w_i^*\|$ dépassent $10^{108}$. On a alors $t = 2$ et

$$ \mu_1 = (1,0,1,0,1,1), \quad \mu_2 = (0,1,0,1,0,0), $$

$$ F_1(X) = X^8 - 40X^6 + 352X^4 - 960X^2 + 576, \quad F_2(X) = X^4 - 10X^2 + 1. $$

Sur cet exemple, dès que l'on prend $\sigma \ge 12$, on trouve $t = 2$, et on vérifie que la base échelonnée de l'étape (8) contient uniquement des 0 et 1 et conduit à des facteurs de F, ce qui est suffisant pour justifier que l'on a bien trouvé tous les facteurs.

## Notes

La première preuve de la borne de Landau-Mignotte est due à Landau en 1905, où elle a été donnée pour le produit des zéros de fonctions analytiques proches de zéro [Lan05]. Mignotte l'a redécouverte en 1974 pour des applications à la factorisation [Mig74].

L'inégalité de Mahler se trouve dans son article de 1961 [Mah61]. La preuve que nous en donnons ici est inspirée d'un article de Vaaler et Boyd [VB91a].

Le Lemme 21.13 est adapté d'une preuve d'Erdős du postulat de Bertrand [Erd32]. Il peut être raffiné [HW08, Chapitre 22] en

$$ \prod_{\substack{2 \le p \le k \\ p \text{ premier}}} p = \exp((1 + o(1))k). $$

En 2001, Gerhard [Ger01] a montré que le coût binaire de la factorisation sans carré en degré $n$ pouvait être abaissé à $\tilde{O}(n(n + \|F\|_{\infty}))$ en moyenne, avec un algorithme effectuant des choix aléatoires. Plus généralement, l'approche multimodulaire pour le calcul de la factorisation séparable est traitée dans l'article de Lecerf de 2008 [Lec08].

La construction des nombres $p$-adiques remonte aux travaux de Hensel en 1918. L'Algorithmme 21.3 naïf a été popularisé en calcul formel par Zassenhaus à la fin des années soixante [Zas69]. Une implémentation comportant de nombreuses optimisations a été réalisée par Abbott, Shoup et Zimmermann [ASZ00].

Il existe des algorithmes classiques permettant d'énumérer tous les sous-ensembles d'une taille donnée les uns après les autres sans avoir besoin de les stocker tous en mémoire [NW78].

Le temps polynomial pour la factorisation des polynômes de $\mathbb{Q}[X]$ a été obtenu par A. Lenstra, H. Lenstra et L. Lovász en 1982 [LLL82], avec une borne de complexité binaire $O(n^{12} + n^9 \log^3 \|F\|_{\infty})$. Schönhage a ensuite obtenu la complexité $O(n^6 + n^4 \log^2 \|F\|_{\infty})$, en calculant les polynômes minimaux des racines complexes de $F$ [Sch84]. Néanmoins, les coûts pratiques de ces algorithmes sont très élevés, et ils n'ont jamais été vraiment compétitifs par rapport à l'approche naïve.

L'algorithme de van Hoeij remonte à 2002 [Hoe02a] : bien que la borne de complexité n'était pas prouvée, une première implémentation permettait de factoriser des polynômes qui étaient auparavant hors de portée. La preuve de la complexité polynomiale est due à Belabas, van Hoeij, Klüners et Steel [Bel+09]. La présentation
qui en est faite dans ce chapitre suit cet article, qui arrive à une borne de complexité $\tilde{O}(n^8+n^6 \log^2 \|F\|_\infty)$, en utilisant un algorithme de réduction de réseau plus performant que celui du chapitre précédent.

Plusieurs travaux ont été poursuivis pour prouver une borne de complexité $\tilde{O}(s^6 + P(s, \log \|F\|_\infty))$ dans le pire cas, où P est un polynôme de degré total 5, qui se rapproche des coûts observés en pratique : tout d'abord dans la thèse de doctorat de Novocin [Nov08] puis dans ses articles en collaboration avec Hart, van Hoeij, Stéhlé et Villard [HHN11; NH09; NSV11].

Bibliographie

ASZ00 ABBOTT, John, Victor SHOUP et Paul ZIMMERMANN (2000). « Factorization in $\mathbb{Z}[x]$ : the searching phase ». In : *ISSAC'00 : International Symposium on Symbolic and Algebraic Computation*. St. Andrews, Scotland : ACM Press, p. 1-7.

Bel+09 BELABAS, Karim, Mark van HOEIJ, Jürgen KLÜNERS et Allan STEEL (2009). « Factoring polynomials over global fields ». In : *Journal de Théorie des Nombres de Bordeaux*, vol. 21, n°1, p. 15-39.

Erd32 ERDŐS, Paul (1932). « Beweis eines Satzes von Tschebyschef ». In : *Acta Litterarum ac Scientiarum, Szeged*, n°5, p. 194-198.

Ger01 GERHARD, Jürgen (2001). « Fast Modular Algorithms for Squarefree Factorization and Hermite Integration ». In : *Applicable Algebra in Engineering, Communication and Computing*, vol. 11, n°3, p. 203-226.

HHN11 HART, William, Mark van HOEIJ et Andrew NOVOCIN (2011). « Practical polynomial factoring in polynomial time ». In : *ISSAC'11 : International Symposium on Symbolic and Algebraic Computation*. ACM Press, p. 163-170.

Hoe02a HOEIJ, Mark van (2002). « Factoring polynomials and the knapsack problem ». In : *Journal of Number Theory*, vol. 95, n°2, p. 167-189.

HW08 HARDY, G. H. et E. M. WRIGHT (2008). *An introduction to the theory of numbers*. 6ᵉ éd. Oxford University Press.

Lan05 LANDAU, E. (1905). « Sur quelques théorèmes de M. Petrovitch relatifs aux zéros des fonctions analytiques ». In : *Bulletin de la S. M. F*. vol. 33, p. 251-261.

Lec08 LECERF, Grégoire (2008). « Fast separable factorization and applications ». In : *Applicable Algebra in Engineering, Communication and Computing*, vol. 19, n°2, p. 135-160.

LLL82 LENSTRA, A. K., H. W. LENSTRA Jr. et L. LOVÁSZ (1982). « Factoring polynomials with rational coefficients ». In : *Mathematische Annalen*, vol. 261, n°4, p. 515-534.

Mah61 MAHLER, K. (1961). « On the zeros of the derivative of a polynomial ». In : *Proceedings of the Royal Society of London A : Mathematical, Physical and Engineering Sciences*, vol. 264, n°1317, p. 145-154.

Mig74 MIGNOTTE, M. (1974). « An inequality about factors of polynomials ». In : *Mathematics of Computation*, vol. 28, p. 1153-1157.
NH09 Novocin, Andy et Mark van Hoeij (2009). « Factoring univariate polynomials over the rationals ». In : *ACM Communications in Computer Algebra*, vol. 42, n°3, p. 157-157.

Nov08 Novocin, Andrew (2008). « Factoring univariate polynomials over the rationals ». Thèse de doctorat. Department of Mathematics, Florida State University, Tallahassee.

NSV11 Novocin, Andrew, Damien Stehlé et Gilles Villard (2011). « An LLL-reduction algorithm with quasi-linear time complexity ». In : *Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing*. STOC '11. Extended abstract. New York, NY, USA : ACM, p. 403-412.

NW78 Nijenhuis, Albert et Herbert S. Wilf (1978). *Combinatorial algorithms for computers and calculators*. Academic Press.

Sch84 Schönhage, Arnold (1984). « Factorization of univariate integer polynomials by diophantine approximation and an improved basis reduction algorithm ». In : *Automata, Languages and Programming : 11th Colloquium Antwerp, Belgium, July 16-20, 1984*. Éd. par Jan Paredaens. Berlin, Heidelberg : Springer Berlin Heidelberg, p. 436-447.

VB91a Vaaler, Jeff et David W. Boyd (1991). « 6613, Mahler's inequality ». In : *The American Mathematical Monthly*, vol. 98, n°5, p. 451-452.

Zas69 Zassenhaus, Hans (1969). « On Hensel factorization I ». In : *Journal of Number Theory*, vol. 1, n°1, p. 291-311.
# 22. Factorisation des polynômes à plusieurs variables

## Résumé

La factorisation des polynômes à plusieurs variables réutilise les techniques des chapitres précédents : des bornes sur les degrés partiels des facteurs, l'algorithme de Newton-Hensel, et la résolution des systèmes linéaires. Nous commençons par présenter des algorithmes généraux puis quelques variantes plus efficaces dans des cas particuliers. Ensuite nous expliquons comment ramener le cas de plus de trois variables à deux variables seulement.

Tout au long de ce chapitre $\mathbb{K}$ représente un corps effectif pour lequel on dispose d'un algorithme de factorisation dans $\mathbb{K}[X]$, et $F$ désigne le polynôme de $\mathbb{K}[X_1, \dots, X_n]$ qu'on souhaite factoriser. Son degré partiel en $X_n$ est noté $d$, et son degré total en les seules variables $X_1, \dots, X_{n-1}$ est noté $\eta = \text{deg}_{X_1, \dots, X_{n-1}}(F)$.

Il est souvent utile de voir $F$ comme le polynôme $\tilde{F}$ en la variable $X_n$ sur l'anneau des coefficients $\mathbb{K}[X_1, \dots, X_{n-1}]$. Le coefficient de tête en $X_n$ de $F$, noté $\text{ct}_{X_n}(F)$, correspond au coefficient de tête de $\tilde{F}$. Le contenu de $F$ en $X_n$ est alors défini comme le contenu de $\tilde{F}$, c'est-à-dire le pgcd des coefficients de $\tilde{F}$. La partie primitive de $F$ en $X_n$ est la partie primitive de $\tilde{F}$, c'est-à-dire le quotient de $F$ par son contenu en $X_n$. Nous dirons aussi que $F$ est séparable en $X_n$ lorsque $\tilde{F}$ est séparable.

Le lemme de Gauss (Proposition 21.1) affirmant que le contenu d'un produit de polynômes est égal au produit de leurs contenus, a pour conséquence pratique de réduire la factorisation de $\mathbb{K}[X_1, \dots, X_n]$ à celle d'un contenu en $X_n$ et celle d'un polynôme primitif en $X_n$ (comme prouvé dans le Théorème 21.2). Attendu que la factorisation du contenu peut se faire par récurrence sur le nombre de variables, nous supposerons tout au long de ce chapitre que $F$ est primitif en $X_n$. Ensuite, en utilisant les algorithmes du Chapitre 18, nous pouvons supposer de plus que $F$ est séparable en $X_n$.
## 22.1 Algorithme naïf par remontée

Posons $\Delta_{X_n}(F)$, le résultant en $X_n$ suivant :

$$ \Delta_{X_n}(F) := \mathrm{Res}_{X_n}\left(F, \frac{\partial F}{\partial X_n}\right) \in \mathbb{K}[X_1, \dots, X_{n-1}]. $$

Nous commençons par expliquer comment se ramener au cas où $\Delta_{X_n}(F)$ ne s'annule pas à l'origine.

### Factorisation locale

Le lemme suivant permet de vérifier que $\Delta_{X_n}(F)$ ne s'annule pas à l'origine, sans avoir à calculer $\Delta_{X_n}(F)$ explicitement.

**Lemme 22.1** La condition $\Delta_{X_n}(F)(0, \dots, 0) \neq 0$ est équivalente à

$$ \mathrm{ct}_{X_n}(F)(0, \dots, 0) \neq 0 \text{ et } \mathrm{Res}_{X_n}\left(F(0, \dots, 0, X_n), \frac{\partial F}{\partial X_n}(0, \dots, 0, X_n)\right) \neq 0. $$

*Démonstration.* La preuve est analogue à celle de Lemme 21.14 du chapitre précédent.

<figure><img src="image_60.png" /></figure>

Pour se ramener au cas où $\Delta_{X_n}(F)$ ne s'annule pas à l'origine, il suffit de chercher un point $(a_1, \dots, a_{n-1})$ dans $\mathbb{K}^{n-1}$ tel que $\mathrm{ct}_{X_n}(F)(a_1, \dots, a_{n-1}) \neq 0$ et

$$ \mathrm{Res}_{X_n}\left(F(a_1, \dots, a_{n-1}, X_n), \frac{\partial F}{\partial X_n}(a_1, \dots, a_{n-1}, X_n)\right) \neq 0, $$

puis de remplacer F par $F(X_1 + a_1, \dots, X_{n-1} + a_{n-1}, X_n)$. Si jamais $\mathbb{K}$ est un corps fini de cardinal trop petit pour trouver un tel point, alors on peut factoriser F dans une extension algébrique suffisamment grande de $\mathbb{K}$ et nous verrons à la fin du chapitre comment en déduire la factorisation sur $\mathbb{K}$.

À partir de maintenant nous supposons que $\Delta_{X_n}(F)$ ne s'annule pas à l'origine, et nous notons $\mathfrak{f}_1, \dots, \mathfrak{f}_s$ les facteurs irréductibles unitaires de $F(0, \dots, 0, X_n)$. Du fait que $F(0, \dots, 0, X_n)$ est séparable de même degré que $F$ en $X_n$, la méthode de Newton-Hensel vue au chapitre précédent nous permet de calculer la factorisation irréductible de $F$ dans $\mathbb{K}[[X_1, \dots, X_n]]\lbrack X_n \rbrack$ à n'importe quelle précision souhaitée. Nous noterons $\mathfrak{f}_1, \dots, \mathfrak{f}_s$ les facteurs unitaires de $F$ dans $\mathbb{K}[[X_1, \dots, X_n]]\lbrack X_n \rbrack$, dis locaux, calculés à une précision notée $\sigma$, que nous préciserons le moment venu, avec la convention que $\mathfrak{f}_i(0, \dots, 0, X_n)$ coïncide avec $\mathfrak{f}_i(X_n)$.

### Recherche exhaustive des recombinations

Si $\sigma \ge \eta + 1$, alors chaque diviseur $G$ de $F$ s'écrit comme le produit

$$ \mathrm{ct}_{X_n}(G) \mathfrak{f}_1^{\ell_1} \cdots \mathfrak{f}_s^{\ell_s} + O((X_1, \dots, X_{n-1})^{\sigma}), $$

où les $\ell_i$ valent 0 ou 1. On pourrait supposer que la factorisation de $\mathrm{ct}_{X_n}(F)$ est disponible, par récurrence sur le nombre de variables. Cela nous conduirait directement à
**Entrée** F ∈ K[X₁,...,Xₙ], primitif en Xₙ, tel que F(0,...,0,Xₙ) soit séparable de degré degXₙ(F).

**Sortie** Les facteurs irréductibles de F.

1. Calculer les facteurs unitaires irréductibles f₁,...,f_s de F(0,...,0,Xₙ) dans K[Xₙ].

2. Poser σ = 1 + degX₁,...,Xₙ₋₁(F), et remonter la factorisation irréductible f₁,...,f_s de F dans K[[X₁,...,Xₙ₋₁]]][Xₙ], à la précision (X₁,...,Xₙ₋₁)° à l'aide de l'Algorithme 21.2 du chapitre précédent.

3. Initialiser S avec {1,...,s}, puis T avec {}, et L avec la liste vide.

4. Parcourir les sous-ensembles E non vides de S par taille croissante au plus (s - card(T))/2 et disjoints de T :

a. calculer ctXₙ(F) ∏ₐ∈E Fₑ à la précision (X₁,...,Xₙ₋₁)°, puis sa préimage H dans K[X₁,...,Xₙ];

b. calculer la partie primitive G de H en Xₙ;

c. si G divise F alors l'insérer dans L, remplacer T par T ∪ E, et F par F/G.

5. Si deg(F) ≥ 1 alors insérer F dans L.

6. Renvoyer L.

Algorithme 22.1 – Méthode naïve de factorisation par remontée et recombinaison.

un algorithme énumérant tous les vecteurs possibles pour (ℓ₁,...,ℓ_s) et tous les diviseurs de ctXₙ(F). Néanmoins, pour limiter le coût exponentiel induit par le parcours des diviseurs de ctXₙ(F), nous préférons nous y prendre différemment. Comme on a degX₁,...,Xₙ₋₁(G) ≤ degX₁,...,Xₙ₋₁(F) et comme ctXₙ(F)/ctXₙ(G)G est aussi un diviseur de F, alors on a la borne un peu plus fine

$$ \deg_{X_1, \dots, X_{n-1}} (\mathrm{ct}_{X_n}(F) / \mathrm{ct}_{X_n}(G) G) \leq \eta. $$

Par conséquent, ctXₙ(F) F₁ℓ₁...F_sℓ_s est un polynôme de degré total au plus η en les variables X₁,...,Xₙ₋₁.

À l'inverse, si l'on nous donne un vecteur (ℓ₁,...,ℓ_s) ∈ {0,1}⁵, nous pouvons d'abord construire le polynôme H ∈ K[X₁,...,Xₙ] comme la préimage de

$$ \mathrm{ct}_{X_n}(F) F_1^{\ell_1} \cdots F_s^{\ell_s}, $$

qui ne conserve que les termes en degré total au plus η en X₁,...,Xₙ₋₁. Ensuite, on calcule la partie primitive G de H en Xₙ. Enfin, on teste si G divise F. Le choix de la précision σ ≥ η + 1 nous assure que nous pouvons découvrir tous les facteurs irréductibles de F en testant tous les vecteurs (ℓ₁,...,ℓ_s) de {0,1}⁵. Cette approche est résumée dans l'Algorithme 22.1 (à comparer avec l'Algorithme 21.3 en page 388).

Définir des structures de données pour représenter les polynômes à plusieurs variables et analyser les coûts des opérations arithmétiques, nous éloignerait trop des
objectifs de cet ouvrage. Dans ce chapitre, nous analyserons le coût des algorithmes de factorisation dans le seul cas où $n = 2$.

**Proposition 22.2** L'Algorithme 22.1 est correct. Si $n = 2$, il effectue une factorisation irréductible de degré $d$ dans $K[X_2]$, plus $\tilde{O}(\eta^{2d})$ opérations arithmétiques dans $K$.

*Démonstration.* Nous venons déjà de justifier que tous les polynômes insérés dans la liste $L$ sont des diviseurs de $F$. Le fait de parcourir les sous-ensembles $E$ par taille croissante assure que les facteurs trouvés sont irréductibles. Enfin, quand on arrive à l'étape (5), cela signifie qu'aucun facteur de la valeur courante de $F$ n'est obtenu à partir d'au plus la moitié de ses facteurs locaux. Par conséquent, un tel polynôme $F$ est soit constant soit irréductible. Par ces faits, nous déduisons que l'algorithme est correct.

La première étape correspond à la factorisation à une variable de l'énoncé de la proposition. Le coût de la remontée de Newton-Hensel de l'étape (2) est quasi-linéaire, par la Proposition 21.20 du chapitre précédent.

Pour le calcul de $H$, on construit l'arbre des sous-produits présenté dans la Section 5.4, de sorte que la Proposition 5.5 implique un coût quasi-linéaire. Pour le calcul du contenu de $H$ on peut utiliser successivement $d$ fois l'algorithme rapide de pgcd, pour obtenir aussi un coût quasi-linéaire. Pour tester si $G$ divise $F$ on peut calculer $F/G$ dans $K[[X_1, \dots, X_n][X_n]]$ à la précision $(X_1, \dots, X_{n-1})^\sigma$ puis la préimage $Q$ de ce quotient dans $K[X_1, \dots, X_n]$ et enfin vérifier que $F$ est égal à $GQ$. On obtient ainsi un coût quasi-linéaire.

Enfin, le nombre de candidats $G$ à construire et tester dans l'étape (6), tant que $F$ et $S$ ne changent pas, est borné par le nombre de sous-ensembles de $S \setminus T$ de taille au plus $(s - \text{card}(T))/2$, c'est-à-dire $2^{s-\text{card}(T)}-1$. ■

**Exemple 22.1** Prenons $K = F_p$ avec $p = 101$, et

$$F(X_1, X_2) = X_2^4 + 99X_2^3 + 100X_2^2 + (2X_1^2 + 2)X_2 + 100X_1^4 + 100X_1^2.$$

Le polynôme $F(0, X_2) = X_2^4 + 99X_2^3 + 100X_2^2 + 2X_2$ est séparable. On trouve $d = 4$, $\eta = 4$, et $s = 4$. Les facteurs locaux à la précision $X_1^5$ sont :

$$F_1 = X_2 + 50X_1^2 + 63X_1^4 + O(X_1^5),$$

$$F_2 = X_2 + 99 + 51X_1^2 + 38X_1^4 + O(X_1^5),$$

$$F_3 = X_2 + 100 + 50X_1^2 + 38X_1^4 + O(X_1^5),$$

$$F_4 = X_2 + 1 + 51X_1^2 + 63X_1^4 + O(X_1^5).$$

L'algorithme commence par tester si l'une des préimages des $F_i$ divise $F$, ce qui n'est pas le cas. Il parcourt ensuite les sous-ensembles $E = \{i, j\}$ de taille 2 de $\{1, 2, 3, 4\}$ et teste si l'une des préimages de $F_i F_j$ divise $F$. On trouve juste $\{1, 2\}$ et $\{3, 4\}$, et on obtient $r = 2$ facteurs irréductibles $F_1 = X_2^2 + 99X_2 + X_1^2$ et $F_2 = X_2^2 + 100X_1^2 + 100$.
Les optimisations vues dans la Section 21.3 du chapitre précédent s'adaptent aisément ici.

## 22.2 Recombinaison des dérivées logarithmiques

Nous présentons dans cette section un algorithme de factorisation fonctionnant en temps polynomial, sous les mêmes hypothèses que dans la section précédente. Et comme pour l'algorithme précédent, nous commençons par calculer une factorisation locale de F en $X_n$, mais jusqu'à une précision plus élevée de sorte à pouvoir résoudre le problème de recombinaison au moyen d'algèbre linéaire. L'idée clé est la même que dans le chapitre précédent : si F se factorise en $F_1 \cdots F_r$ alors le calcul des dérivées logarithmiques en $X_n$ conduit à

$$ \frac{\partial F}{\partial X_n} = \frac{F}{F_1} \frac{\partial F_1}{\partial X_n} + \cdots + \frac{F}{F_s} \frac{\partial F_s}{\partial X_n}, $$

ce qui permet, d'une certaine façon, de « linéariser » le problème.

### Dérivées logarithmiques

Nous continuons de noter $F_1, \dots, F_s$ les facteurs locaux unitaires de F en précision $(X_1, \dots, X_{n-1})^\sigma$. Pour chaque facteur irréductible $F_i$ de F on définit le vecteur $\mu_i \in \{0, 1\}^s$ par l'égalité

$$ F_i = \text{ct}_{X_n}(F_i) F_1^{\mu_{i,1}} \cdots F_s^{\mu_{i,s}} + O((X_1, \dots, X_{n-1})^{\sigma}). $$

En prenant la dérivée logarithmique et en multipliant par F les deux membres de cette égalité, nous obtenons :

$$ \frac{F}{F_i} \frac{\partial F_i}{\partial X_n} = \mu_{i,1} \frac{F}{F_1} \frac{\partial F_1}{\partial X_n} + \cdots + \mu_{i,s} \frac{F}{F_s} \frac{\partial F_s}{\partial X_n} + O((X_1, \dots, X_{n-1})^{\sigma-1}). $$

Si G est un diviseur primitif de F qui s'écrit

$$ G = \text{ct}_{X_n}(G) F_1^{\ell_1} \cdots F_s^{\ell_s} + O((X_1, \dots, X_{n-1})^{\sigma}), $$

avec $(\ell_1, \dots, \ell_s) \in \{0, 1\}^s$, alors $\frac{F}{G} \frac{\partial G}{\partial X_n}$ est de degré total en $X_1, \dots, X_{n-1}$ au plus $\eta$ et on a

$$ \frac{F}{G} \frac{\partial G}{\partial X_n} = \ell_1 \frac{F}{F_1} \frac{\partial F_1}{\partial X_n} + \cdots + \ell_s \frac{F}{F_s} \frac{\partial F_s}{\partial X_n} + O((X_1, \dots, X_{n-1})^{\sigma-1}). $$

Observons que $(\ell_1, \dots, \ell_s)$ est la somme d'un sous-ensemble des $\mu_i$. On obtient ainsi la propriété suivante satisfaite par les $\ell_i$ :

$$ \ell_1 \frac{F}{F_1} \frac{\partial F_1}{\partial X_n} + \cdots + \ell_s \frac{F}{F_s} \frac{\partial F_s}{\partial X_n} $$

est un polynôme de degré total au plus $\eta$ en $X_1, \dots, X_{n-1}$, modulo $(X_1, \dots, X_{n-1})^\sigma$. Nous allons montrer que cette condition est suffisante pour trouver des diviseurs de F lorsque $\sigma$ est suffisamment grand.
## Troncatures

Si $\mathfrak{a}$ est une série entière, nous notons $[\mathfrak{a}]^\sigma$ le polynôme obtenu à partir des seuls termes de $\mathfrak{a}$ de degrés totaux au plus $\sigma - 1$. On définit ensuite $[\mathfrak{a}]_\tau$ comme la série obtenue supprimant tous les termes de $\mathfrak{a}$ de degrés totaux au plus $\tau - 1$ et on note

$$[\mathfrak{a}]_{\tau}^{\sigma} = [\mathfrak{a}]_{\tau}^{\sigma}.$$

Contrairement au chapitre précédent, la fonction $[\cdot]_\tau^\sigma$ est linéaire : si $\mathfrak{a}_1, \dots, \mathfrak{a}_s$ sont des séries, et si $\ell_1, \dots, \ell_s$ sont dans $\mathbb{K}$, alors on peut écrire

$$[\ell_1 \mathfrak{a}_1 + \dots + \ell_s \mathfrak{a}_s]_{\tau}^{\sigma} = \ell_1 [\mathfrak{a}_1]_{\tau}^{\sigma} + \dots + \ell_s [\mathfrak{a}_s]_{\tau}^{\sigma} + O((X_1, \dots, X_{n-1})^{\sigma}).$$

Si $\mathfrak{P} = \mathfrak{P}_0 + \mathfrak{P}_1 X_n + \dots + \mathfrak{P}_m X_n^m$ est un polynôme de $\mathbb{K}[[X_1, \dots, X_{n-1}]]\{X_n\}$, on étend naturellement la notation coefficient par coefficient comme suit :

$$[\mathfrak{P}]_{\tau}^{\sigma} = [\mathfrak{P}_0]_{\tau}^{\sigma} + [\mathfrak{P}_1]_{\tau}^{\sigma} X_n + \dots + [\mathfrak{P}_m]_{\tau}^{\sigma} X_n^m.$$

On introduit les polynômes

$$\mathfrak{G}_i = \left[ \frac{\mathrm{F}}{\mathrm{F}_i} \frac{\partial \mathrm{F}_i}{\partial X_n} \right]_{\eta+1}^{\sigma-1},$$

puis le système linéaire $L$ en les inconnues $\ell_1, \dots, \ell_n$ dans $\mathbb{K}$ dont les equations sont :

$$\ell_1 \mathfrak{G}_1 + \dots + \ell_s \mathfrak{G}_s = 0. \qquad (22.1)$$

**Proposition 22.3** Si $\sigma \ge 2 + \eta(2d - 1)$ alors $\mu_1, \dots, \mu_r$ est une base des solutions de $L$.

*Démonstration.* Par construction, les $\mu_i$ sont bien des solutions du système. Notons $\ell = (\ell_1, \dots, \ell_n)$ une solution non nulle de $L$. Notons $j$ un indice tel que $\ell_j \ne 0$, et $k$ l'indice tel que $\mu_{k,j} = 1$. On définit $\tilde{\ell} = \ell - \ell_j \mu_k$, qui satisfait $\tilde{\ell}_j = 0$. On considère ensuite

$$\mathfrak{H} = \tilde{\ell}_1 \frac{\mathrm{F}}{\mathrm{F}_1} \frac{\partial \mathrm{F}_1}{\partial X_n} + \dots + \tilde{\ell}_s \frac{\mathrm{F}}{\mathrm{F}_s} \frac{\partial \mathrm{F}_s}{\partial X_n} + O((X_1, \dots, X_{n-1})^{\sigma-1}),$$

puis $H = [\mathfrak{H}]^{\eta+1}$. Par construction on a alors : $\mathfrak{H} = H + O((X_1, \dots, X_{n-1})^{\sigma-1})$ et $\mathfrak{F}_j$ divise $H$ à la précision $O((X_1, \dots, X_{n-1})^{\sigma-1})$.

Par la multiplicativité du résultant, le polynôme

$$R = \mathrm{Res}_{X_n}(\mathrm{F}, H) \in \mathbb{K}[X_1, \dots, X_{n-1}]$$

s'annule donc à la précision $O((X_1, \dots, X_{n-1})^{\sigma-1})$. Comme son degré total est au plus $\eta(2d - 1)$, l'hypothèse sur la précision $\sigma$ implique que $R$ est le polynôme nul. Par conséquent, le polynôme $\mathfrak{F}_k$, qui est multiple de $\mathfrak{F}_j$, divise $H$, ce qui prouve que $\tilde{\ell}_l = 0$ pour tout indice $l$ tels que $\mu_{k,l} = 1$.

En procédant de même avec les autres indices $j$ de $\ell$, nous pouvons déduire que $\ell$ est bien dans l'espace des $\mu_i$, ce qui conclut la preuve. ■
**Entrée** $F \in \mathbb{K}[X_1, \dots, X_n]$, primitif et tel que $F(0, \dots, 0, X_n)$ soit séparable en $X_n$ de degré $d = \text{deg}_{X_n}(F)$.

**Sortie** Les facteurs irréductibles de $F$.

1. Calculer les facteurs unitaires irréductibles $f_1, \dots, f_s$ de $F(0, \dots, 0, X_n)$ dans $\mathbb{K}[X_n]$.

2. Poser $\eta = \text{deg}_{X_1, \dots, X_{n-1}}(F)$, puis $\sigma = 2 + \eta(2d - 1)$, et monter la factorisation irréductible $f_1, \dots, f_s$ de $F$ dans $\mathbb{K}[[X_1, \dots, X_{n-1}]][X_n]$ à la précision $(X_1, \dots, X_{n-1})^{\sigma}$ à l'aide de l'Algorithme 21.2 du chapitre précédent.

3. Construire la matrice $L$ définie dans (22.1).

4. Calculer la base échelonnée réduite des solutions de $L$, qui n'est autre que $\mu_1, \dots, \mu_r$.

5. Pour chaque $i \in \{1, \dots, r\}$, calculer $F_i$ comme la partie primitive de $\text{ct}_{X_n}(F) F_1^{\mu_{i,1}} \dots F_s^{\mu_{i,s}} \rvert_{\eta+1}$.

6. Renvoyer $F_1, \dots, F_r$.

**Algorithme 22.2** – Algorithme rapide de factorisation à plusieurs variables.

### Synthèse de l'algorithmme

La méthode de factorisation basée sur les idées que nous venons de présenter est résumée dans l'Algorithme 22.2. Nous notons $\theta$ un exposant réalisable pour la complexité du produit des matrices au sens du Chapitre 8 : deux matrices de taille $n \times n$ peuvent être multipliées en temps $O(n^\theta)$.

**Théorème 22.4** L'Algorithme 22.2 est correct. Si $n=2$, il nécessite de factoriser un polynôme de degré $d$ dans $\mathbb{K}[X_2]$, plus $\tilde{O}(\eta d^{\theta+1})$ opérations arithmétiques dans $\mathbb{K}$.

*Démonstration.* La preuve de l'algorithmme découle de la Proposition 22.3 qui garantit l'assertion de l'étape (4). Supposons maintenant $n=2$, et analysons la complexité. L'étape (2) coûte $\tilde{O}(\eta d^2)$ opérations dans $\mathbb{K}$, par la Proposition 21.20 du Chapitre précédent. Le calcul de chaque $\mathfrak{G}_i$ peut se faire en temps $\tilde{O}(\eta ds)$ par le lemme suivant. Par conséquent le coût de l'étape (3) est $\tilde{O}(\eta d^3)$.

Le système linéaire comporte $O(d)$ inconnues et $O(\eta d^2)$ équations, une base des solutions peut être calculée en temps $\tilde{O}(\eta d^{\theta+1})$. Comme les $\mu_i$ forment une base orthogonale très particulière, une base échelonnée des solutions de $L$ peut être déduite en temps linéaire.

La reconstruction des facteurs à l'étape (5) est réalisable en temps quasi-linéaire en utilisant les arbres des sous-produits. ■
**Exemple 22.2** Avec le polynôme F de l'Exemple 22.1, nous obtenons

$$ \frac{F}{F_1} \frac{\partial F_1}{\partial X_n} = X_2^3 + (99 + 51X_1^2 + 38X_1^4 + 19X_1^6 + 75X_1^8 + O(X_1^{10}))X_2^2 \\ + (100 + 100X_1^2 + O(X_1^{10}))X_2 \\ + 2 + 52X_1^2 + 12X_1^4 + 44X_1^6 + 7X_1^8 + O(X_1^{10}), $$

$$ \frac{F}{F_2} \frac{\partial F_2}{\partial X_n} = X_2^3 + (50X_1^2 + 63X_1^4 + 82X_1^6 + 26X_1^8 + O(X_1^{10}))X_2^2 \\ + (100 + 100X_1^2 + O(X_1^{10}))X_2 \\ + 51X_1^2 + 89X_1^4 + 57X_1^6 + 94X_1^8 + O(X_1^{10}), $$

$$ \frac{F}{F_3} \frac{\partial F_3}{\partial X_n} = X_2^3 + (100 + 51X_1^2 + 63X_1^4 + 19X_1^6 + 26X_1^8 + O(X_1^{10}))X_2^2 \\ + (99 + 76X_1^4 + 63X_1^6 + 49X_1^8 + O(X_1^{10}))X_2 \\ + X_1^2 + 51X_1^4 + 63X_1^6 + 19X_1^8 + O(X_1^{10}), $$

$$ \frac{F}{F_4} \frac{\partial F_4}{\partial X_n} = X_2^3 + (98 + 50X_1^2 + 38X_1^4 + 82X_1^6 + 75X_1^8 + O(X_1^{10}))X_2^2 \\ + (2 + 2X_1^2 + 25X_1^4 + 38X_1^6 + 52X_1^8 + O(X_1^{10}))X_2 \\ + 100X_1^2 + 50X_1^4 + 38X_1^6 + 82X_1^8 + O(X_1^{10}). $$

Si on prend $\sigma = 8$, alors on trouve le système linéaire

$$ \begin{aligned} 44\ell_1 + 57\ell_2 + 63\ell_3 + 38\ell_4 &= 0, \\ 63\ell_3 + 38\ell_4 &= 0, \\ 19\ell_1 + 82\ell_2 + 19\ell_3 + 82\ell_4 &= 0. \end{aligned} $$

La base échelonnée des solutions est $\mu_1 = (1, 1, 0, 0)$ et $\mu_2 = (0, 0, 1, 1)$. Avec cet exemple, on trouve donc la factorisation de F sans avoir besoin d'aller à la borne de précision $2 + \eta(2d - 1) = 30$. Il est donc très utile en pratique d'essayer des précisions plus petites plutôt que d'utiliser directement la borne.

## 22.3 Algorithme de Lecerf

Lorsque la caractéristique $p$ de $K$ est nulle ou bien non nulle mais suffisamment grande, il est possible d'améliorer nettement la borne de précision $\sigma$ de l'algorithme précédent, en changeant de système linéaire L. C'est ce que nous allons montrer dans les paragraphes suivants.

Soit $G$ un polynôme de degré au plus $d-1$ en $X_n$ et de degré total en les variables $X_1, \dots, X_{n-1}$ au plus $\eta$. On note $\varphi_1, \dots, \varphi_d$ les racines de $F$ vu comme un polynôme de $\mathbb{K}[[X_1, \dots, X_{n-1}]]|_{X_n}$. En notant $\rho_i$ le résidu de $G/F$ en $\varphi_i$,

$$ \rho_i = \frac{G(X_1, \dots, X_{n-1}, \varphi_i)}{\frac{\partial F}{\partial X_n}(X_1, \dots, X_{n-1}, \varphi_i)}, $$
on a la décomposition en éléments simples de G/F suivante :

$$ \frac{G}{F} = \frac{\rho_1}{X_n - \varphi_1} + \dots + \frac{\rho_d}{X_n - \varphi_d}. $$

Pour tout indice $k \le n-1$, la dérivée partielle de $\rho_i$ en $X_k$ est donnée par

$$ \frac{\partial \rho_i}{\partial X_k} = \frac{N_k(X_1, \dots, X_{n-1}, \varphi_i, \frac{\partial \varphi_i}{\partial X_k})}{\frac{\partial F}{\partial X_n}(X_1, \dots, X_{n-1}, \varphi_i)^2}, $$

où

$$ N_k(X_1, \dots, X_n, Y) = \left( \frac{\partial G}{\partial X_k} + \frac{\partial G}{\partial X_n} Y \right) \frac{\partial F}{\partial X_n} - G \left( \frac{\partial^2 F}{\partial X_k X_n} + \frac{\partial^2 F}{\partial X_n^2} Y \right). $$

Ensuite, en utilisant

$$ \frac{\partial \varphi_j}{\partial X_k} = - \frac{\frac{\partial F}{\partial X_k}}{\frac{\partial F}{\partial X_n}} $$

et en posant

$$ P_k(X_1, \dots, X_n) = \left( \frac{\partial G}{\partial X_k} \frac{\partial F}{\partial X_n} - \frac{\partial G}{\partial X_n} \frac{\partial F}{\partial X_k} \right) \frac{\partial F}{\partial X_n} - G \left( \frac{\partial^2 F}{\partial X_k X_n} \frac{\partial F}{\partial X_n} - \frac{\partial^2 F}{\partial X_n^2} \frac{\partial F}{\partial X_k} \right), \quad (22.2) $$

on parvient à exprimer la dérivée du résidu de façon purement algébrique en terme de $\varphi_i$ :

$$ \frac{\partial \rho_i}{\partial X_k} = \frac{P_k(X_1, \dots, X_{n-1}, \varphi_j)}{\frac{\partial F}{\partial X_n}(X_1, \dots, X_{n-1}, \varphi_j)^3}. $$

La nullité de $\frac{\partial \rho_i}{\partial X_k}$ pour tout $i \in \{1, \dots, s\}$ est équivalente à la divisibilité de $P_k$ par F dans $\bar{\mathbb{K}}[[X_1, \dots, X_{n-1}]]\![X_n]$. En observant que $P_k$ est de degré total au plus $3\eta$ en $X_1, \dots, X_{n-1}$, et de degré au plus $3d-3$ en $X_n$, le lemme suivant donne une borne suffisante pour la précision permettant de tester cette divisibilité.

**Lemme 22.5** Soit P un polynôme de degré total au plus $3\eta$ en $X_1, \dots, X_{n-1}$ pour $1 \le i \le n-1$, et de degré au plus $3d-3$ en $X_n$. On note $Q$ et $R$ le quotient et le reste de la division de P par F dans $\bar{\mathbb{K}}[[X_1, \dots, X_{n-1}]]\![X_n]$, de sorte que $P = QF + R$. Alors, le polynôme F divise P dans $\bar{\mathbb{K}}[[X_1, \dots, X_{n-1}]]\![X_n]$ si, et seulement si, $[Q]_{2\eta+1}^{3\eta+1} = 0$ et $[R]^{3\eta+1} = 0$.

*Démonstration.* Supposons que F divise P dans $\bar{\mathbb{K}}[[X_1, \dots, X_{n-1}]]\![X_n]$. On a alors $R=0$ et $P=QF$, avec $Q \in \bar{\mathbb{K}}(X_1, \dots, X_{n-1})\![X_n]$. Notons $Q = A/a$ avec $A \in \bar{\mathbb{K}}[X_1, \dots, X_n]$ et $a \in \bar{\mathbb{K}}[X_1, \dots, X_{n-1}]$ premiers entre eux, de sorte à pouvoir écrire $aP = AF$ dans $\bar{\mathbb{K}}[X_1, \dots, X_n]$. Comme F est primitif, le lemme de Gauss (Proposition 21.1) sur la multiplicativité des contenus assure que $a$ est un polynôme constant. On obtient ainsi l'égalité $P = QF$ dans $\bar{\mathbb{K}}[X_1, \dots, X_n]$. Comme le degré total de Q en $X_1, \dots, X_{n-1}$ est au plus $2\eta$, on déduit $[Q]_{2\eta+1}^{3\eta+1} = 0$.
Réciproquement, supposons $\lceil R \rceil^{3\eta+1} = 0$ et $\lceil Q \rceil_{2\eta+1}^{3\eta+1} = 0$. Comme le degré total de $\lceil Q \rceil^{2\eta+1} F$ en $X_1, \dots, X_{n-1}$ est au plus $3\eta$, on a l'égalité $P = \lceil Q \rceil^{2\eta+1} F$ dans $\mathbb{K}[X_1, \dots, X_n]$, et donc F divise P dans $\mathbb{K}[[X_1, \dots, X_{n-1}]]\lceil X_n \rceil$.

Pour chaque $1 \le i \le s$ et chaque $1 \le k \le n-1$ on introduit

$$ \mathfrak{G}_{i,k} = \left[ \frac{F}{F_i} \frac{\partial F_i}{\partial X_n} \right]^{\eta+1}. $$

On note $P_{i,k}$ la valeur de $P_k$ obtenue lorsqu'on remplace $G$ par $\mathfrak{G}_{i,k}$ dans la formule (22.2). Enfin les polynômes $Q_{i,k}$ et $R_{i,k}$ représentent le quotient et le reste de la division de $P_{i,k}$ par $F$ dans $\mathbb{K}[[X_1, \dots, X_{n-1}]]\lceil X_n \rceil$ à la précision $(X_1, \dots, X_{n-1})^{3\eta+1}$. Le système linéaire $L'$ à considérer maintenant est formé par les équations

$$ \ell_1 \lceil Q_{1,k} \rceil_{2\eta+1}^{3\eta+1} + \dots + \ell_s \lceil Q_{s,k} \rceil_{2\eta+1}^{3\eta+1} = 0, \quad \text{et} $$

$$ \ell_1 \lceil R_{1,k} \rceil^{3\eta+1} + \dots + \ell_s \lceil R_{s,k} \rceil^{3\eta+1} = 0, \quad \text{pour } 1 \le k \le n-1. $$

**Lemme 22.6** Si $\mathbb{K}$ est de caractéristique nulle ou supérieure ou égale à $1+\eta(2d-1)$, alors les $\mu_i$ forment une base des solutions de $L'$, à une permutation près.

*Démonstration.* Indépendamment de l'hypothèse sur $\mathbb{K}$, par construction, les $\mu_i$ sont clairement des solutions de $L'$. Soit $\ell = (\ell_1, \dots, \ell_s)$ un vecteur solution de $L'$. On considère $G = \ell_1 \mathfrak{G}_1 + \dots + \ell_s \mathfrak{G}_s$. Par construction, les résidus de $\frac{\mathbb{G}}{F}$ en $X_n$ ont toutes leurs dérivées partielles nulles. Par conséquent le résidu $\rho_i$ de $G/F$ en $\varphi_i$ satisfait

$$ \rho_i = \ell_i + O((X_1, \dots, X_{n-1})^\tau), $$

avec $\tau = \infty$ si $p = 0$ et $\tau = p$ sinon, et on obtient

$$ \frac{\mathbb{G}}{F} = \frac{\ell_1}{X - \varphi_1} + \dots + \frac{\ell_1}{X - \varphi_s} + O((X_1, \dots, X_{n-1})^\tau). $$

Soit $j$ un indice tel que $\ell_j \neq 0$, et soit $k$ l'indice tel que $\mu_{k,j} = 1$. On pose $\tilde{\ell} = \ell - \ell_j \mu_k$, de sorte que $\tilde{\ell}_j = 0$, et on introduit $\tilde{\mathbb{G}} = G - \ell_j F_k$. Les $\tilde{\ell}_1, \dots, \tilde{\ell}_s$ sont les résidus de $\tilde{\mathbb{G}}/F$, et $X_n - \varphi_j$ divise $G$ à la précision $O((X_1, \dots, X_{n-1})^\tau)$. Le résultant $R = \text{Res}_{X_n}(F, G)$ s'annule donc à cette précision.

Avec l'hypothèse sur la caractéristique, comme le degré total de $R$ est au plus $\eta(2d-1)$, il s'ensuit que $R$ est le polynôme nul. Par conséquent $F_k$ divise $\tilde{\mathbb{G}}$ et $\ell_i$ est nul pour tout indice $l$ tel que $\mu_{k,l} = 1$. En procédant ainsi avec tous les indices $j$, on vient de prouver que $\ell_{j_1} = \ell_{j_2}$ dès lors qu'il existe $k$ tel que $\mu_{k,j_1} = \mu_{k,j_2} = 1$. En d'autres termes, $\ell$ s'exprime comme combinaison linéaire des $\mu_i$.
**Théorème 22.7** Si $\mathbb{K}$ est de caractéristique nulle ou supérieure ou égale à $1+\eta(2d-1)$, et si $n=2$, alors la factorisation de $F \in \mathbb{K}[X_1, X_2]$ peut se faire en factorisant un polynôme de degré $d$ dans $\mathbb{K}[X_2]$, plus $\tilde{O}(\eta d^\theta)$ opérations arithmétiques dans $\mathbb{K}$.

*Démonstration.* On modifie l'Algorithme 22.2 en prenant pour précision $\sigma = \eta + 1$, et en utilisant le système linéaire $L'$ à la place de $L$. Le lemme précédent assure que l'algorithme est correct.

Quant à la complexité, lorsque $n=2$, il faut compter un temps quasi-linéaire pour les étapes (2) et (5). Dans l'étape (3), le calcul de chaque $\mathfrak{G}_{i,1}$ peut être réalisé en temps quasi-linéaire. Les calculer tous requiert un coût $\tilde{O}(\eta d^2)$. Le système $L'$ est constitué de $O(\eta d)$ équations en $O(d)$ inconnues. Il peut donc être résolu au moyen de $O(\eta d^\theta)$ opérations dans $\mathbb{K}$ en utilisant le Théorème 8.6 en page 175. En déduire les $\mu_i$ peut se faire en temps linéaire. ■

Lorsque $n=2$ et qu'on peut échanger les rôles des deux variables, il est préférable de prendre pour deuxième variable celle de plus petit degré partiel, de sorte que la complexité du théorème puisse être bornée par $\tilde{O}((\eta d)^{(\theta+1)/2})$, ce qui s'interprète comme un coût sous-quadratique dans la taille dense de $F$.

## 22.4 Réduction probabiliste au cas de deux variables

La taille des systèmes linéaires $L$ et $L'$ intervenant dans les algorithmes précédents croît rapidement avec le nombre de variables. Nous présentons ici une méthode probabiliste pour ramener la factorisation au cas de seulement deux variables.

Nous continuons à travailler sous les mêmes hypothèses : $F$ est primitif en $X_n$, et $F(0, \dots, 0, X_n)$ est séparable de degré $d = \text{deg}_{X_n}(F)$. L'entier $\eta$ représente le degré total de $F$ en les $n-1$ premières variables. Bien sûr nous supposons $n \ge 3$ tout au long de cette section. Nous allons voir que pour presque toutes les valeurs de $(a_1, \dots, a_{n-1}) \in \mathbb{K}^{n-1}$, les facteurs irréductibles de $F$ sont en bijection naturelle avec ceux de $F(a_1 Y, \dots, a_{n-1} Y, Z) \in \mathbb{K}[Y, Z]$, où $Y$ et $Z$ sont des nouvelles variables.

On introduit de nouvelles variables $A_1, \dots, A_{n-1}$. Le lemme suivant opère un changement de variables suffisamment générique pour préserver l'irréductibilité :

**Lemme 22.8** Si $F$ est irréductible, alors le polynôme $F(A_1 Y, \dots A_{n-1} Y, Z)$ est irréductible dans $\mathbb{K}(A_1, \dots, A_{n-1})[Y, Z]$.

*Démonstration.* Posons

$$G(A_1, \dots, A_{n-1}, Y, Z) = F(A_1 Y, \dots A_{n-1} Y, Z).$$

Comme $G$ est primitif en $Z$ et appartient à $\mathbb{K}[A_1, \dots, A_{n-1}, Y, Z]$, il suffit de prouver qu'il est irréductible dans $\mathbb{K}[A_1, \dots, A_{n-1}, Y, Z]$.

Comme $F(0, \dots, 0, Z) = G(0, \dots, 0, 1, Z)$, les facteurs irréductibles unitaires $F_1, \dots, F_s$ de $F$ vus comme polynômes de $\mathbb{K}[[X_1, \dots, X_{n-1}]][[X_n]]$ sont en bijection avec ceux de $G$ dans $\mathbb{K}(A_1, \dots, A_{n-1})[[Y]][[Z]$, notés $\mathfrak{G}_1, \dots, \mathfrak{G}_s$. Autrement dit, quitte à permuter les indices, on a $\mathfrak{G}_i = F_i(A_1 Y, \dots, A_{n-1} Y, Z)$. Par conséquent, tout facteur irréductible de $G$
dans $K[A_1, \dots, A_{n-1}, Y, Z]$ est de la forme $H(A_1 Y, \dots, A_{n-1} Y, Z)$ avec $H \in K[X_1, \dots, X_n]$. En remplaçant $Y$ par $1$, il s'ensuit que le polynôme $H(A_1, \dots, A_{n-1}, Z)$ est nécessairement un facteur de $F(A_1, \dots, A_{n-1}, Z)$, et donc que $G$ est irréductible. ■

Rappelons que les facteurs irréductibles de $F$ sont notés $F_1, \dots, F_r$. Un point $(a_1, \dots, a_{n-1})$ de $K^{n-1}$ est dit de Hilbert pour $F$ lorsque tous les polynômes

$$F_i(a_1 Y, \dots, a_{n-1} Y, Z)$$

sont irréductibles. En d'autres termes, les facteurs irréductibles de $F$ sont en bijection avec ceux de $F(a_1 Y, \dots, a_{n-1} Y, Z)$.

**Théorème 22.9** Soit $F$ un polynôme primitif en $X_n$, et tel que $F(0, \dots, 0, X_n)$ est séparable de degré $d = \deg_{X_n}(F)$. Il existe un polynôme $A \in K[A_1, \dots, A_{n-1}]$ non nul de degré au plus $\eta(d-1)(2d-1)$ qui s'annule en tous les points de $K^{n-1}$ qui ne sont pas de Hilbert pour $F$.

*Démonstration.* Comme la fonction $\delta(d) = (d-1)(2d-1)$ satisfait $\delta(d_1)+\delta(d_2) \le \delta(d_1+d_2)$ pour n'importe quels entiers strictement positifs $d_1$ et $d_2$, il suffit de prouver le résultat lorsque $F$ est irréductible.

Posons $G(A_1, \dots, A_{n-1}, Y, Z) = F(A_1 Y, \dots, A_{n-1} Y, Z)$, et réutilisons les notations de la preuve précédente. Avec $\sigma = 2 + \eta(2d-1)$, la Proposition 22.3 nous garantit que le système linéaire

$$\ell_1 \left[ \frac{F}{F_1} \frac{\partial F_1}{\partial X_1} \right]_{\eta+1}^{\sigma-1} + \dots + \ell_s \left[ \frac{F}{F_s} \frac{\partial F_s}{\partial X_s} \right]_{\eta+1}^{\sigma-1} = 0$$

est de rang $s-1$. Il existe donc un mineur non nul $A$ de ce système de taille $s-1$. Si maintenant $A(a_1, \dots, a_{n-1}) \ne 0$, alors le système reste de rang $s-1$ lorsqu'on spécialise les $A_i$ en les $a_i$. Pour une telle spécialisation, le polynôme $F(a_1 Y, \dots, a_{n-1} Y, Z)$ est donc irréductible, en utilisant la Proposition 22.3.

Pour chaque $j \ge 0$ et $k \ge 0$, le coefficient de $Y^j Z^k$ dans

$$\frac{F}{F_l} \frac{\partial F_1}{\partial X_l}$$

est de degré au plus $j$. Le degré total de $A$ est donc au plus $(s-1)\eta(2d-1)$. ■

**Lemme 22.10 — Schwartz-Zippel.** Soit $S$ un sous-ensemble fini de $K$. Si $A$ est un polynôme non nul de $K[A_1, \dots, A_m]$, alors il a au plus $\deg(A)\text{card}(S)^{m-1}$ racines dans $S^m$.

*Démonstration.* Lorsque $m=1$, le résultat est immédiat. Supposons par récurrence la borne prouvée pour $m \ge 1$. Le coefficient de tête $\text{ct}_{A_n}(A)$ appartient à $K[A_1, \dots, A_{m-1}]$ et est de degré total au plus $\delta = \deg(A) - \deg_{A_n}(A)$. Il admet au plus $\delta\text{card}(S)^{m-2}$ racines dans $S^{m-1}$. Par ailleurs, les points qui annulent $A$ sans annuler son coefficient
de tête en $A_n$, sont forcément au plus $\deg_{A_n}(A)\text{card}(S)^{m-1}$. Au total le nombre de zéros est borné par

$$ (\delta\text{card}(S)^{m-2})\text{card}(S) + \deg_{A_n}(A)\text{card}(S)^{m-1} = \deg(A)\text{card}(S)^{m-1}, $$

comme annoncé.

<figure><img src="image_61.png" /></figure>

On déduit naturellement de ces résultats une approche probabiliste efficace. On fixe un ensemble $S$ de taille au moins $C\eta(d-1)(2d-1)$, pour une constante $C$ assez grande. On tire au hasard un point $(a_1, \dots, a_{n-1}) \in S^{n-1}$, on factorise ensuite $F(a_1 Y, \dots, a_{n-1} Y, Z)$, puis on utilise la remontée de Newton-Hensel en précision $\eta+1$ pour reconstruire les facteurs de $F$. Le lemme précédent nous assure que l’algorithme aboutit à un résultat correct avec une probabilité $\ge 1-1/C$. Si un facteur remonté en précision $\eta+1$ divise $F$, alors c’est un facteur irréductible de $F$. Si tel n’est pas le cas, alors il faut prendre un autre point $(a_1, \dots, a_{n-1}) \in S^{n-1}$ au hasard et recommencer. Ainsi il est donc aisé d’assurer que l’algorithme renvoie toujours un résultat correct. Le nombre de tentatives est en moyenne borné par une constante.

Cette approche probabiliste ne peut pas être appliquée lorsque le cardinal de $\mathbb{K}$ est trop petit. Nous avons déjà rencontré cette problématique au début de ce chapitre. Nous décrivons une solution dans la section suivante.

## 22.5 Cas particulier des corps finis

Si $\mathbb{K}$ est un corps fini $\mathbb{F}_q$ de cardinal trop petit pour pouvoir appliquer les résultats vus dans ce chapitre, alors nous pouvons procéder comme suit. Tout d'abord nous construisons une extension algébrique $\mathbb{F}_{q^l}$ de $\mathbb{F}_q$ de degré $l$ sous la forme $\mathbb{F}_{q^l}[Z]/(\chi(Z))$, avec $\chi$ irréductible de degré $l$. Notons $\alpha$ une racine de $\chi$ dans $\mathbb{F}_{q^l}$. En prenant $l \in O(\log_q(\eta d))$ suffisamment grand pour pouvoir factoriser $F$ dans $\mathbb{F}_{q^l}$ avec les algorithmes de ce chapitre, nous pouvons obtenir les facteurs irréductibles $\mathcal{F}_1, \dots, \mathcal{F}_t$ de $F$ dans $\mathbb{F}_{q^l}$. En prenant les préimages des coefficients des $\mathcal{F}_i$ dans $\mathbb{F}_q[Z]$, nous construisons des polynômes $F_i(X_1, \dots, X_n, Z)$ de degrés au plus $l-1$ en $Z$, tels que $\mathcal{F}_i(X_1, \dots, X_n) = F_i(X_1, \dots, X_n, \alpha)$.

Pour chaque $i \in \{1, \dots, t\}$, nous pouvons calculer

$$ G_i = \text{pgcd}(F, \text{Res}_Z(F_i(X_1, \dots, X_n, Z), \chi(Z))), $$

qui s'avère être un facteur irréductible de $F$. En effet, considérons un facteur irréductible $H$ de $G_i$. Par la formule de Poisson (Théorème 6.5), le polynôme

$$ \text{Res}_Z(F_i(X_1, \dots, X_n, Z), \chi(Z)) $$

est proportionnel à

$$ \prod_{\chi(\beta)=0} F_i(X_1, \dots, X_n, \beta). $$

Le facteur $H$ est donc divisible par l'un des $F_i(X_1, \dots, X_n, \beta)$ et donc par tous. Ceci nous donne $H = G_i$. Par ailleurs, des arguments similaires montrent que chaque facteur
irréductible de F apparaît au moins une fois comme l'un des $G_i$, et au plus l fois. Les redondances sont éliminées simplement, en triant la liste des $G_i$.

Pour construire le polynôme irréductible $\chi$, on peut factoriser des polynômes de degré $l$ pris au hasard, jusqu'à en trouver un irréductible. Nous ne justifierons pas le fait que l'on trouve rapidement un polynôme irréductible en toute généralité. Néanmoins on peut ici accepter de prendre $l$ premier, de sorte que la Proposition 19.8 permet d'obtenir que le nombre de polynômes unitaires irréductibles de degré $l$ est $(q^l - q)/l$.

Lorsque $n=2$, on admettra que chaque $G_i$ se calcule par évaluation-interpolation rapide en $\tilde{O}(\eta d)$ opérations dans $\mathbb{F}_{q^l}$. Au final le surcoût total pour résoudre les problèmes avec les corps finis trop petits reste donc borné par un facteur acceptable $\log^{O(1)}(\eta d)$.

## Notes

La factorisation des polynômes à plusieurs variables est un sujet d'étude important en calcul formel depuis les années soixante-dix. L'utilisation de la remontée de Newton-Hensel à plusieurs variables a débuté avec les articles de Musser, Wang et Rothschild [Mus75; Wan78; WR75]. Des améliorations ont ensuite été trouvées par von zur Gathen et Kaltofen [Gat84; GK85a; Kal85d]. Une implémentation très efficace de ces idées a été réalisée par Bernardin et Monagan [BM97].

Dans le chapitre précédent, nous avons étudié le coût binaire de la factorisation sans carré dans $\mathbb{Q}[X]$. Cette approche peut être aisément adaptée au cas de deux variables, par évaluation/interpolation, dès lors que le corps de base contient suffisamment d'éléments : on obtient un coût $\tilde{O}(\eta d^2)$, où $\eta$ et $d$ représentent les degrés partiels. De plus, en acceptant des choix aléatoires au moment de l'exécution, on peut atteindre un coût quasi-linéaire en moyenne [Lec08].

Pendant longtemps, l'étape de recombinaison a été effectuée par la méthode de recherche exhaustive, qui a un coût exponentiel dans le pire cas. Néanmoins, si $K$ est un corps fini, en moyenne sur l'ensemble des polynômes, son coût est essentiellement quadratique [GL02], ce qui justifie le très bon comportement pratique de cette approche.

Les premiers algorithmes de factorisation en temps polynomiaux sont dus à Kaltofen au début des années quatre-vingt [Kal82a; Kal82b; Kal82c; Kal85a; Kal85b; Kal85c; Kal85d]. Plusieurs autres auteurs ont contribué à ce problème pour couvrir les corps de coefficient usuels : Chistov, von zur Gathen, Grigoriev et Lenstra. Ces algorithmes calculent un facteur rationnel à partir d'un seul facteur local, sans utiliser la totalité de la décomposition locale. Malheureusement les exposants des bornes de complexité sont grands et les seuils d'efficacité pratique sont très élevés. Les détails historiques sont présentés dans des articles de synthèse de von zur Gathen et Kaltofen [Gat06; Kal03; Kal90; Kal92].

La première réduction de la factorisation de deux à une variable en temps quasi-quadratique, pour la caractéristique nulle ou suffisamment grande, est due à Shuhong Gao [Gao03] par un calcul direct du premier groupe de cohomologie de De Rham du complémentaire de l'hypersurface définie par $F=0$, dans la continuité des travaux de Ruppert [Rup86; Rup99] sur les tests d'irréductibilité.
Dans le présent chapitre nous nous sommes concentrés sur les méthodes utilisant la remontée de Newton-Hensel. L'Algorithmme 22.2 est dû à Belabas, van Hoeij, Klüners et Steel [Bel+09]. La première borne de précision linéaire en le degré total de F a été prouvée par Bostan, Lecerf, Salvy, Schost et Wiebelt [Bos+04b], puis a été abaissée par Lecerf [Lec06]. L'algorithme de Lecerf présenté ici est issu de l'article de 2010 [Lec10], qui traite aussi les autres cas de petite caractéristique efficacement, avec les meilleures bornes de complexités connues à l'heure actuelle.

Le Théorème 22.9 est une forme quantitative d'un résultat plus général classique présenté par exemple dans le livre de Shafarevich [Sha94, Chapter II, Section 6.1]. En fait, ce cas particulier semble être dû à Hilbert [Hil92, p. 117], comme souligné par Kaltofen [Kal95a]. Pour cette raison, il est fréquent de trouver les terminologies « théorème de Hilbert » ou « théorème de Bertini » dans la littérature.

L'utilisation du théorème de Bertini en calcul formel a été mise en avant pour la première fois dans les travaux de Heintz et Sieveking d'une part [HS81], et de Kaltofen d'autre part [Kal82c]. Son utilisation s'est rapidement imposée dans de nombreux algorithmes et études de complexité [Gat85; GK85b; Kal85a; Kal85b; Kal85c; Kal85d]. Plusieurs auteurs ont contribué à obtenir des bornes de probabilité de plus en plus fines [Baj+93; Chè04; Gao03; Kal95a]. Les meilleurs résultats connus actuellement sont dûs à Lecerf [Lec07; Lec13].

Pour davantage de détails historiques concernant la factorisation des polynômes à plusieurs variables nous renvoyons le lecteur aux livres de Zippel [Zip93], Schinzel [Sch00], von zur Gathen et Gerhard [GG03], Mullen et Panario [MP13], mais aussi aux notes de cours de Lecerf [Lec13].

## Bibliographie

* Baj+93 BAJAJ, Chanderjit, John CANNY, Thomas GARRITY et Joe WARREN (1993). « Factoring rational polynomials over the complex numbers ». In : *SIAM Journal on Computing*, vol. 22, n°2, p. 318-331.

* Bel+09 BELABAS, Karim, Mark van Hoeij, Jürgen KLÜNERS et Allan STEEL (2009). « Factoring polynomials over global fields ». In : *Journal de Théorie des Nombres de Bordeaux*, vol. 21, n°1, p. 15-39.

* BM97 BERNARDIN, Laurent et Michael B. MONAGAN (1997). « Efficient multivariate factorization over finite fields ». In : *Applied algebra, algebraic algorithms and error-correcting codes (Toulouse, 1997)*. Vol. 1255. Lecture Notes in Computer Science. Springer-Verlag, p. 15-28.

* Bos+04b BOSTAN, Alin, Grégoire LECERF, Bruno SALVY, Éric SCHOST et Bernd WIEBELT (2004). « Complexity issues in bivariate polynomial factorization ». In : *ISSAC'04 : International Symposium on Symbolic and Algebraic Computation*. ACM Press, p. 42-49.

* Chè04 CHÈZE, Guillaume (2004). « Des méthodes symboliques-numériques et exactes pour la factorisation absolue des polynômes en deux variables ». Thèse de doctorat. Université de Nice-Sophia Antipolis (France).

* Gao03 GAO, Shuhong (2003). « Factoring multivariate polynomials via partial differential equations ». In : *Mathematics of Computation*, vol. 72, n°242, p. 801-822.