diff options
| -rw-r--r-- | rappels-maths.tex | 212 |
1 files changed, 210 insertions, 2 deletions
diff --git a/rappels-maths.tex b/rappels-maths.tex index 7fad063..16f0802 100644 --- a/rappels-maths.tex +++ b/rappels-maths.tex @@ -41,7 +41,7 @@ \maketitle {\footnotesize \begin{center} -CVS: \verb=$Id: rappels-maths.tex,v 1.7 2008-10-19 18:48:48 david Exp $= +CVS: \verb=$Id: rappels-maths.tex,v 1.8 2008-10-19 22:44:33 david Exp $= \end{center} \par} \pretolerance=10000 @@ -136,7 +136,7 @@ Le nombre $\pi(x)$ de nombres premiers $\leq x$ est équivalent à $\frac{x}{\ln x}$ lorsque $x\to +\infty$ (Hadamard \& de la Vallée Poussin : « théorème des nombres premiers »). Moralement : la probabilité qu'un nombre de $n$ bits aléatoire soit premier est -environ $n\,\ln 2$. +environ $\frac{1}{n\,\ln 2}$. Beaucoup de questions ouvertes. Par exemple : Conjecture des nombres premiers jumeaux : existe-t-il une infinité de nombres premiers $p$ @@ -1082,6 +1082,214 @@ 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é $d'/d$. +On va voir plus loin comment tester l'irréductibilité d'un polynôme +sur un corps fini, et comment en produire. + +% +\subsection{Polynôme minimal} + +[Dans les quelques sections qui suivent, le cas important est $q = p$ + premier. 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é ($\leq 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). +\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. + +% +\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}$. (Cf. théorème des nombres premiers.) + +\medbreak + +\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 +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$. +\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 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$.) + +\smallskip + +Exercice : Vérifier que $f = t^4 + t + 1$ est irréductible dans +$\mathbb{F}_2[t]$. (On a $t^4 \equiv t+1 \pmod{f}$ donc $t^8 \equiv +t^2+1$ donc $t^{16} \equiv t^4 + 1 \equiv t$ donc le premier critère +est vérifié. Pour le second, $t^4-t \equiv 1 \pmod{f}$ donc +l'algorithme d'Euclide termine immédiatement et $t^4-t$ et $f$ sont +bien irréductibles.) Vérifier que $g = t^4 + t^3 + 1$ est +irréductible dans $\mathbb{F}_2[t]$. (On a $t^4 \equiv t^3+1 +\pmod{g}$ donc $t^8 \equiv t^6+1 \equiv t^3+t^2+t$ donc $t^{16} \equiv +t^6+t^4+t^2 \equiv t$ donc le premier critère est vérifié. Pour le +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.) + +% +\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 il n'y a pas d'autre condition à vérifier.) + +% +\subsection{Éléments primitifs} + +\textbf{Théorème :} Le groupe multiplicatif d'un corps fini est +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)$. + +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(d)$. + +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$. + +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 + +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}. + % % % |