summaryrefslogtreecommitdiffstats
path: root/rappels-maths.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2011-10-24 15:44:19 +0200
committerDavid A. Madore <david+git@madore.org>2011-10-24 15:44:19 +0200
commita882a3e0878b28289dd4e5cc4702a7463bd3627c (patch)
treee52232b8c19391e7fde2310a3425ade3a2b35d33 /rappels-maths.tex
parent2c0256cb192f4579ba7ae9c4d57886a5af93c043 (diff)
downloadinfmdi720-a882a3e0878b28289dd4e5cc4702a7463bd3627c.tar.gz
infmdi720-a882a3e0878b28289dd4e5cc4702a7463bd3627c.tar.bz2
infmdi720-a882a3e0878b28289dd4e5cc4702a7463bd3627c.zip
Slight update/corrections.
Diffstat (limited to 'rappels-maths.tex')
-rw-r--r--rappels-maths.tex70
1 files changed, 55 insertions, 15 deletions
diff --git a/rappels-maths.tex b/rappels-maths.tex
index 8df213a..57a421b 100644
--- a/rappels-maths.tex
+++ b/rappels-maths.tex
@@ -850,7 +850,8 @@ multiplicative ; en notation additive, cela s'écrirait : $mg = 0$,
i.e., un multiple de $g$) ; c'est aussi le nombre de puissances
distinctes (en notation additive : de multiples distincts) de
l'élément $g$. Lorsque $g$ est d'ordre $m$, on a $g^m = 1$ mais aussi
-$g^{m'} = 1$ si et seulement si $m'$ est multiple de $m$.
+$g^{m'} = 1$ si et seulement si $m'$ est multiple de $m$, et donc $g^i
+= g^j$ si $i \equiv j \pmod{m}$.
Un \textbf{sous-groupe} $H$ d'un groupe $G$ est un sous-ensemble de
$G$ qui est lui-même un groupe pour la même opération et le même
@@ -1318,7 +1319,8 @@ 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$.
+corps premier $\mathbb{F}_p$, ou simplement « degré absolu »
+de $\mathbb{F}$.
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 à
@@ -1395,9 +1397,9 @@ 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$.
+absolu de $x$ (ou : 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
@@ -1483,8 +1485,8 @@ 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.)
+\pmod{t^3+t+1}$ puis $t^3+t+1 \equiv t+1 \pmod{t^2}$ et enfin $t^2
+\equiv 1 \pmod{t+1}$, donc $t^4-t$ et $g$ sont bien irréductibles.)
\medbreak
@@ -1501,16 +1503,41 @@ irréductibilité, et de recommencer jusqu'à obtenir un irréductible.
\medbreak
+\textbf{Polynôme minimal d'un élément :} Pour tout $x \in
+\mathbb{F}_q$, où $q = p^d$, il existe un unique polynôme unitaire
+irréductible $f \in \mathbb{F}_p[t]$ (noter que $x$ est dans
+$\mathbb{F}_q$ mais que $f$ est à coefficients dans $\mathbb{F}_p$)
+tel que $f(x) = 0$. Ce polynôme s'appelle le \emph{polynôme minimal}
+de $x$. Son degré $\delta$ est égal au degré absolu de $x$, dont on
+rappelle qu'il est défini comme le nombre de conjugués $\Frob^i(x)$
+de $x$ ; et les racines de $f$ dans $\mathbb{F}_q$ sont exactement les
+conjugués $\Frob^i(x)$ en question : on a $f = \prod_{i=0}^{\delta-1}
+(t-\Frob^i(x))$ (on rappelle que le degré absolu $\delta$ de $x$
+divise le degré absolu $d$ de $\mathbb{F}_q$).
+
+Si $\mathbb{F}_q$ est vu comme $\mathbb{F}_p[t]/(f)$ avec $f$ un
+polynôme unitaire irréductible de degré $d$ sur $\mathbb{F}_p$, alors
+le polynôme minimal de $\bar t$ est précisément $f$. Réciproquement,
+si $x \in \mathbb{F}_q$ a pour degré $d$ (le degré absolu
+de $\mathbb{F}_q$, c'est-à-dire le $d$ tel que $q=p^d$) et polynôme
+minimal $f$ (de degré $d$, donc), alors il existe un unique
+isomorphisme de corps $\psi\colon \mathbb{F}_p[t]/(f) \to
+\mathbb{F}_q$ tel que $\psi(\bar t) = x$.
+
+\smallbreak
+
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é
+\prod_{a \in \mathbb{F}_q} (t-a)$. Il est utile de savoir ce qu'il en
+est sur $\mathbb{F}_p$ :
+
+Le polynôme $t^q - t$ (où $q = p^d$) se factorise dans
+$\mathbb{F}_p[t]$ comme le produit de \emph{tous} les polynômes
+unitaires irréductibles dont le degré $\delta$ divise $d$. (Chacun de
+ces facteurs $f$ est égal, dans $\mathbb{F}_q[t]$, au produit des
+$(t-a)$ pour les $\delta$ conjugués $a$ d'un élément de
+degré $\delta$.) 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
@@ -1537,6 +1564,19 @@ 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).
+Si $g \in \mathbb{F}_q$ est primitif, alors tout élément de
+$\mathbb{F}_q$ est soit $0$ soit de la forme $g^i$ pour un entier $i$
+(cet entier est défini de façon unique modulo $q-1$ ; l'application
+$\psi \colon \mathbb{Z}/(q-1)\mathbb{Z} \to \mathbb{F}_q^\times$
+donnée par $\bar\imath \mapsto g^i$ définit un isomorphisme de
+groupes). La représentation des éléments de $\mathbb{F}_q^\times$
+sous la forme $g^i$ permet facilement de calculer des produits, mais
+ne permet pas de calculer des sommes.
+
+Le problème consistant à retrouver $i$ connaissant (l'élément
+primitif $g$ et) $g^i$ s'appelle le \emph{problème du logarithme
+ discret}, et il est algorithmiquement difficile.
+
%
%
%