Corps finis

On construit un corps fini de cardinal $p^n$ pour tout $p$ premier et $n\in\mathbf{N}^\bullet$.

Vous savez peut-être déjà que tout corps fini $A$ a un cardinal de la forme $p^n$ où $p$ est la caractéristique de $A$ et, réciproquement, que pour tout $p$ premier, et tout $n$ non nul, il existe un corps de cardinal $p^n$ (unique à isomorphisme près).

C’est une chose de connaître l’existence d’un objet, mais ç’en est une autre de le construire explicitement : quelle tête a le corps de cardinal $2^8$ ? comment sont définies ses opérations ? Répondre à ces questions demande un peu de travail…

Dans la suite, $A$ est un corps (commutatif). Si $p$ est premier, on note $\mathbf{F}_p$ le corps $\mathbf{Z}/p\mathbf{Z}$.

Cardinal des corps finis

On montre que le cardinal d’un corps fini $A$ est nécessairement de la forme $p^n$ avec $p$ premier ($p$ étant alors la caractéristique de $A$).

On considère la fonction \[ \begin{array}{rcl} f:\mathbf{Z}&\to& A \\ n &\mapsto& n1_A \end{array} \] Cette fonction préserve les opérations d’anneau: son noyau $\{ n\mid f(n) = 0 \}$ est un idéal de $\mathbf{Z}$, donc il est nécessairement de la forme $p\mathbf{Z}$ et on appelle $p$ la caractéristique de $A$.

Lorsque $A$ est fini, $f$ n’est pas injective, donc son noyau n’est pas réduit à $0$ et $p\not=0$. L’image de $f$ est alors un sous-anneau de $A$, isomorphe à $\mathbf{Z}/p\mathbf{Z}$. Or $A$ est un corps, donc c’est un anneau intègre, donc l’image de $f$ aussi, et donc $p$ est nécessairement premier.

Par ailleurs, $A$ est muni d’une structure de $\mathbf{F}_p$-espace vectoriel, le produit externe étant donné par $\bar k\cdot a=f(k)\times a$: comme $A$ est fini, la dimension $n$ de $A$ est finie et donc $A$ a $p^n$ éléments.

Ajouter des racines

Soit $P$ un polynôme non nul. On note $A[X]/P$ le quotient de $A[X]$ par la relation $\sim_P$ de congruence modulo $P$ : formellement, $Q\sim_P R$ ssi $P\mid Q-R$, c’est-à-dire si $Q\mod P = R\mod P$. Comme pour $\mathbf{Z}/n\mathbf{Z}$, on peut identifier la classe $\bar Q$ de $Q$ avec le reste de la division de $Q$ par $P$.

Exercices

• Vérifiez que si $A$ a $n$ éléments alors $A[X]/P$ a $n^{d(P)}$ éléments.
• Vérifiez que les opérations d’anneau et d’algèbre (somme, opposé, produit externe, produit interne) sont compatibles avec cette équivalence: $A[X]/P$ est encore une algèbre sur $A$. De plus, dès que $d(P)>0$, $a\mapsto \bar a$ plonge injectivement $A$ dans $A[X]/P$.
• Vérifiez que dans $A[X]/X-a$, $X$ est identifié avec $a$. Plus généralement, vérifiez que $\bar X$ devient une racine de $P$, vu comme un polynôme sur $A[X]/P$.
• Vérifiez que $A[X]/P$ est un corps ssi $P$ est irréductible.

Remarque. On peut montrer (mais on ne le fait pas ici) que lorque $P$ est irréductible $A[X]/P$ est le corps de rupture de $P$: une extension minimale du corps $A$, dans laquelle $P$ admet au moins une racine (et que cette extension est essentiellement définie de manière unique par cette propriété).

Polynômes dérivés

Si $P=\sum_{i=0}^n a_i X^i$, on pose $D(P)=\sum_{i=1}^n i\times a_i X^{i-1}$ son polynôme dérivé (évidemment, si $A$ est $\mathbf{R}$ ou $\mathbf{C}$, $\widehat{D(P)}$ est la fonction dérivée de $\hat{P}$ au sens habituel).

Exercices

• Vérifiez que l’opérateur de dérivation suit la règle de Leibiz \[ D(PQ)=D(P)Q+PD(Q). \]
• Déduisez-en que si $Q^2\mid P$ alors $Q\mid D(P)$.
• (Optionnel, mais facile) Ajoutez une méthode derive(self) à la classe P, qui renvoie le polynôme dérivé.

Un certain polynôme

On suppose que $A$ admet $q$ éléments, et on pose $U_n=X^{q^n}-X$, pour tout $n\in\mathbf{N}^\bullet$. On va démontrer:

Théorème. Le polynôme $U_n$ est le produit des polynômes unitaires irréductibles dans $A[X]$, de degré divisant $n$.

On rappelle (ou admet) le résultat suivant:

Lemme. Le groupe multiplicatif d’un corps fini est cyclique.

On en trouve des démonstrations dans des styles variés, par exemple :

• celle de Patrick Massot, qui reprend l’argument classique de l’exposant;
• celle de Daniel Perrin (Théorème 2.7, p. 74 de son cours d’algèbre chez Ellipses, dont on trouve une reprise par exemple sur le site de la prépa agrég de Rennes) est plus ad hoc, mais fait le travail en une demi-page.

Dans les exercices suivants, il est utile de ne pas oublier les autres cours de ce semestre…

Exercices

• Préliminaire: Soient $p,d,n\in\mathbf{N}^\bullet$ avec $p>1$. Montrez que $p^d-1\mid p^n-1$ ssi $d\mid n$.
• Vérifiez que, si $d\mid n$, alors $U_d\mid U_n$.
• Vérifiez que $D(U_n)=-1$. Déduisez-en qu’il n’y a pas de facteur multiple dans la décomposition de $U_n$ en facteurs irréductibles.
• Vérifiez que, dans toute algèbre sur $A$, l’ensemble des racines de $U_n$ forme une sous-algèbre (c’est-à-dire qu’il contient $0$ et $1$, et qu’il est stable par somme, produit binaire, et produit par un élément de $A$).
• Soit maintenant $P$ un polynôme irréductible dans $A[X]$, de degré $d$: vérifiez que, dans $A[X]/P$, la classe de $X$ est à la fois une racine de $P$ et une racine de $U_d$. Déduisez-en que $P\mid U_d$ et, si $d\mid n$, $P\mid U_n$.
• Réciproquement, si $P$ est un diviseur irréductible de $U_n$ dans $A[X]$, de degré $d$, vérifiez que tous les éléments de $A[X]/P$ sont solutions de $U_n$. Déduisez-en (grâce au lemme ci-dessus) que $q^{d}-1\mid q^{n}-1$ et donc $d\mid n$.

Existence de polynômes irréductibles en tout degré

On a donc établi que, dans la décomposition en polynômes irréductibles de $U_n$, chaque polynôme unitaire irréductible de degré $d\mid n$ apparait exactement une fois. En notant $m_d$ le nombre de polynômes unitaires irréductibles de degré $d$ sur $A$, on obtient: \[ q^n = d(U_n) = \sum_{d\mid n} d\times m_d . \]

Exercice

• Déduisez-en que $m_n\le \frac{q^n}{n}$, puis que $m_n> \frac{q^n-q^{\lfloor n/2\rfloor+1}}{n} $. En particulier $m_n>0$.

Critère d’irréductibilité

On sait donc qu’il y a des polynômes irréductibles en tout degré. Mieux, comme $\frac{q^n-q^{\lfloor n/2\rfloor+1}}{n} $ est équivalent à $\frac{q^n}{n}$ quand $n$ est grand, un polynôme unitaire de grand degré $n$ a à peu près une chance sur $n$ d’être irréductible. Ça a donc du sens de les tirer au hasard : reste à savoir, quand on tire un tel polynôme au hasard, s’il est bien irréductible.

Exercices

• Montrez qu’un polynôme unitaire $P$ de degré $n$ est irréductible sur $A$ ssi: $P\mid U_n$ et, pour chaque facteur premier $d$ de $n$, $P$ est premier avec $U_{n/d}$.
• Notons $Q_n=X^{q^n}\mod P$. Montrez que, lorsque $n>1$, la condition précédente est équivalente à: $Q_n = X$ et, pour chaque facteur premier $d$ de $n$, $(Q_{n/d}-X)\wedge P=1$ (l’avantage est que ces polynômes sont de degré $n$ plutôt que $q^n$).

Trouver des polynômes irréductibles

Au moyen des résultats mathématiques précédents, on construire des corps finis en Python: pour déterminer un corps de cardinal $p^n$, il suffit de se donner un polynôme irréductible sur $F_p$, de degré $n$.

La première étape est de se doter d’une classe de polynômes à coefficients dans $F_p$ : on réutilise une bonne partie du travail précédent.

Exercices

• Définissez une classe PF telle que, si n est un entier naturel non nul et a une liste de coefficients entiers, alors PF(n,a) représente le polynôme dont les coefficients sont ceux de a, considérés dans $\mathbf{Z}/n\mathbf{Z}$, équipé des méthodes pour l’addition, la soustraction, la multiplication et la division euclidienne, ainsi que des méthodes unitaire(), pgcd_couple_bezout() et pgcd(), comme pour la classe P. (On peut reprendre le code de la classe P, en s’assurant que tout est fait modulo n. Et on peut utiliser la classe ZZ pour les coefficients.)
• Ajoutez une méthode est_irreductible(p,u) qui retourne True si ce polynôme est irréductible et False sinon. Pour appliquer le critère ci-dessus, vous aurez besoin d’une fonction qui calcule les facteurs premiers de n : on a déjà fait ça, et on n’a heureusement pas besoin qu’elle soit très efficace. Il sera par contre utile de calculer efficacement les puissances de polynômes modulo $P$ (le degré de $X^{q^n}$ peut être très grand devant $n$ et nos opérations sur les polynômes ne sont pas très efficaces): vous pouvez écrire une fonction puissance_modulo(p,u,n), qui calcule la puissance n-ième de u modulo p, en utilisant l’exponentiation rapide pour faire encore mieux.
• Écrivez une fonction irreductibles(n,p) qui retourne la liste des polynômes unitaires irréductibles de degré n sur $F_p$. Combien y a-t-il de polynômes irréductibles de degré $8$ sur $F_2$ ?
• Pour de plus grandes valeurs de n, ça rame déjà beaucoup, mais ce n’est pas très grave : plutôt que de chercher tous les polynômes, il suffit d’en trouver un. Écrivez une fonction trouve_irreductible(n,p) qui retourne un polynôme unitaire irréductible de degré n sur $F_p$, en tirant les n coefficients de degré <n au hasard jusqu’à trouver un irréductible.

Construire des corps finis

Pour construire un corps de cardinal $p^n$ avec $p$ premier, on n’a donc qu’à trouver un polynôme irréductible $Q$ de degré $n$ sur $F_p$, puis à considérer $F_p[X]/Q$. On obtient une bijection avec $\{ 0, \cdots, p^n-1 \}$, via \[ k = \sum_{i=0}^{n-1} a_i p^i \mapsto C_Q(k) = \sum_{i=0}^{n-1} a_i X^i. \] On a évidemment $C_Q(0)=\bar{0}$ et $C_Q(1)=\bar{1}$, mais il n’y bien sûr aucune raison pour que l’opération préserve les opérations.

Exercices

• Donnez les tables d’addition et multiplication de $F_2[X]/Q$ pour $Q$ l’unique unitaire irréductible de degré $2$ sur $F_2$.
• Définissez une classe Corps telle que, si Q est un polynôme irréductible sur $F_p$ avec $p$ premier, Corps(Q,k) représente l’élément $C_Q(k)$ dans $F_p[X]/Q$. Alternativement, si P est un polynôme du même type que Q, Corps(Q,P) représente la classe de P dans $F_p[X]/Q$. Munissez cette classe de toutes les opérations de corps.
• Le calcul systématique des opérations est assez coûteux: si le but est de se munir d’un corps fini, il serait bien plus efficace de précalculer les tables. Définissez une classe TableCorps telle que, si Q est un polynôme irréductible sur $F_p$ avec $p$ premier, TableCorps(Q) est muni de méthodes addition(k,l), multiplication(k,l), inverse(k), etc. qui renvoient leur résultat en temps constant (la construction de l’objet TableCorps(Q) peut par contre prendre beaucoup de temps…).

Pour aller plus loin

Une bonne partie de cette activité est directement inspirée du livre Cours d'algèbre. Primalité Divisibilité. de Michel Demazure (2008), dont je vous recommande très chaudement la lecture (on n’en a effleuré que certains points), ainsi que de sa « digestion » sur la page Wikipédia Corps fini.