diff options
| -rw-r--r-- | rappels-maths.tex | 399 |
1 files changed, 166 insertions, 233 deletions
diff --git a/rappels-maths.tex b/rappels-maths.tex index 7c3312f..dfcad4b 100644 --- a/rappels-maths.tex +++ b/rappels-maths.tex @@ -30,7 +30,7 @@ \newcommand{\ppcm}{\operatorname{ppcm}} \newcommand{\signe}{\operatorname{signe}} \newcommand{\tee}{\mathbin{\top}} -\newcommand{\Frob}{\operatorname{Fr}} +\newcommand{\Frob}{\operatorname{Frob}} \renewcommand{\qedsymbol}{\smiley} % % @@ -41,7 +41,7 @@ \maketitle {\footnotesize \begin{center} -CVS: \verb=$Id: rappels-maths.tex,v 1.12 2008-11-26 17:35:18 david Exp $= +CVS: \verb=$Id: rappels-maths.tex,v 1.13 2009-10-21 17:09:11 david Exp $= \end{center} \par} \pretolerance=10000 @@ -717,11 +717,15 @@ a^{\varphi(m)} \equiv 1 \pmod{m} Démonstration : l'élément $\bar a \in (\mathbb{Z}/m\mathbb{Z})^\times$ a un ordre qui doit diviser l'ordre du groupe, i.e. $\varphi(m)$. -Attention ! ne pas confondre l'ordre d'un élément du groupe additif -$\mathbb{Z}/m\mathbb{Z}$ et l'ordre d'un élément du groupe -multiplicatif $(\mathbb{Z}/m\mathbb{Z})^\times$. Exemple : quel est -l'ordre de $2$ dans $\mathbb{Z}/7\mathbb{Z}$ ? dans -$(\mathbb{Z}/7\mathbb{Z})^\times$ ? +\textbf{Attention !} ne pas confondre l'ordre (« additif ») d'un +élément du groupe additif $\mathbb{Z}/m\mathbb{Z}$ et l'ordre +(« multiplicatif ») d'un élément du groupe multiplicatif +$(\mathbb{Z}/m\mathbb{Z})^\times$. Exemple : quel est l'ordre de $2$ +dans $\mathbb{Z}/7\mathbb{Z}$ ? (réponse : $7$ car $2+2+2+2+2+2+2 = +0$ dans $\mathbb{Z}/7\mathbb{Z}$ et qu'on ne trouve pas $0$ avant) ; +et dans $(\mathbb{Z}/7\mathbb{Z})^\times$ ? (réponse : $3$ car +$2\times 2\times 2 = 1$ dans $(\mathbb{Z}/7\mathbb{Z})^\times$ et +qu'on ne trouve pas $1$ avant). Cas particulier : « petit théorème de Fermat » : si $p$ est premier, alors $a^{p-1} \equiv 1 \pmod{p}$ lorsque $a$ n'est pas multiple @@ -1026,55 +1030,120 @@ le \textbf{corps de rupture} de $P$ sur $k$. \subsection{Sous-corps premier et caractéristique} -Caractéristique d'un corps : c'est l'ordre additif de $1$ si celui-ci -est fini (sinon on convient que c'est $0$). +Si $\mathbb{F}$ est un corps fini, alors l'ensemble $\{0_{\mathbb{F}}, +1_{\mathbb{F}}, 1_{\mathbb{F}}+1_{\mathbb{F}}, +1_{\mathbb{F}}+1_{\mathbb{F}}+1_{\mathbb{F}}, \ldots\}$ est fini. Cet +ensemble a la structure d'un $\mathbb{Z}/p\mathbb{Z}$ avec $p$ +premier : on dit qu'il s'agit du \textbf{(sous-)corps premier} +de $\mathbb{F}$, et que $p$ en est la \textbf{caractéristique}. +Autrement dit, ce $p$ est l'ordre additif de l'élément $1$ +de $\mathbb{F}$, et il s'agit toujours d'un nombre premier. + +Si $q$ est le cardinal de $\mathbb{F}$, alors $q$ est toujours une +puissance de $p$ (par exemple, si on sait ce que ça signifie, parce +que $\mathbb{F}$ est un espace vectoriel de dimension finie $d$ sur +son corps premier $\mathbb{F}_p$) ; on note typiquement $q = p^d$, et +alors $d$ s'appelle le \textbf{degré} de $\mathbb{F}$ au-dessus de son +corps premier $\mathbb{F}_p$. + +En particulier, le nombre d'éléments d'un corps fini est toujours une +puissance $q = p^d$ d'un nombre premier $p$ (il n'y a pas de corps à +$6$ ou $10$ éléments !), et tout corps fini contient un +$\mathbb{Z}/p\mathbb{Z}$. -Tout corps de caractéristique $p>0$ contient un -$\mathbb{Z}/p\mathbb{Z}$, qui en est un sous-corps $\mathbb{F}_p$ -(donc $p$ est premier) : on dit que c'est le sous-corps premier. Le -corps est alors un espace vectoriel dessus : le corps est fini, et si -$d$ est sa dimension, son nombre d'éléments est $p^d$. +% +\subsection{Petit théorème de Fermat, unicité des corps finis} -Moralité : le nombre d'éléments d'un corps fini est une puissance $q = -p^d$ d'un nombre premier $p$ (il n'y a pas de corps à $6$ ou $10$ -éléments !), et le corps contient alors $\mathbb{F}_p = -\mathbb{Z}/p\mathbb{Z}$ qu'on appelle son corps premier ; et $p$ -s'appelle la caractéristique. +Dans un corps $\mathbb{F}$ à $q$ éléments, on a $a^{q-1} = 1$ pour +tout $a \in \mathbb{F}^\times$ (par Lagrange appliqué au groupe +multiplicatif $\mathbb{F}^\times = \mathbb{F} \setminus\{0\}$ qui +a $q-1$ éléments). On a donc $a^q = a$ pour tout $a \in F$ (« petit + théorème de Fermat » généralisé aux corps finis). -% -\subsection{Unicité} +Ceci peut aussi se dire : le polynôme $t^q - t \in \mathbb{F}[t]$ +s'annule en tout point de $\mathbb{F}$ (tout élément de $\mathbb{F}$ +en est racine). Comme il est de degré $q$, on a sa factorisation : +\[ +t^q - t = \prod_{a \in \mathbb{F}} (t-a) +\] -Dans un corps $F$ à $q$ éléments, on a $a^{q-1} = 1$ pour tout $a \in -F^\times$ (par Lagrange) donc on a $a^q = a$ pour tout $a \in F$ -(« petit théorème de Fermat » généralisé). +Cette factorisation étant valable dans n'importe quel corps $L$ (fini +ou non) contenant $\mathbb{F}$, on voit que $\mathbb{F}$ peut se +définir (dans n'importe quel corps $L$ le contenant) comme l'ensemble +des éléments $x$ vérifiant $x^q = x$ (plus explicitement : le petit +théorème de Fermat signifie que tout élément de $\mathbb{F}$ vérifie +$x^q = x$, mais réciproquement tout élément de $L$ vérifiant cette +équation est automatiquement dans $\mathbb{F}$). -Comme le polynôme $t^q-t$, de degré $q$, ne peut avoir que $q$ -racines, si $F$ est contenu dans un corps $L$ plus gros, alors $F = -\{x\in L : x^q = x\}$. Moralité : un corps ne peut contenir qu'un -seul corps fini à $q$ éléments (pour $q$ fixé). +Ceci constitue une forme d'unicité des corps finis : un corps $L$ +donné ne peut contenir qu'\emph{au plus un} sous-corps $\mathbb{F}$ +ayant $q$ éléments (pour n'importe quel $q$) --- dès qu'il en contient +un, ce corps est complètement déterminé (comme l'ensemble des éléments +vérifiant $x^q = x$). -En particulier, le sous-corps premier $\mathbb{F}_p$ d'un corps $L$ de -caractéristique $p$ est $\mathbb{F}_p = \{x\in L : x^p = x\}$. +En particulier, le sous-corps premier $\mathbb{F}_p$ d'un corps fini +$L$ de caractéristique $p$ est $\mathbb{F}_p = \{x\in L : x^p = x\}$. On admet également l'unicité à isomorphisme près : deux corps finis à -$q$ éléments, pour le même $q$, sont isomorphes. +$q$ éléments, pour le même $q$, sont isomorphes. (C'est-à-dire qu'il +s'agit abstraitement du même objet, mais dont les éléments peuvent +être « nommés » différemment.) % -\subsection{Morphisme de Frobenius} - -Si $K$ est un corps de caractéristique $p$ alors $\Frob\colon K\to K, -x\mapsto x^p$ (le morphisme de Frobenius) est un morphisme de corps -($\Frob(xy) = \Frob(x)\,\Frob(y)$ toujours vrai, et $\Frob(x+y) = -\Frob(x) + \Frob(y)$ car on est en caractéristique $p$ donc tous les +\subsection{Morphisme de Frobenius, conjugués d'un élément} + +Si $\mathbb{F}$ est un corps fini de caractéristique $p$ alors +l'application $\Frob\colon \mathbb{F}\to \mathbb{F}, x\mapsto x^p$ +(parfois notée $\Frob_p$ pour plus de clarté) est appelée +\textbf{(morphisme de) Frobenius} de $\mathbb{F}$ (au-dessus +de $\mathbb{F}_p$). C'est un morphisme de corps : il vérifie +$\Frob(x+y) = \Frob(x) + \Frob(y)$ et $\Frob(xy) = \Frob(x)\,\Frob(y)$ +(le second est évident, et le premier est est vrai car on est en +caractéristique $p$ donc, quand on développe $(x+y)^p$, tous les coefficients binomiaux intermédiaires sont multiples de $p$ donc -nuls). On le note aussi $\Frob_p$ pour éviter l'ambiguïté. +nuls). C'est aussi une bijection de $\mathbb{F}$ sur lui-même +(c'est-à-dire que $\Frob$ permute les éléments de $\mathbb{F}$, chacun +ayant un unique antécédent ou racine $p$-ième). + +En appliquant plusieurs fois successivement le morphisme $\Frob$ à un +élément $x \in \mathbb{F}$ où $\mathbb{F}$ est un corps fini à $q = +p^d$ éléments, on obtient successivement : $x = +\Frob^0(x)\;,\penalty0\;\; \Frob^1(x) = x^p\;,\penalty0\;\; \Frob^2(x) += (x^p)^p = x^{p^2}\;,\penalty0\;\; \Frob^3(x) = (x^{p^2})^p = +x^{p^3}\;,...\penalty0\;\; \Frob^i(x) = x^{p^i}$. Ces éléments +$x^{p^i}$ s'appellent les \textbf{conjugués} de $x$ (au-dessus +de $\mathbb{F}_p$). + +On a vu plus haut que $x^{p^d} = x$ (c'est le petit théorème de +Fermat), autrement dit, au bout de $d$ applications du Frobenius on +retombe sur l'élément $x$ de départ ; il se peut qu'on retombe sur $d$ +plus tôt : le plus petit $r$ tel que $x^{p^r} = x$, qui est aussi le +nombre de conjugués distincts de $x$, s'appelle le \textbf{degré} +de $x$ (au-dessus de $\mathbb{F}_p$), et ce degré $r$ divise $d$ +(qu'on a appelé le degré de $\mathbb{F}$). Tous les conjugués de $x$ +ont bien sûr le même degré que $x$. + +\bigbreak -Si $q = p^d$, on a souvent besoin d'introduire $\Frob^d = \Frob_q -\colon x \mapsto x^q$ (composée $d$-ième du Frobenius). Notamment, -dans un corps à $q = p^d$ éléments, puisque $x^q = x$ pour tout $x$, -la composée $d$ fois de $\Frob_p$, soit $\Frob_q$, est l'identité. -(Pour cette raison, on dit aussi que $\Frob_q$ est le Frobenius -\emph{au-dessus} de $\mathbb{F}_q$.) +\textbf{Attention !} si $\mathbb{F}$ est un corps fini à $q = p^d$ +éléments, ne pas confondre les trois choses suivantes : +\begin{itemize} +\item L'ordre additif d'un élément $x$ dans $\mathbb{F}$ (groupe + additif) : cet ordre vaut toujours $q$ sauf pour $x=0$ (auquel cas + c'est $1$). +\item L'ordre multiplicatif d'un élément $x \neq 0$ dans + $\mathbb{F}^\times$ (groupe multiplicatif des éléments non nuls) : + cet ordre divise $q-1$ puisque le groupe $\mathbb{F}^\times$ est + d'ordre $q-1$. +\item Le degré $r$ d'un élément $x$ au-dessus de $\mathbb{F}_p$ qu'on + vient de définir : ce degré divise $d$. +\end{itemize} +Il y a cependant des rapports : par exemple, si $x \neq 0$ est de +degré $r$ alors son ordre multiplicatif divise $p^r - 1$ (car on a +$x^{p^r} = x$ par définition de $r$, donc $x^{p^r - 1} = 1$) ; +notamment, si $x$ est d'ordre $q - 1 = p^d - 1$ (on va voir qu'il +existe de tels éléments) alors $x$ est de degré $d$ (mais la +réciproque n'est pas vraie). % \subsection{Existence et inclusions des corps finis} @@ -1085,132 +1154,35 @@ comme $\mathbb{F}_q \cong \mathbb{F}_p[t]/(f)$ pour un certain polynôme $f \in \mathbb{F}_p[t]$ irréductible de degré $d$ (l'affirmation est qu'il en existe !). +\smallbreak + Si $q = p^d$ et $q' = p^{\prime d'}$, alors $\mathbb{F}_q$ est contenu dans $\mathbb{F}_{q'}$ (plus proprement : $\mathbb{F}_{q'}$ contient un sous-corps ayant $q$ éléments) si et seulement si : (1) $p=p'$ et -(2) $d|d'$. Cela équivaut encore à : $q'$ est une puissance de $q$, -soit $q' = q^e$. (Exemple : $\mathbb{F}_4$ est contenu dans -$\mathbb{F}_{16}$ mais pas dans $\mathbb{F}_8$.) Lorsque c'est le -cas, alors $\mathbb{F}_{q'} \cong \mathbb{F}_q[t]/(f)$ pour un certain -polynôme $f \in \mathbb{F}_q[t]$ irréductible de degré $e = d'/d$. - -On va voir plus loin comment tester l'irréductibilité d'un polynôme -sur un corps fini, et comment en produire. +(2) $d|d'$. Cela équivaut encore à : $q'$ est une puissance de $q$. +(Exemple : $\mathbb{F}_4$ est contenu dans $\mathbb{F}_{16}$ mais pas +dans $\mathbb{F}_8$.) % -\subsection{Polynôme minimal} - -[Dans les quelques sections qui suivent, le cas important est $q = p$ - premier (lire alors $p^d$ pour $q^e$). On peut ignorer le cas plus - général.] - -Rappel : dans $\mathbb{F}_q[t]/(f)$ (avec $f$ irréductible unitaire -pour fixer les idées), on a $f(\bar t) = 0$, c'est-à-dire que $\bar t$ -est racine de $f$. A contrario : - -\textbf{Prop :} Soit $x \in \mathbb{F}_{q^e}$, alors $x$ est racine -d'un unique polynôme irréductible unitaire sur $\mathbb{F}_q$, et -celui-ci est de degré divisant $e$. - -Ce polynôme s'appelle \textbf{polynôme minimal} de $x$ -sur $\mathbb{F}_q$, et son degré (divisant $e$, donc) s'appelle le -\textbf{degré} de $x$ sur $\mathbb{F}_q$. - -Naturellement, dans $\mathbb{F}_q[t]/(f)$, avec $f$ irréductible -unitaire, le polynôme minimal de $\bar t$ sur $\mathbb{F}_q$ est $f$. -Lorsque $a \in \mathbb{F}_q$, le polynôme minimal de $a$ est $t-a$, de -degré $1$ ; réciproquement, un élément de $\mathbb{F}_{q^e}$ est dans -$\mathbb{F}_q$ si et seulement si son degré est $1$. - -Si $x \in \mathbb{F}_{q^e}$ est de degré exactement $e$ -(c'est-à-dire : pas moins), et que $f$ est son polynôme minimal, alors -$\mathbb{F}_{q}[t]/(f) \cong \mathbb{F}_{q^e}$ (ce qu'on savait -déjà...) en envoyant $\bar t$ sur $x$, et plus généralement la classe -de $g \in \mathbb{F}_q[t]$ sur $g(x)$. - -Si on ne précise pas, le polynôme minimal s'entend sur le corps -premier. - -Exercice : déterminer dans $\mathbb{F}_4$ vu comme -$\mathbb{F}_2[t]/(t^2+t+1)$ les polynômes minimaux des différents -éléments, et les degrés sur $\mathbb{F}_2$. (Réponse : $0$ et $1$ ont -polynôme minimal $t$ et $t+1$ respectivement, et tous deux degré $1$ ; -$\bar t$ a polynôme minimal $t^2+t+1$ et $\bar t+1$ aussi, tous deux -ont degré $2$.) - -% -\subsection{Éléments conjugués} - -[On peut toujours imaginer $q = p$ premier.] - -Si $f$ est irréductible unitaire de degré $e$ sur $\mathbb{F}_q$ alors -dans $\mathbb{F}_q[t]/(f)$ les racines de $\bar t$ sont : $\bar t$, -$\bar t^q$, $\bar t^{q^2}$, ..., $\bar t^{q^{e-1}}$. Cette situation -porte un nom : - -On dit que deux éléments $x, x' \in \mathbb{F}_{q^e}$ sont -\textbf{conjugués} lorsqu'ils vérifient les conditions équivalentes -suivantes : -\begin{itemize} -\item $x$ et $x'$ ont le même polynôme minimal sur $\mathbb{F}_q$, -\item il existe $i$ (qu'on peut prendre entre $0$ et $e-1$) tel que - $x' = x^{q^i}$ (= on passe de l'un à l'autre en appliquant - suffisamment de fois le Frobenius $\Frob_q$). -\end{itemize} -Le nombre d'éléments conjugués à $x$ (en comptant $x$ lui-même) est le -degré de $x$. On parle d'un ensemble complet de conjugués -(sur $\mathbb{F}_q$). - -% -\subsection{Factorisation de $t^{q^e}-t$} - -[On peut toujours imaginer $q = p$ premier.] - -Dans la décomposition en facteurs irréductibles de $t^{q^e}-t$ dans -$\mathbb{F}_q$ : -\begin{itemize} -\item chaque polynôme irréductible de degré divisant $e$ sur -$\mathbb{F}_q$ apparaît une et une seule fois, -\item chaque facteur correspond à un ensemble complet de conjugués (de - cardinal égal au degré du facteur) dans $\mathbb{F}_{q^e}$, -\item le nombre de facteurs de degré exactement $e$ est $\frac{1}{e}$ - fois le nombre d'éléments appartenant à $\mathbb{F}_{q^e}$ mais à - aucun $\mathbb{F}_{q^{e_1}}$ pour $e_1$ divisant strictement $e$. -\end{itemize} - -\smallbreak - -Exercice : Expliquer pourquoi $t^{64}-t$ se -décompose en irréductibles sur $\mathbb{F}_2$ en : $2$ facteurs de -degré $1$, $1$ de degré $2$, $2$ de degré $3$ et $9$ de degré $6$. - -\medbreak - -Le nombre de polynômes irréductibles unitaires de degré $e$ dans -$\mathbb{F}_q[t]$ est approximativement $\frac{1}{e}q^e$ (l'erreur est -$O(q^{e/2})$). Autrement dit, la probabilité qu'un polynôme unitaire -aléatoire dans $\mathbb{F}_q[t]$ soit irréductible est -environ $\frac{1}{e}$ où $e$ est son degré. (Cf. théorème des nombres -premiers.) - -\medbreak +\subsection{Test de Rabin, factorisation de $t^{p^d}-t$} \textbf{Test d'irréductibilité de Rabin :} Étant donné $f \in -\mathbb{F}_q[t]$ de degré $e$, il est irréductible si et seulement si +\mathbb{F}_p[t]$ de degré $d$, il est irréductible si et seulement si les deux conditions suivantes sont vérifiées : \begin{itemize} -\item $f$ divise $t^{q^e}-t$, et -\item $f$ est premier avec $t^{q^{e_1}}-t$ pour tout diviseur strict - $e_1$ de $e$ (en fait, on peut se contenter de tester pour les - diviseurs stricts \emph{immédiats}, c'est-à-dire les $e_1 = e/\ell$ - avec $\ell$ premier). +\item[(a)] $f$ divise $t^{p^d}-t$, et +\item[(b)] $f$ est premier avec $t^{p^e}-t$ pour tout diviseur strict + $e$ de $d$ (en fait, on peut se contenter de tester pour les + diviseurs \emph{immédiats}, c'est-à-dire les $e = d/\ell$ avec + $\ell$ premier). \end{itemize} -(Remarque : le premier s'écrit $t^{q^e}\equiv t \pmod{f}$, et pour le -vérifier on applique un algorithme d'exponentiation -rapide\footnote{Par exemple, dans ce cas, tout simplement élever $e$ - fois successivement à la puissance $q$.} dans $\mathbb{F}_q[t]/(f)$. -De même, la seconde condition se teste avec l'algorithme d'Euclide en -commençant par calculer $t^{q^{e_1}}$ modulo $f$.) +(Remarque : la condition (a) s'écrit $t^{p^d}\equiv t \pmod{f}$, et +pour la vérifier on applique un algorithme d'exponentiation +rapide\footnote{Par exemple, dans ce cas, tout simplement élever $d$ + fois successivement à la puissance $q$.} pour calculer $\bar +t^{p^d}$ dans $\mathbb{F}_p[t]/(f)$. De même, la condition (b) se +teste avec l'algorithme d'Euclide en commençant par calculer $t^{q^e}$ +modulo $f$.) \smallskip @@ -1227,43 +1199,40 @@ second, $t^4-t \equiv t^3+t+1 \pmod{g}$ puis $g = t^4+t^3+1 \equiv t^2 \pmod{t^3+t+1}$ et enfin $t^3+t+1 \equiv 1 \pmod{t^2}$ donc $t^4-t$ et $g$ sont bien irréductibles.) -\bigbreak +\medbreak + +Le nombre de polynômes unitaires irréductibles de degré $d$ dans +$\mathbb{F}_p[t]$ vaut approximativement $\frac{1}{d} p^d$ (plus +exactement, c'est $\frac{1}{d} p^d + O(p^{d/2})$ lorsque $d \to ++\infty$). Ceci signifie que parmi les $p^d$ polynômes unitaires de +degré $d$ sur $\mathbb{F}_p$, il y en a une proportion d'environ +$\frac{1}{d}$ qui sont irréductibles. + +Ainsi, pour générer un polynôme irréductible, il est raisonnable de +tirer un polynôme (unitaire) au hasard, et de tester son +irréductibilité, et de recommencer jusqu'à obtenir un irréductible. + +\medbreak + +On a vu plus haut que sur le corps $\mathbb{F}_q$ (lorsque $q = p^d$), +le polynôme $t^q - t$ se factorise en irréductibles comme $t^q - t = +\prod_{a \in \mathbb{F}_q} (t-a)$. Il est utile de savoir que sur +$\mathbb{F}_p$, ce même polynôme se factorise comme le produit de +\emph{tous} les polynômes unitaires irréductibles dont le degré $r$ +divise $d$ (plus précisément, chaque polynôme unitaire irréductible +$f$ de degré $r$ sur $\mathbb{F}_p$ devient, quand on le regarde sur +$\mathbb{F}_q$, le produit des $(t-a)$ pour les $r$ conjugués $a$ d'un +élément de degré $r$). Ce fait peut servir à dénombrer de façon +précise les polynômes unitaires irréductibles de n'importe quel degré +sur $\mathbb{F}_p$. + +\medbreak \textbf{Note :} Contrairement à la situation dans les entiers, on peut effectuer efficacement la factorisation des polynômes sur les corps finis. % -\subsection{Récapitulation : comment manipuler les $\mathbb{F}_q$} - -Moralité des paragraphes précédents : comment faire des calculs dans -$\mathbb{F}_q$ avec $q = p^d$ ? - -On sait travailler dans $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$ -(travailler dans $\mathbb{Z}$ et faire des divisions euclidiennes -par $p$). - -Trouver un polynôme irréductible unitaire $f$ de degré $d$ dans -$\mathbb{F}_p[t]$ : pour cela, choisir un polynôme unitaire aléatoire -de degré $d$ parmi les $p^d$ possibles, utiliser le test de Rabin pour -tester son irréductibilité, et recommencer jusqu'à obtenir un $f$ qui -passe le test (en moyenne, on fera environ $d$ essais). - -Représenter les éléments de $\mathbb{F}_q \cong \mathbb{F}_p[t]/(f)$ -par des polynômes de degré $<d$ sur $\mathbb{F}_p$. L'addition se -fait terme à terme. Pour la multiplication, faire suivre d'une -division euclidienne par $f$ dont on ne conserve que le reste. Pour -l'inverse, utiliser une relation de Bézout avec $f$ (cf. le calcul des -inverses dans $\mathbb{Z}/m\mathbb{Z}$). Pour l'exponentiation, -utiliser un algorithme d'exponentiation rapide. - -Exercice : Vérifier que $f = t^3 + t + 1 \in \mathbb{F}_2[t]$ est -irréductible, et s'en servir pour dresser les tables d'opération de -$\mathbb{F}_8$. (Pour vérifier que $f$ est irréductible : $t^3 \equiv -t+1 \pmod{f}$ donc $t^4 \equiv t^2+t$ donc $t^8 \equiv t^4+t^2 \equiv -t$, et par ailleurs $f \equiv 1 \pmod{t^2-t}$.) - -% \subsection{Éléments primitifs} \textbf{Théorème :} Le groupe multiplicatif d'un corps fini est @@ -1271,49 +1240,13 @@ cyclique. Autrement dit, si $\mathbb{F}$ est un corps fini, il existe des éléments $g$, dits \textbf{primitifs}, qui engendrent le groupe -multiplicatif des éléments non nuls de $\mathbb{F}$, c'est-à-dire tels -que tout élément non nul de $\mathbb{F}$ soit une puissance de $g$. - -Le nombre d'éléments primitifs est bien sûr $\varphi(q-1)$. - -Si un élément $g \in \mathbb{F}_q$, avec $q = p^d$, est primitif, -alors tous ses conjugués sur le corps premier $g^p, g^{p^2}, g^{p^3}, -\ldots, g^{p^{d-1}}$ le sont aussi. On peut donc aussi dire que leur -polynôme minimal (commun) est primitif ; il est nécessairement de -degré $d$. Le nombre de polynômes irréductibles primitifs de -degré $d$ sur $\mathbb{F}_p$ est donc $\frac{1}{d} \varphi(p^d-1)$. - -Exemple : si $g \in \mathbb{F}_{16}^\times$ est primitif, alors -$\{g,g^2,g^4,g^8\}$ est un ensemble complet de conjugués -(sur $\mathbb{F}_2$), tous primitifs ; $\{g^7,g^{14},g^{13},g^{11}\}$ -est également un ensemble complet de conjugués, également primitifs -car $7$ engendre $\mathbb{Z}/15\mathbb{Z}$ ; $\{g^3,g^6,g^{12},g^9\}$ -en est un autre, de degré $4$ mais \emph{non primitifs} ; enfin, -$\{g^5,g^{10}\}$ est un ensemble complet de conjugués de degré $2$ ; -et $\{1=g^{15}\}$ et $\{0\}$ sont les deux seuls éléments de degré $1$ -sur le corps de base $\mathbb{F}_2$ ; on a donc $\mathbb{F}_4 = \{0, -1, g^5, g^{10}\}$. - -Exercice : on a trouvé précédemment deux polynômes irréductibles -unitaires $f = t^4 + t + 1$ et $g = t^4 + t^3 + 1$ de degré $4$ -sur $\mathbb{F}_2$. Sont-ils primitifs ? (Réponse : oui.) En -admettant que $h = t^4 + t^3 + t^2 + t + 1$ est irréductible, est-il -primitif ? (Réponse : non, car $t^5 \equiv 1 \pmod{h}$.) - -\smallskip +multiplicatif $\mathbb{F}^\times$ des éléments non nuls +de $\mathbb{F}$, c'est-à-dire tels que tout élément non nul de +$\mathbb{F}$ soit une puissance de $g$. -Moralité : Donné un élément $g \in \mathbb{F}_q^\times$ primitif, avec -$q = p^d$, ou bien son polynôme minimal $\pi \in \mathbb{F}_p[t]$ -(voir $g$ comme $\bar t \in \mathbb{F}_p[t]/(\pi)$), on peut -représenter les éléments de $\mathbb{F}_q$ de deux façons : soit comme -des polynômes de degré $<d$ en $g$ (en $\bar t$), soit comme zéro et -des puissances entre $0$ et $q-1$ de $g$ (de $\bar t$). Dans le -premier cas, l'addition est facile et la multiplication est un peu -plus difficile, dans le second cas, la multiplication est facile et -l'addition presque impossible. Passer de la seconde représentation à -la première est facile ; le passage dans le sens inverse (par exemple, -écrire $1+g$ comme une puissance de $g$) correspond au problème du -\emph{logarithme discret}. +Le nombre d'éléments primitifs est bien sûr $\varphi(q-1)$ (puisque, +une fois qu'on sait que $\mathbb{F}^\times$ est cyclique, comme il est +d'ordre $q-1$, le nombre d'éléments qui l'engendrent est connu). % % |