\documentclass[XUPS,XML,SOM,Unicode,francais,ThmDefs]{cedram}
\OneNumberAllTheorems
\setcounter{tocdepth}{2}
\usepackage{xups05-02}

\begin{document}
\frontmatter

\title{L'algorithmique de\nobreakspace la\nobreakspace théorie\nobreakspace algébrique des nombres}
\author[\initial{K.} \lastname{Belabas}]{\firstname{Karim} \lastname{Belabas}}
\address{Université Bordeaux~I,
351 Cours de la Libération,
33405 Talence Cedex, France}
\email{karim.belabas@math.u-bordeaux.fr}
\urladdr{https://www.math.u-bordeaux.fr/~kbelabas/}

\thanks{Journées X-UPS 2005. Théorie algorithmique des nombres et équations diophantiennes. Éditions de l'École polytechnique, 2005}

\maketitle
\vspace*{-1.5\baselineskip}
\tableofcontents
\mainmatter

Commençons par une équation difficile... dans un contexte sans difficulté:

\begin{theo} Soit $n > 2$ et $x$, $y$, $z$ trois \emph{polynômes} à coefficients complexes, premiers entre eux. Alors $x^n + y^n = z^n$ implique que les trois polynômes sont des constantes.
\end{theo}

\begin{proof}
Supposons qu'il existe trois polynômes $(x,y,z)$ premiers entre eux satisfaisant $x^n+y^n=z^n$, tels que le maximum des trois degrés soit $D > 0$. On les choisit tels que $D$ soit minimal. Posant $\zeta:=\exp(2i\pi/n)$, on a
\begin{equation} \label{eq:fact} z^n = x^n+y^n = (x+y)(x+\z y)(x+\z^2y)\cdots(x+\z^{n-1}y).
\end{equation}
Deux facteurs quelconques du produit n'ont pas de diviseur commun, puisqu'un tel facteur diviserait $x$ et $y$. Leur produit étant une puissance $n$-ème, ces facteurs sont de la forme $\beta u^n$, $\beta\in \CM^*$, ce qui s'écrit encore $(\alpha u)^n$. Puisque $n-1\geq2$, il existe des polynômes $u$, $v$, $w$ premiers entre eux tels que
$$x + y = u^n, \quad x + \z y = v^n, \quad x + \z^2 y = w^n.$$
En éliminant $x$ et $y$ de ces équations, on trouve $w^n + \z u^n = (1 + \z)v^n$. Les constantes entrent de nouveau sous les puissances et on pose $x'=w$, $y'=\z^{1/n}u$, $z'=(1+\z)^{1/n}v$, qui vérifient ${x'}^n+{y'}^n={z'}^n$. Ces nouveaux polynômes sont toujours premiers entre eux ($\z+1=0$ implique $n=2$) et de degré maximal $D'$ satisfaisant $0 <\nobreak D' \leq\nobreak D/n < \nobreak D$. Contradiction.
\end{proof}

Il y a essentiellement deux arguments dans la preuve:
\begin{itemize}
\item
$\CM$ contient $\z$ et chaque complexe à une racine $n$-ème,
\item
$\CM[X]$ est factoriel (notion de pgcd et écriture comme puissances $n$-èmes).
\end{itemize}
Le premier est surtout une étape conceptuelle: même si l'on s'intéresse aux solutions dans $\ZM[X]$, raisonner dans $\ZM[X]$ est inadapté. On agrandit l'anneau de base pour pouvoir travailler; mais pas trop, pour ne pas vider le problème de sa substance arithmétique: dans l'anneau de séries formelles $\CM[[X]]$, tout devient trivial. Le deuxième argument, par contre, est profond. Si l'on essaie de démontrer Fermat sur $\QM$ en copiant le premier point, on introduit l'anneau $\ZM[\zeta]$, qui n'est presque jamais factoriel. La théorie algébrique des nombres s'est créée autour de cette question (et des généralisations de la loi de réciprocité quadratique de Legendre-Gauss), notamment avec l'invention des \og nombres idéaux\fg par Kummer pour restaurer l'unicité de la décomposition en facteurs irréductibles.

Bien sûr, cela n'a pas suffi pas à résoudre le problème général de Fermat. Mais la théorie algébrique des nombres classique\footnote{Les développements ultérieurs (théorie du corps de classe, théorie d'Iwasawa, structures galoisiennes et cohomologie, $K$-théorie algébrique...) nous éloigneraient un peu des motivations diophantiennes immédiates et ne seront plus mentionnées.}, essentiellement telle qu'axiomatisée par Dedekind puis Hecke, résout de très nombreuses équations concrètes,... avec le renfort des estimations modernes de transcendance (en particulier les minorations de formes linéaires en logarithmes), et du calcul algorithmique des invariants que nous allons introduire. Les méthodes \og modulaires\fg (utilisant les théorèmes de Ribet et Wiles),... qui permettent de démontrer Fermat, se prêtent également à un traitement algorithmique, pour lequel je renvoie au survol de Siksek~\cite{Sik2004}.

Dans une première partie, j'introduis le langage de la théorie algébrique des nom\-bres, en démontrant tout ce qui peut se faire en quelques lignes. On se contente de résultats classiques, en évitant les notions et les preuves les plus générales. Voir par exemple Lang~\cite{Lang-ANT} pour les démonstrations manquantes.

Une deuxième partie, algorithmique, rendra tout ceci effectif. Elle est largement inspirée par Lenstra~\cite{Len-algANT} et Cohen~\cite{Coh-coucom}. À partir de données explicites, quelles quantités sont effectivement calculables? Comment et sous quelle forme? En quel temps? Je n'ai pas cherché à être exhaustif, ni toujours efficace, ni suffisamment explicite pour permettre une implantation directe (dans ce but, se référer à~\hbox{\cite{GatGer, Coh-coucom, Bel-top}}), mais à présenter un panorama d'idées et d'algorithmes essentiels, sous une forme que j'espère compréhensible.

\part{Théorie algébrique des nombres}

\section{Préliminaires}

\subsection{\texorpdfstring{$\ZM$}{ZM}-modules de type fini}

Un $\ZM$-module est un groupe abélien~$G$. Il est \emph{de type fini} s'il est engendré par un nombre fini d'éléments. Il est \emph{libre} s'il admet une base, c'est-à-dire une famille génératrice $(e_i)_{i\leq n}$ libre: si $\sum_{i\leq n} \lambda_i e_i = 0$, $\lambda_i\in\ZM$, alors $\lambda_1 = \cdots = \lambda_n = 0$. Contrairement aux espaces vectoriels, les modules n'admettent pas nécessairement de base, par exemple $G = \ZM/2\ZM$. Par contre s'il existe des bases, elles ont bien le même cardinal $n$, appelé \emph{rang} de $G$ et noté $\rg G$. Les changements de bases sont les éléments de $\Gl_n(\ZM)$.

\begin{theo}[base adaptée]\label{th:adapt} Si $G$ est un $\ZM$-module libre de type fini et~$H$ un sous-$\ZM$-module, il existe une base $(g_i)$ de $G$ et \hbox{$d_n\mid \dots \mid d_2\mid d_1$} dans $\NM$ tels que $\set{d_ig_i\colon d_i > 0}$ soit une base de $H$. Les $(d_i)$ ne dépen\-dent pas de la base de $G$ choisie.
\end{theo}

En particulier:

\begin{coro}\label{co:fini} Un sous-module $H$ d'un $\ZM$-module libre de type fini $G$ est libre de type fini. De plus, $\rg H \leq \rg G$.
\end{coro} Plus généralement:

\begin{coro}[diviseurs élémentaires] Si $G$ est un $\ZM$-module de type fini, il existe $g_1,\dots,g_n\in G$ tels que
$$
G = \bigoplus_{i = 1}^n \, (\ZM/d_i\ZM) \cdot g_i,
$$
où $d_n\mid \dots \mid d_2 \mid d_1$ dans $\NM$ ne dépendent que de $G$.
\end{coro}

\begin{proof}
Considérer $M$, le module libre sur les générateurs de~$G$, et $\L\subset M$, le noyau de la projection canonique $M\to G$. Dans une base adaptée, interpréter $G = M/\L$.
\end{proof}

\noindent On appelle les $(d_i)$ les \emph{diviseurs élémentaires} de $G$ (\emph{cf}.~\S\ref{se:HNF}). Le~groupe fini $G_{\textup{tor}}:= \oplus_{i, d_i > 0} (\ZM/d_i\ZM)\cdot g_i$ est la \emph{torsion} de $G$, et $r :=\#\set{i: d_i = 0} = \rg G$ son \emph{rang}. Pour $p$ premier, on note $r_p(G) = \dim_{\FM_p} G/ pG = \#\set{i: p\mid d_i}$ le $p$-rang de $G$.

En particulier, tout groupe abélien fini est somme directe de groupes cycliques et un $\ZM$-module de type fini est libre si et seulement s'il est sans torsion. Si $H\subset G$ sont deux $\ZM$-modules, on note $[G:H] = \#(G/H) \leq +\infty$ l'\emph{indice} de $H$ dans $G$.

\begin{coro}\label{co:coker} Si $\phi:\ZM^n\to\ZM^n$ est un morphisme dont l'image est de rang $n$,
$$
[\ZM^n : \im \phi] = \abs{\det \phi}.
$$
\end{coro}

\begin{proof}
On choisit une base $(g_i)$ de $\ZM^n$ telle que $(d_ig_i)$ soit une base de $\im \phi$ (comme $\phi$ est de rang $n$, aucun $d_i$ n'est nul), donc $[\ZM^n:\im\phi] = d_1\cdots d_n$. Le morphisme $\psi:d_ig_i\mto \phi(g_i)$ est un changement de base de $\im\phi$, donc de déterminant $\pm1$. Comme $\phi$ est la composition de l'application diagonale $g_i\mto d_ig_i$ et de $\psi$, on obtient $\abs{\det \phi} = d_1\cdots d_n$.
\end{proof}

\subsection{Réseaux, déterminant, discriminant}\label{se:reseau}

Si $(E,q)$ est un espace euclidien de dimension $n$, un réseau $\L \subset E$ est un sous-$\ZM$-module libre de rang $n$. Si $(e_i)_{i\leq n}$ est une base de $\L$, le \emph{discriminant} de $\L$ est le déterminant de la matrice de Gram
$$
\Gram(e_1,\dots,e_n) = \big( \gen{e_i, e_j}\big)_{1\leq i,j\leq n}.
$$
Le \emph{déterminant} $d(\L) = d(\L,q)$ de $\L$ est la racine carrée du discriminant de $\L$. Il est égal au volume du parallélotope fondamental
$$\set{\sum x_i e_i \colon 0 \leq x_i < 1}.$$

\begin{prop}\label{pr:phiGram} Si $\phi$ est un endomorphisme de $E$, de matrice $A$
$$\Gram(\phi(e_1),\dots,\phi(e_n)) = \tran{A}\cdot \Gram(e_1,\dots,e_n) \cdot A.$$
\end{prop}

\skpt
\begin{coro}\label{co:indice}
\begin{enumerate}
\item
$d(\L)$ ne dépend pas de la base $(e_i)$ choisie.
\item
Si $L\subset \L$ est un sous-réseau, $d(L) = d(\L)[\L:L]$.
\end{enumerate}
\end{coro} \noindent (Noter que si $L\subset\L$ est un sous-réseau, l'indice $[\L:L]$ est fini, puisque $L$ et $\L$ ont même rang $n$.) En particulier, si $E = \RM^n$, muni de la forme euclidienne standard, et $\L = \im \phi$, pour $\phi:\ZM^n\to E$ de rang $n$, alors $d(\L) = \abs{\det \phi}$.

Nous arrivons au résultat principal de cette partie, dont le seul tort est d'être \emph{non effectif}. (L'algorithme LLL~(\S\ref{se:LLL}) en donnera une variante effective.)

\begin{theo}[Minkowski] Si $C\subset \RM^n$ est convexe, symétrique autour de $0$ ($-C = C$) de volume $V(C) \leq +\infty$, et si $\L$ est un réseau de déterminant $d(\L) < 2^{-n} V(C)$, alors $C\cap \L \neq (0)$.
\end{theo}

La preuve est classique, je la reproduis pour manifester son caractère non effectif. Une variante pratique : si $C$ est de plus compact, alors l'égalité large $d(\L)\leq 2^{-n}V(C)$ suffit pour obtenir la conclusion (exercice).

\begin{proof}
On commence par montrer le théorème de Blichfeldt: si $\L$ est un réseau, $S\subset \RM^n$ et $d(\L) < V(S)$, alors il existe $s_1,s_2\in S$, $s_1 \neq s_2$, tels que $s_1 - s_2\in \L$. C'est clair: si $P$ est un parallélotope fondamental pour $\L$, les $S_x := S\cap (x + P)$, $x\in \L$, forment une partition de $S$, donc
$$V(S) = \sum_{x\in \L} V(S_x) = \sum_{x\in \L} V(S_x - x) > d(\L) = V(P).$$
Comme les $S_x - x$ sont inclus dans $P$, ils ne sont pas disjoints.

Le théorème est un corollaire immédiat pour $S = \frac{1}{2}C$, de volume $2^{-n}V(C) > d(\L)$. Par définition, $2s_1,2s_2\in C$, par symétrie $-2s_2\in\nobreak C$, et par convexité $c := \frac{1}{2}(2s_1 - 2s_2)\in C$.
\end{proof}

À titre d'entraînement:
\begin{exo}
Soit $p\equiv 1 \pmod{4}$ un nombre premier, $r\in\ZM$ tel que $r^2 \equiv -1 \pmod{p}$ et $\Lambda \subset \RM^2$ le réseau engendré par les colonnes de la matrice $ \smallmat{p & r\\0 & 1} $. Montrer que $\Lambda$ contient un point $(a,b)$ tel que $0 < a^2 + b^2 < 2p$. En déduire que $p = a^2 + b^2$ est somme de deux carrés. \hint{Solution. $C:=B(0,\sqrt{2p})$, $V(C) = 2\pi p > 2^2 p = 2^nd(\Lambda)$.}
\end{exo}
\begin{exo}
Soit $p$ un nombre premier, montrer qu'il existe $r,s\in\ZM$ tels que $r^2 + s^2 \equiv -1\pmod{p}$ \hint{il y a $(p+1)/2$ valeurs possibles pour~$r^2$, autant pour $-1-s^2$}. Soit $\Lambda\subset \RM^4$ le réseau engendré par les colonnes de
$$\arraycolsep4pt
\begin{pmatrix} p & 0 & r & s \\ 0 & p & s & -r \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\
\end{pmatrix}.
$$
Montrer que $\Lambda$ contient un point $(a,b,c,d)$ tel que $0 < a^2 + b^2 + c^2 + d^2 < 2p$. \hint{$d(\L) = p^2$, $C = B(0, \sqrt{2p})$, $V(C) = \frac{\pi^2}{2} (2p)^2 > 2^4 d(\L)$.} En déduire que $p$ est somme de $4$ carrés. \hint{Corollaire: tout entier positif est somme de $4$ carrés.}
\end{exo}

\subsection{Nombres \texorpdfstring{$p$}{p}-adiques} $\RM$ est le complété de $\QM$ pour la topologie associée à la valeur absolue usuelle. En d'autres termes, on peut réaliser $\RM$ comme l'anneau des suites de Cauchy de $\QM$, modulo l'idéal des suites de limite nulle. C'est un corps, auquel s'étend la valeur absolue de $\QM$, et il est complet pour la topologie associée.

Si $p$ est premier, et $v_p(x)$ désigne la valuation $p$-adique de $x$, la formule $\abs{x}_p := p^{-v_p(x)}$ définit de même une valeur absolue sur $\QM$, donc une topologie (cf.~\S\ref{se:places}). Le complété de $\QM$ par rapport à cette topologie $p$-adique se note $\QM_p$. La valuation $v_p$ et $\abs{\cdot}_p$ s'étendent à $\QM_p$.

On peut voir $\QM_p$ comme le corps de fractions de $\ZM_p = \limpro_{n>0} \ZM/p^n\ZM$, c'est-à-dire qu'un élément $x$ de $\ZM_p$ est donné par une suite d'approximations $(x_k)_{k\geq 1}$, $x_k\!\in\!\ZM/p^k\ZM$, où $x_{k+1} \!\equiv\! x_k \pmod{p^k}$ pour tout~\hbox{$k\!\geq\!1$}. En particulier il y a une projection canonique
\[
\phi_k: \ZM_p \to \ZM/p^k\ZM,
\]
donnée par $x\mto x_k$, pour tout $k\geq 1$.

\begin{theo}[Lemme de Hensel faible] Soit $F\in \ZM_p[X]$ unitaire, $\bar{F}$ sa réduction dans $\FM_p[X]$. On suppose que $\bar{F} = \prod_{i=1}^g \bar{F}_i$ dans $\FM_p[X]$, où les $\bar{F}_i$ sont unitaires, deux à deux premiers entre eux. Alors il existe $F_1,\dots,F_g\in \ZM_p[X]$ unitaires, tels que la réduction de $F_i$ dans $\FM_p[X]$ soit $\bar{F}_i$ pour tout $i\leq g$, et tels que $F = \prod_{i=1}^g F_i$.
\end{theo}

\noindent En d'autres termes une factorisation \emph{sans facteurs carrés} dans $\FM_p[X]$ se relève à $\ZM_p[X]$. Plus généralement, une factorisation suffisamment précise pour qu'il n'y ait plus de facteurs carrés se relève:

\begin{theo}[Lemme de Hensel] On suppose que $F, F_1,\dots,F_g\in \ZM_p[X]$ sont unitaires, et $a_1,\dots,a_g$ dans $\ZM_p[X]$ tels que
\begin{align*}
F &\equiv \prod_{i=1}^g F_i \pmod{p^e\ZM_p[X]}\\
\tag*{\textit{et}} p^d &\equiv \sum_{i=1}^g a_i\prod_{j\neq i} F_j \pmod{p^{d+1}\ZM_p[X]},
\end{align*} où $d\geq 0$, $e > 2d$. Alors il existe des polynômes $\hat{F_1},\dots,\hat{F_g}\in \ZM_p[X]$ unitaires, $\hat{F}_i \equiv F_i \pmod{p^e\ZM_p[X]}$ tels que $ F = \prod_{i=1}^g \hat{F_i} $.
\end{theo}

\begin{proof}
On construit par récurrence, pour tout $k \geq e$, des polynômes $F^{(k)}_1,\dots,F^{(k)}_g$ de $\ZM_p[X]$ tels que
\begin{align*}
F &\equiv \prod_{i=1}^g F_i^{(k)} \pmod{p^{k+1}\ZM_p[X]}\\
\tag*{et} p^d &\equiv \sum_{i=1}^g a_i\prod_{j\neq i} F_j^{(k)} \pmod{p^{d+1}\ZM_p[X]}.
\end{align*}
On pose ensuite $\hat{F_i} := \lim_{k\to\infty} F_i^{(k)}$. (La suite est de Cauchy dans $\ZM_p[X]_{\deg F_i}$, qui est complet.) Soit donc $u := p^{-k} (F - \prod_i F_i^{(k)})$, et pour $i=1,\dots,g$, soit $v_i$ le reste de la division euclidienne de $u a_i$ par~$F_i$. On pose $F_i^{(k+1)} := F_i^{(k)} + p^{k - d}v_i$.
\end{proof}

\noindent La congruence impliquant les $a_i$ est une identité de type Bézout, qui entraîne que les $F_i$ sont premiers entre eux; en fait, ils le sont déjà modulo $p^{d+1}$. La version faible est le cas $d = 0$, $e = 1$. Il est crucial pour nos applications que la preuve soit constructive.

\section{Corps de nombres}

Un \emph{corps de nombres} $K$ est une extension finie de $\QM$, c'est-à-dire un corps contenant $\QM$, de dimension finie comme $\QM$-espace vectoriel; cette dimension est appelée \emph{degré} de $K$. Si $\a$ est un nombre algébrique, par exemple $\a = \sqrt{2}$ ou $\a = \exp(2i\pi/m)$ ($m > 0$ entier), la~$\QM$-algèbre $\QM(\a)$ est un corps de nombres, respectivement de degré~$2$ et $\phi(m)$.

Réciproquement, le théorème de l'élément primitif dit que si $K$ est un corps de nombres, il existe $\a\in K$ tel que $K = \QM(\a)$. Si~$K$ est de degré $n$ et $T\in\QM[X]$ est le polynôme minimal de $\a$ sur~$\QM$, alors $T$ est de degré $n$, irréductible dans $\QM[X]$, et l'évaluation $Q\mto Q(\a)$ induit un isomorphisme de $\QM[X]/(T)$ sur $K$. Rappelons que le polynôme minimal $\Min{x}$ de $x\in K$ est le générateur \emph{unitaire} de l'idéal $\set{Q\in\QM[X], Q(x) = 0}$. On conserve ces notations dans la suite du texte.

\subsection{Plongements, signature}

Factorisons $T = \prod_{i=1}^n (X - \a_i)$ sur~$\CM$; les $\a_i$ sont les \emph{conjugués} de $\a$. Soit $r_1$ le nombre de racines réelles de $T$, $2r_2$ le nombre de racines non réelles. On ordonne les $\a_i$ de façon à ce que $\a_1,\dots, \a_{r_1}\in \RM$, $\a_{i + r_1} = \overline{\a_{i + r_1+r_2}}$ pour $1 \leq i \leq r_2$. Chaque $\a_i$ définit un plongement $\s_i:Q\mto Q(\a_i)$ du corps abstrait $K = \QM[X]/(T)$ dans $\CM$. Tout morphisme de corps de $K$ dans $\CM$ est manifestement de cette forme; les $\s_i$, $i \leq r_1$ sont les \emph{plongements réels} de $K$ et les $\s_i$, $r_1 < i \leq n$ ses \emph{plongements complexes}, $(r_1,r_2)$ est sa \emph{signature}. Bien sûr, $r_1 + 2r_2 = n$.

Chaque $\s_i$ s'étend à $\RM[X]/(T)$ et $\s:=(\s_1,\dots,\s_{r_1+r_2})$ définit un isomorphisme de $\RM$-algèbres de $\RM[X]/(T)$ dans $\RM^{r_1}\times \CM^{r_2}$. En d'autres termes la signature $(r_1,r_2)$ donne la structure de la $\RM$-algèbre $K\otimes_\QM \RM$.

\subsection{Trace, norme}

Soit $x$ dans $K$; la multiplication par $x$ induit un endomorphisme $m_x:K\to K$ de $\QM$-espace vectoriel. On définit le polynôme caractéristique de $x$, noté $\Char{x}$, la trace de $x$, notée $\Tr(x)$, et la norme de $x$, notée $\N(x)$, respectivement comme le polynôme caractéristique, la trace et le déterminant de $m_x$. La trace est un morphisme de $\QM$-espaces vectoriels de $K\to \QM$, la norme un morphisme de groupes $K^*\to \QM^*$. Plus généralement, ces définitions ont un sens dans n'importe quelle $k$-algèbre commutative de dimension finie sur un corps $k$ (on les utilisera dans $\QM_p[X]/(T)$ au \S\ref{se:r4}).

La matrice de $m_\a$ dans la base $(1,\a,\dots,\a^{n-1})$ est la matrice compagnon de $\Char{\a} = T$. (En particulier $\Char{\a}(\a) = 0$, qui résulte aussi de Cayley-Hamilton.) En se ramenant au cas primitif $K = \QM(\alpha)$, on montre plus généralement que

\begin{theo}\label{th:char} On a
\begin{align} \Char{x}(X) & =  \prod_{i = 1}^n (X - \s_i(x)) = \Min{x}(X)^{\dim_{\QM(x)} K}, \\ \Tr(x) & =  \sum_{i = 1}^n \s_i(x), \\ \N (x) & =  \prod_{i = 1}^n \s_i(x).\label{eq:Nsigma}
\end{align}
\end{theo}

\noindent Ces calculs sont effectués dans $\CM$, mais le résultat final appartient au sous-corps $\QM$.

\begin{theo}\label{th:tr} La forme bilinéaire $T:(x,y)\mto \Tr(xy)$ sur $K^2$ est non dégénérée.
\end{theo}

\begin{proof}
Si $x\neq 0$, alors $\Tr (x \cdot 1/x) = \Tr (1) = n \neq 0$.
\end{proof}

\noindent L'extension de cette forme quadratique à $K\otimes_\QM \RM\simeq \RM^{r_1}\times \CM^{r_2}$ est
\begin{equation}\label{eq:T} (x_1,\dots,x_{r_1},a_1+ib_1,\dots,a_{r_2}+ib_{r_2}) \mto \sum_{i\leq r_1} x_i^2 + 2\sum_{j\leq r_2} (a_j^2 - b_j^2),
\end{equation}
de signature $(r_1+r_2, r_2)$.

\subsection{Théorie de Galois} On va peu en parler, par manque de temps, et l'utiliser comme hypothèse technique dans des théorèmes ultérieurs. L'extension $K/\QM$ de degré $n$ est \emph{galoisienne} si le corps~$K$ admet $n$ automorphismes; autrement dit, si les conjugués $\a_i$ de $\a$ sont tous dans $K$. (Un automorphisme fixe $\QM$, donc est nécessairement de la forme $\a\mto\a_i$). On notera $\Gal(K/\QM)$ le groupe des automorphismes de $K$. Par exemple, un corps quadratique est galoisien, de groupe $\ZM/2\ZM$, ainsi que les corps cyclotomiques $\QM\big(\exp(2i\pi/n)\big)$, de groupe $(\ZM/n\ZM)^*$.

Remarquons que si $K/\QM$ est galoisienne de groupe de Galois $G$, on peut considérer $K$ comme sous-corps de $\CM$ et les $\s_i$ ne sont rien d'autre que les éléments de $G$. Plus précisément, pour chaque $i\leq n$, il existe un unique $\tau_i\in G$ tel que $\s_i = \s_1 \circ \tau_i$.

Si $T\in \QM[X]$, le corps de décomposition $K_T\subset \CM$ de $T$ est le plus petit corps contenant toutes les racines complexes de $T$. C'est une extension galoisienne de $\QM$. Par abus de langage, on appelle \emph{groupe de Galois} de $T$ le groupe de Galois de $K_T$.

\section{Anneau des entiers} Soit $x\in K$; $x$ est un \emph{entier algébrique} (ou simplement un \emph{entier} s'il n'y a pas risque de confusion) s'il satisfait les conditions équivalentes suivantes :
\begin{enumerate}
\item
$\Min{x}\in \ZM[X]$,
\item
$\Char{x}\in \ZM[X]$,
\item
il existe $Q\in\ZM[X]$, $Q$ unitaire, tel que $Q(x) = 0$,
\item
$\ZM[x]$ est un $\ZM$-module de type fini,
\item
il existe $M\subset K$ un $\ZM$-module de type fini contenant $\ZM[x]$.
\end{enumerate} On note $\ok$ l'ensemble des entiers de~$K$. On a $\ZM\subset \ok$; on voit facilement que $\O_\QM = \ZM$.

\begin{coro}\label{co:Z} En particulier, si $x\in \ok$, $\Tr x \in \ZM$, $\N x\in \ZM$.
\end{coro}

\begin{proof}
C'est une conséquence de la deuxième caractérisation.
\end{proof}

\begin{theo}\label{th:anneau} $\ok$ est un anneau intègre, de corps de fractions~$K$.
\end{theo}

\begin{proof}
La quatrième caractérisation montre que $\ok \subset K$ est stable par addition et multiplication: si $\ZM[x],\ZM[y]$ sont de type fini, $\ZM[x,y]\supset \ZM[x+y],\ZM[xy]$ aussi. Donc $\ok$ est un anneau. Étant contenu dans un corps, il est intègre.

Si $x\in K$, soit $d\in \ZM\subset \ok$ le dénominateur commun des coef\-ficients de $\Min{x}$. Alors $dx\in \ok$ puisque son polynôme minimal $d^n\Min{x}(X/d)$ est dans $\ZM[X]$. Donc $K = \Frac\ok$.
\end{proof}

Ceci montre que $\ok$ contient une $\QM$-base de $K$, $(e_1,\dots,e_n)$. Soit $(f_1,\dots,f_n)$ la base duale par rapport à la forme bilinéaire non dégénérée du théorème~\ref{th:tr}.
\begin{prop}\label{pr:dual} $\ok \subset \gen{f_1,\dots, f_n}_\ZM$.
\end{prop}

\begin{proof}
Si $x\!\in\!\ok$, $x \!=\! \sum x_i f_i$, $x_i\!\in\! \QM$. Pour tout $i$, $xe_i\!\in\!\ok$ d'après le théorème~\ref{th:anneau}, donc $\Tr (xe_i) = x_i\in \ZM$ (Corollaire~\ref{co:Z}).
\end{proof}

\begin{coro}\label{co:ok} $\ok$ est un $\ZM$-module libre de rang $n$.
\end{coro}

\begin{proof}
Le $\ZM$-module engendré par les $f_i$ est de type fini et sans torsion, donc libre. Donc $\ok$ est de type fini, libre de rang $\leq n$ (Proposition~\ref{pr:dual} et Corollaire~\ref{co:fini}). Il contient une $\QM$-base de $K$, donc est de rang exactement $n$.
\end{proof}

\noindent Donc il existe une base $(w_1,\dots, w_n)$ tel que tout $x\in\ok$ s'écrive de façon unique $x = \sum x_i w_i$, $x_i\in \ZM$. Ceci implique en particulier que $\ok/d\ok$ est de cardinal $d^n$ pour tout entier $d > 0$.

\begin{exemple*}
Un entier $d\in\ZM$ est dit sans facteurs carrés s'il n'existe pas $p$ premier tel que $p^2 \mid d$. Soit donc $d\in\ZM$ sans facteurs carrés, $T = X^2 - d$, $\a$ une racine de $T$ et $K = \QM(\a)$. Si $x = \frac{1}{2}(u + v\a)\in \QM(\a)$, $u,v\in\QM$, on calcule $\Char{x} = X^2 - uX + (u^2 + dv^2) / 4$. Donc $x\in \ok$ si et seulement si $u\in \ZM$, $u^2 - dv^2\in 4\ZM$; on en déduit $dv^2\in\ZM$, soit $v\in\ZM$ (car $d$ est divisible par le carré du dénominateur de $v$). Les seuls carrés modulo $4$ étant $0$ et $1$, on en déduit que $u,v$ sont pairs si $d\equiv 2,3\pmod{4}$ et de même parité si $d\equiv 1\pmod{4}$. Soit
$$\ok =
\begin{cases} \ZM[\a] & \text{si $d \equiv 2,3\pmod{4}$},\\ \ZM[(1+\a)/2] & \text{si $d \equiv 1\pmod{4}$}.
\end{cases}
$$
\end{exemple*}

\section{Idéaux} \subsection{Produit d'idéaux, idéaux fractionnaires, idéaux inversibles} Soit $R$ un anneau intègre, de corps de fractions $K$. Un idéal \emph{non nul} de $R$ est dit \emph{entier}. Si $\A,\B$ sont deux idéaux entiers, on définit leur produit $\A\B$ comme l'idéal engendré par les produits $ab$, $a\in \A$, $b\in \B$. C'est une opération associative dont $R$ est l'élément neutre.

On appelle \emph{idéal fractionnaire} de $K$ un sous $R$-module $\A$ de $K$ tel que $d\A$ soit entier pour un $d\in K^*$. (En particulier un idéal fractionnaire est non nul.) La multiplication des idéaux s'étend aux idéaux fractionnaires: si $\A,\B$ sont entiers, on pose $(\A/a)(\B/b) = \A\B/ab$. Un~idéal fractionnaire $\A$ de $K$ est \emph{inversible} s'il existe un idéal fractionnaire $\B$ tel que $\A\B = R$; on note $\B = \A^{-1}$.

Un anneau intègre est dit \emph{de Dedekind} si tout idéal fractionnaire est inversible.

\subsection{Norme d'idéaux}\label{se:norme} On note $\N\A = \#(\ok/\A) \leq +\infty$ la \emph{norme de $\A$}; en particulier, si $\A = (a)$ est principal, le corollaire~\ref{co:coker} appliqué à $\phi = m_a$ donne $\N\A = \abs{\N(a)}$.
\begin{prop} Si $\A\subset\ok$ est un idéal non nul, le quotient $\ok/\A$ est fini.
\end{prop}

\begin{proof}
Si $a\in\A\setminus\set{0}$, la surjection $\ok/(a) \twoheadrightarrow \ok/\A$ montre que $\N\A \mid \N(a)$, qui est un entier non nul.
\end{proof}

\begin{coro} Un idéal premier non nul de $\ok$ est maximal.
\end{coro}

\begin{proof}
Un anneau intègre fini est un corps. (La multiplication par un élément non nul est un endomorphisme injectif, donc surjectif par finitude.)
\end{proof}

\Subsection{Théorème fondamental de l'arithmétique}

\begin{theo} Si $K$ est un corps de nombres, $\ok$ est un anneau de Dedekind. De plus, on a
$$
\A^{-1} = (\ok:\A) := \set{x\in K\colon x\A \subset \ok}.
$$
\end{theo}

La démonstration n'est pas difficile mais assez technique, on va seulement l'esquisser. On voit facilement que $\A' := (\ok:\A)$ est un idéal fractionnaire et $\A\A'\subset \ok$, mais l'inclusion réciproque n'a rien d'évident. L'étape cruciale consiste à montrer que le théorème est vrai pour $\A = \p$ maximal. Dans ce cas on montre d'abord l'existence de $a\in \A'\setminus\ok$, qui vient d'un argument de maximalité, utilisant le caractère noethérien de $\ok$ et le fait que tout idéal premier non nul est maximal. Comme $\A'\p$ est un idéal entier et $\p$ est maximal, la~double inclusion $\p\subset \A'\p \subset \ok$ implique $\A'\p = \ok$ (et on a fini), ou $\A'\p = \p$. Mais ce dernier cas est impossible puisque $\p$ est un $\ZM$\nobreakdash-module de type fini, donc $a\p \subset \p$ impliquerait $a\in \ok$. On conclut en montrant que tout idéal entier est produit d'idéaux premiers, avec le même type d'argument noethérien que celui omis ci-dessus.

Plus généralement, la démonstration prouve qu'un anneau intègre~$R$ est de Dedekind si et seulement s'il est
\begin{itemize}
\item
noethérien (tout $R$-idéal a un nombre fini de générateurs),
\item
intégralement clos (si $x\in\Frac R$ est racine d'un polynôme unitaire de $R[X]$ alors $x\in R$),
\item
de dimension de Krull $1$ (tout idéal premier non nul est maximal).
\end{itemize}
La preuve a un corollaire important, généralisation du théorème fondamental de l'arithmétique sur $\ZM$, qui montre que $\ok \subset K$ est une généralisation appropriée de $\ZM\subset\QM$:

\begin{coro}\label{co:uni} Si $K$ est un corps de nombres, tout idéal fractionnaire~$\A$ se factorise de manière unique sous la forme $\A = \prod_\p \p^{e_\p}$, où $\p$ parcourt l'ensemble des idéaux maximaux de $\A$, $e_\p\in\ZM$, tous nuls sauf un nombre fini. (On convient que le produit vide est l'élément neutre de la multiplication, $\ok$. En particulier $\p^0 = \ok$.)
\end{coro}

\begin{proof}
Il suffit de le démontrer pour un idéal entier. Seule l'unicité reste à voir: on choisit un idéal entier $\A$, qui a une décomposition de longueur minimale parmi les idéaux entiers admettant plusieurs décompositions. Soit $\A = \p_1\cdots\p_r = \q_1\cdots\q_s$, où les $\p_i$ et les $\q_j$ sont maximaux et $r$ minimal. Alors $\q_1\cdots\q_s \subset \p_1$ et, $\p_1$ étant premier, l'un des $\q_i$ est contenu dans $\p_1$; $\q_i$ étant maximal, ils sont égaux. En multipliant par $\p_1^{-1}$, on obtient un idéal entier admettant deux décomposition, dont l'une de longueur $ < r$. Contradiction.
\end{proof}

\noindent L'existence d'une décomposition est vraie sous des hypothèses plus faibles. Le point crucial est l'\emph{unicité}.

\subsection{Valuation et divisibilité} Pour $\A = \prod \p^{e_\p}$ fractionnaire et $\p$ maximal, on définit la valuation $\p$-adique de $\A$, $v_\p(\A) := e_\p$. Pour $x\in K^*$ on pose $v_\p(x) := v_\p(x\ok)$, et $v_\p(0) = +\infty$. Noter que
\begin{equation}\label{eq:triang} v_\p(x + y) \geq \min(v_\p(x), v_\p(x)),
\end{equation}
avec égalité si $v_\p(x) \neq v_\p(y)$. Finalement on écrit pour $x,y\in K$, $\A$ un idéal fractionnaire:
$$
x \equiv y \pmod{\A},\quad\text{si}\quad v_\p(x - y) \geq v_\p(\A), \forall \p.$$
Par exemple, $\sfrac{1}{2} \equiv \sfrac{5}{2} \pmod{2\ZM}$ dans $\QM$.

Grâce au théorème fondamental, on transporte aux idéaux fractionnaires le vocabulaire de la divisibilité dans $\ZM$: $\A \mid \B$ si $v_\p(\A) \leq v_\p(\B)$, $\forall \p$; on pose
$$
\pgcd(\A,\B) := \prod_\p \p^{\min(v_\p(\A), v_\p(\B))},$$
$$
\ppcm(\A,\B) := \prod_\p \p^{\max(v_\p(\A), v_\p(\B))},$$
d'où on tire $\pgcd(\A,\B)\cdot \ppcm(\A,\B) = \A\B$. À titre d'exercice, démontrer les deux lemmes suivants:

\begin{lemm}
Si $\A,\B$ sont des idéaux fractionnaires, $\A\mid \B\Leftrightarrow \B \subset \A$.
\end{lemm}

\begin{lemm}
Si $\A,\B$ sont des idéaux entiers et $\A + \B$ le plus petit idéal contenant $\A$ et $\B$, alors $\A + \B = \pgcd(\A,\B)$.
\end{lemm}

On dit que $\A,\B$ sont premiers entre eux si $\pgcd(\A,\B) = \ok$. Le lemme chinois s'adapte facilement:

\begin{lemm}
Si $\A,\B$ sont entiers et premiers entre eux, on a un isomorphisme d'anneaux $\ok/\A\B \simeq \ok/\A \times \ok/\B$.
\end{lemm}

\begin{proof}
Comme $\A\B\subset \A\cap\B$ l'application $\ok/\A\B\to \ok/\A\times \ok/\B$ est bien définie. Si $x\in \ok$ est tel que $\A\mid (x)$ et $\B\mid (x)$, alors $\A\B\mid (x)$ par coprimalité et unicité de la décomposition en produit d'idéaux maximaux; ceci assure l'injectivité. Pour la surjectivité, il~existe $a\in\nobreak \A$, $b\in\B$, tels que $a + b = 1$ (car $\A + \B = \ok$); donc si $(\a,\b)\in \ok/\A \times \ok/\B$, alors $b\a + a\b\in \ok/\A\B$ est un antécédent.
\end{proof}

\noindent En particulier, les cardinaux des deux membres sont les mêmes. Plus généralement

\begin{prop}
Si $\A,\B$ sont deux idéaux entiers, alors on a $\N \A\B = \N\A\cdot\nobreak\N\B$.
\end{prop}

\begin{proof}
En itérant le lemme chinois, il reste à montrer que $\N\p^{k+1} = \N\p \N\p^k$ pour $\p$ maximal. Soit $a\in \p^{k+1}\setminus \p^k$; la multiplication par $a$ induit un morphisme de groupe additifs de $\ok/\p\to \p^k/\p^{k+1}$. Si $x$ est dans le noyau, $\p^{k+1} \mid (xa)$ soit $\p \mid (x)$; l'injectivité suit. Pour la surjectivité, soit $y$ un représentant de $\bar{y}\in \p^k/\p^{k+1}$; comme $y\in \p^{k+1} + (a) = \p^k$, la congruence $ax \equiv y \pmod{\p^{k+1}}$ a une solution $x\in \ok$.
\end{proof}

\noindent On prolonge la norme aux idéaux fractionnaires:
\[
\N(\A/a) := \N\A / \abs{\N(a)}.
\]
Elle reste bien entendu multiplicative.

\begin{prop}\label{pr:idfini} Le nombre d'idéaux entiers de norme $\leq C$ est fini.
\end{prop}

\begin{proof}
La norme étant un entier positif, il suffit de démontrer qu'il existe un nombre fini d'idéaux entiers $\A$ de norme donnée $N = \#(\ok/\A)$. Le théorème de Lagrange donne $N \in \A$ soit $\A \mid N\ok$. Or $N\ok = \prod_\p \p^{e_\p}$ a exactement $\prod_\p (e_\p + 1) < +\infty$ diviseurs.
\end{proof}

\subsection{Décomposition des premiers}\label{se:primes} Un cas particulier important du théorème fondamental nous dit que chaque nombre premier~$p$ se décompose sous la forme
\begin{equation}\label{eq:decomp} p\ok = \prod_{\p \mid p} \p^{e(\p/p)},
\end{equation}
et on écrit $\N\p = \abs{\ok/\p} = p^{f(\p/p)}$. On dira que $\p$ est \emph{au-dessus} de~$p$. L'exposant $e(\p/p)$ est le \emph{degré de ramification} de $\p/p$. L'exposant $f(\p/p)$ est le \emph{degré résiduel} de $\p/p$. Déterminer la décomposition des nombres premiers est la clé de la factorisation effective d'un idéal fractionnaire $\A$: en effet, factorisant séparément numérateur et dénominateur, on peut supposer $\A$ entier. Comme on vient de le voir $\A \mid (\N\A)\ok$, il suffit donc de factoriser l'entier naturel $\N\A$ et de calculer $v_\p(\A)$ pour chaque $\p \mid p \mid \N\A$.

\begin{theo}[Kummer]\label{th:Kummer} Soit $K = \QM(X)/(T)$, $T\in\ZM[X]$ unitaire et $\t = X \pmod{T}$. \emph{On suppose que $p\nmid [\ok:\ZM[\t]]$.} Alors \og la factorisation de $T\bmod p$ reflète celle de $p\ok$\fg. Plus précisément, supposons
$$
T \equiv \prod_i P_i^{e_i} \pmod{p\ZM[X]},$$
où les $P_i$ sont unitaires, irréductibles et $2$ à $2$ distincts modulo $p$. Alors
$$
p\ok = \prod_i \p_i^{e_i},
$$
où les $\p_i := p\ok + P_i(\t)\ok$ sont maximaux, $2$ à $2$ distincts et de degré résiduel $\deg P_i$.
\end{theo}

Le théorème~\ref{th:dedek} explique comment tester l'hypothèse \hbox{$p\!\nmid\! [\ok{:}\ZM[\t]]$}, vraie pour tout $p$ sauf un nombre fini. En particulier elle est vérifiée quand $\overline{T}$ est sans facteurs carrés (les $e_i$ sont tous égaux à $1$). Le théorème~\ref{th:r4} nous dira quoi faire quand elle n'est pas satisfaite.

On dit que $p$ est \emph{non ramifié} si $e(\p/p) = 1$ pour tout $\p\mid p\ok$. La discussion qui précède a montré que c'est le cas générique: un nombre fini de $p$ sont ramifiés. On s'intéressera aux valeurs possibles pour $f(\p/p)$ au \S\ref{se:densite}. Pour l'instant, notons que la multiplicativité de la norme, appliquée à \eqref{eq:decomp}, implique l'identité
\begin{equation}\label{eq:efg} \sum_{\p \mid p} e(\p/p) \cdot f(\p/p) = n.
\end{equation}

\Subsection{Le morphisme de Frobenius}

\begin{prop}\label{pr:trans} Si $K/\QM$ est galoisienne de groupe $G$, les idéaux maximaux $\p$ divisant un même premier $p$ sont permutés transitivement par~$G$.
\end{prop}

\begin{proof}
Supposons que $\p$ et $\q$ sont deux maximaux divisant un même premier $p$, appartenant à deux orbites distinctes, $o(\p)\neq o(\q)$. Soit $x\in\p\setminus o(\q)$ (existe par le lemme chinois). Puisque $x\in\p$, $p \mid \N\p \mid \N(x)$; d'autre part, $\N(x) = \prod_{\s\in G} \s(x)$. Comme $\q \mid p\ok$, $\q\mid \N(x)\ok$, soit $\prod \s(x) \in \q$. L'idéal $\q$ étant premier, il existe $\s\in G$ tel que $\s(x)\in \q$, soit $x\in\s^{-1}\q$. Contradiction.
\end{proof}

Si $K/\QM$ est galoisienne, on en déduit que $e = e(\p/p)$ et $f = f(\p/p)$ dépendent uniquement de $p$, pas de $\p$, et l'équation \eqref{eq:efg} s'écrit $ef\#\set{\p \mid p} = n$. On note
$$
D(\p) = \set{\s\in G\colon \s\p = \p},
$$
donc $D(\s\p) = \s D(\p) \s^{-1}$ pour tout $\s\in G$. De $\abs{G} = n$ et de la proposition~\ref{pr:trans}, on déduit $\#D(\p) = ef$. Le groupe $G$, donc aussi $D(\p)$, stabilise $\ok$; on montre que la projection canonique $\ok\to \ok/\p$ induit un morphisme \emph{surjectif} de $D(\p)$ dans $\Aut (\ok/\p)$, qui est un groupe de cardinal $f$, engendré par le morphisme de Frobenius $x\mto x^p$. Le noyau $I(\p)$ est donc de cardinal $e$; en particulier, $p$ est non ramifié si et seulement si $I(\p) = \set{\Id}$.

Dans ce cas, on note $\Frob_\p$ l'unique $\s\in D(\p) \subset G$ se réduisant sur le Frobenius $x\mto x^p$. Le \emph{symbole de Frobenius} $\Frob_p\subset G$ désigne l'ensemble des $\Frob_\p$ pour $\p \mid p$. De même que $D(\s\p) =\s D(\p)\s^{-1}$, on vérifie que $\Frob_{\s\p} = \s \Frob_\p \s^{-1}$, pour $\s\in G$. Donc $\Frob_p$ est une classe de conjugaison de $G$.

En particulier, si $G$ est abélien, les classes de conjugaison ont un unique élément et $p\mto \Frob_p\in G$ associe un automorphisme de $K$ à tout premier non ramifié. Ainsi, si $K = \QM(\z_n)$, $G \simeq (\ZM/n\ZM)^*$ est abélien et $\Frob_p$ est donné par la classe de $p$ dans $(\ZM/n\ZM)^*$. D'après le théorème de la progression arithmétique, tout élément de $G$ est un Frobenius. C'est un phénomène général sur lequel on s'étendra au \S\ref{se:densite}.

\subsection{Valeurs absolues et places} \label{se:places} On appelle \emph{valeur absolue} de $K$ un morphisme $\abs{\cdot}:K^*\to\RM^*_+$, étendu à $K$ par $\abs{0} = 0$, et satisfaisant une inégalité triangulaire faible: il existe $C\geq 1$ tel que $\abs{x+y} \leq C(\abs{x} + \abs{y})$ pour tout $x,y\in K$. Une valeur absolue définit une métrique sur $K$, \textit{via} $d(x,y) = \abs{x - y}$, donc une topologie. Deux valeurs absolues sont \emph{équivalentes} si elles définissent la même topologie.

\begin{theo} Deux valeurs absolues $\abs{\cdot}_1$ et $\abs{\cdot}_2$ sont équivalentes si et seulement s'il existe $t > 0$ tel que $\abs{\cdot}_1 = \abs{\cdot}_2^t$.
\end{theo}

Par exemple, si $\p$ est maximal, $\abs{x}_\p := \N\p^{-v_\p(x)}$ est une valeur absolue. Plus généralement, $c^{v_\p(x)}$ serait une valeur absolue (équivalente à celle-ci) pour $c < 1$. L'inégalité triangulaire est ici renforcée, puisque \eqref{eq:triang} donne
$$
\abs{x+y}_\p \leq \max(\abs{x}_\p, \abs{y}_\p);
$$
on dit que $\abs{\cdot}_\p$ est \emph{non archimédienne}, par référence à l'axiome d'Archimède sur l'ordre de $\RM$. En effet ce dernier énonce que si $x, y\in\RM^*$, il existe $n\in \ZM$, tel que $\abs{nx} > \abs{y}$. Or $\abs{z}_\p \leq 1$ pour tout $z\in\ok\supset \ZM$, soit $\abs{nx}_\p \leq \abs{x}_\p$ pour tout $x\in K$, $n\in \ZM$.

Une autre classe d'exemples provient des plongements de $K$. Si $\s:K \hto \CM$ est l'un des $r_1 + 2r_2$ plongements de $K$ dans $\CM$, $|x| = \abs{\s(x)}^t$ est une valeur absolue pour tout $t > 0$. Celles-ci sont \emph{archi\-mé\-diennes} (vérifient l'axiome d'Archimède). Les valeurs absolues associées à deux plongements complexes conjugués sont équivalentes. On choisit la normalisation suivante
$$
\abs{x}_\s :=
\begin{cases} \abs{\s(x)} & \text{si $\s$ est réel},\\ \abs{\s(x)}^2 & \text{si $\s$ est complexe}.\\
\end{cases}
$$
Noter que $\abs{\cdot}_\s$ pour $\s$ complexe ne vérifie pas l'inégalité triangulaire. (C'est l'unique raison pour laquelle on a affaibli celle-ci.)

Un dernier exemple parfaitement inintéressant est fourni par la valeur absolue triviale: $\abs{x} = 1$ pour $x\in K^*$. On appelle \emph{place} de $K$ une classe d'équivalence de valeurs absolues non triviales.

\begin{theo}[Ostrowski] Les $\abs{\cdot}_{\s_i}$, pour $i \leq r_1 + r_2$ et les $\abs{\cdot}_\p$, pour~$\p$ maximal sont un système de représentants des places de $K$.
\end{theo}

En contemplant \eqref{eq:Nsigma} on obtient alors la \emph{formule du produit}: pour tout $x\in K^*$, on a $\prod_v \abs{x}_v = 1 $, où $v$ parcourt l'ensemble des représentants normalisés des places de $K$.

\section{Géométrie des nombres}

\subsection{Tailles} Une \og taille\fg $H$ sur un ensemble $E$ associe à chaque $x\in E$ un réel positif $H(x)$ tel que $\set{x\in E\colon H(x) < C}$ soit fini pour tout $C$. On veut introduire des considérations de taille sur $K$. Si la norme convient pour les idéaux entiers (Proposition~\ref{pr:idfini}), l'exemple des $(2 - \sqrt{3})^n$, $n\in \NM$, tous distincts de norme $1$ montre qu'il n'en est pas de même sur $K$. Le même exemple montre que le module complexe, en considérant $K \subset \CM$, ne suffit pas non plus.
\begin{defi} La \emph{hauteur} naïve $H(\a)$ de $\a\in K$ est définie par
$$
H(\a):= \prod_v \max\set{1, \abs{\a}_v},
$$
où $v$ parcourt l'ensemble des places de $K$.
\end{defi} On montre que $H(\a)$ ne dépend pas du corps de nombres $K$ contenant $\QM(\a)$. Elle a aussi une traduction agréable quand $K = \QM$:
\begin{prop} Soit $a/b \in \QM$, fraction réduite au plus petit dénominateur. Alors $H(a/b) = \max(\abs{a}, \abs{b})$.
\end{prop}

\begin{proof}
Les places de $\QM$ sont les $p$ premiers et la place archimédienne associée à la valeur absolue usuelle. Si $a = 0$, $b = \pm1$ et le résultat est évident. Sinon, le produit sur les $p$ premiers vaut $\prod_{p, v_p(a/b) < 0} p^{-v_p(a/b)} = \abs{b}$, que l'on multiplie par $\max(1, \abs{a/b})$.
\end{proof}
\begin{prop} Pour tout $C \!\geq\! 1$, le nombre de $x\!\in\! K$ tels que $H(x) \!<\! C$ est fini.
\end{prop}

\begin{proof}
On peut écrire $x\ok = \A/\B$ où $\A,\B$ sont entiers premiers entre eux. Le produit sur les $v$ non archimédiennes et archimédiennes sont tous deux bornés par $C$. Le premier montre que $\N\B < C$ (nombre fini de possibilités), le deuxième que $y = \N\B x$, qui appartient à $\ok$, a tous ses plongements bornés par $C^2$; les coefficients de $\Char{y}\in \ZM[X]$ sont donc bornés. On a donc un nombre fini de possibilités pour $\Char{y}$, donc pour~$y$.
\end{proof}

La fonction $H$ est la \og bonne\fg notion théorique; cependant, d'un point de vue calculatoire, elle est peu commode. On préférerait une notion de type norme infinie, par exemple $H_{\infty}(x) := \max \abs{x}_v$ où~$v$ parcourt seulement l'ensemble des places \emph{archimédiennes}. On ne contrôle plus les dénominateurs, mais $H_{\infty}(x)$ ne dépend toujours pas de $K$ et peut jouer le rôle de taille sur $\ok$. D'un strict point de vue algorithmique, on préfère une norme $L^2$ pour des raisons qui apparaîtront aux~\S\ref{se:polred} et~\S\ref{se:ALLL}, l'algorithme LLL en particulier. On considère donc $K\otimes_\QM \RM \simeq \RM^{r_1} \times \CM^{r_2}$ comme un espace euclidien muni de la forme naturelle
$$
T_2: (x_1, \dots, x_{r_1}, z_1, \dots, z_{r_2}) \mto \sum_{i\leq r_1} x_i^2 + 2\sum_{j\leq r_2} \abs{z_j}^2,
$$
\emph{cf}.~\eqref{eq:T}; noter que si $r_2 = 0$, $T_2$ est la forme trace du théorème~\ref{th:tr}. Explicitement, pour $x\in K$,
$$
T_2(x) = \sum_{k = 1}^n \abs{\s_k(x)}^2.
$$
\begin{prop}\label{pr:T2fini} Pour $C > 0$, le nombre de $x\in \ok$ tels que $T_2(x) < C$ est fini.
\end{prop}

\begin{proof}
$\ok$ est discret (corollaire~\ref{co:ok}) et la boule $T_2(x) \leq\nobreak C$ est compacte.
\end{proof}

\begin{theo}[Kronecker]\label{th:kro} Soit $x\in \ok$, $x\neq 0$. Alors $T_2(x) \geq n$ avec égalité si et seulement si $x$ est une racine de l'unité.
\end{theo}

\begin{proof}
L'inégalité est celle de la moyenne arithmético-géométrique: $\abs{\N(x)}^{2/n} \leq \frac{1}{n}T_2(x)$, qui implique $T_2(x)\geq n$ puisque $\abs{\N(x)}\geq 1$. On a égalité si et seulement si les $\abs{\s_k(x)}^2$ sont tous égaux, nécessairement à $1$ puisque leur somme est $n$. L'ensemble $\set{x^k, k > 0}\subset \ok$ est borné pour $T_2$, donc fini d'après la proposition. Donc $x$ est une racine de l'unité.
\end{proof}

\subsection{Discriminant} On utilise les notations du \S\ref{se:reseau}. Par extension des scalaires, $E = (K\otimes_\QM \RM, T_2)$ est un espace euclidien. Si $\L$ est un sous-$\ZM$-module libre de rang $n$ de $K$, on peut le considérer comme réseau de $E$. On a défini au \S\ref{se:reseau} son déterminant $d(\L)$ et son discriminant $\D_\L = d(\L)^2$.
\begin{defi} On note $\D_K = \D_{\ok}$ le discriminant de $\ok$.
\end{defi} \noindent Ceci définit le discriminant comme carré d'un volume, on aurait pu le définir algébriquement grâce aux identités suivantes: si $(e_1,\dots,e_n)$ est une $\ZM$-base de $\L$, $S = (\s_j(e_i))_{i,j\leq n}$, et $T = (\Tr (e_i e_j))_{i,j\leq n}$ la matrice de la forme trace, on a
$$
\text{Gram}(e_1,\dots,e_n) = S \cdot \overline{\tran{S}}, \quad T = \Big(\sum_k \s_k(e_i) \s_k(e_j)\Big)_{i,j\leq n} = S \cdot \tran{S}.
$$
En particulier, $\D_K = \abs{\det T}$. Comme $T$ est à coefficients entiers, $\D_K\in\NM$. Plus généralement:
\begin{prop}\label{pr:indice} Soit $\O$ un sous-$\ZM$-module d'indice fini de $\ok$, et $\D_\O$ son discriminant. Alors $\D_\O\in\NM$ et $\D_\O = \D_K[\ok:\O]^2$.
\end{prop}

\begin{proof}
Résulte de ce qui précède et du corollaire~\ref{co:indice}.
\end{proof}

\subsection{Applications du théorème de Minkowski}

Notre premier corollaire dit simplement qu'un idéal entier contient un élément non nul de norme proche du minimum:

\begin{coro}\label{co:minid} Si $K$ est un corps de nombres de degré $n$ et signature $(r_1,r_2)$, alors tout idéal entier $\A$ contient un $a\neq 0$ tel que
$$
\abs{\N(a)} \leq c_K \cdot \N\A, \quad\text{où $c_K := \left(\frac{4}{\pi}\right)^{r_2}\frac{n!}{n^n} \sqrt{\D_K}$.}
$$
\end{coro}
\noindent
Noter que $a\in \A$ implique $\N\A \mid \N(a)$.

\begin{proof}
On plonge $K$ dans $K\otimes_\QM \RM \simeq \RM^{r_1}\times \CM^{r_2}\simeq \RM^n$ par
\begin{multline*}
x\mto\big(\s_1(x),\dots, \s_{r_1}(x), \re\s_{r_1+1}(x), \im\s_{r_1+1}(x), \dots,\\ \re\s_{r_1+r_2}(x), \im\s_{r_1+r_2}(x) \big),
\end{multline*}
muni de la forme euclidienne standard. On en considère $\A$ et $\ok$ comme des réseaux, qui vérifient $d(\A) = d(\ok)\N\A$. Par rapport à la structure euclidienne utilisée pour définir $\sqrt{\D_K} = d(\ok,T_2)$, on a remplacé $T_2(x) = \sum_{i=1}^{r_1+2r_2} \abs{\s_i(x)}^2$ par $\sum_{i=1}^{r_1+r_2} \abs{\s_i(x)}^2$, soit $d(\ok) = 2^{-r_2}\sqrt{\D_K}$.

On pose
$$
C_t \!:=\! \Big\{(x_1,\dots,x_{r_1}, z_1,\dots,z_{r_2}) \in\RM^{r_1}\times \CM^{r_2}\colon\hspace*{-1mm} \sum_{i\leq r_1} \abs{x_i} + 2\sum_{j\leq r_2} \abs{z_j}^2 \leq t\Big\},$$
de volume $V(C_t) = 2^{r_1}(\frac{\pi}{2})^{r_2} t^n / n!$\,. Il existe un point non nul de $\A$ dans $C_t$ si $V(C_t) \geq 2^n d(\A)$: on peut prendre $t^n = (\frac{4}{\pi})^{r_2} n! \sqrt{\D_K} \N\A$, en utilisant $r_1 + 2r_2 = n$. D'autre part, par l'inégalité de la moyenne arithmético-géométrique, un point de $C_t$ vérifie \[ \prod_i \abs{x_i}\prod_j \abs{z_j}^2 \leq \paren{\frac{t}{n}}^n.\qedhere \]
\end{proof}

\begin{coro}\label{co:ck} Tout idéal fractionnaire $\AA$ de $K$ s'écrit $\AA = (\a)\A$, où $\a\in k^*$ et $\A$ est un idéal entier tel que $\N\A \leq c_K$.
\end{coro}

\begin{proof}
Soit $\BB := \AA^{-1} = \frac{1}{d}\B$, où $\B$ est entier. Donc $\B$ contient $b\neq 0$ tel que $\abs{\N(b)} \leq c_K \N\B$; l'idéal $(b)\B^{-1}$ est entier, de norme $\leq c_K$. On pose $\a = d/b$.
\end{proof}

\noindent Appliquant le corollaire~\ref{co:minid} à $\A = \ok$, on remarque que le membre de gauche est un entier naturel $\geq 1$. Une rapide étude de fonction donne:

\begin{coro} Si $n > 1$, i.e.~$K\neq \QM$, alors $\D_K > 1$. Si $n\to+\infty$, alors $\D_K \to+\infty$.
\end{coro} \noindent Les mêmes techniques permettent de prouver:

\begin{theo}[Hermite] Soit $X > 0$. Les corps de nombres $K$ tels que $\D_K < X$ sont en nombre fini.
\end{theo}

\begin{proof}[\proofname\ (idée)]
Grâce au dernier corollaire, on peut supposer~$K$ de degré $n$ fixé. Supposons d'abord $r_1 > 0$. Par Minkowski, on construit $\a\in \ok$ tel que tous les $\s_i(\a)$ sont de module $< 1$, à~l'exception d'un d'entre eux, de module borné en fonction de $\D_K$. D'après la proposition~\ref{pr:T2fini}, il existe un nombre fini de tels $\a$. Par construction, la racine distinguée de $\Char{\a}$ est simple donc $K = \QM(\a)$ (Théorème~\ref{th:char}). Si $r_1 = 0$, on procède de même avec deux racines distinguées de module $> 1$, complexes conjuguées et toutes deux simples.
\end{proof}

\noindent Si $N_n(X)$ désigne le nombre de corps de nombres $K$ de degré $n > 1$ satisfaisant $\D_K\leq X$, on pense que $N_n(X)\sim \a_n X$ quand $X\to\nobreak \infty$, pour un certain $\a_n > 0$. Le meilleur résultat connu dans cette direction, obtenu par Ellenberg et Venkatesh~\cite{EllVen}, dit que pour tout $\e > 0$, on a
$$
\limsup_{X\to+\infty} \frac{\log N_n(X)}{\log X} < n^\e,\quad \liminf_{X\to+\infty} \frac{\log N_n(X)}{\log X} \geq \frac{1}{2} + \frac{1}{n^2},
$$

\section{Groupe des classes, unités} Revenons à nos préoccupations diophantiennes; on a une bonne théorie de la divisibilité pour les idéaux. Si $\ok$ est principal, et que l'on maîtrise ses unités $U(K)$, on peut revenir des idéaux aux éléments de $K$.

\subsection{Groupe des classes} D'après le théorème fondamental, l'ensemble $I(K)$ des idé\-aux fractionnaires de $K$ est un groupe abélien. Le \emph{groupe des classes d'idéaux} de $K$, noté $\Cl(K)$, est le quotient de $I(K)$ par le sous groupe $P(K)$ des idéaux fractionnaires principaux.

\begin{theo} Le groupe $\Cl(K)$ est fini.
\end{theo}

\begin{proof}
On applique le corollaire~\ref{co:ck}. Les idéaux entiers de norme bornée étant en nombre fini (Proposition~\ref{pr:idfini}), il en est de même du nombre de classes d'idéaux.
\end{proof}

\noindent Le cardinal de $\Cl(K)$, noté $h(K)$, est le \emph{nombre de classes} de $K$.

Le groupe des classes mesure une obstruction (à la principalité de~$\ok$); idéalement, il est trivial. C'est expérimentalement relativement fréquent, mais la conjecture naturelle est toujours ouverte:
\begin{guess}[Gauss-Hasse] Il existe une infinité de corps de nombres $K\subset \CM$ tels que $h(K) = 1$.
\end{guess} Pour toute signature $(r_1,r_2)$ différente de $(1,0)$ ($K = \QM$) et $(0,1)$ ($K$ quadratique imaginaire), on pense qu'il existe une infinité de $K$ partageant cette signature tels que $h(K) = 1$. Il est nécessaire d'exclure $(0,1)$ :

\begin{theo}[Heegner, Stark, Baker (indépendamment)]\label{th:h1} Un corps quadratique imaginaire $K \!=\! \QM(\sqrt{-\D_K})$ vérifie $h(K) \!=\! 1$ si et seulement si
$$
\D_K \in \set{3, 4, 7, 8, 11, 19, 43, 67, 163}
$$
\end{theo}

\noindent C'est un théorème difficile (qui serait une conséquence facile de l'hypo\-thèse de Riemann, voir le théorème de Brauer-Siegel~\ref{th:BS}); par contre, il est relativement simple de montrer que la liste est complète à une exception près.

\subsection{Unités, \texorpdfstring{$S$}{S}-unités, et régulateurs} Les \emph{unités} $U(K) := \ok^*$ de $\ok$ forment un $\ZM$-module de type fini dont la structure est donnée par le théorème de Dirichlet:
$$
U(K) = (\ZM/w\ZM)\cdot \zeta \oplus \bigoplus_{i = 1}^{r_1 + r_2 - 1} \ZM \cdot \eta_i.
$$
En d'autre termes chaque unité s'écrit $\zeta^{a_0}\prod \eta_i^{a_i}$ où $a_0\in\ZM/w\ZM$ et les $a_i\in \ZM$ sont uniquement déterminés. Plus généralement, soit $S_\infty$ l'ensemble des $r_1 + r_2$ places archimédiennes et $S$ un ensemble fini de places contenant $S_\infty$. On définit
$$
U_S(K) = \set{x\in K: \abs{x}_{\p} = 1, \forall\p\not\in S},
$$
le groupe des \emph{$S$-unités} de $K$. En particulier $U_{S_\infty}(K) = U(K)$.

\begin{theo}[Dirichlet, généralisé par Chevalley et Hasse] $U_S(K)$ est somme directe du groupe cyclique $\mu(K)$ des racines de l'unité de $K$ et d'un $\ZM$-module libre de rang $\abs{S} - 1$.
\end{theo}

\begin{proof}[\proofname\ (vague idée)]
Comme le corps cyclotomique $\QM(\zeta_n)$ est de degré $\phi(n)\to+\infty$ quand $n\to+\infty$, $\mu(K)$ est fini. Il est donc cyclique (comme sous-groupe fini du groupe multiplicatif d'un corps). On considère $\Phi: U_S(K)\to \RM^S$, qui à $x$ associe $(\log \abs{x}_v)_{v\in S}$. C'est un morphisme de groupe dont l'image est incluse dans l'hyperplan $\sum_v x_v = 0$ (formule du produit). Le théorème \ref{th:kro} donne $\Ker \Phi = \mu(K)$. On montre ensuite que l'image de $\Phi$, isomorphe à $U_S(K) / \mu(K)$, est un réseau de cet hyperplan (c'est assez long).
\end{proof}

Soit $(\eta_i)_{1\leq i < \abs{S}}$ une base de $U_S(K)/\mu(K)$. Le $S$-\emph{régulateur}~$R_S(K)$ de $K$ est la valeur absolue du déterminant de la matrice
\[
(\log \abs{\eta_i}_v)_{v\in S\setminus\set{v_0}},
\]
où $v_0\in S$ est choisie arbitrairement, et le déterminant de la matrice vide est $1$ par définition si $S$ ne contient qu'un élément. (Exercice: la définition ne dépend pas du choix de~$v_0$.) On pose $R(K) := R_{S_\infty}(K)$.

\subsection{Heuristiques}\label{se:heu} On a très peu de résultats généraux sur $\Cl(K)$, mais on dispose d'un modèle probabiliste convaincant, dû à Cohen-Lenstra~\cite{Coh-heucla} (corps $K/\QM$ quadratiques) et Cohen-Martinet~\cite{Coh-etuheu} (extensions $K/k$ arbitraires). Voici le cas le plus simple:
\begin{guess} Si $f$ est une fonction de l'ensemble des classes d'isomorphismes de groupes abéliens finis dans $\RM^+$, si $G$ parcourt l'ensemble des classes d'isomorphismes de groupes abéliens finis, et $K$ les classes d'isomorphismes de corps quadratiques imaginaires, on définit
$$
\E_0(f) := \lim_{X\to+\infty} \dfrac{\sum\limits_{K, \D_K < X} f(\Cl(K))} {\sum\limits_{K, \D_K < X} 1} \leq +\infty,
$$
$$
\E'_0(f) := \lim_{X\to+\infty} \dfrac{\sum\limits_{G, \abs{G} < X} \frac{1}{\abs{\Aut G}} f(G)} {\sum\limits_{G, \abs{G} < X} \frac{1}{\abs{\Aut G}} 1} \leq +\infty.
$$
Alors, si $f$ est \og raisonnable\fg,
$$
\E_0(f) = \E'_0(f).$$
\end{guess}

Intuitivement, le modèle dit qu'en moyenne, le groupe des classes d'un corps quadratique imaginaire est le groupe (abélien, fini) $G$ avec probabilité $1/\abs{\Aut G}$. C'est un poids omniprésent en arithmétique, en particulier dans les \og formules de masse\fg, qui a le mérite d'expliquer la prépondérance des groupes cycliques parmi les groupes de classes calculés en pratique. Une première généralisation du modèle assimile les groupes de classes d'extensions galoisiennes $K/\QM$ dont le rang des unités $\rg U(K)$ est $r$ à un quotient $G/\gen{\s_1,\dots,\s_r}$ (dans la conjecture citée, $r = 0$).

Les fonctions liées au $2$-Sylow $G_2$ de $G$ (plus généralement aux $p$-Sylow $G_p$ pour $p$ divisant l'ordre de $\Gal(K/\QM)$) sont \textit{a priori} dérai\-sonnables: $G_2$ est soumis à des contraintes plus fortes et ne suit pas le modèle naïf. Par exemple si $K$ est quadratique imaginaire,
$$
r_2(\Cl(K)) = \w(\D_K) - 1,
$$
où $\w(n)$ désigne le nombre de diviseurs premiers distincts de $n$ (formule des genres, due à Gauss). Des fonctions $f$ raisonnables sont par exemple, $f(G) = \abs{G_p}$ ($p$ impair), la fonction caractéristique de l'ensemble des $G$ tels que $G/G_2$ soit cyclique, etc.

Pour les fonctions $f$ arithmétiquement raisonnables, $\E'_0(f)$ existe et se calcule facilement. Dans les rares cas où $\E_0(f)$ est connue, elle coïncide avec la prédiction. Un exemple célèbre est $f(G) = 3^{r_3(G)}$ (théorème de Davenport-Heilbronn~\cite{Dav-dendis2}), dont la valeur moyenne est connue pour les groupes de classes des corps quadratiques. L'accord avec le petit nombre de tables existantes est acceptable, mais la convergence apparente des densités est lente (une ou deux décimales correctes).

\section{Théorie analytique des nombres} \subsection{Fonctions \texorpdfstring{$L$}{L} de Hecke}

On encode tout ce que nous venons de voir dans la fonction zêta de Dedekind de $K$:
$$\zeta_K(s) := \sum_\A \N\A^{-s},$$
où $\A$ parcourt l'ensemble des idéaux entiers et $\re(s) > 1$. (Exercice: vérifier la convergence.) Bien sûr, $\zeta_\QM(s) = \zeta(s)$ est la fonction zêta de Riemann.

Plus généralement, soit $\chi:I(K)\to \CM^*$ un morphisme de groupes, trivial sur les idéaux principaux. Par passage au quotient, $\chi$ définit un caractère du groupe abélien fini $\Cl(K)$. On définit
$$
L(s,\chi,K) = \sum_\A \chi(\A)\N\A^{-s},
$$
où $\A$ parcourt l'ensemble des idéaux entiers de $K$. En particulier, si~$\chi_0$ est le caractère trivial, $L(s,\chi_0,K) = \zeta_K(s)$. \skpt

\begin{theo}\label{th:L}
\begin{enumerate}
\item
Si $\re(s) > 1$,
$$L(s,\chi,K) = \prod_\p (1 - \chi(\p)\N\p^{-s})^{-1}
$$
admet un produit eulérien, où $\p$ parcourt l'ensemble des idéaux maximaux de $\ok$.

\item
$(s-1)L(s,\chi,K)$ admet un prolongement holomorphe au plan complexe. On garde les notations $L(s,\chi,K)$ et $\zeta_K$ pour les fonctions méromorphes associées.

\item
$\zeta_K(s)$ a un pôle simple en $s = 1$ de résidu
$$
r_K := 2^{r_1}(2\pi)^{r_2} \frac{h(K)R(K)}{w(K)\sqrt{\D_K}},
$$
où $h(K)$, $R(K)$, $w(K)$ sont respectivement le nombre de classes, le régulateur, et le nombre de racines de l'unité de $K$.

\item
Si $\chi \neq \chi_0$, $L(s,\chi,K)$ est une fonction entière.

\item
Soit $A := 2^{-r_2}\pi^{-n/2}\D_K^{1/2}$ et $\gamma(s) := A^s \Gamma(s/2)^{r_1}\Gamma(s)^{r_2}$. La fonction
$$\xi(s,\chi,K) := s(s-1) \gamma(s) \zeta_K(s),
$$
est entière et vérifie l'équation fonctionnelle
$$\xi(s,\chi,K) = W(\chi) \cdot \xi(1 - s,\overline{\chi},K),$$
où $W(\chi)$ est un complexe de module $1$. On a $W(\chi_0) = 1$.
\end{enumerate}
\end{theo}

Les fonctions $L$ associées aux caractères de $\Cl(K)$ sont d'un genre très particulier, et ne généralisent pas les séries $L$ de Dirichlet, associées à un caractère de $(\ZM/N\ZM)^*$. Une généralisation possible est la suivante: on remplace $\Cl(K)$ par le \emph{groupe des classes de rayon $\f$}, $\Cl_\f:= I_\f(K)/\Cl_\f(K)$, où $\f$ est un idéal entier, $I_\f(K)$ est le sous-groupe de $I(K)$ formé des idéaux premiers à $\f$, et $P_\f(K)$ le sous-groupe des idéaux fractionnaires principaux $(\a)$, où $\a \equiv 1 \pmod{\f}$ et $\sigma(\a) > 0$ pour toutes les plongements \emph{réels} de~$K$. Le groupe $\Cl_\f(K)$ est fini, et c'est une extension de $\Cl(K)$ par
$$\big((\ok/\f)^* \times \set{-1,1}^{r_1}\big) / U(K),$$
où $U(K)\to (\ok/\f)^*$ est la projection canonique et $U(K)\to \set{-1,1}^{r_1}$ est le vecteur des signes des plongements réels. En particulier, si $K =\nobreak \QM$, $\f = q\ZM$, $\Cl_\f(K) = (\ZM/q\ZM)^*$.

Étant donné un caractère de $\Cl_\f$, on définit
\[
L(s,\chi,K) = \sum_\A \chi(\A)\N\A^{-s},
\]
en posant $\chi(\A) = 0$ si $\A$ et $\f$ ne sont pas premiers entre eux. Cette fonction $L$ vérifie des propriétés analogues à celles du théorème~\ref{th:L}, avec une équation fonctionnelle plus compliquée.

Les groupes $\Cl_\f(K)$ jouent un rôle important dans la théorie (classique) du \emph{corps de classe}, qui étudie les extensions abéliennes de $K$, c'est-à-dire les extensions galoisiennes de groupe de Galois abélien. Toute extension abélienne de $K$ se réalise comme sous-corps d'une extension $H_\f(K)/K$ pour un certain idéal entier $\f$, dont le groupe de Galois est $\Cl_\f(K)$. Si $K = \QM$, $\f = q\ZM$, on a $H_\f(K) = \QM(\zeta_q)$ et on retrouve le théorème de Kronecker-Weber: toute extension abélienne de $\QM$ est contenue dans un corps cyclotomique.

\subsection{Densités d'idéaux premiers}\label{se:densite}

La fonction $\zeta$ de Riemann permet de montrer le théorème des nombres premiers (essentiellement équivalent à $\zeta(1+it)\neq 0$ pour $t\in \RM$), les séries $L$ le théorème de la progression arithmétique (essentiellement équivalent à $L(1,\chi)\neq\nobreak 0$). Tous deux se généralisent en utilisant essentiellement les mêmes arguments analytique ($\zeta_K(1+it)\neq 0$ et $L(1,\chi,K)\neq 0$):

\begin{theo}[des idéaux premiers]\label{th:TNP} Soit $K$ un corps de nombres et $\pi_K(X)$ le cardinal de
$$
\set{\p\subset\ok\colon\text{$\p$ maximal, $\N\p \leq X$}}.
$$
Quand $X\to+\infty$, $\pi_K(X)\sim X/\log X$.
\end{theo}

\noindent La démonstration est analogue à celle du théorème des nombres premiers. Le théorème de la progression arithmétique est plus difficile, et a joué un rôle historique important dans le développement de la théorie du corps de classe:

\begin{theo}[Chebotarëv]\label{th:chebo} Soit $K/\QM$ une extension galoisienne de groupe $G$, et $C$ une classe de conjugaison de $G$. On note $\pi_K(X, C)$ le nombre de premiers $p \leq X$ non ramifiés tels que $\Frob_p \in C$. Quand $X\to+\infty$,
$$
\pi_K(x,C) \sim \frac{\abs{C}}{\abs{G}} \cdot \pi_K(X).
$$
\end{theo}

\noindent Pour une démonstration, voir \cite{Lang-ANT} ou \cite{Len-Ste} (ce dernier donne les grandes lignes d'une preuve n'utilisant pas la théorie du corps de classes).

Le théorème de Chebotarëv généralise le théorème de \hbox{Dirichlet}: $K \!=\! \QM(\zeta_q)$ est une extension galoisienne de $\QM$ de groupe $G \!\simeq\! (\ZM/q\ZM)^*$, qui est abélien. Donc $\abs{C} = 1$ et le théorème de Chebotarëv dit que les nombres premiers se répartissent de manière asymptotiquement équiprobable entre les différentes classes de $(\ZM/q\ZM)^*$.

Mentionnons un dernier corollaire utile, reposant sur l'interprétation suivante: soit $f\in\ZM[X]$ unitaire, irréductible de degré $n$ dans $\QM[X]$ et $K$ un corps de décomposition de $f$. L'extension $K/\QM$ est galoisienne de groupe de Galois $G\subset S_n$ ($G$ permute les $n$ racines de $f$ dans $K$). Supposons que la réduction $\bar{f}$ dans $\FM_p[X]$ est sans facteurs carrés, ce qui implique que $p$ est non ramifié dans $K$. Alors la classe de conjugaison de $\Frob_p$ dans $G$ détermine le type de décomposition de $f$ modulo $p$ (en fait, la classe de conjugaison dans $S_n$ le détermine déjà). Plus précisément:
\begin{itemize}
\item
si $\bar{f} = f_1\cdots f_g$ dans $\FM_p[X]$, où les $f_i$ sont irréductibles, distincts, l'ensemble $T = \set{\deg f_1,\dots,\deg f_g}$ est le \emph{type de décomposition} de~$\bar{f}$. (Par abus de langage, on écrira $\bar{f}\in T$.)

\item
si $\s\in S_n$, $\s = c_1\cdots c_g$ où les $c_i$ sont des cycles disjoints de $S_n$, la classe de conjugaison de $\s$ est déterminée par $\set{\lg(c_1),\dots, \lg(c_g)}$, où $\lg(c)$ désigne la longueur du cycle $c$.
\end{itemize}
Ces deux ensembles d'entiers sont identiques si $\s = \Frob_p$, sous l'hypothèse que les $f_i$ sont distincts (exercice).

\begin{coro}[Frobenius, Hecke] Soient $f$, $n$, $K$, $G$ comme ci-des\-sus; soit $T$ un type de décomposition de $f$, aussi vu comme classe de conjugaison de $S_n$. Alors
$$\lim_{x\to +\infty} \frac{\#\set{p \leq x\colon \bar{f}\in T}} {\#\set{p \leq x}} = \frac{\abs{T\cap G}}{\abs{G}}.$$
\end{coro} \noindent Le résultat de densité ci-dessus est dû à Hecke. Frobenius utilisait la densité analytique d'un ensemble $\mathcal{P}$,
$$
\delta(\mathcal{P}) := \lim_{s\to 1^+}\, \frac{1}{\log (s - 1)}\sum_{p\in \mathcal{P}} p^{-s},
$$
qui est une notion plus faible: si la densité naturelle existe, la densité analytique aussi et elles sont égales. La réciproque est fausse.

\subsection{L'hypothèse de Riemann}\label{se:Riemann}

L'\emph{hypothèse de Riemann} (généralisée, GRH) dit que $L(s, \chi, K) \neq 0$ si $\re(s) > 1/2$; elle n'est bien sûr connue pour aucun $K$ ou $\chi$. Elle a des conséquences remarquables sur les termes d'erreurs dans les théorèmes de densité du paragraphe précédent (voir~\cite{LagOd77}), qui sont obtenus à l'aide de formules intégrales du type
\begin{multline}\label{eq:FE}
\sum_{\N\A \leq x} \chi(\A)\Lambda(\A)\\[-10pt]
= \frac{1}{2i\pi}\int_{\re s = c} -\frac{L'}{L}(s,\chi,K) \, x^{-s}\, \frac{ds}{s}, \quad\text{($x > 0$, $x\not\in\NM$),}
\end{multline}
où $c > 1$ et $\Lambda(\A) = \log \N\p$ si $\A = \p^k$ est une puissance d'un idéal maximal, et $0$ sinon. Il \og suffit\fg ensuite de déplacer un contour: le terme $x^{-s}$ est un $O(x^{-\re s})$ et l'intégrale devient négligeable par rapport aux résidus que l'on récupère en déplaçant la droite d'intégration vers la gauche. Il est clair qu'une bonne localisation des singularités de l'intégrande dans le demi-plan $\re s > 0$ ($s = 1$ si $\chi = \chi_0$ et les zéros de $L$) permet d'estimer plus finement les résidus.

En particulier, si GRH est vraie, il existe $p = O(\log \D_K)^2$ satisfaisant $\Frob_p \in C$ dans le théorème de Chebotarëv, où la constante implicite est effective (voir~\cite{LagMonOd79}). On peut donc trouver un tel $p$ en un temps raisonnable, et en tout cas précisément borné, par une recherche exhaustive $p = 2,3,5,\dots$.

Une conséquence du corollaire~\ref{co:ck} est que les (classes des) idéaux maximaux de $\ok$ de norme $\leq c_K = O(\sqrt{\D_K})$ engendrent $\Cl(K)$. GRH permet beaucoup mieux:

\begin{theo}[Bach~\cite{Bac-exp}]\label{th:Bach} Sous GRH, les idéaux maximaux de $K$ de norme inférieure à $12(\log \D_K)^2$ engendrent $\Cl(K)$.
\end{theo}

\begin{proof}[\proofname\ (vague idée)] Supposons que les idéaux de norme \hbox{$<\!x$} engendrent un sous-groupe \emph{strict} $H$ de $\Cl(K)$. Alors il existe un carac\-tère $\chi \neq \chi_0$ de $\Cl(K)$ tel que $\chi_{\mid H} = {\chi_0}_{\mid H}$: il suffit de relever un caractère non trivial de $\Cl(K)/H \neq \set{1}$. Au vu de \eqref{eq:FE},
$$
\int_{\re s = c} \frac{L'}{L}(s,\chi,K) \, x^{-s}\, \frac{ds}{s} = \int_{\re s = c} \frac{L'}{L}(s,\chi_0,K) \, x^{-s}\, \frac{ds}{s}.
$$
D'après le théorème~\ref{th:L}, en $s = 1$, $L(s,\chi_0,K)$ a un pôle simple alors que $L(s,\chi,K)$ est régulière. Sous GRH, aucun des deux intégrandes n'a de pôle de partie réelle $\frac{1}{2} < \re(s) < 1$, et on en tire une contradiction du type $O(x^{1/2}) = x + O(x^{1/2})$. Malheureusement, les constantes implicites dépendent de $K$!

Pour rendre ceci rigoureux, il faut donc étudier la dépendance en $K$ des termes d'erreurs. En fait, on utilise une \og Formule Explicite\fg~\cite[Chap.\,17]{Lang-ANT}, provenant de la dérivée logarithmique du produit de Weierstrass de la fonction d'ordre $1$
$$\xi(s,\chi,K) = e^{b_0+b_1 s} \prod_\rho \Bigl(1 - \frac{s}{\rho}\Bigr)e^{s/\rho},
$$
et qui généralise \eqref{eq:FE} en remplaçant la fonction caractéristique de $[0,x[$ par une fonction test $f$ très générale. Elle énonce une égalité entre
$$
\sum_\A \chi(\A)\Lambda(\A)\, f(\N\A).$$
et une somme sur les zéros de $L(s,\chi,K)$, modulo quelques termes parasites. L'essentiel du travail consiste à optimiser la fonction test.
\end{proof}

Donnons une dernière application, liée aux estimations du nombre de classes:

\begin{theo}[Brauer-Siegel]\label{th:BS} Si $K$ parcourt l'ensemble des corps de nombres de degré $n$ fixé, on a, pour tout $\e > 0$,
$$
\D_K^{-\e} \ll_\e \frac{h(K)R(K)}{\sqrt{\D_K}} \ll_\e \D_K^\e.$$
En particulier, $\log \big(h(K)R(K)\big) \sim \log \sqrt{\D_K}$ quand $\D_K\to\infty$ et que le degré de $K$ reste fixe.
\end{theo}

La borne supérieure est élémentaire et effective; inconditionnellement, la borne inférieure n'est \emph{pas} effective, on ne peut donc pas démontrer le théorème~\ref{th:h1} ainsi. Mais elle le devient sous GRH! Plus précisément, la constante dépend de $\D_{K_0}$, où $K_0/\QM$ est une clôture galoisienne d'une extension de degré $n$ telle qu'il existe $s_0 \in{}]\frac{1}{2}, 1[$ tel que $\zeta_{K_0}(s_0) = 0$. Sous GRH, $K_0$ n'existe pas.

La seule minoration effective de $h(K)$ actuellement connue inconditionnellement (Goldfeld-Gross-Zagier, voir~\cite{Oes-bour}) concerne les corps quadratiques \emph{imaginaires}, pour lesquels $R(K) = 1$, et elle est nettement inférieure à $\log \D_K$ (\string!):
$$
h(K) > \frac{\log \D_K}{1700} \prod_{p\mid \D_K}\left(1 - \frac{4\sqrt{p}}{p - 1}\right).
$$

\section{Cahier des charges} Notre tâche principale est de calculer les objets suivants, associés à un corps de nombres $K$, défini par le polynôme minimal d'un élément primitif $T$:
\begin{enumerate}
\item
plongements, signature,
\item
$\ZM$-base de $\ok$, factorisation des idéaux,
\item
$\Cl(K)$, $U(K)$.
\end{enumerate} On peut y rajouter de nombreux problèmes annexes, qui surgissent naturellement
\begin{enumerate} \setcounter{enumi}{3}
\item
tables de corps de nombres ordonnés par discriminants,
\item
énumération des $x\in K$, $H(x) < C$,
\item
factorisation des polynômes de $K[X]$,
\item
calcul de $\Aut K$, du corps de décomposition $K_T$, de son groupe de Galois,
\item
calcul approché de $\zeta_K(s)$, $s\in \CM$.
\item[etc.]
\end{enumerate}

\part{Algorithmique}

\section{Introduction}

\subsection{Complexité} On ne définira pas précisément ce qu'est un \emph{algorithme} (qui impliquerait la spécification d'un modèle de calcul, de la représentation des données, d'un programme et de la relation souhaitée entre entrée et sortie de celui-ci), qu'on assimilera à un programme informatique. La \emph{taille} d'une donnée est le nombre de bits utilisés pour la coder, dans la représentation choisie. Le \emph{temps de calcul} est le nombre de pas de programme exécutés avant l'arrêt.

Nous considérerons des algorithmes \emph{probabilistes}, qui ont le droit de faire des choix aléatoires, et des algorithmes \emph{déterministes}, qui ne l'ont pas. Informellement, un algorithme est \emph{bon} s'il s'exécute en un temps polynomial en la taille combinée des entrées et de la sortie du programme\footnote{Ainsi la taille associée au problème de la recherche des sous-ensembles de $\set{1,\dots, n}$ est de l'ordre de $2^n$, pas $\log n$. La taille de l'entrée est $\log n$, celle de la sortie $\sum_{k = 0}^n \binom{n}{k} k \log n = 2^{n-1} n\log n$.}. Pour un algorithme probabiliste, ceci signifie que, pour une entrée fixée, la moyenne des temps de calculs sur toutes les exécutions possibles de l'algorithme est polynomiale en la taille~$T$; l'incertitude porte uniquement sur le temps de calcul, pas sur la correction du résultat. Un problème est \emph{facile} si on connaît un bon algorithme pour le résoudre, et \emph{difficile} sinon. À défaut de bon algorithme, on apprécie qu'il soit sous-exponentiel, en temps $o(\exp(\e T))$ pour tout $\e > 0$.

C'est une définition naïve: on ne se prononce pas sur la difficulté intrinsèque du problème et, de fait, la classe des problèmes \og difficiles\fg a tendance à se résorber. À l'inverse, une modification anodine d'un problème facile peut le rendre difficile\footnote{Par exemple exiger un algorithme déterministe, ou demander un bon comportement sur des données creuses (on mesure alors la taille en fonction du nombre de coefficients non nuls d'un polynôme, par exemple, et non plus en fonction de son degré).}; donc, sans spécification précise du modèle de calcul, on bâtit sur du sable. Mais on peut déjà dire des choses intéressantes à partir de cette approche naïve. (Voir~\cite{Aho-des}, et surtout~\cite{Pap}, pour une approche plus formelle.) Il est aussi utile de distinguer plus finement entre bons, ou moins bons, algorithmes. Dans ce survol, on ne s'en préoccupera pas, ou à peine.

\noindent Quelques problèmes faciles:
\begin{itemize}
\item
primalité sur $\ZM$ (Agrawal-Kayal-Saxena~\cite{AKS}),
\item
factorisation sur $\QM[X]$ (Lenstra-Lenstra-Lovász~\cite{LLL}) ou sur $\FM_q[X]$ (Berlekamp~\cite{Ber-fact}),
\item
construction d'un corps fini $\FM_{p^n}$ (Galois, Adleman-Lenstra~\cite{Adl-Len}).
\end{itemize}
Quelque problèmes difficiles:
\begin{itemize}
\item
factorisation sur $\ZM$,
\item
calcul d'une $\ZM$-base de $\ok$,
\item
groupe de Galois d'un polynôme de $\QM[X]$,
\item
calcul de $\Cl(K)$ ou $U(K)$.
\end{itemize}
Si on rejette les algorithmes probabilistes, alors la factorisation sur $\FM_q[X]$ et la construction d'un corps fini deviennent difficiles, mais le test d'irréductibilité dans $\FM_q[X]$ reste facile. Même le calcul d'une racine carrée ou la construction d'un corps quadratique $\FM_{p^2}$ sont difficiles dans le cadre déterministe. \emph{Si} GRH est vraie, construire $\FM_{p^n}$ redevient facile; plus précisément, on dispose d'un bon algorithme déterministe (utilisant essentiellement le théorème de Chebotarëv) qui, pour chaque valeur de $(n,p)$ fixée, soit construit un polynôme irréductible de degré $n$ sur $\FM_p$, soit prouve que GRH est fausse.

\subsection{Un exemple} Nous allons \og calculer\fg des groupes abéliens: $\Cl(K)$, $U(K)$... Qu'entend-on par là ? Commençons par un exemple simple: soit $p$ un nombre premier, on veut \og calculer\fg $G = (\ZM/p\ZM)^*$ le groupe multiplicatif du corps fini associé. Quelques descriptions possibles:
\begin{itemize}
\item
théorique: $G \simeq \ZM/(p-1)\ZM$ est cyclique.
\item
pseudo-effective: $G = \ZM/(p-1)\ZM\cdot g$, où on fixe un générateur $g$ pour fixer un isomorphisme. La recherche de $g$ se fait en temps fini en calculant l'ordre des éléments successifs de $G$.

Complexité: la taille des données est $\log_2 p$. En supposant que la factorisation de $p - 1$ est connue, on a un bon algorithme pour calculer cet ordre. Sous GRH (pour $K \!=\! \QM$ et les caractères modulo~$p$), il existe un générateur de représentant $O(\log^2 p)$. On a donc un bon algorithme en testant $2,3,\dots$ Seul le caractère polynomial de l'algorithme est conditionnel. Si la factorisation de $p - 1$ est inconnue, même le calcul de l'ordre d'un élément est difficile. Par exemple, véri\-fier qu'un~$g$ donné répond bien à la question est difficile.

\item
effective: comme la précédente mais, pour que l'isomorphisme soit effectif, il faut savoir résoudre le problème du logarithme discret dans $G$: étant donné $a\in G$, trouver l'unique $x:=\log_g a\in\ZM/(p-1)\ZM$ tel que $g^x = a$.
\end{itemize}
Plus généralement pour décrire un groupe abélien de type fini, on le représente sous la forme
$$
G = \bigoplus_{i=1}^g \,(\ZM/d_i\ZM)g_i, \quad\text{où $d_1\mid \dots\mid d_g$}.
$$
Le problème du logarithme discret correspondant est le plus souvent difficile.

\subsection{Notations} Dans la suite, on fixe $K/\QM$ un corps de nombres, $n := \dim_\QM K$. On supposera que $K$ est donné par le polynôme minimal $T$ d'un élément primitif\footnote{D'autres points de vue sont possibles, qui ont tous leur intérêt, par exemple $K\mathop{\hto}\limits^\s \CM$ (on fixe un plongement explicite), $K$ corps de décomposition ou donné par une tour d'extensions, $K$ compositum de sous-corps, corps fixe donné par théorie de Galois, extension donnée par théorie du corps de classe...}. En d'autres termes $K = \QM[X]/(T)$; on note $\t = X \pmod{T}$, soit $K = \QM(\t)$. On supposera que $T\in\ZM[X]$. La lettre $p$ désigne toujours un nombre premier, et $\p$ un idéal maximal de $\ok$ au dessus de $p$.

Après quelques préliminaires, dont le plus important est sans conteste l'algorithme LLL (\S\ref{se:LLL}), on s'intéressera aux plongements du corps $K$: complexes (\S\ref{se:factC}), $p$-adiques (\S\ref{se:factQp}), ainsi que dans d'autres corps de nombres (\S\ref{se:factQ}), ce qui se traduit par de classiques problèmes de factorisation de polynômes, dans $\CM[X]$, $\QM_p[X]$ (en particulier $\FM_p[X]$), ou $\QM[X]$. Dans une deuxième partie, on s'intéressera à l'arithmétique de $K$: ses ordres (\S\ref{se:o}) et son anneau d'entiers $\ok$ (\S\ref{se:ok}). Finalement, on parlera de groupes de classes et d'unités (\S\ref{se:Cl}).

\section{Préliminaires}\label{se:prelim} \subsection{Opérations élémentaires}

Les opérations élémentaires sont faciles dans $\ZM$: addition, multiplication, division euclidienne, pgcd (algorithme d'Euclide). Il en est de même dans le corps de fractions~$\QM$, ainsi que dans les quotients $\ZM/N\ZM$, manipulés \textit{via} un système complet de représentants ($0,\dots,N-1$, ou bien les représentants de valeur absolue minimale). À ceci près que dans $\ZM/N\ZM$ la division euclidienne est remplacée par l'inversion, qui échoue sur un diviseur de $0$, et se réalise à l'aide de l'algorithme d'Euclide étendu. Plus généralement, une relation de Bézout entre $a,b\in\NM$ s'obtient grâce à une suite d'opérations sur les lignes du système\vspace*{-3pt}\enlargethispage{\baselineskip}
$$
\begin{pmatrix} u_i & v_i \\ u_{i+1} & v_{i+1} \\
\end{pmatrix}
\begin{pmatrix} a \\ b
\end{pmatrix} =
\begin{pmatrix} x_i \\ x_{i+1}
\end{pmatrix}, \quad\text{avec }
\begin{pmatrix} u_0 & v_0 \\ u_1 & v_1 \\
\end{pmatrix} = \Id, \
\begin{pmatrix} x_0 \\ x_1
\end{pmatrix} =
\begin{pmatrix} a \\ b
\end{pmatrix}.
$$
Si $x_{i+1} = 0$, l'algorithme s'arrête et la première ligne est une relation de Bézout, sinon on pose la division euclidienne $x_{i} = q x_{i+1} + r$ et $(L_1, L_2)\from (L_2, L_1 - qL_2)$. Ceci effectue simplement l'algorithme d'Euclide sur le membre de droite, en conservant la trace des opérations dans une matrice auxiliaire, comme il est d'usage en algèbre linéaire. En inversant l'identité ci-dessus, on obtient\vspace*{-3pt}
$$
\begin{pmatrix} a \\ b
\end{pmatrix} =
\begin{pmatrix} \abs{v_{i+1}} & \abs{v_i} \\ \abs{u_{i+1}} & \abs{u_i} \\
\end{pmatrix}
\begin{pmatrix} x_i\\ x_{i+1}
\end{pmatrix},
$$
d'où on déduit des majorations de toutes les quantités en jeu, et un coût quadratique $O(\log \max(a,b))^2$ pour l'algorithme. À ce stade, on remarque qu'il suffit de calculer une seule colonne de la matrice $\smallmat{ u_i & v_i \\ u_{i+1} & v_{i+1} }$, puisque la connaissance du pgcd et d'un coefficient de Bézout permet de déterminer l'autre.

À partir d'une relation de Bézout, le lemme chinois est effectif. Les anneaux de polynômes $\FM_p[X]$ et leurs quotients se traitent de même, où les représentants choisis sont de degrés minimal. On peut traiter de même $\QM[X]$ et ses quotients, mais l'explosion des coefficients fait que l'algorithme d'Euclide naïf n'est plus un algorithme utilisable. (Il~reste bon, mais ça n'a rien d'évident, voir~\cite[Chap.\,6]{GatGer}.) Une méthode modulaire s'impose: calcul du pgcd dans $\FM_p[X]$ modulo suffisamment de petits premiers et reconstruction du pgcd global par lemme chinois.

À l'exception du pgcd dans $\QM[X]$, les algorithmes naïfs pour les problèmes ci-dessus sont tous au pire quadratiques en la taille des données. Les méthodes utilisant la multiplication par transformation de Fourier rapide (\S\ref{se:FFT}) et l'inversion par itération de Newton~\eqref{eq:invnewton} sont asymptotiquement quasi-linéaires, voir~\cite{GatGer}.

\subsection{Exponentiation binaire}\label{se:bin}

\mbox{}\hspace*{-1mm}La technique est simple mais~utile: si $n = \sum_{i = 0}^k \e_i 2^i > 0$, $\e_i\in\set{0,1}$, on calcule
$$
x^n = \prodstack{i = 0 \\ \e_i = 1}^k x^{2^i},$$
où les $x^{2^i}$ sont obtenus par mise au carré successives, soit $O(\log n)$ multiplications au lieu de $n - 1$. Notons une application typique, en dehors des tests de primalité: $\pgcd(X^p - X, T)$ dans $k[X]$ se calcule comme $\pgcd(A - X, T)$, où $A\in k[X]$ est un représentant de la classe de $X^p$ dans $k[X]/(T)$, calculé en $O(\log p)$ multiplications n'impliquant que des polynômes de degré inférieur à $\deg T$.

Des variantes gagnent sur la constante implicite, par exemple
$$
y_0 := x^{e_k},\quad y_i := y_{i-1}^2 x^{e_{k - i}} \quad\text{pour $1\leq i \leq k$},
$$
alors $y_k = x^n$, qui rappelle le schéma de Horner. Dans le cas typique ci-dessus, les multiplications par $x^{e_i}$ sont des multiplications par $X$, peu coûteuses.

\subsection{Factorisation, primalité dans \texorpdfstring{$\ZM$}{ZM}}

La primalité est facile, la factorisation difficile. Ces techniques sont complexes, mais bien et fréquemment décrites dans la littérature. Voir \cite{Sch-prim} et \cite{Coh-coucom, Len-NFS} respectivement pour une présentation des tests de primalité et des algorithmes de factorisation.

\Subsection{Formes normales d'Hermite (HNF) et de Smith (SNF)}\label{se:HNF}

Ce sont des familles de matrices, généralisant les formes normales de Gauss-Jordan des espaces vectoriels aux $\ZM$-modules (plus généralement aux $A$-modules pour $A$ principal). L'algorithme qui permet de s'y ramener (si la relation de Bézout est effective dans $A$, par exemple si $A$ est euclidien) généralise le pivot de Gauss. L'inversion d'un \hbox{pivot} est en général impossible, mais l'algorithme d'Euclide permet d'y suppléer: si $au + bv = \pgcd(a,b) = d$ est une relation de Bézout, la multiplication à droite par la matrice inversible $\smallmat{b/d & u \\ -a/d & v}\in \Sl_2(\ZM)$ met la matrice ligne $(a, b)$ sous forme normale $(0, d)$.

Par une suite d'opérations élémentaires de ce type sur ses colonnes, une matrice $m\times n$ à coefficients dans $\ZM$ peut être mise sous forme échelonnée, dite \emph{forme normale d'Hermite} (HNF), en annulant successivement tous les coefficients \emph{à gauche} d'un pivot dans une ligne donnée, avant de poursuivre sur la matrice extraite dont on a supprimé la ligne et la colonne du pivot. Il n'est en général pas possible d'annuler les coefficients \emph{à droite} d'un pivot~$q$, tout au plus peuvent-ils être choisis dans un système fixé de représentants de $\ZM/q\ZM$. Formellement, la matrice $(0|H)\in M_{m\times n}(\ZM)$ est une HNF si $H = (h_{i,j})$ est une matrice $m\times r$ de rang $r\leq n$ telle qu'il existe une fonction $f:[1,r]\to[1,m]$ strictement croissante telle pour $1 \leq j\leq r$, on ait
\begin{enumerate}
\item
$q_j := h_{f(j),j} > 0$ et $h_{i,j} = 0$ si $i > f(j)$,
\item
$0 \leq h_{f(j), k} < q_j$ si $k > j$.
\end{enumerate} ($f(j)$ indique la ligne où se trouve le pivot $q_j > 0$ de la colonne $j$ de $H$, les coefficients à droite du pivot sont réduits modulo $q_j$.) Les matrices HNF $m\times n$ forment un système complet de représentants de $M_{m\times n}(\ZM) / \Gl_n(\ZM)$. En d'autres termes, le $\ZM$-module engendré par les colonnes d'une matrice a une base (échelonnée) canonique, donnée par les colonnes non nulles de sa HNF.

En autorisant de plus les opérations élémentaires sur les lignes, on applique un algorithme de pivot à la ligne $L_i$ d'une matrice (opérations sur les colonnes), puis à la colonne $C_j$ (opérations sur les lignes); en itérant à $i$ et $j$ fixés, le pivot $q_{i,j}$ diminue strictement jusqu'à être le seul élément non nul de $L_i$ et $C_j$. En poursuivant sur les autres lignes et colonnes, on obtient cette fois une matrice diagonale, à un bloc de $0$ près. Toujours par des opérations inversibles sur lignes et colonnes, on peut remplacer un couple $(a,b)$ de pivots consécutifs par $(\ppcm(a,b), \pgcd(a,b))$, et ainsi supposer que les pivots successifs $(d_1,\dots,d_n)$ sont positifs ou nuls et vérifient $d_n \mid \dots \mid d_1$. Formellement, les matrices $m\times n$ de forme $(0|D)$ ou $\smallmat{0\\D}$ sont des \emph{Formes Normales de Smith} (SNF) si $D$ est une matrice diagonale vérifiant la condition ci-dessus. Les matrices SNF $m\times n$ forment un système complet de représentants de $\Gl_m(\ZM) \backslash M_{m\times n}(\ZM) / \Gl_n(\ZM)$. Nous \hbox{venons} essentiellement de démontrer le théorème~\ref{th:adapt} de la base adaptée (reste à voir l'unicité des~$d_i$).

\begin{lemm}\label{le:SNF} Soit $M\in M_{n\times n}(\ZM)$ et $(d_1,\dots,d_n)$ la diagonale de sa SNF. Alors $G = \ZM^n/\im M \simeq \oplus_{i=1}^n (\ZM/d_i\ZM)$.
\end{lemm}

\skpt\begin{proof}
Soit $D = UMV$ la SNF de $M$, où $U,V\in\Gl_n(\ZM)$. Soit $(e_1,\dots,e_n)$ la base canonique de $\ZM^n$; ses projections engendrent~$G$. Les seules relations entre les $e_i$ sont de la forme $(e_1,\dots,e_n)MY =\nobreak 0$, $Y\in \ZM^n$. Soit
$$(g_1,\dots,g_n) = (e_1,\dots,e_n)U^{-1}$$
une nouvelle famille génératrice de $G$; on a $(g_1,\dots,g_n)X = 0$ si et seulement si $X\in \im D$. Donc \[ G = \Big(\sum_i \ZM \cdot g_i\Big) \Big/ \im D = \sum_{i = 1}^n (\ZM/d_i\ZM) \cdot \bar{g_i}.\qedhere \]
\end{proof}

\noindent Se restreindre à $M_{n\times n}(\ZM)$ au lieu de $M_{m\times n}(\ZM)$ est sans importance: on peut remplacer $M$ par les colonnes non nulles de sa HNF pour assurer $n \leq m$, puis concaténer des colonnes nulles pour assurer $n =\nobreak m$.

Contrairement à Euclide sur $\ZM$ (mais conformément à Euclide sur $\QM[X]$), les algorithmes naïfs évoqués ci-dessus ne sont pas bons : les $O(n m^2)$ opérations dans $\ZM$ associées à l'algorithme de pivot font exploser les coefficients. De bons algorithmes existent, reposant toujours sur des techniques modulaires~(voir Storjohann~\cite{Sto2000}).

Un des principes de l'algorithmique arithmétique est de transformer les problèmes arithmétiques en algèbre linéaire sur des $\ZM$-modules; l'algorithme d'Euclide pour le pgcd est l'exemple type. L'algèbre linéaire sur un corps fini ou sur $\ZM$ est facile. Par là j'entends plus précisément la résolution de systèmes linéaires, le calcul d'une base de noyaux, images ou conoyaux, et celui de polynôme minimal ou caractéristique. Sur un corps fini cela suit du pivot de Gauss, sur~$\ZM$, de la forme normale d'Hermite. En particulier, il est facile de transformer un système fini de $\ZM$-générateurs d'un $\ZM$-module libre en une $\ZM$-base. Si $A$ et $B$ sont des sous-$\ZM$-modules libres de $\ZM^n$, vu comme $\ZM$-algèbre, on en déduit de bons algorithmes pour le calcul de $A\cap B$, $A+B$, $AB$, $(A:B) = \set{z\in\ZM^n\colon zB \subset A}$.

\begin{exemple*}
Soit à résoudre le système linéaire $XM = Y$, $M\in M_{m\times n}(\ZM)$, d'inconnue $X \in M_{\ell \times m}(\ZM)$. On pose $MU = (0|H)$ la HNF de $M$, où $U\in\Gl_n(\ZM)$ et $H$ est de rang $r \leq n$. L'équation est équivalente au système triangulaire $X(0|H) = YU$, qu'il est facile de résoudre par substitution.
\end{exemple*}

\subsection{Réduction de bases de réseaux, LLL}\label{se:LLL}

Parmi les bases d'un réseau, certaines sont plus agréables que d'autres: ainsi la base canonique de $\ZM^2$ est une base de vecteurs courts (pour la forme euclidienne standard), mais si $au - bv = 1$ est une relation de Bézout, les vecteurs $\smallmat{a \\b}, \smallmat{v\\ u}$ forment une base de $\ZM^2$, dont les vecteurs peuvent être rendus arbitrairement longs. La réduction d'une base est simplement son remplacement par une base dont les vecteurs sont plus courts. On peut définir une notion de base optimale (Minkowski), dont les vecteurs sont aussi courts que possibles, mais on ne connaît pas de bon algorithme pour en déterminer une à partir d'une base arbitraire. Essentiellement, on en vient à tester successivement tous les vecteurs du réseau dans une boule et leur nombre est exponentiel en la dimension. Nous allons définir une notion de réduction adaptée au traitement algorithmique.

Soit $(\RM^n,q)$ un espace euclidien et $\L$ un réseau donné par une base $(b_i)_{i\leq n}$. Soit $(b_i^*)$ la base orthogonale de $\RM^n$ donnée par le procédé de Gram-Schmidt, telle que
$$
b_1^* = b_1,\quad b_i^* = b_i - \sum_{j < i} \mu_{i,j} b_j^*,\quad \mu_{i,j} = \frac{b_i\cdot b_j^*}{b_j^* \cdot b_j^*},\quad \text{pour $1\leq j < i \leq n$}.$$

\begin{lemm}\label{le:bi*} $\prod_{i=1}^n q(b_i^*) = d(\L)^2$ ne dépend que de $\L$.
\end{lemm}

\begin{proof}
La matrice de Gram de $(b_i^*)$ est diagonale, donc son déterminant est $\prod q(b_i^*)$. D'autre part la matrice de changement de $\RM$-base de $(b_i)$ à $(b_i^*)$ est triangulaire de déterminant $1$. On conclut avec la proposition~\ref{pr:phiGram}.
\end{proof}

\begin{defi} Soit $c \in{}]1/4, 1[$. Une famille libre de vecteurs $(b_1,\dots,b_n)$ est dite LLL-réduite pour la constante de Lovász $c$ si
\begin{enumerate}
\item
$\abs{\mu_{i,j}} \leq \frac{1}{2}$, pour $1\leq j < i \leq n$.
\item
$q(b_i^* + \mu_{i,i-1} b_{i-1}^*) / q(b^*_{i-1}) \geq c $, pour $1 < i \leq n$.
\end{enumerate}
\end{defi} \noindent La première condition $\abs{\mu_{i,j}} \leq 1/2$ pour $j < i$ est facile à mettre en {\oe}uvre et suit d'une \og rédu\-ction de $b_i$ modulo $b_1,\dots,b_{i-1}$\fg. Supposons qu'elle soit vérifiée pour $\ell < j < i$ (initialement $\ell = i$), alors la substitution $b_i \from b_i - \round{\mu_{i,\ell}} b_\ell$
\begin{itemize}
\item
ne modifie pas les $\mu_{t,j}$ pour $t < i$
\item
ne modifie pas les $\mu_{i,j}$ pour $j > \ell$
\item
remplace $\mu_{i,\ell}$ par $\mu_{i,\ell} - \round{\mu_{i,\ell}}$ dont la valeur absolue est $\leq 1/2$.
\end{itemize}

La deuxième condition compare les longueurs des projections de $b_i$ (numérateur) et $b_{i-1}$ (dénominateur) sur l'orthogonal de $(b_1,\dots,b_{i-2})$. Intuitivement, on veut placer en premier le plus \og petit\fg des deux vecteurs (par rapport aux vecteurs restant à réduire), puisqu'il réduira \og mieux\fg les vecteurs suivants.

Pour simplifier, on prend $c = 3/4$ pour la suite. La condition $(2)$ est équivalente à $q(b_i^*)\geq \big(\frac{3}{4} - \mu^2_{i,i-1}\big)q(b_{i-1}^*)$. Avec la première, elle implique $q(b_{i-1}^*)\leq 2 q(b_i^*)$, et en fait
$$
\frac{q(b_i)}{q(b_i^*)} = 1 + \sum_{j < i} \mu_{i,j}^2 \frac{q(b_j^*)}{q(b_i^*)} \leq 1 + \frac{1}{4}\sum_{j < i} 2^{i - j} = \frac{2^i + 1}{2}
$$
Ce quotient étant $\geq 1$, $q(b_i)$ et $q(b_i^*)$ sont proches. On en déduit facilement :
\begin{prop}\label{pr:LLL} Soit $\L$ un réseau de l'espace euclidien $(\RM^n, q)$ dont $(b_i)$ une base {\rm LLL}-réduite. Alors, pour toute toute suite de vecteurs indépendants $x_1,\dots,x_n$ de $\L$, on a
$$
q(b_j) \leq 2^{n-1} \max\set{q(x_1),\dots,q(x_j)}, \quad\text{pour $j\leq n$}.$$
\end{prop} \noindent En particulier le premier vecteur $b_1$ est essentiellement aussi court que possible, à un facteur $2^{n-1}$ près. Trouver un \emph{plus court} vecteur est difficile.

Bien sûr, l'intérêt de la notion est l'existence d'un bon \emph{algorithme} de calcul d'une base LLL-réduite, dû à A.~Lenstra, H.~Lenstra et Lovász~\cite{LLL}. L'algorithme est très simple. Comme celui d'Euclide qu'il généralise c'est une succession de réductions et d'échanges: supposons que $(b_1,\dots,b_{k-1})$ soit LLL-réduite (c'est initialement le cas pour $k =\nobreak2$).

\Subsubsection*{Réduction} On remplace $b_k$ par une combinaison linéaire $b_k - \sum_{i < k} a_i b_i$ comme ci-dessus de façon à ce que $\abs{\mu_{k,j}} \leq \sfrac{1}{2}$ pour tout $j < k$.

\Subsubsection*{Échange}
\begin{itemize}
\item
si $q(b_k^* + \mu_{k,k-1} b_{k-1}^*) \geq \frac{3}{4} q(b^*_{k-1})$, alors $(b_1,\dots,b_k)$ est LLL-réduite et on incrémente $k$. Si $k > n$, l'algorithme s'arrête.
\item
sinon, on échange $b_{k-1}$ et $b_k$ et on décrémente $k$.
\end{itemize}
Intuitivement, la réduction diminue la taille de $b_k$, et les échanges mélangent les vecteurs en tentant de favoriser les réductions suivantes. Il est clair que $(b_1,\dots,b_n)$ reste une base du réseau tout au long de l'algorithme, et qu'elle est LLL-réduite quand il s'arrête. Il n'est pas clair qu'il s'arrête, ni \textit{a fortiori} que ce soit un bon algorithme.

\begin{theo}[Lenstra-Lenstra-Lovász] C'est un bon \hbox{algorithme}.
\end{theo}

\skpt
\begin{proof}[\proofname\ (idée)] Soit $\L_i$ le réseau (de $\RM^i$) engendré par $(b_1,\dots,b_i)$. On note
$$
D_i = \prod_{j\leq i} q(b_j^*) = d(\L_i)^2 > 0,\quad D := \prod_{i < n} D_i.$$
$D$ ne peut changer que lors d'un échange, où $(b_{k-1}^*, b_k^*)$ est remplacé par $(s,t)$, avec $ s = b_k^* + \mu_{k,k-1} b_{k-1}^*$. Puisque $D_i$ ne dépend que de $\L_i$ et pas de la base utilisée pour le définir (Lemme~\ref{le:bi*}), on a $q(s)q(t) = q(b^*_{k-1})q(b^*_k)$ et l'échange laisse les $D_i$ invariants, à l'exception de $D_{k-1}$ qui est multiplié par $q(s)/q(b^*_{k-1}) < \frac{3}{4}$. Donc $D$ est multiplié par un facteur $< \frac{3}{4}$.

Soit $m_i$ la longueur d'un plus petit vecteur non nul de $\L_i\subset \RM^i$. D'après le théorème de Minkowski, $m_i^i v_i\leq 2^i d(\L_i)$ où $v_i$ est le volume de la boule unité de $\RM^i$ (et $m_i^iv_i$ celui de la boule de rayon $m_i$). On en déduit que
$$d(\L_i) \geq v_i \cdot (m_i/2)^i \geq v_i\cdot (m_n/2)^{i},$$
qui ne dépend que de $i$ et de $\L$, mais plus des $(b_i)$. On en déduit que~$D$ est minoré par une constante strictement positive ne dépendant que du réseau, ce qui permet de borner le nombre d'échanges avant l'arrêt de l'algorithme. Reste à compter le nombre d'opérations et à estimer la taille de leurs opérandes en termes des données.
\end{proof}

\noindent Plus précisément:

\begin{theo}[Nguyen-Stehlé~\cite{Ngu-Ste05}] Soit $\L\subset \ZM^d$ un réseau, donné par une famille génératrice de $n$ vecteurs de longueur inférieure à $B$. Une base {\rm LLL}-réduite de $\L$ se calcule en temps $O(d^4n(d + \log B)\log B)$.
\end{theo}

\section{Factorisation dans \texorpdfstring{$\CM[X]$}{CM}}\label{se:factC} Notre but est de calculer les plongements du corps de nombres $K = \QM[X]/(T)$ ce qui revient à approcher les racines complexes de~$T$. Les méthodes itératives de type Newton sont bien connues, mais il est difficile de garantir un temps d'exécution, ni l'exactitude du résultat en présence d'erreurs d'arrondi. J'en tire prétexte pour présenter l'utilisation d'algorithmes numériques (Newton, lemme chinois approché, intégration complexe par discrétisation, FFT, méthode de Graeffe) dans notre contexte algébrique.

Les racines complexes sont une fonction continue du polynôme, mais le problème est déjà mal conditionné par rapport au polynôme lui-même:
$$
P = (x - 1/10)^{20}, \quad \text{et}\quad \widehat{P} = P - 10^{-20}
$$
coïncident jusqu'à 20 chiffres après la virgule, mais $\widehat{P}$ admet la racine~$0$ qui est à distance $0.1$ de l'unique racine de $P$. Dans le contexte de la résolution d'équations diophantiennes, il faut borner rigoureusement la distance des racines approchées aux racines de $P$, et pouvoir la rendre arbitrairement petite.

\subsection{L'algorithme de Schönhage}

On présente ici les grandes lignes de l'algorithme de Schönhage, développé par Gourdon~\cite{Gou-algo}. Étant donné un polynôme $P\in\CM[X]$ unitaire de degré~$n$, et un paramètre d'erreur~$\e$, l'algorithme retourne $n$ complexes $z_1,\dots,z_n$ tels que\vspace*{-3pt}\enlargethispage{\baselineskip}
$$
\abs{P - (X - z_1)\cdots(X - z_n)} < \e \abs{P},
$$
où $\abs{\cdot}$ est la norme $L^1$; on en déduira un encadrement des racines au~\S\ref{se:encadr}. Ce type de résultat est particulièrement adapté au cas de données approchées: plutôt que d'estimer l'erreur commise sur le résultat, on estime la distance des données réelles à des données virtuelles qui produiraient ce résultat exact.

C'est un bon algorithme, quoique assez technique: pour des raisons d'efficacité, les calculs sont approchés, et il faut démontrer de nombreux résultats de perturbation, ainsi qu'estimer au plus près de nombreux paramètres.

Si $P$ est de degré $1$, il n'y a rien à faire. Sinon, l'algorithme détermine d'abord un cercle de séparation $\Gamma$, dont l'intérieur contient $k < n$ racines de $P$, disons $u_1,\dots, u_k$ (idéalement $k\approx n/2$ et $\Gamma$ est éloigné des racines de $P$), puis il approche les sommes de Newton associées:\vspace*{-3pt}
$$
s_m = u_1^m + \cdots + u_k^m = \frac{1}{2i\pi}\oint_\Gamma \frac{P'(z)}{P(z)} z^m\,dz,\quad 1 \leq m \leq k,
$$
par intégration numérique. Grâce aux formules de Newton, on reconstruit une valeur approchée $F_0$ de $F = \prod_{i \leq k} (X - u_i)$ à partir des valeurs approchées des $s_i$, et on applique récursivement l'algorithme à $F_0$ et $G_0 = P/F_0$ qui approche $G = P/F$.

Voici un exemple typique d'utilisation non triviale : soit $T_{300}\in\ZM[X]$ le $300$-ème polynôme de Chebyshev, de norme infinie $\approx 3\cdot 10^{113}$, on veut les racines de $T_{300} + i$ (toutes de module $< 1$, proches de l'axe réel). Le temps de calcul sur une machine à 1.6GHz est de $\approx 28$ secondes pour 28 décimales garanties, $\approx 75$ secondes pour 1000 décimales.

\Subsection{Itération de Newton-Schönhage}

En pratique, on applique une stratégie mixte: l'approximation grossière $P \approx F_0G_0$ est raffinée par une itération de Newton, fondée sur une nouvelle intégration complexe. Plus précisément, on cherche des termes correcteurs $f$ et $g$ tels que $F_1 = F_0 + f$ et $G_1 = G_0 + g$ soient de meilleures approximations que $F_0$ et $G_0$, c'est-à-dire telles que $P - F_0 G_0 = fG_0 + gF_0$ (ce qui implique que $P - F_1G_1 = -fg$ est du second ordre). On peut obtenir $f$ et $g$ par l'algorithme d'Euclide, mais ce dernier est instable et difficile à contrôler numériquement.

On introduit plutôt $H$, le représentant de degré minimal de l'inverse de $G_0$ dans $\CM[X]/(F_0)$, qui existe puisque les racines de $G_0$ sont à l'extérieur de $\Gamma$ et celles de $F_0$ à l'intérieur. Il suffit ensuite de poser $f = HP \mymod F_0$ et de calculer $G_0+g$ comme quotient de la division euclidienne de $P$ par $F_0 + f$. Au lieu de l'algorithme d'Euclide pour le calcul d'un inverse dans $\CM[X]/(F_0)$, on utilise la formule
$$
H(X) = \frac{1}{2i\pi}\oint_\Gamma \frac{1}{F_0G_0(z)} \frac{F_0(X) - F_0(z)}{X - z}\, dz.
$$
En effet, c'est bien un polynôme de degré $< k = \deg F_0$ et un calcul de résidu montre que $H(z) = 1/G_0(z)$ si $z$ est l'une des $k$ racines de $F_0$ à l'intérieur de $\Gamma$. Par intégration numérique, on obtient une approximation grossière $H_0$ de $H$ que l'on raffine par l'itération de Newton
$$
H_{m+1} = H_m(2 - H_m G_0) \pmod{F_0},$$
qui converge quadratiquement vers $H$. Cette dernière est un analogue de l'itération classique utilisée pour calculer l'inverse dans $\RM$, qui suit de la méthode de Newton appliquée à la fonction $f(x) = \Psfrac{1}{x} - y$:
\begin{equation}\label{eq:invnewton} x_{m+1} = x_m - \frac{f(x_m)}{f'(x_m)} = x_m(2 - x_m y).
\end{equation}

\subsection{Intégration numérique et FFT}\label{se:FFT}

Par translation et homothétie, on ramène les intégrales sur $\Gamma$ au cercle unité. On discrétise le cercle par les racines de l'unité d'ordre $2^N$ et il suffit d'évaluer nos fractions rationnelles en ces points (et de borner l'erreur commise en fonction de la distance estimée de $\Gamma$ aux racines de~$P$).

On utilise la transformée de Fourier rapide (FFT, pour Fast Fourier Transform), qui permet d'évaluer un polynôme $Q$ de degré $n < 2^N$ en toutes les racines $2^N$-èmes de l'unité en $O(N 2^N)$ multiplications au lieu de $2^{2N}$ par l'algorithme de Horner appliqué $2^N$ fois. Soit $Q_{\text{pair}}(X^2)$ la partie paire de $Q$ et $X Q_{\text{impair}}(X^2)$ sa partie impaire. La FFT vient de l'identité
$$
Q(\w^j) = Q_{\text{pair}}\big((\w^2)^j\big) + \w^j Q_{\text{impair}}\big((\w^2)^j\big),
$$
qui ramène essentiellement le calcul d'une transformée de longueur $L$ à deux transformée de longueur $L/2$.

Ce type d'idées permet aussi de multiplier rapidement polynômes\footnote{À partir de ses valeurs aux racines $2^N$-èmes de l'unité, on reconstruit un poly\-nôme de degré $< 2^N$ par interpolation de Lagrange, qui est une transformée de Fourier inverse dans ce cadre.} et entiers (voir \cite{GatGer}), et peut être utilisé par les autres phases de l'algorithme, en particulier l'itération de Graeffe.

\subsection{Le cercle de séparation}

Notons $u_1,\dots,u_n$ les racines de $P = a_n X^n + \cdots + a_0$ ordonnées par modules croissants et $\rho_1(P) \leq \cdots \leq \rho_n(P)$ leurs modules. On suppose $n\geq 2$. Pour déterminer un cercle $\Gamma$ convenable, il suffit de savoir estimer les $\rho_k(P)$.

En effet, par translation de vecteur $a_{n-1}/a_n$, on place le barycentre des racines à l'origine. Par homothétie de rapport $1/\rho_n(P)$ on ramène la racine de plus grand module au voisinage du cercle unité. Un petit dessin montre que l'un des 4 polynômes translatés $P(X+\lambda)$, pour $\lambda = \pm 2, \pm 2i$ vérifie $\rho_n \geq 2$, $\rho_1 \leq \big|2 - e^{i\pi/4}\big|$, soit $\rho_n/\rho_1 > 1.35$.

On s'est donc ramené au cas où $\rho_n/\rho_1$ n'est pas trop proche de $1$. Le cercle $\Gamma$ est centré en $0$, reste à choisir son rayon $R$. La quantité intervenant dans les termes d'erreurs est $\delta$ tel qu'il n'y ait aucune racine de $P$ dans la couronne $R e^{-\delta} < \abs{z} < R e^{\delta}$, et il faut la maximiser. Si $j$ maximise le rapport de deux modules consécutifs $\rho_{j+1}/\rho_j$, on~pose donc $R = \sqrt{\rho_{j}\rho_{j+1}}$. En pratique, on ne calcule pas tous les~$\rho_j$, $j\leq n$, mais on utilise une dichotomie qui en calcule $O(\log n)$ pour produire un cercle de même qualité.

\subsection{Estimation de \texorpdfstring{$\rho_k(P)$}{rkP}, la méthode de Graeffe}

On note $\text{Graeffe(P)}$ le polynôme $Q$ tel que $Q(X^2) = P(X)P(-X)$: c'est un polynôme de même degré que $P$, dont les racines sont les carrés des racines de $P$. On construit une suite de polynômes $(P_m)$ par la récurrence $P_0 = P$, $P_{m+1} = \text{Graeffe}(P_m)$ et on écrit $P_m = \sum_{k\leq n} a_k^{(m)} X^k$. On a
$$
\frac{a_k^{(m)}}{a_n^{(m)}} = \sum_{i_1 < \cdots < i_{n-k}} (u_{i_1}\cdots u_{i_{n-k}})^{2^m}.
$$
Supposons dans un premier temps que les modules des racines sont $2$ à $2$ \emph{distincts}. Alors
$$
\frac{a_k^{(m)}}{a_n^{(m)}} \sim (u_{k+1}\cdots u_n)^{2^m}, \quad\text{et}\quad \lim_{m\to+\infty}\abs{a_{k-1}^{(m)} \big/ a_k^{(m)}}^{2^{-m}} = \rho_k(P).
$$
Bien sûr si les $\rho_j$ sont proches, la convergence peut être lente. Pour obtenir une borne rigoureuse, on applique des inégalités générales grossières aux $P_m$, dont on déduit des bornes arbitrairement précises pour~$P$ lorsque $m$ est assez grand.

\begin{lemm}[de Cauchy] Soit $P = a_0 + \cdots + a_n X^n \in\CM[X]$, alors
$$
\rho_n(P) \leq 2 \max_{i < n} \abs{a_i/a_n}^{1/n-i}.
$$
\end{lemm}

\begin{proof}
Si $(\abs{z}/2)^{n-i} > \abs{a_i/a_n}$ pour tout $i$, on a
$$\sum_{i < n} \abs{a_i} \abs{z}^i < \abs{a_n} \abs{z}^n \sum_{i < n} 2^{n-i} < \abs{a_n} \abs{z}^n.$$
Donc $P(z) = 0$ est impossible.
\end{proof}

Voir Henrici~\cite[\S6.4]{Hen74} pour des renforcements conséquents du lemme suivant:

\begin{lemm}\label{le:rhok} Soit $P = a_0 + \cdots + a_n X^n \in\CM[X]$, $n \geq 2$, et $k\in\NM$ tel que $\abs{a_k} = \max_{i\leq n} \abs{a_i}$ et $a_0a_n \neq 0$. Alors
$$\rho_k(P) \leq 2n,\quad \rho_{k+1}(P) \geq \frac{1}{2n}.
$$
\end{lemm}

\begin{proof}
Il suffit de démontrer la première inégalité: la deuxième suit de la première appliquée au polynôme réciproque $P^*(X) = X^n P(1/X)$ de $P$, qui vérifie $\rho_{n-k}(P^*) = \rho_{k+1}(P)^{-1}$. (L'hypothèse $a_0a_n\neq 0$ assure que les $\rho_i$ sont non nuls.)

Le cas $k = n$ suit de l'inégalité de Cauchy. Le cas général pour $k < n$ suit de l'inégalité de Cauchy appliquée à $Q = P/(X-\nobreak u_n)\cdots(X-\nobreak u_{k+1}) = b_0 +\nobreak \cdots + b_k X^k$, qui vérifie $\rho_k(Q) = \rho_k(P) =: \rho$. Plus précisément, on a
\begin{align*}
\frac{1}{(X-u_n)\cdots(X-u_{k+1})}&\\
&\hspace*{-1cm} = (-1)^{n-k} (u_n\cdots u_{k+1})^{-1}\hspace*{-2mm} \prod_{\ell = k+1}^n\hspace*{-2mm} \bigg( \sum_{j_\ell \geq 0} \left(\frac{X}{u_\ell}\right)^{j_\ell} \bigg) \\
&\hspace*{-1cm} =: \sum_{i \geq 0} s_i X^i \in \CM[[X]],
\end{align*}
où $\abs{s_i} \leq \rho^{-(n-k+i)}\#\set{(j_{k+1},\dots,j_n)\in \NM^{n-k}\colon j_{k+1} + \cdots + j_n = i}$. Ce dernier cardinal vaut $\binom{n-k-1+i}{i}$, mais la majoration triviale $(i+1)^{n-k}$ suffit. Supposons $\rho > 2n$, soit $(i+1)\rho^{-1} < 1$ et $\abs{s_i} < \rho^{-i}$ pour tout $i < k \leq n$. On a $b_k = a_k$ et
$$
\abs{b_i} = \sum_{j \leq i} s_j a_{i - j} \leq \abs{a_k}\sum_j \rho^{-j} < 2\abs{b_k},
$$
soit $\rho = \rho_k(Q) \leq 4$ (Cauchy) et $4 > 2n$. Contradiction.
\end{proof}

\begin{lemm}\label{le:rm} Soit $P = a_0 + \cdots + a_n X^n \in\CM[X]$, $n\geq 1$. On peut choisir $r > 0$ pour que $Q = P(r X) = b_0 + \cdots + b_n X^n$ soit tel qu'il existe $\ell$ et $h$ vérifiant
$$
\ell < k \leq h,\quad \abs{b_\ell} = \abs{b_h} \geq \abs{b_j},\quad \text{pour $j \leq n$.}$$
En particulier
$$
\frac{1}{2n} \leq \rho_\ell(Q) \leq \rho_k(Q) \leq \rho_h(Q) \leq 2n.
$$
\end{lemm}

\begin{proof}
Soit $\mathcal{C}$ l'enveloppe convexe supérieure des points $M_j = (j, \log \abs{a_j})$. On considère les $j$ tels que $M_j\in\mathcal{C}$ et on choisit $\ell:=$ le plus grand tel $j < k$, et $h:=$ le plus petit tel $j \geq k$. On choisit enfin $r = \abs{a_\ell/a_h}^{1/(h-\ell)}$. Les hypothèses du lemme~\ref{le:rhok} sont donc vérifiées pour les indices $\ell$ et $h$ et $P = Q$.
\end{proof}

Étant donné $P\in\CM[X]$ non nul, un entier $1\leq k\leq n$, et un paramètre d'erreur $\delta > 0$, on veut déterminer un rayon $R > 0$ tel que
$$
R e^{-\delta} \leq \rho_k(P) \leq R e^\delta.
$$
On définit les suites de polynômes $P_m$, $Q_m$, par
$$
P_0 = P, \quad Q_m = P_m(r_m X), \quad P_{m+1} = \text{Graeffe}(Q_m),$$
où $Q_m, r_m$ proviennent du lemme~\ref{le:rm} appliqué à $P = P_m$. Les racines de $Q_m$ sont les
$$
(u_i / R_m)^{2^m},\quad R_m = r_0r_1^{1/2}\cdots r_m^{1/2^m}.
$$
L'inégalité
$$
\frac{1}{2n} \leq \rho_{\ell_m}(Q_m) \leq \rho_k(Q_m) \leq \rho_{h_m}(Q_m) \leq 2n,$$
donne
$$
R_m \cdot (2n)^{-1/2^m} \leq \rho_k(P) \leq R_m \cdot (2n)^{1/2^m}.$$
Il suffit donc de choisir $m$ tel que $2^m \!\geq\! \log(2n)/ \delta$ et de retourner $R \!=\! R_m$.

\subsection{Encadrement des racines}\label{se:encadr} À partir de l'estimation
$$
\abs{P - (X - z_1)\cdots(X - z_n)} < \e^n,
$$
on peut estimer les racines $(u_1,\dots,u_n)$ de $P$ par un argument d'ho\-mo\-to\-pie:

\begin{theo}[Ostrowski] Soit $\rho = \max(1, \abs{z_1},\dots,\abs{z_n})$. En réordonnant au besoin les $u_i$, on a pour tout $i \leq n$, l'inégalité
$$(1 - 4\rho\e)\abs{u_i - z_i} < 4\rho \e.
$$
\end{theo}

\begin{proof}
Soit $z$ une racine de $\hat{P} = (X - z_1)\cdots(X-z_n)$. Considérons la famille continue de polynômes $H_t = tP + (1-t)\hat{P}$, $t\in [0,1]$. Par continuité des racines de $H_t$, il existe un chemin continu $t\mto d_t$ tel que $d_0 = 0$ et $z + d_t$ est racine de $H_t$ pour tout $t$; en particulier, $z + d_1 = u$ est racine de $H_1 = P$. Ainsi
$$
\abs{\hat{P}(z + d_t)} = t \abs{(\hat{P} - P)(z + d_t)} < \e^n (\rho + \abs{d_t})^n.
$$
Par continuité, $\abs{d_t}$ prend au moins toutes les valeurs dans $[0,\abs{u - z}]$. Par ailleurs,
$$
\abs{\hat{P}(z + d_t)} = \prod_i \abs{(z+d_t) - z_i} \geq \prod_i \big| \abs{d_t} - \abs{z - z_i} \big|,$$
soit, pour tout $d\in [0,\abs{u-z}]$,
$$
\prod_i (d - \abs{z - z_i}) \leq \e^n (\rho + d)^n \leq \e^n(\rho + \abs{u-z})^n.
$$
D'après la propriété de minimax des polynômes de Chebyshev (lemme~\ref{le:minimax}), il existe $d$ dans $[0,\abs{u-z}]$ tel que le membre de gauche soit $\geq (\abs{u-z}/4)^{n}$ et le résultat suit.
\end{proof}

\begin{lemm}\label{le:minimax} Soit $T_n(X)$ ($= \cos(n \arccos(X))$ pour $X\in[-1,1]$) le $n$\nobreakdash-ème polynôme de Chebyshev et $\mathcal{P}$ l'ensemble des polynômes unitaires de $\RM[X]$ de degré $\leq n$. Alors $t_n := 2^{1-n} T_n \in \mathcal{P}$ et, pour tout $P\in\mathcal{P}$, on a
$$\max_{x\in[a,b]} \abs{P(x)} \geq \Bigl(\frac{b-a}{2}\Bigr)^n \max_{x\in [-1,1]}\abs{t_n(x)}= 2\Bigl(\frac{b-a}{4}\Bigr)^n.$$
\end{lemm}

\begin{proof}
$t_n$ est le polynôme unitaire de degré $n$ de plus petite norme uniforme sur $[-1,1]$, qui vaut $2^{1-n}$ (voir par exemple \cite[\S3.1]{Dema-nanum}). Grâce à l'application linéaire $x\mto \frac{a+b}{2} + x\frac{b-a}{2}$ de $[-1,1]$ dans $[a,b]$, on écrit
$$
\max_{x\in [a,b]} \abs{P(x)} = \Big(\frac{b-a}{2}\Big)^n \!\!\max_{x\in [-1,1]} \abs{Q(x)}, \ \ \text{où } Q(X) := P\Big(X + \frac{a+b}{a-b}\Big).
$$
\end{proof}

\subsection{Factorisation dans \texorpdfstring{$\RM[X]$}{RM}}\label{se:factR} Une factorisation approchée dans $\RM[X]$ s'obtient à partir d'une factorisation dans $\CM[X]$ suffisamment précise pour identifier les paires de racines conjuguées. Le cas particulier de la recherche de \emph{racines} réelles d'un polynôme de $\RM[X]$ est important, mais nettement plus simple puisque les méthodes de dichotomie sont directement disponibles (voir Rouillier-Zimmermann~\cite{RouZim}). L'algorithme de Sturm (\cite[\S4.1]{Coh-coucom}) fournit le \emph{nombre} de racines réelles dans un intervalle $]a,b]$.

\section{Factorisation dans \texorpdfstring{$\QM_p[X]$}{QM}}\label{se:factQp} Nous examinons maintenant un algorithme numérique $p$-adique typi\-que, fondé sur le lemme de Hensel. L'avantage sur les méthodes complexes est que les résultats de perturbations sont en général évidents, et qu'il n'y a pas d'erreur d'arrondi. Par contre, les divisions par $p$ induisent une perte de précision, et le champ d'application est limité aux contextes algébriques.

Le lemme de Hensel permet de relever une factorisation suffisamment précise pour être sans facteurs carrés. Comment obtenir cette dernière ? On va déjà voir comment procéder modulo $p$, c'est-à-dire dans $\FM_p[X]$, et considérer d'abord le cas particulier de la recherche de racines dans $\FM_p$. Ces méthodes s'adaptent sans mal au cas d'un corps fini $\FM_q$ général, avec un petit effort supplémentaire en caractéristique~$2$.

\subsection{Principe}

Pour factoriser un élément $N$ d'un anneau euclidien $R$, on recherche (ou on fabrique) un diviseur de $0$ dans $R/(N)$, c'est-à-dire un $\bar{a}$ non nul tel que $m_{\bar{a}}$ soit non injective. Alors, si $a$ relève~$\bar{a}$, $d:=\pgcd(a, N)$ est un facteur non trivial de $N$, fourni par l'algorithme d'Euclide. On invoque ensuite récursivement l'algorithme sur chacun des deux facteurs $d$ et $N/d$. Par exemple, la plupart des méthodes modernes de factorisation dans $\ZM$ construisent une identité $x^2 \equiv y^2 \pmod{N}$, d'où on tire un diviseur de $0$ potentiel $x - y$. (Les mauvais jours, $x = \pm y$ et on a travaillé pour rien.)

\subsection{Racines dans \texorpdfstring{$\FM_p[X]$}{FM}}\label{se:rac}

Soit donc $T\in \FM_p[X]$, qu'on peut supposer scindé à racines simples en le remplaçant par $\pgcd(T, X^p -\nobreak X)$ (\S\ref{se:bin}). On pose $n = \deg T$. On veut trouver un diviseur de $0$ dans la $\FM_p$-algèbre $\FM_p[X]/(T) \simeq (\FM_p)^n$, dont tous les éléments vérifient
$$
0 = x^p - x = \prod_{i\in \FM_p} (x - i).$$
Calculer le produit partiel jusqu'à trouver $0$ n'est pas un bon algorithme si $n \ll p$: au pire $p$ multiplications, pour une taille $n \log p$. Si~$p = 2$, cette méthode est satisfaisante. Sinon, on choisit $x$ au hasard dans $\FM_p[X]/(T)\simeq (\FM_p)^n$ et on écrit
$$
0 = x(x^t - 1)(x^t + 1),\quad t:= (p-1)/2.
$$
Si les trois termes sont non nuls, on a obtenu un diviseur de $0$. Les mauvais cas correspondent à $x = 0$ ($1$ cas), $x^t - 1= 0$ ($t^n$ cas), ou $x^t + 1= 0$ ($t^n$ cas). On est donc malchanceux avec probabilité
$$
\frac{1 + 2t^n}{p^n} \leq \frac{1}{2^{n-1}} \leq \frac{1}{2},\quad\text{si $n \geq 2$}.
$$
L'espérance du nombre d'essais avant de trouver un facteur de $T$ est inférieure à~$2$: c'est un bon algorithme.

\subsection{Factorisation dans \texorpdfstring{$\FM_p[X]$}{FM}}\label{se:Ber}

Soit $T\in\FM_p[X]$, qu'on peut supposer sans facteurs carrés: si $T' = 0$, alors $T = Q(X^p) = Q(X)^p$ et on remplace $T$ par $Q$, sinon $D = \pgcd(T,T')$ est un diviseur strict de $T$; on remplace successivement $T$ par $T/D$ (sans facteurs carrés) puis $D$ (de degré $< \deg T$).

Soit $\phi$ l'endomorphisme de la $\FM_p$-algèbre
$$\FM_p[X]/(T) \simeq \prod_{i = 1}^r \FM_p[X]/(T_i), \quad \text{si $T = \prod_{i = 1}^r T_i$,}$$
donné par $a\mto a^p - a$ et $V := \Ker \phi \simeq (\FM_p)^r$. Alors $\dim_{\FM_p} V = r$ est le nombre de diviseurs irréductibles de $T$. Si $r = 1$, $T$ est irréductible; sinon, soit $\a\in V\setminus \FM_p$ et $\Min{\a}$ son polynôme minimal, qui est scindé à racines simples, de degré $\geq 2$ puisque $\a\not\in\FM_p$. Si $z\in \FM_p$ est une des racines (\S\ref{se:rac}), $\a - z$ est un diviseur de $0$ de $\FM_p[X]/(T)$.

\Subsection{L'algorithme Round~4} \skpt
\begin{defi}
\begin{itemize}
\item
Un polynôme unitaire $Q\in\ZM_p[X]$ est \emph{de type Eisenstein} si
$$Q = b^k + p(qb + r),$$
où $b,q,r\in \ZM_p[X]$, $b$ est irréductible modulo $p$, $\deg r < \deg b$ et $r$ est non nul modulo $p$.
\item
Soit $T\in\ZM_p[X]$ unitaire; on dit que $\a\in \QM_p[X]$ \emph{certifie} (l'irréductibilité de) $T$ si le polynôme caractéristique de $\bar{\a}$ dans $\QM_p[X]/(T)$ est de type Eisenstein.
\end{itemize}
\end{defi} \noindent Par exemple, un polynôme d'Eisenstein est de type Eisenstein avec $b = X$. Un polynôme de type Eisenstein est irréductible; en effet, une décomposition serait de la forme $T = (b^{k_1} + pa_1)(b^{k_2} + pa_2)$, ce qui interdit $r\not\equiv 0\pmod{p}$ si $k_1k_2 \neq 0$.

\begin{prop}[Zassenhaus, \emph{cf.}~Ford-Pauli-Roblot~\cite{ForRob-round4}]
\begin{enumerate}
\item
$T$ est irréductible dans $\QM_p[X]$ si et seulement s'il existe $\a\in \QM_p[X]$ certifiant $T$.

\item
Supposons qu'il existe $\bar{\a}$ dans la $\QM_p$-algèbre $\QM_p[X] / (T)$ dont le polynôme caractéristique $\Char{\bar{\a}}$ appartient à $\ZM_p[X]$ et admet deux facteurs irréductibles distincts modulo $p$. Alors $T$ est réductible dans $\QM_p[X]$.
\end{enumerate}
\end{prop}

\begin{proof}[\proofname\ de $(2)$]
Soit $\a\in\QM_p[X]$ relevant $\bar{\a}$. Par le lemme de Hensel, on peut écrire $\Char{\bar{\a}} = P_1P_2$ dans $\ZM_p[X]$. Alors
\[
T = \pgcd(T, P_1(\a)) \cdot \pgcd(T, P_2(\a))
\]
est une décomposition non triviale.
\end{proof}

La suffisance dans (1) est évidente: si $T$ est réductible, l'algèbre $\QM_p[X]/(T)$ est une somme directe et les polynômes caractéristiques de tous ses éléments sont réductibles. La réciproque est plus technique (il faut étudier les extensions finies de $\QM_p$, en particulier les extensions non ramifiées), mais constructive. L'algorithme Round~4 (Zassenhaus) s'efforce de construire $\a$ certifiant $T$, en calculant successivement les chiffres de son développement $p$-adique. S'il échoue, il produit une factorisation dans $\QM_p[X]$ comme indiqué dans la démonstration de (2), puis essaie récursivement de certifier les facteurs.

L'algorithme précis est technique (voir~\cite{ForRob-round4}): les calculs sont effectués à précision finie, c'est-à-dire dans $\ZM/p^k\ZM$ et non dans $\ZM_p$. Donc il faut borner tous les dénominateurs susceptibles d'apparaître pour choisir une valeur de $k$ suffisante pour maîtriser les erreurs d'arrondi.

\section{Factorisation dans \texorpdfstring{$\QM[X]$}{QM}}\label{se:factQ}

\subsection{L'algorithme naïf}

Après ce qui précède, il suffit de connaî\-tre une borne sur la taille des facteurs pour obtenir un algori\-thme de factorisation dans $\QM[X]$. Il y a plusieurs possibilités, par exemple \hbox{\cite{Beau-prod, Mig-ineq}}. La plus simple est la suivante:

\begin{theo}[Landau] Si $F\in\CM[X]$ est de degré $m$ et $A\mid F$, alors $\norm[\infty]{A} \leq 2^m \norm[2]{F}$.
\end{theo}

\begin{proof}
On factorise $F = a_m \prod_{i\leq m} (X - \a_i)$ et on définit la mesure de Mahler:
$$M(F) = \abs{a_m} \prod_{i\colon \abs{\a_i} > 1} \abs{\a_i}.$$
La majoration $\norm[\infty]{A} \leq 2^m M(F)$ suit de l'expression des coefficients de $A$ comme fonction symétrique de ses racines (qui sont racines de~$F$). Un calcul immédiat montre que, pour tout $\a\in\CM$ et $C\in\CM[X]$, les polynômes $(X - \a)C$ et $(\bar{\a}X - 1)C$ ont même norme $L^2$. Donc $F$ à la même norme que
$$
\abs{a_m} \prod_{i\colon \abs{\a_i} > 1} (X - \a_i) \prod_{i\colon \abs{\a_i} \leq 1} (\bar{\a_i}X - 1),$$
dont on minore la norme par la valeur absolue $M(F)$ de son coefficient constant. Soit $M(F) \leq \norm[2]{F}$.
\end{proof}

Soit donc $F\in\QM[X]$ que l'on désire factoriser. On peut supposer successivement que $F$ est dans $\ZM[X]$, unitaire (par changement de variable; le lemme de Gauss dit alors que ses facteurs unitaires sont dans $\ZM[X]$), et sans facteurs carrés. Le théorème fournit $C > 0$ tel que tous les diviseurs de $F$ ont leurs coefficients dans $[-C,C]$.

On cherche un premier $p$ tel que $F$ modulo $p$ reste sans facteurs carrés dans $\FM_p[X]$. Il y a un nombre fini de premiers à éviter: les diviseurs du résultant de $F$ et $F'$, qui est non nul\footnote{Mieux, il est bornée polynomialement en terme des données, il existe donc un petit nombre premier qui ne le divise pas : le théorème des nombres premiers (Théorème~\ref{th:TNP} pour $K = \QM$) implique que $\sum_{p\leq x} \log p \sim x$ donc un entier divisible par tous les premiers $< x$ est minoré par $\exp(x-o(x))$.}. On peut alors factoriser $F$ dans $\ZM_p[X]$ grâce au lemme de Hensel (faible), c'est-à-dire écrire,
$$
F \equiv \prod_{i = 1}^r F_i \pmod {p^k\ZM_p[X]}.
$$
où les $F_i\in\ZM_p[X]$ sont irréductibles modulo $p$ et connus modulo $p^k$, et où on choisit $k$ tel que $p^k > 2C$.

Les diviseurs de $F$ dans $\QM[X]$ sont de la forme $F_S:=\prod_{i\in S}F_i$ où $S\subset\set{1,\dots, r}$. On calcule une approximation $\hat{F_S} \equiv F_S \pmod{p^k}$, $\hat{F_S}\in\ZM[X]$, dont les coefficients sont dans $]-p^k/2, p^k / 2]$. D'après le théorème de Landau, $F_S\in\ZM[X]$ si et seulement si $F_S = \hat{F_S}$ et il suffit de tester si $\hat{F_S}$ divise $F$ dans $\ZM[X]$ pour le déterminer.

Jusqu'à présent, tout ceci est un bon algorithme. Mais il reste $2^r$ possibilités pour $S$, et il est facile de construire des exemples où $r \geq \frac{1}{2}\deg F$, quel que soit $p$. Par exemple, le polynôme minimal de \hbox{$\sqrt{2} + \sqrt{3} + \cdots + \sqrt{p_k}$}, où $p_k$ est le $k$-ème nombre premier, est irréductible de degré $2^k$, définit une extension galoisienne de groupe de Galois $(\ZM/2\ZM)^k$, et le théorème de Chebotarëv (théorème~\ref{th:chebo}) implique qu'il se décompose dans $\FM_p[X]$ en produit de facteurs tous linéaires ou tous quadratiques, avec probabilité $2^{-k}$ et $1 - 2^{-k}$ respectivement. Par contre, si le groupe de Galois d'un corps de décomposition $K$ de $F$ contient une classe de conjugaison favorable (un produit d'un petit nombre de cycles), et si $\D_K$ est raisonnablement petit, le \S\ref{se:Riemann} indique qu'on trouvera rapidement un premier $p$ qui l'exhibe, ou bien un contre-exemple à GRH.

\subsection{LLL et l'algorithme de van Hoeij}

Il existe un bon algorithme de factorisation dans $\QM[X]$, inconditionnel, qui est l'application originelle de l'algorithme LLL~\cite{LLL}. On considère un facteur $p$-adique~$F_1$ de $F$, une approximation $\hat{F_1}\in\ZM[X]$ de $F_1$, modulo $p^K$, et on cherche un facteur strict de $F$ dans $\ZM[X]$ que $F_1$ divise. Pour ceci, on considère le réseau de $\RM_{\deg F - 1}[X] \simeq \RM^{\deg F}$ engendré par
$$
\hat{F_1}\set{1, X, \dots, X^{\deg F - \deg F_1 - 1}} \cup p^K \set{1, X, \dots, X^{\deg F - 1}},$$
qui contient tous les polynômes de $\ZM[X]$ de degré $< \deg F$ qui sont multiples de~$F_1$. Soit $(b_i)$ une base LLL-réduite de ce réseau. Si $p^K$ est assez grand, on démontre que, soit $\pgcd(b_1, F)$ est un facteur non trivial de $F$, soit ce dernier est irréductible dans $\QM[X]$.

L'algorithme de van Hoeij~\cite{Hoe-fac, BHKS} est un autre bon algorithme, qui utilise aussi LLL, mais sur un réseau plus agréable. On considère le morphisme injectif
\begin{align*} \Phi: \QM_p(X)^*/\QM_p^* & \to \QM_p(X)\\[-2pt] g & \mto F\cdot \frac{g'}{g}
\end{align*} Si $g$ appartient au sous-groupe $G_p$ engendré par les $F_i$, alors $\Phi(g)\in\ZM_p[X]$. Si $g$ appartient au sous-groupe $G\subset G_p$ engendré par les facteurs dans $\QM[X]$, alors $\Phi(g)\in\ZM[X]$.

On détermine $G$ à partir d'une base LLL-réduite du réseau engendré par les $\Phi(F_i) \pmod{p^K}$ et les $p^K X^i$. Plus précisément, on dispose d'une borne sur $\norm[\infty]{\Phi(g)}$ si $g$ est un facteur de $F$ dans $\QM[X]$; les vecteurs de la base trop longs pour provenir de tels facteurs rationnels sont éliminés; si $K$ est suffisamment grand, les éléments restants de la base sont les générateurs de $\Phi(G)$. On en déduit $G$, puis les facteurs.

L'intérêt par rapport à l'algorithme précédent est qu'il existe une base LLL-réduite donnée par une matrice de changement de base~$U$ dont les coordonnées sont dans $\set{0,1}$ (ce sont essentiellement les~$\e_i$ tels que $\prod F_i^{\e_i}\in \ZM[X]$). On peut espérer détecter ces vecteurs, ou l'irréductibilité, à une précision $p^K$ bien inférieure à la précision théorique. Ce que le premier algorithme a peu de chance de faire puisque, dans ce cas, les coefficients de $U$ sont ceux d'un facteur, donc potentiellement gigantesques.

\subsection{Factorisation dans \texorpdfstring{$K[X]$}{K}}\label{se:factK}

Les idées du paragraphe précédent se généralisent à la factorisation dans $K[X]$, où $K = \QM(\theta)$ est un corps de nombres, ainsi d'ailleurs qu'a la factorisation dans $k[X,Y]$ où $k$ est un corps tel que l'on dispose d'un algorithme de factorisation dans $k[X]$, par exemple un corps fini.\enlargethispage{\baselineskip}

Une méthode plus simple pour factoriser $F\in K[X]$, quoique moins efficace en général, se ramène au cas sans facteurs carrés en remplaçant $F$ par $F/\pgcd(F,F')$, puis considère $F_\lambda = F(X + \lambda\theta)$ pour $\lambda\in\ZM$, et $\N(F_\lambda) := \prod_\sigma \sigma(F_\lambda) \in \QM[X]$, où $\sigma$ parcourt les plongements complexes de $K$. Pour tout $\lambda$ sauf un nombre fini (et facilement borné), $\N(F_\lambda)$ est sans facteurs carrés. On choisit un tel $\lambda$ et on factorise $\N(F_\lambda) = \prod f _i$ dans $\QM[X]$, où les $f_i$ sont irréductibles et distincts. Alors les facteurs irréductibles de $F$ dans $K[X]$ sont les $\pgcd(f_i(X - \lambda\theta), F)$ dans $K[X]$. Voir~\cite[\S3.6]{Coh-coucom} pour une démonstration simple. C'est un bon algorithme si on utilise un bon algorithme de factorisation dans $\QM[X]$. Contrairement aux apparences, ces calculs sont exacts: $\theta$ est une variable formelle, classe de $Y$ modulo $T(Y)$ dans $K = \QM[Y]/(T)$; les pgcd se calculent donc par l'algorithme d'Euclide et $\N(F_\lambda) = \Res_Y(F(X+\lambda Y), T(Y)$ est un simple résultant.

Grâce à ce qui précède, on peut maintenant
\begin{itemize}
\item
calculer $\Aut K$ (trouver les facteurs de degré un de $T$ dans $K[X]$),

\item
tester si $K \subset L$, plus précisément s'il existe un plongement de $\QM[X]/(T)$ dans le corps de nombres $L$ ($T$ a-t-il une racine dans $L[X]$?),

\item
tester si $K \simeq L$ (tester si $\deg T = \dim_\QM L$ et appliquer le point précédent).
\end{itemize}

\section{Ordres}\label{se:o} Il est difficile de calculer $\ok$ si on ne connaît pas la factorisation de $\D_K$. Or, la factorisation dans $\ZM$ est difficile. Heureusement, pour de nombreuses applications, on n'a pas besoin de $\ok$, mais seulement d'un sous-anneau qui en est une approximation raisonnable. On peut citer la décomposition des nombres premiers, la factorisation dans $K[X]$ donc les problèmes d'isomorphisme ou du sous-corps (a-t-on $L\subset K$?), la détermination de l'ensemble des sous-corps, du groupe de Galois de $K/\QM$...\enlargethispage{\baselineskip}

\subsection{Définition}\label{se:intro} Un \emph{ordre}\footnote{Introduit par Dedekind (\emph{Ordnung}) comme anneau de stabilisateurs $(A:A)$ d'un $\ZM$-module de type fini $A$. Généralise la notion introduite par Gauss pour les formes quadratiques binaires de discriminant fixé (\emph{ordo,-inis} = rangée, file).} de $K$ est un sous-anneau, donc contenant $1$, qui est un $\ZM$-module de rang $n=\dim_{\mathbb Q}K$ (de façon équivalente, $\Frac \O = K$). Les ordres de $K$ sont partiellement ordonnés par inclusion.
\begin{prop} L'anneau $\ok$ des entiers algébriques de $K$ est son ordre maximal.
\end{prop}

\begin{proof}
$\ok$ est un ordre. Soit $\O$ un ordre de $K$ et $\a\in \O$. Alors $\ZM[\a]\subset\O$ est de type fini, donc $\a$ est entier.
\end{proof}

En un certain sens, la notion d'ordre est duale de celle de localisé: un ordre est un sous-anneau de $\ok$ de type fini comme $\ZM$-module, mais non intégralement clos (si $\O\subsetneq \ok$). Un localisé $S^{-1}\ok = \set{\sfrac{a}{s}\colon a\in\ok, s\in S}$ est un sur-anneau intégralement clos, non de type fini (si $S\not\subset U(K)$). Dans le langage de la géométrie algébrique, cette notion correspond à celle de courbe singulière: sur la courbe $(\spec\O,\O)$, un nombre fini de localisés $\O_\p$ ne sont pas des anneaux de valuation discrète.

Les ordres non maximaux sont de braves anneaux intègres (noethériens, de dimension $1$) de corps de fractions $K$, mais ils gardent des comportement pathologiques par rapport à l'anneau de Dedekind $\ok$. Par exemple, la norme $\N\A:=\O/\A$ d'un idéal non nul est bien définie mais n'est plus multiplicative, il existe des idéaux non inversibles, $\A \subset \B$ n'implique pas $\B \mid \A$ (il existe un $\O$-idéal $\C$ tel que $\A = \B\C$).

\subsection{Construction} L'intérêt de la notion est qu'il est facile de construire des ordres. Par exemple, si $T\in\ZM[X]$ est \emph{unitaire}, alors
$$
\O_T := \gen{1, \t, \dots, \t^{n-1}}_\ZM = \ZM[\t]
$$
est un ordre. Plus généralement.

\begin{theo}[Dedekind] Soit $T(X) = a_0 X^n + \cdots + a_n\in\ZM[X]$; on définit une suite $(T_i)$ de polynômes de degré $i<n$:
$$T_0 := a_0\quad\text{et}\quad T_{i+1} := XT_i + a_{i+1},\text{ pour $0\leq i < n$}.$$
Alors $\O_T:=\gen{1, T_1(\t), \dots, T_{n-1}(\t)}_\ZM$ est un ordre.
\end{theo}

\noindent La suite $(T_i)$ est un schéma d'évaluation de Horner pour $T$, en particulier $T_n = T$. Si $a_0 = \pm1$, on retrouve l'exemple précédent.

\begin{proof}
Posons $t_i\!:=\!T_i(\t)$ pour $0\!\leq\! i\!\leq\! n$. Pour $1 \!\leq\! i\!\leq\! j\! <\! n$, on a
$$t_i t_j = (\t t_{i-1} + a_i)t_j = a_i t_j + t_{i-1}(t_{j+1} - a_{j+1}) \equiv t_{i-1}t_{j+1} \mod \O.$$
En itérant, on se ramène au cas de $t_i t_n$ ou $t_0t_j$; le premier est nul, le deuxième égal à $a_0 t_j \in\O$. Donc ce $\ZM$-module de rang au plus $n$ est un anneau. Il contient $a_0 \t$, donc on a bien $\Frac\O = K$.
\end{proof}

\noindent Plus généralement, les ordres apparaissent comme \og anneaux de stabilisateurs\fg. Si $A$ et $B$ sont deux sous-$\ZM$-modules de $K$, on note
$$
(A : B) := \set{\a\in K, \a B \subset A},
$$
appelé transporteur de $B$ dans $A$, ou \og $A$ divisé par $B$\fg. C'est un $\ZM$-module. Si $\O = \ok$ est de Dedekind, et $\A$, $\B$ sont des idéaux fractionnaires, on a $(\A:\B) = \A\B^{-1}$.

\begin{prop}\label{pr:AA} Si $A\subset K$ est un $\ZM$-module de rang $n$, $\O = (A :\nobreak A)$ est un ordre.
\end{prop}

\begin{proof}
C'est évidemment un anneau. Tout $\a\in\O$ est entier ($A$ est un $\ZM$-module de type fini tel que $\a A\subset A$!), donc $\O\subset \ok$ est de type fini. Comme $\ok A$ est de type fini et $A$ contient une $\QM$-base de $K$, il existe $d \in \NM_{> 0}$ tel que $d\ok A\subset A$, donc $\O\supset d\ok$ est de rang $n$.
\end{proof}

\begin{exemple*}
On pose $A:=\gen{ 1,\t,\dots,\t^{n-1} }_\ZM$ ($\neq\ZM[\t]$ si $T$ n'est pas unitaire!). Alors $(A : A) = \O_{T/\delta}$, où $\delta$ est le pgcd des coefficients de~$T$.
\end{exemple*}

\subsection{Manipulation des ordres, dénominateurs}\label{se:manip}

Un ordre $\O$ est donné par une base $(w_i)$ et la table de multiplication correspondante $w_iw_j = \sum a_{i,j,k}w_k $, où $a_{i,j,k}\in\ZM$. On donne un élément de~$\O$ par ses coordonnées dans la base $(w_i)$, un sous-$\ZM$-module de $\O$ par une $\ZM$-base, c'est-à-dire par une matrice à coefficients entiers. Si on veut une représentation unique, la HNF donne une base canonique ($(w_i)$ étant fixée).

Pour représenter $x\in K$, on choisit un entier $d\in\NM_{>0}$, unique si on l'impose minimal, tel que $dx\subset\O$, et on est ramené au cas précédent. Un sous $\ZM$-module de type fini $M$ de $K$, par exemple un idéal fractionnaire, se manipule de même. Jusqu'à présent, avec l'écriture $K = \QM[X]/(T)$, $T$ unitaire, nous avons ainsi utilisé l'ordre $\O = \O_T$, qui admet la représentation alternative économique $\ZM[X]/(T)$.

Choisir un autre ordre que $\O_T$ est souvent plus flexible. Par exemple, pour calculer $\ok$ (\S\ref{se:r2}). Pour minimiser les dénominateurs, on choisit $\O = \ok$, qui n'est en général pas de la forme $\O_T$ (\S\ref{se:iness}). Si on exprime $\a\in\ok$ dans une $\ZM$-base de $\O$, son dénominateur divise l'exposant du groupe additif $\ok/\O$.

\section{L'ordre maximal \texorpdfstring{$\ok$}{ok}}\label{se:ok}

\begin{defi} Soit $m$ un entier. Un ordre $\O\subset\ok$ est dit \emph{$m$-maximal} si $m$ et l'indice $[\ok:\O]$ sont premiers entre eux.
\end{defi}

Le calcul de $\ok$ est un problème local: à partir d'un ordre $\O$, il~suffit de calculer un ordre $p$-maximal $\O_p\supset \O$ pour chaque~$p$ \hbox{premier}, et $\ok = \sum_p \O_p$ (puisque ce dernier est un ordre $p$-maximal pour tout $p$). On peut prendre $\O_p = \O$ si $p^2\nmid \D_\O$ (Proposition~\ref{pr:indice}), donc il n'y a qu'un nombre fini de premiers à traiter. D'un point de vue algorithmique, la vraie obstruction est globale:

\begin{theo}[Chistov] Les deux problèmes suivants sont de même difficulté:
\begin{itemize}
\item
étant donné un corps de nombres $K$, trouver $\ok$,
\item
étant donné un entier $D$, trouver le plus grand entier $d\mid D$ qui soit sans facteurs carrés.
\end{itemize}
\end{theo}

\noindent Le deuxième problème est actuellement aussi difficile que la factorisation dans $\ZM$, donc calculer $\ok$ est difficile. Pour la même raison, tester si un ordre donné est maximal est difficile: il faut décider si un entier est sans facteurs carrés. Pour s'en convaincre, considérer le cas particulier $\ZM[\sqrt{D}] \subset \QM(\sqrt{D})$. Examinons maintenant le problème local.

\subsection{L'algorithme Round 2}\label{se:r2}

Soit $\O$ un ordre et $p$ un nombre premier. On désire calculer l'ordre $p$-maximal $R$, $\O\subset R\subset \ok$, tel que $[R:\O]$ soit une puissance de $p$. Explicitement
$$
R:=\set{x\in \ok,~\text{$p^n x\in\O$ pour $n\gg 1$}}.
$$
On note $I_p=\rad (p\O)$ l'idéal radical de $p\O$: par définition $I_p/p\O$ est le nilradical (l'idéal des nilpotents) de l'anneau fini $\O/p\O$ et $I_p$ en est le relèvement dans $\O$. C'est aussi l'intersection des idéaux premiers de $\O$ contenant $p$,\vspace*{-3pt}
$$
I_p := \bigcap_{\p\colon p\in\p} \p = \prod_{\p\colon p\in\p} \p.
$$
Ces idéaux premiers sont en nombre fini et ils sont maximaux (dans~$\O$).

\begin{prop} Il est facile de calculer $I_p$.
\end{prop}

\begin{proof}
Si $t$ est un entier tel que $p^t \geq n = \dim_\QM K$, alors $\O/p\O$ est un $\FM_p$-ev de dimension $n$ et $I_p/p\O$ est le noyau\footnote{ Si $p > n$, c'est aussi le noyau \vspace*{-3pt}\begin{align*} \O/p\O & \to \Hom(\O/p\O, \FM_p)\\[-2pt] x & \mto (y\mapsto \Tr(xy)).\vspace*{-5pt}
\end{align*}
\begin{proof}
Soit $u$ un endomorphisme d'un $\FM_p$-ev de dimension finie $n < p$; si~$\Tr(u^k) = 0$ pour tout $k\geq 1$, alors $u$ est nilpotent (formules de Newton + Cayley-Hamilton par exemple). Donc un élément du noyau appartient à $I_p$ (en~choisissant $y = 1, x, x^2,\dots$). Réciproquement, un nilpotent est de trace nulle.
\end{proof}
\vspace*{-3pt}
\noindent Cette deuxième description est préférable quand $p$ est grand: on supprime le coût de la mise à la puissance $p$. } de l'application $\FM_p$-linéaire $x\mto x^{p^t}$.
\end{proof}

L'algorithme Round 2 est un bijou, issu du théorème suivant:

\begin{theo}[Zassenhaus] Soit $\O' := (I_p : I_p)$. L'ordre $\O$ est $p$-maximal si et seulement si $\O = \O'$. Dans le cas contraire, on a \hbox{$p\mid [\O':\O] \mid p^n$}.
\end{theo}

\subsubsection*{Idée} On veut vérifier que les maximaux contenant $p$ sont inversibles; il suffit de vérifier que leur produit l'est.
\enlargethispage{.5\baselineskip}%

\begin{proof}
$\O'$ est un ordre contenant $\O$ (car $I_p$ est un $\O$-idéal, Proposition~\ref{pr:AA}); comme $p\in I_p$, on obtient $p\O'\subset I_p\subset\O$ donc $[\O':\O] \mid p^n$. D'où $\O=\O'$ si $\O$ est $p$-maximal.

Réciproquement, si $\O = \O'$, soit $R$ l'ordre $p$-maximal contenant~$\O$ du début de la section. Comme $I_p$ et $R$ sont de type fini, on a $I_p^m\subset p\O$ et $p^mR \subset \O$ pour $m\gg 1$. Donc $RI_p^m \subset \O$ pour $m$ assez grand. Par l'absurde, supposons qu'il existe $m\geq 0$ tel que $RI_p^m\not\subset\O$ et choisissons $m$ maximal, puis $\a\in R I_p^m\setminus\O$. Alors $\a I_p\subset\O$ et donc $\a I_p\subset I_p$ (comme $I_p$ est de type fini, il existe $k$ tel que $I_p^k\subset p\O$), soit $\a\in (I_p:I_p) = \O' = \O$. Absurde.
\end{proof}

\noindent L'algorithme de normalisation est immédiat: on part de $\O = \O_T$; on calcule $I_p/p\O$ et on remplace $\O$ par $\O':= (I_p:I_p)$ tant que $\O\neq \O'$. C'est un bon algorithme, qu'on applique à tous les $p$ premiers tels que $p^2\mid \D_\O$. À condition de les connaître!

Il est remarquable que l'on puisse remplacer $p$ par un entier $m$ sans facteurs carrés arbitraire (Buchmann-Lenstra~\cite{BucLen-app}). Soit l'algorithme rencontre une impossibilité qui exhibe un facteur de $m$ (un~élément non nul mais non inversible de $\ZM/m\ZM$), soit il produit un ordre $m$\nobreakdash-maximal.

\subsection{Le cas particulier de \texorpdfstring{$\O_T$}{OT}} Pour chaque premier $p$, la première étape de l'algorithme Round 2 se traduit plus efficacement par (revoir le théorème~\ref{th:Kummer}):

\begin{theo}[Dedekind]\label{th:dedek} Soit $K = \QM(X)/(T)$, $T\in\ZM[X]$ unitaire et $\t = X \!\pmod{T}$, tel que
$$
T \equiv \prod_i P_i^{e_i} \pmod{p\ZM[X]},$$
où les $P_i$ sont unitaires, irréductibles et $2$ à $2$ distincts modulo $p$. Soit
$$
f:= \prod P_i,\quad g:= \prod P_i^{e_i - 1},\quad h:= (T - fg) / p\in\ZM[X].
$$
Soit $\delta := \pgcd(\overline{f},\overline{\vphantom{h}g},\overline{h})$ dans $\FM_p[X]$, et $U$ un relèvement de $\overline{T}/ \delta$, alors
$$
\O' = \O_T + \frac{U(\t)}{p} \O_T.
$$
En particulier, $\O_T$ est $p$-maximal si et seulement si $\delta = 1$.
\end{theo}

\begin{proof}
On trouve $I_p = p\O_T + g(\t)\O_T$, et on explicite le calcul de $(I_p : I_p)$.
\end{proof}

\begin{coro} Si $T = b^k + p (qb+r)$ est de type Eisenstein, alors $\O_T$ est $p$-maximal.
\end{coro}

\begin{proof}
$f = b$, $g = b^{k-1}$, $h = qb+r$. On a $\pgcd(\overline{f},\overline{\vphantom{h}g},\overline{h}) = (\overline{b},\overline{\vphantom{h}r}) = 1$.
\end{proof}

\subsection{L'algorithme Round 4}\label{se:r4}

Round~2 nécessite quand même la manipulation de matrices $n\times n\times n$ (\S\ref{se:manip}) et de nombreuses itérations quand $v_p([\ok:\O])$ est grand ($[\O':\O]\mid p^n$, donc la valuation de l'indice diminue au plus de $n$ à chaque itération). En pratique, on utilise un autre algorithme de normalisation locale, lié à la factorisation dans $\QM_p[X]$ par l'algorithme Round~4. Par rapport à Round~2, il est d'autant plus intéressant que $n$ ou $v_p([\ok:\O])$ est grand, mais de description moins attrayante. Je ne sais pas si l'on peut obtenir les même garanties pour Round~$4$ que pour l'algorithme Round~$2$ modifié par Buchmann et Lenstra, où $p$ est remplacé par $m$ sans facteurs carrés. C'est probable.

On utilise la généralisation suivante du théorème~\ref{th:Kummer}, auquel il se réduit si $T$ est sans facteurs carrés modulo $p$:

\begin{theo}\label{th:r4} Soit $T\in \ZM[X]$ unitaire irréductible dans $\QM[X]$. Soit $T = F_1\cdots F_g$ la factorisation de $F$ en produit de polynômes unitaires irréductibles dans $\ZM_p[X]$ (ils sont distincts), et $\a_i\in\QM_p[X]$ certifiant $F_i$ pour $i = 1,\dots,g$. Soit $p^d$ un dénominateur commun aux $\a_i$; pour $x\in\QM_p[X]$, on définit une approximation $\hat{x}\in\QM[X]$ telle que $x - \hat{x}\in p^{d+1}\ZM_p[X]$ et sa projection $\overline{x}$ dans $\QM[X]/(T)$. Alors, pour tout~$i$,
\begin{itemize}
\item
$F_i \equiv t_i^{e_i} \pmod{p\ZM_p[X]}$, où $t_i$ est irréductible modulo $p$,
\item
$\p_i = p \ok + t_i(\overline{\a_i})\ok$ est maximal,
\item
les $\p_i$ sont distincts, on a $e(\p_i/p) = e_i$, $f(\p_i/p) = \deg t_i$ et
$$
p\ok = \p_1^{e_1} \cdots \p_g^{e_g}.
$$
\end{itemize}
Soit $\e_1,\dots,\e_g$ les idempotents orthogonaux associés:\par\noindent si $\sum_{i = 1}^g a_i \cdot (T/F_i) = 1$ est une relation de Bézout dans $\QM_p[X]$, on pose $\e_i = a_i \cdot (T/F_i)$; alors
$$\O_p := \sum_{i=1}^g \overline{\e_i}\, \ZM[\overline{\a_i}]$$
est $p$-maximal.
\end{theo}

\subsection{Diviseurs inessentiels}\label{se:iness} En changeant $T$, on espère obtenir un ordre $\O_T$ qui soit $p$-maximal. Hélas, dès que $n\geq 3$, il peut exister des \emph{diviseurs inessentiels}\footnote{Dedekind écrit \emph{ausserwesentlich} (= d'essence extérieure), Bourbaki (mal inspiré) \og facteurs extraordinaires\fg dans ses notes historiques. La littérature se partage entre diviseurs essentiels ou inessentiels... pour la même notion.} $p$ du discriminant tels que $p\mid [\ok:\O_T]$ pour tout $T$ tel que $p\nmid a_0$ (ou, de façon équivalente, pour $T$ unitaire):

\begin{theo}[Hensel] Soit $p$ un nombre premier fixé. On note
\begin{itemize}
\item
$r(f)$ le nombre de $\p \mid p$ de degré résiduel $f$.
\item
$i(f)$ le nombre de $P\in\FM_p[X]$ irréductibles unitaires de degré $f$.
\end{itemize}
Alors $p$ est diviseur inessentiel si et seulement s'il existe $f$ tel que $r(f) > i(f)$.
\end{theo}

\begin{proof}
La condition est suffisante d'après le critère de Kummer (théorème~\ref{th:Kummer}). La réciproque est un calcul local assez précis (fait dans Hasse~\cite{Has-zah}).
\end{proof}

\begin{coro} Si $p$ est diviseur inessentiel, alors $p < n = \dim_\QM K$.
\end{coro}

\begin{proof}
D'après \eqref{eq:efg}, $f\cdot r(f) \leq n$. D'autre part, soit
$$I := f\cdot i(f) = \sum_{d\mid f} \mu(f/d)p^d.$$
On a $I > 0$ et $I$ est divisible par $p$, donc $I\geq p$. (Si on ne veut pas utiliser l'existence de $\FM_{p^f}$, on peut se contenter de $I\geq 0$, $I \equiv p^d\pmod{p^{d+1}}$, $d$ minimal tel que $f/d$ soit sans facteurs carrés, qui donne $I \geq p^d$.)
\end{proof}

\begin{exemple*}
si $n = 3$, seul $2$ peut être diviseur inessentiel. En fait, il l'est si et seulement si $2\ok = \p_1\p_2\p_3$, où $e(\p_i/2) = f(\p_i/2) = 1$ pour $i = 1,2,3$. On trouve facilement des exemples de ce phénomène en utilisant le théorème~\ref{th:r4}: par exemple $K = \QM[X]/(T)$ où $T = x^3 - x - 8 = x(x-1)(x+1) + 8$.
\end{exemple*}

\subsection{Valuations}

L'algorithme Round 4 (\S\ref{se:r4} et Théorème \ref{th:r4}) fournit simultanément la factorisation de $T$ dans $\QM_p[X]$, un ordre $p$-maximal $\O$ de $\QM[X]/(T)$, et la décomposition de $p\O$ en produit d'idéaux maximaux donnés sous la forme $\p = p\O + \pi \O$.

\begin{prop} Si $x\in K^*$, il est facile de calculer $v = v_\p(x)$.
\end{prop}

\begin{proof}
On peut supposer $x\in \O$, $x \neq 0$. Il suffit alors d'appliquer la définition: $v = \max\set{w: x\in \p^w}$.

Une variante plus agréable utilise l'écriture $\p = p\O+\pi\O$: la multiplication par $\pi$ dans la $\FM_p$-algèbre $\O/p\O$ n'est pas injective (son image est $\p/p\O$ qui est de codimension $f(\p/p) \geq 1$). Soit $\tau_0\in \O\setminus p\O$ un relèvement d'un élément non trivial de son noyau et $\tau := \tau_0/p$. Alors $v = \max\set{w, \tau^w x\in \O}$; en effet, $v_\p(\tau) = -1$ et $v_\q(\tau) \geq 0$ pour tout $\q \neq \p$.
\end{proof}

\noindent La valuation d'un idéal se calcule comme le min des valuations de ses générateurs.

\subsection{L'algorithme \sc{Polred}}\label{se:polred} Un corps de nombres $K = \QM[X]/(T)$ est représenté par une infinité de polynômes $T\in\ZM[X]$ différents. Certains d'entre eux sont plus agréables que d'autres. L'algorithme {\sc Polred} (Polynomial Reduction) de Cohen et Diaz y Diaz essaie de trouver un joli polynôme $T$ définissant le même corps. Il calcule une base LLL-réduite $(b_i)$ du réseau $(\ok,T_2)$ et teste si l'un des $b_i$ est primitif en vérifiant si leur polynôme caractéristique est sans facteurs carrés. Soit $\a = A(X) \mymod{T}$ dans~$K$. Son polynôme caractéristique se calcule comme un résultant $\Char{\a}(Y) = \Res_X(T(X), Y - A(X))$, ou comme produit des $Y - \sigma_i(\a)$, où les $\sigma_i$ sont les plongements complexes de~$K$.

{\sc Polred} peut échouer: il arrive qu'aucun des $b_i$ ne soit primitif, auquel cas on considère de petites combinaisons linéaires des $b_i$. En cas de succès, il fournit un polynôme $T$ engendrant le même corps $K$, dont les racines sont petites; ainsi donc que ses coefficients. Remarquons qu'en cas d'échec, {\sc Polred} fournit des sous-corps de $K$.

\subsection{Réduction LLL}\label{se:ALLL}

Soit $\AA$ un idéal fractionnaire non nul. Le premier vecteur d'une base LLL-réduite du réseau $(\AA,T_2)$ est un $\a\in\AA$ de norme relativement petite. On récrit
\enlargethispage{1.5\baselineskip}%
$$
\AA = (\a)(\AA/\a) = (a)(\a)\A,
$$
où $\A$ est entier et primitif, $\a\in\ok$ et $a\in\QM^*$. Ces trois composantes dépendent de la variante de l'algorithme LLL utilisé mais
\begin{prop} $\N\A$ est bornée par une constante ne dépendant que de $K$.
\end{prop}

\begin{proof}\mbox{}\hspace*{-1.5mm}
Corollaire~\ref{co:minid} (Minkowski) et Proposition~\ref{pr:LLL}~(LLL).
\end{proof}

En particulier, un produit quelconque d'idéaux se simplifie sous la forme $(\a)\A$, où $\a$ est un produit d'éléments de $K^*$, que l'on peut développer si nécessaire, et $\A$ est un \emph{petit} idéal entier. Il est préférable de conserver $\a$ sous forme de produit \emph{formel}: on écrit $\a=\prod x_i^{e_i}\in\ZM[K^*]$. Par exemple, méditer sur les $30103$ chiffres décimaux de la représentation développée des 7 caractères \og $2^{100000}$\fg. Dans l'essentiel des applications, on n'utilisera pas $\a$ mais sa projection sur un domaine où les calculs sont plus simples: $K\otimes \RM$, $K\otimes \QM_p$, $(\ok/\mathfrak{f})^*$, $K^*/(K^*)^\ell$... On en verra un exemple au \S\ref{se:applN}.

\section{Groupe de classes et unités}\label{se:Cl} Dans cette section, on suppose connu l'ordre maximal $\ok$. On~peut définir $\Cl(\O)$ et $\O^*$ pour un ordre quelconque, mais en rajoutant des difficultés techniques sans éclaircir le problème initial. Pour montrer que $\Cl(K)$ est calculable en principe, il ne suffit pas d'invoquer la borne de Minkowski (Corollaire~\ref{co:minid}). Il manque une procédure effective pour décider si deux idéaux sont équivalents. \og Factoriser suffisamment d'idéaux principaux\fg n'est pas recevable...

\subsection{Calculabilité} Pour toute place $\p$ de $K$, on note $\abs{.}_\p$ la valeur absolue normalisée associée. Soit $S_{\infty}$ l'ensemble des places archimédiennes de $K$ et $S\supset S_{\infty}$ un ensemble fini de places.

\begin{theo}[Lenstra~\cite{Len-algANT}]\label{th:len} Soit
\[
d := (2/\pi)^{r_2} \D_K^{1/2},\quad S_0:= \set{\p, \N\p \leq d}\quad\text{et}\quad S := S_\infty\cup S_0.
\]
Alors le groupe $U_S(K)$ est engendré par $\set{\a\in U_S(K), H(\a) \leq d^2}$, et~$\Cl(K)$ est engendré par les classes des éléments de $S_0$.
\end{theo}

\noindent La calculabilité de $U(K)$ et $\Cl(K)$ se déduit de la suite exacte:
$$
0 \to U(K) \to U_S(K) \To{f} \ZM^{S_0} \To{g} \Cl(K)\to 0,
$$
où $f:\a \mto (v_\p(\a))_{\p\in S_0}$ et $g: (e_\p) \mto \prod_\p \p^{e_\p}$. L'exactitude provient du théorème et il suffit de calculer noyau et conoyau de $f$, en commençant par construire une $\ZM$-base de $U_S(K)$ grâce au théorème~\ref{th:len}.

La démonstration est élémentaire, fondée sur le théorème de Minkowski; l'assertion sur les générateurs de $\Cl(K)$ est immédiate car plus faible que celle du corollaire~\ref{co:ck}. À première vue, ce théorème est un peu surprenant si $r_1+r_2 > 1$ (c'est-à-dire $U(K) \neq \mu(K)$): on s'attend à ce que le \emph{régulateur} $R(K)$ de $K$ soit souvent de la taille de $\sqrt{\D_K}$ d'après Brauer-Siegel (Théorème~\ref{th:BS}) et les heuristiques de Cohen-Lenstra-Martinet (\S\ref{se:heu}) qui prédisent que $h(K)$ est \og fréquemment\fg petit. Donc certains plongements des unités fondamentales devraient être de l'ordre de $\exp( \sqrt{\D_K} / n )$, quelle que soit la $\ZM$-base choisie pour $U(K)/\mu(K)$. Par exemple, il est bien connu que l'unité fondamentale d'un corps quadratique peut devenir gigantesque, voir le célèbre problème des B\oe{}ufs d'Archimède. L'astuce consiste à considérer un système non minimal de générateurs.

Ce n'est \emph{pas} un bon algorithme, car $U_S(K)$ est beaucoup trop gros: son rang est exponentiel en $\log \D_K$. En pratique, on utilise le principe du calcul d'indice.

\subsection{Calcul d'indice}

Pour calculer un groupe abélien \emph{fini} $M$ par générateurs et relations, la méthode de calcul d'indice nécessite quatre ingrédients:
\begin{itemize}
\item
Un $\ZM$-module libre $A_0$ dont $M$ est un quotient
$$
0 \to \L_0 ? \to A_0 \to M \to 0
$$
(le noyau $\L_0$ est inconnu).

\item
Un sous-groupe \emph{de type fini} $A \subset A_0$, muni d'une $\ZM$-base $\BB$, dont $M$ reste un quotient:
$$
0 \to \L_0 \cap A =: \L ? \to A = \ZM^\BB \to M \to 0
$$
(le noyau $\L$ est inconnu). Un élément de $\L_0$ appartenant à $\L$ est dit \emph{friable}, $\BB$ est une \emph{base de factorisation}.

\item
Un moyen de produire des éléments \og bien répartis\fg dans $\L_0$, puis de les plonger dans $\ZM^\BB$ s'ils appartiennent à $\L$ (factorisation des éléments friables).

\item
Une évaluation grossière $H$ de $h := \#M = [A:\L]$, telle que $H < 2h$.
\end{itemize}
L'algorithme probabiliste suivant détermine alors $M$: produire des éléments de $\L$, engendrant un sous groupe $\widehat{\L}\subset\L$, jusqu'à ce que
$$
\widehat{h} := [A:\widehat{\L}] \leq H < 2h,
$$
ce qui entraîne $\widehat{h} = h$ puisque $\widehat{h}$ est un multiple entier de $h$, et donc $\widehat{\L} = \L$. On en déduit la structure de $M = \ZM^\BB/\L$ en calculant la SNF de $\L$ (Lemme~\ref{le:SNF}):
$$M = \oplus (\ZM/d_i\ZM) g_i, \quad d_1\mid d_2 \mid \dots,\quad g_i\in A.
$$
La solution du logarithme discret dans $A$, c'est-à-dire l'écriture d'un élément de $M$ comme produit des $g_i$ et d'un élément de $\L$ est une généralisation simple que l'on considérera ultérieurement.

\subsection{Adaptation au cas \texorpdfstring{$M = \Cl(K)$}{MCK}, sous GRH}

Pour calculer $\Cl(K)$ et $U(K)$ en un temps raisonnable, on admet GRH pour pouvoir utiliser la borne de Bach~(Théorème~\ref{th:Bach}). On pose donc
$$
\BB:=\set{\p, \N\p \leq 12(\log \D_K)^2},
$$
qui engendre $\Cl(K)$ et remplace l'ensemble $S_0$ de Lenstra. Même sous ces hypothèses fortes, la complexité des algorithmes est au mieux sous-exponentielle en $\log \D_K$, et reste heuristique. Elle n'est démontrée, sous GRH, que pour $K$ quadratique imaginaire (Hafner-McCurley~\cite{Haf-rig}). La complexité n'est pas seule en jeu: si GRH est fausse, le résultat obtenu peut l'être aussi. Tous les algorithmes permettant de le vérifier inconditionnellement sont exponentiels.

On étend l'idée du calcul d'indice en calculant simultanément $\widehat{\L}$ comme ci-dessus et un sous-groupe $\widehat{U}$ de $U = U(K)$. On désire calculer $M := \Cl(K)$,
\begin{itemize}
\item
$A_0$ est le groupe des idéaux fractionnaires de $K$,

\item
On produit des élément de $\L_0$ de petite norme dans $\ok$ en utilisant la réduction~\S\ref{se:ALLL} sur un produit aléatoire d'éléments de $\BB$: si le petit représentant de sa classe d'idéaux est friable, on obtient une relation. Le test de friabilité et la factorisation d'un élément friable s'effectue par divisions successives par les éléments de $\BB$.

\item
On calcule une approximation numérique du produit $hR$, par un produit eulérien tronqué convergeant vers le résidu en $s = 1$ de $\zeta_K$:
$$
\prod_{p\leq Y} \frac{(1-p^{-1})}{\prod_{\p\mid p} (1 - \N\p^{-1})} \to \Bigl(\frac{\zeta_K}{\zeta}\Bigr)(1) = 2^{r_1}(2\pi)^{r_2} \frac{hR}{w\sqrt{\D_K}}
$$
Toujours sous GRH, l'approximation obtenue pour $Y = O(\log \D_K)^2$ est suffisamment précise.

\item
Dans la formule du résidu, $\D_K$ est connu puisque $\ok$ l'est, $(r_1,r_2)$ se calcule avec l'algorithme de Sturm (\S\ref{se:factR}), et $w$ en énumérant les points tels que $T_2(x) = n$ (Théorème~\ref{th:kro}) ou en testant l'inclusion de corps cyclotomiques $\QM(\zeta_m)$ dans $K$ pour des valeurs convenables de $m$ (\S\ref{se:factK}).
\end{itemize}
Les dépendances entre éléments de $\widehat{\L}$, découvertes au moment du calcul de $[A:\widehat{\L}]$, se traduisent par des identités entre idéaux principaux $(\a) = (\a')$. On en déduit des unités $u:=\a/\a' \in U$; ces éléments $u$ engendrent un sous-groupe $\widehat{U}$ de $U$. Soit $\widehat{R}$ le régulateur de $\widehat{U}$, qui est un multiple entier du régulateur $R$; tout comme ci-dessus, lorsque $hR < 2\widehat{h}\widehat{R}$, alors $U = \widehat{U}$ et $\L = \widehat{\L}$, d'où on tire $\Cl(K)$.

Pour obtenir des générateurs $(g_i)$ explicites, il faut conserver les matrices de changement de base associées à toute cette algèbre liné\-aire. On obtient les $g_i$ sous forme \emph{factorisée} dans $\ZM^\BB$, ce qui est une présentation compacte agréable. On peut la développer en utilisant la technique du \S\ref{se:ALLL} pour obtenir de petits représentants de leurs classes d'idéaux.

D'après la discussion qui suit le théorème~\ref{th:len}, la taille de l'écriture naïve de générateurs de $U(K)$ comme éléments de $\QM[X]/(T)$ est \textit{a priori} exponentielle. Dans l'algorithme ci-dessus, les unités sont obtenues elles-aussi comme produit de $S$-unités, qui n'appartiennent pas à $U(K)$ individuellement. Cette présentation compacte des unités est de taille raisonnable.

\subsection{Logarithme discret}

Nous pouvons donc calculer
$$\Cl(K) = \oplus (\ZM/d_i\ZM) g_i,$$
où l'on sait exprimer les $g_i$ comme produits d'éléments de $\BB$, ou comme \emph{petit} idéal, à un idéal principal explicite près. Réciproquement on peut exprimer un élément de $\BB$ en terme des $g_i$. Soit maintenant un idéal $\A$; on veut calculer son logarithme discret dans $\Cl(K)$, c'est-à-dire $(e_i)\in \prod_i (\ZM/d_i\ZM)$ et $\tau\in K^*$, tels que $\A = (\tau)\prod g_i^{e_i}$.
\begin{itemize}
\item
Pour calculer les $(e_i)$, multiplier $\A$ par des produits aléatoires d'idéaux de $\BB$ et LLL-réduire le résultat, jusqu'à ce que la composante non principale soit friable. À un idéal principal près, on sait alors exprimer $\A$ comme produit d'éléments de $\BB$, donc des $g_i$.

\item
Calculer $\A \prod g_i^{-e_i}$ sous la forme $(\b)\BB$, $\b\in\ZM[K^*]$ (\S\ref{se:ALLL}). Puis réaliser le \emph{petit} idéal \emph{principal} $\BB$ comme $(\g)$, en utilisant la même méthode que ci-dessus, mais cette fois-ci en accumulant les idéaux principaux rencontrés. On pose $\tau := \b \g \in \ZM[K^*]$.
\end{itemize}

\subsection{Application: entiers de norme donnée}\label{se:applN} Soit $a\in \ZM$, $a\neq 0$, et soit à résoudre l'équation $\N(x) = a$, $x\in \ok$. C'est une équation diophantienne en les $x_i\in \ZM$, si on exprime $x = \sum_{i = 1}^n x_i w_i$, dans une $\ZM$-base $(w_i)$ de $\ok$. Par exemple $x^2 - 2y^2 = -1$ est de cette forme.

Il suffit de chercher les solutions modulo les unités de norme~$1$. On détermine d'abord s'il existe une unité de norme $-1$, en considérant successivement les générateurs de $U(K)$. Remarquons que la présentation compacte $u = \prod x_i^{e_i}\in\ZM[K^*]$ permet de tester le signe de $\N(u)$ à faible coût : il est donné par la parité du nombre de plongement réels $\sigma$ de $K$ tels que $\sigma(u) < 0$ (la norme est le produit des plongements, le produit de deux plongements complexes conjugués est $> 0$). Ce signe se détecte à partir de valeurs approchées des $\sigma(x_i)$ associés aux $e_i$ impairs.

En factorisant $\abs{a}$ en produit de nombres premiers, puis en décomposant ceux-ci dans $K/\QM$, on détermine l'ensemble (fini) des idéaux entiers de norme $\abs{a}$. Pour un tel idéal $\A$, on teste s'il est principal; si $\A = (\a)$, on teste si $a\N(\a) > 0$, comme indiqué ci-dessus. Sinon, $\N(\a) = -a$ et s'il existe une unité $u$ de norme $-1$, on corrige $\a \from u\a$.

\backmatter
\addtocontents{toc}{\protect\lsectionpart}
\bibliographystyle{jepplain+eid}
\bibliography{xups05-02}
\end{document} 