diff options
Diffstat (limited to 'rappels-maths.tex')
| -rw-r--r-- | rappels-maths.tex | 59 |
1 files changed, 39 insertions, 20 deletions
diff --git a/rappels-maths.tex b/rappels-maths.tex index 1c48796..0377aef 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.9 2008-10-19 22:53:13 david Exp $= +CVS: \verb=$Id: rappels-maths.tex,v 1.10 2008-10-21 16:04:33 david Exp $= \end{center} \par} \pretolerance=10000 @@ -671,7 +671,7 @@ additive : multiples). L'ordre $m$ de ce sous-groupe est l'ordre de $g$. Ce sous-groupe est isomorphe à $\mathbb{Z}/m\mathbb{Z}$, avec $\bar 1 \mapsto g$. -Théorème de Lagrange : dans un groupe fini, l'ordre de tout +\textbf{Théorème de Lagrange :} Dans un groupe fini, l'ordre de tout sous-groupe divise l'ordre du groupe. En particulier, l'ordre d'un élément divise l'ordre du groupe : si $G$ est un groupe fini et $g \in G$ alors $g^{\#G} = 1$. @@ -723,8 +723,8 @@ 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$ ? -Cas particulier : petit théorème de Fermat : si $p$ est premier, alors -pour tout entier $a$ on a +Cas particulier : « petit théorème de Fermat » : si $p$ est premier, +alors pour tout entier $a$ on a \[ a^p \equiv a \pmod{p} \] @@ -757,7 +757,7 @@ $(\mathbb{Z}/m\mathbb{Z})^\times$). \item $(\mathbb{Z}/m\mathbb{Z})^\times$ (groupe \emph{multiplicatif}, d'élément neutre $1$) est d'ordre $\varphi(m)$ et est \emph{parfois} cyclique (auquel cas ses générateurs s'appellent éléments -\emph{primitifs}). +\emph{primitifs} et il y en a $\varphi(\varphi(m))$). \end{itemize} \medbreak @@ -778,7 +778,8 @@ cyclique (auquel cas ses générateurs s'appellent éléments \item Si $p=2$ et $r \geq 3$, alors $(\mathbb{Z}/2^r\mathbb{Z})^\times$ \emph{n'est pas} cyclique : il est produit d'un groupe cyclique d'ordre $2$ engendré par $-1$ et - d'un groupe cyclique d'ordre $2^{r-2}$ engendré par $5$. + d'un groupe cyclique d'ordre $2^{r-2}$ engendré par $5$ (l'ordre + maximal possible d'un élément est $2^{r-2}$). \end{itemize} % @@ -968,7 +969,7 @@ irréductibles. Lorsque ce sont les seuls, le corps $k$ est dit Le corps $\mathbb{C}$ est algébriquement clos. Le corps $\mathbb{R}$ ne l'est pas : les polynômes irréductibles sur $\mathbb{R}$ sont les -$t-a$ et les $t^2-2bt+c$ où $b^2-c<0$. Les corps finis (notamment +$t-a$ et les $t^2-bt+c$ où $b^2-4c<0$. Les corps finis (notamment $\mathbb{F}_p$ déjà vu) ne sont pas algébriquement clos (« encore moins » que $\mathbb{R}$). @@ -1027,16 +1028,24 @@ le \textbf{corps de rupture} de $P$ sur $k$. Caractéristique d'un corps : c'est l'ordre additif de $1$ si celui-ci est fini (sinon on convient que c'est $0$). -Tout corps fini contient un $\mathbb{Z}/p\mathbb{Z}$, qui en est un -sous-corps $\mathbb{F}_p$ : on dit que c'est le sous-corps premier. -Le corps est alors un espace vectoriel dessus : si $d$ est sa -dimension, son nombre d'éléments est $p^d$. +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$. + +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. % \subsection{Unicité} Dans un corps $F$ à $q$ éléments, on a $a^{q-1} = 1$ pour tout $a \in -K^\times$ (par Lagrange) donc on a $a^q = a$ pour tout $a \in K$. +K^\times$ (par Lagrange) donc on a $a^q = a$ pour tout $a \in K$ +(« petit théorème de Fermat » généralisé). 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 = @@ -1062,7 +1071,9 @@ nuls). On le note aussi $\Frob_p$ pour éviter l'ambiguïté. 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$ est l'identité. +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$.) % \subsection{Existence et inclusions des corps finis} @@ -1192,10 +1203,11 @@ les deux conditions suivantes sont vérifiées : $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$.) +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$.) \smallskip @@ -1212,6 +1224,12 @@ 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 + +\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$} @@ -1240,7 +1258,7 @@ 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.) +t$, et par ailleurs $f \equiv 1 \pmod{t^2-t}$.) % \subsection{Éléments primitifs} @@ -1253,7 +1271,7 @@ Autrement dit, si $\mathbb{F}$ est un corps fini, il existe des 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)$. +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}, @@ -1270,7 +1288,8 @@ 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$. +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$ |