summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authordavid <david>2008-10-21 16:04:33 +0000
committerdavid <david>2008-10-21 16:04:33 +0000
commit21b86dcae598eecc05c63fd68f46ed344d461bdf (patch)
tree1dbd5d569bf52e0057a30ad39dacd42c5fe094c2
parenta7d606004af4ebe845afbf36a72735967e55a7dd (diff)
downloadinfmdi720-21b86dcae598eecc05c63fd68f46ed344d461bdf.zip
infmdi720-21b86dcae598eecc05c63fd68f46ed344d461bdf.tar.gz
infmdi720-21b86dcae598eecc05c63fd68f46ed344d461bdf.tar.bz2
Some additions and corrections.
-rw-r--r--rappels-maths.tex59
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$