From 68c428a129df822b8e33dd93fcbf5142c5c37142 Mon Sep 17 00:00:00 2001
From: david <david>
Date: Sun, 19 Oct 2008 22:44:33 +0000
Subject: End of course.

---
 rappels-maths.tex | 212 +++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file 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 
 $\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}.
+
 %
 %
 %
-- 
cgit v1.2.3