Rappels sur les corps finis#
Construction et premières propriétés.#
Théorème#
À isomorphisme près, il existe un unique corps fini \(\mathbb{F}_q\) à \(q = p^n\) éléments (\(p\) premier, \(n \geq 1\)) et ce sont les seuls corps finis. De plus, \(\mathbb{F}_q\) (avec \(q=p^n\)) vérifie les propriétés suivantes :
\(\mathbb{F}_q\) est de caractéristique \(p\);
pour tout \(x \in \mathbb{F}_q\), on a \(x^{p^n} = x\) et dans \(\mathbb{F}_q [X]\), on a \( X^{p^n} - X = \prod_{a \in \mathbb{F}_q} (X - a)\).
\(\mathbb{F}_q^\times\) est cyclique;
l’application \( \begin{array}{llll} F : & \mathbb{F}_q & \longrightarrow & \mathbb{F}_q\\ & a & \longmapsto & a^p \end{array} \) est un automorphisme appelé morphisme de Frobenius et ses points fixes sont les éléments de \(\mathbb{F}_p\);
pour tout \(P\) polynôme irréductible de \(\mathbb{F}_p [X]\) de degré \(n\), on a \( \mathbb{F}_q \simeq \mathbb{F}_p [X] / (P) \) (et de tels polynômes irréductibles existent toujours).
Exercice 1. Corps finis avec sage - Manipulations de base.#
Dans sage, les corps finis se définissent à l’aide de la commande GF.
Calculer les carrés des éléments de \(\mathbb F_4\).
Calculer les ordres (pour la multiplication) des éléments non nuls de \(\mathbb F_9\). Commenter.
La méthode polynomial permet d’obtenir le polynôme unitaire et irréductible choisi automatiquement par sage pour définir un corps composé. Déterminer le polynôme choisi par sage pour définir \(\mathbb F_4\). Vérifier que ce polynôme est irréductible dans \(\mathbb F_2[x]\). Factoriser ce polynôme sur \(\mathbb F_4\). Commenter.
Déterminer la liste des polynômes irréductibles de degré \(2\) de \(\mathbb F_2[x]\) et la liste des polynômes irréductibles de degré \(3\) de \(\mathbb F_2[x]\). On pourra utiliser la méthode polynomials des objets anneaux de polynômes.
L’option modulus de GF permet d’imposer un choix de polynôme unitaire irréductible dans la définition d’un corps composé. Définir \(\mathbb F_8\) en utilisant deux polynômes irréductibles différents.
On considère un corps fini \(\mathbb F_q = \mathbb F_p[X]/(P)\) où \(P\in \mathbb F_p[X]\) est irréductible de degré \(n\). On note \(x=\overline{X}\). L’élément \(x\) est-il toujours un générateur de \(\mathbb F_q^\times\) ? Expérimenter avec sage (attention, sage ne choisit pas ses polynômes irréductibles au hasard pour construire un corps fini).
Propriété (sous-corps d’un corps fini)#
Soit \(p\) un nombre premier alors \(\mathbb{F}_{p^m} \subset \mathbb{F}_{p^n}\) si et seulement si \(m\) divise \(n\). De plus, si \(m\) divise \(n\), \(\mathbb{F}_{p^m} = \{ a \in \mathbb{F}_{p^n}, a^{p^m} = a \} \subset \mathbb{F}_{p^n}\).
Exercice 2. Sous-corps d’un corps fini.#
Définir \(\mathbb F_{256}\) avec sage et donner explicitement les éléments de \(\mathbb F_{16}\) vu comme sous-corps de \(\mathbb F_{256}\). Parmi ces éléments, lesquels peuvent correspondre à la classe de \(X\) si on écrit \(\mathbb F_{16}\) sous la forme \(\mathbb F_2[X]/(Q)\) ? Que vaut \(Q\) dans ce cas (attention \(Q\) peut dépendre de l’élément considéré) ?
Indication : on pourra factoriser \(X^{16}-X\) sur \(\mathbb F_2\).
Dans \(\mathbb F_{531441}\), conjecturer puis vérifier avec sage le cardinal des ensembles des racines des polynômes suivants \(X^{81}-X\), \(X^{729}-X\) et \(X^{19683}-X\). (Bonus) Démontrer la conjecture.
Propriété (racines)#
On se place dans \(\mathbb{F}_q \simeq \mathbb{F}_p [X] / (P)\) où \(P\) est un polynôme irréductible de \(\mathbb{F}_p [X]\) de degré \(n\) et on pose \(\alpha = \overline{X}\). Alors les racines de \(P\) dans \(\mathbb{F}_q\) sont exactement \(\alpha, \alpha^p, \ldots, \alpha^{p^{n - 1}}\).
Exercice 3. Effet du morphisme de Frobenius sur les racines.#
Soit \(P=x^3+x^2+2x+1\).
Factoriser \(P\) sur \(\mathbb F_{17}\) et \(\mathbb F_{289}\).
Prédire l’effet du morphisme de Frobenius sur les racines de \(P\) dans \(\mathbb F_{289}\). Vérifier avec sage.
On écrit \(\mathbb F_{289}=\mathbb F_{17}[x]/(Q)\) où \(Q=x^2-x+3\). On note \(a\) la classe du polynôme \(x\) dans ce quotient. Déterminer (sans tous les tester) un polynôme unitaire \(R\) de degré \(3\) de \(\mathbb F_{17}[x]\) tel que \(2\) et \(a+1\) soient des racines de \(R\) dans \(\mathbb F_{289}\). Ce polynôme est-il unique ?
Plus généralement, montrer que si \(P\in\mathbb F_{p}[X]\) alors le morphisme de Frobenius permute ses racines dans \(\mathbb F_{p^n}\).
Propriétés (automorphismes)#
Les automorphismes de \(\mathbb{F}_q\) sont \(\mathrm{Id}, F, \ldots, F^{n -1}\) (où \(F\) est le morphisme de Frobenius).
Exercice 4. Corps finis isomorphes.#
Soient \(P_1=X^3+X^2+1\) et \(P_2=X^3+X+1\) des polynômes de \(\mathbb F_2[X]\). On note \(k_1=\mathbb F_2[X]/(P_1)\) et \(k_2=\mathbb F_2[X]/(P_2)\). Construire explicitement un isomorphisme de corps entre \(k_1\) et \(k_2\) (on demande une formule explicite et un argument théorique garantissant que la formule est bien un isomorphisme, on pourra utiliser sage pour effectuer d’éventuels calculs). Combien y a-t-il de tels isomorphismes ?
Coût des opérations#
Question 5.#
Quelle est le coût des opérations dans un corps fini (à l’aide des alogrithmes de la première partie du cours) ?
Réponse 5.#
On considère \(K = \mathbb F_p[X]/(P)\) avec \(P\) irréductible de degré \(n\).
l’addition de deux éléments de \(K\) revient à additionner deux polynômes, c’est un \(O(n)\) opération dans \(\mathbb F_p\);
le calcul d’un opposé s’effectue également en \(O(n)\) opération dans \(\mathbb F_p\);
la multiplication de deux éléments s’obtient (naïvement) en multipliant deux polynômes puis en réduisant modulo \(P\) (par division euclidienne), on obtient une complexité en \(O(n^2)\) par l’algorithme (non effiace) du cours.
l’inverse d’un élément s’obtient en calculant une relation de Bézout, ce qui s’effectue en \(O(n^2)\) opérations par l’algorithme (non efficace) du cours.
Polynômes sur les corps finis.#
Exercice 6. Algorithme de Berlekamp.#
Soit \(k\) un corps fini de cardinal \(p\). Nous allons programmer l’algorithme de Berlekamp pour factoriser un polynôme \(P \in k[X]\) sans facteur carré.
Étant donné un polynôme \(P\in k[X]\), considérons \(\Phi\) l’application linéaire de \(k[X]/(P)\) dans lui même définie par \(\Phi : f \mapsto f^p - f\). Écrire une fonction qui prend en argument un polynôme \(P(X)\in k[X]\) et qui renvoie la matrice de \(\Phi\) dans la base \(\{1, X, X^2, . . .\}\). Que s’attend-t-on à trouver pour la première colonne ? Quelle matrice obtient-on pour le polynôme \(P = X^4 + X^3 + X^2 + X + 1\) de \( \mathbb{Z}/19\mathbb{Z}[X]\) ?
Comprendre comment obtenir une base du noyau de cette matrice avec sage.
On suppose \(P = P_1\cdots P_r\) est sans carré. Soit \(Q\) tel que \(\Phi(\overline{Q})=0\). Expliquer pourquoi \(Q [P_i]\) est une constante. Expliquer comment utiliser cette propriété pour trouver un facteur non trivial de \(P\). Écrire une fonction qui prend en argument deux polynômes \(P\) et \(Q\), et qui recherche un \(s \in k\) tel que le PGCD de \(P\) et de \(Q - s\) soit non trivial, en renvoyant le diviseur de \(P\) ainsi trouvé, et en renvoyant
Nones’il n’y en a pas.Programmer une fonction qui prend un polynôme sans facteur carré à coefficients dans un corps fini et qui donne un diviseur non trivial de ce polynôme (éventuellement le polynôme lui-même, ou plutôt
None(c’est a dire rien du tout), s’il est irréductible).Tester avec \(X^4 + 1\) puis avec \(X^{12} + X^2 + 1 \in \mathbb{F}_p[X]\) pour les nombres premiers \(2 \leq p \leq 19\). On pourra vérifier les résultats avec la méthode
.is_ irreducible()ou.factor(). Que se passe-t-il pour \(X^4 + 1\) et \(p = 2\) ?Programmer la fonction
Berlekampqui prend un polynôme sans facteur carré à coefficients dans un corps fini, et qui renvoie sa décomposition en produit d’irréductibles. Tester avec \(X^{12} + X^2 + 1\) sur \(\mathbb{F}_{19}\).
Exercice 7 (Bonus). Factorisation par degré.#
Soit \(p\) un nombre premier et \(n\) un entier positif.
En étudiant les orbites des éléments de \(\mathbb F_{p^n}\) sous l’action du morphisme de Frobenius, démontrer que \(X^{p^n}-X\in\mathbb F_p[X]\) est le produit des polynômes unitaires irréductibles de \(\mathbb F_p[X]\) et dont le degré divise \(n\) (on admettra que \(X^{p^n}-X\) est sans facteur carré).
Déduire de la propriété précédente un algorithme de factorisation par degrés : un tel algorithme prend un entrée un polynôme sans carré \(P\) de degré \(n\) de \(\mathbb F_p[X]\) et renvoie le \(n\)-uplet de polynômes \((Q_1,\dots, Q_n)\) où \(Q_i\) est le produit des facteurs irréductibles de \(P\) de degré \(i\). Implémenter cet algorithme et étudier sa complexité.
Exerccice 8 (Bonus). Algorithme de Ben-Or.#
On considère le pseudo-code :
Entrée : Un nombre premier \(p\) et un entier \(n\geq 1\)
Sortie : Un polynôme unitaire irréductible de \(\mathbb F_p\) de degré \(n\) choisi uniformément au hasard
Choisir un polynôme unitaire \(P\) de degré \(n\) sur \(\mathbb F_p\) aléatoirement
Pour \(i=1,..,\lfloor n/2 \rfloor\)
\( g_i \leftarrow \mathrm{pgcd}(x^{p^i}-x,P)\), si \(g_i\neq 1\) retourner à l’étape 1.renvoyer \(P\).
Montrer que le polynôme \(P\) renvoyé est bien un polynôme irréductible de degré \(n\).
Implémenter l’algorithme de Ben-Or avec sage.
Modifier l’algorithme précédent pour estimer le nombre d’essais effectués avant de trouver un polynôme irréductible.
Illustrer et commenter en utilisant le fait que le nombre de polynômes irréductibles de degré \(n\) est comparable à \(1/n\).