\documentclass[a4paper,10pt]{lecon}
\usepackage[latin1]{inputenc}
\usepackage{lecon,amssymb,french,multicol,landscape,theorem}

%xdvi -paper 29.7x21cm corpsfinis.dvi

\parindent 0mm
\parskip 1mm

\newcommand{\fff}[1]{\mathbb{F}_{#1}}
\newcommand{\fp}{\fff{p}}
\newcommand{\fq}{\fff{q}}
\newcommand{\fqn}{\fff{q^n}}
\newcommand{\zzz}{\mathbb{Z}}

\setlength{\theorempreskipamount}{3mm}
\setlength{\theorempostskipamount}{1mm}
\newtheorem{theoreme}{Théorème}
\newtheorem{corollaire}{Corollaire}
\newtheorem{lemme}{Lemme}

\begin{document}
\binoppenalty=10000
\relpenalty=10000
\begin{titlepage}
\begin{multicols}{3}[\begin{center}
\textbf{\Large Algèbre 17 \quad -- \quad Corps finis. Applications.}
\end{center}][0cm]

\section{Structure des corps finis}

\subsection{Caractéristique, cardinal}
% Serre p 9, Lidl p 45

$K$: corps fini. Image de $\zzz$ dans $K$: isomorphe à un $\zzz/p\zzz$
($p$ premier: \emph{caractéristique}). Corps des fractions isomorphe à
$\fp = \zzz/p\zzz$, \emph{sous-corps premier} de $K$.

$\sigma:\ x \mapsto x^p$ est un automorphisme de $K$.

$K$: extension de $\fp$ de degré $n$. On a $|K| = p^n$.

\subsection{Existence et unicité des corps finis}
% Lidl p 45

\begin{theoreme}[existence]
Pour tout $p$ premier et tout $n \geqslant 1$, il existe un corps fini à
$q = p^n$ éléments: le corps de décomposition de $x^q-x$ sur $\fp$, noté
$\fq$.
\end{theoreme}

% Preuve:
%  _ simplicité des racines (dérivée -1). --> ensemble S des q racines.
%  _ S sous-corps de F_q. --> F_q = S.

\begin{theoreme}[unicité]
Tout corps à $q$ éléments est isomorphe à $\fq$.
\end{theoreme}

% Preuve: dans un corps à q éléments, tout x vérifie x^q = x (groupe mult.).

\subsection{Conditions suffisantes (cas fini)}
% Lidl

\begin{theoreme}
% Lidl p 12
Tout anneau intègre fini est un corps.
\end{theoreme}

\begin{theoreme}[Wedderburn]
% Lidl p 66
Tout anneau à division fini est un corps.
\end{theoreme}

\subsection{Sous-corps, clôture algébrique}

\begin{theoreme}
% Lidl p 46
Soit $\fq$ un corps fini à $q = p^n$ éléments. Alors tout sous-corps de
$\fq$ est d'ordre $p^m$ où $m\,|\,n$. Réciproquement, si $m\,|\,n$,
$\fq$ a un unique sous-corps $\fff{r}$ d'ordre $r = p^m$.
\end{theoreme}

$\fff{r} = \left\{ x \in \fq:\ x^r - x = 0 \right\}$

On peut alors définir:
$\displaystyle \widehat{\fp} = \bigcup_{n \geqslant 1} \fff{p^{n!}}$.
C'est la clôture algébrique de tout $\fq$ avec $q = p^n$.

\section{Groupe multiplicatif de $\fq$}
% Serre

\begin{theoreme}
% Serre p 11
Le groupe multiplicatif $\fq^*$ du corps fini $\fq$ est cyclique
d'ordre $q-1$.
\end{theoreme}

\underline{Application:} logarithme discret, cryptographie.
% Menezes, Lidl ex. 2.8 p 71

\vskip 2mm

\begin{theoreme}
% Serre p 14
Si $p = 2$, tout élément de $\fq$ est un carré. Si $p \ne 2$, les carrés
de $\fq^*$ forment un sous-groupe d'indice~2 de $\fq^*$, noyau de
l'homomorphisme $\eta:\ x \mapsto x^{(q-1)/2}$, à valeurs dans $\{\pm1\}$.
\end{theoreme}

$\eta$ est appelé \emph{caractère quadratique} de $\fq$.

\underline{Conséquence:} tout élément de $\fq$ est somme de 2~carrés.

\section{Polynômes sur les corps finis}

$\fq$: corps fini; $n$: entier $\geqslant 1$.

\subsection{Existence de polynômes irréductibles}
% Lidl p 48

Soit $\alpha$ générateur de $\fqn^*$. Alors $\fqn = \fq(\alpha)$. Le
polynôme minimal de $\alpha$ sur $\fq$ est un polynôme irréductible
de $\fq[X]$ de degré~$n$.

\subsection{Corps de décomposition, corps de rupture}
% Lidl p 49

\begin{theoreme}
% Lidl th. 2.14
Soit $f$ un polynôme irréductible de $\fq[X]$ de degré~$n$. Alors $f$ a une
racine $\alpha \in \fqn$. De plus, $f$ a $n$ racines simples dans $\fqn$:
$\alpha$, $\alpha^q$, $\alpha^{q^2}$, \ldots, $\alpha^{q^{n-1}}$.
\end{theoreme}

\underline{Conséquences:}

Le corps de rupture et le corps de décomposition d'un polynôme irréductible
sont les mêmes. Deux polynômes irréductibles de même degré ont le même corps
de décomposition.

Automorphismes de $\fqn$ laissant $\fq$ invariant: groupe engendré par
$x \mapsto x^q$ (cyclique d'ordre~$n$).

% Lidl ex. 2.22 p 71
Si $p$ est premier, $n$ divise $\varphi(p^n-1)$.

\subsection{Théorème de Chevalley}
% Serre p 13

\begin{theoreme}
$K$: corps fini de caractéristique $p$. Soient $f_i \in K[X_1,\ldots,X_n]$
des polynômes à $n$ variables tels que $\sum \deg(f_i) < n$. Alors le nombre
de zéros communs dans $K^n$ est divisible par $p$.
\end{theoreme}

\begin{corollaire}
Si les $f_i$ sont sans terme constant, alors ils ont un zéro commun
non trivial.
\end{corollaire}

\section{Applications}

\subsection{Groupes simples finis}

$PSL(n,K)$ est simple sauf pour $n = 2$ et $K = \fff{2}$ ou $\fff{3}$.
De plus, si $K$ est fini, $PSL(n,K)$ est un groupe simple fini.

\subsection{Théorème de Sylow}

\begin{lemme}
L'ensemble des matrices triangulaires supérieures dont les termes diagonaux
sont égaux à $1$ est un $p$-sous-groupe de Sylow de $GL(\fp^n)$.
\end{lemme}

\subsection{Construction de matrices de Hadamard}
% Lidl p 274
% + produit de Kronecker

\emph{Matrices de Hadamard} $H_n$: matrices de $\mathcal{M}_{n,n}(\{\pm1\})$
telles que $H_n H_n^{\mathrm{T}} = n I_n$.

% Condition nécessaire d'existence: n = 1 ou 2 ou un multiple de 4.
% Cette condition est-elle suffisante? Problème ouvert...

\begin{theoreme}
Soient $a_1$, \ldots, $a_q$ les éléments de $\fq$ avec
$q \equiv 3\ \mathrm{mod}\ 4$, $\eta$ le caractère quadratique de $\fq$, et
$H = (b_{ij})_{0 \leqslant i,j \leqslant q}$ avec $b_{ij} = +1$ pour $i = 0$
ou $j = 0$, $b_{ij} = -1$ pour $i = j \geqslant 1$, $b_{ij} = \eta(a_j-a_i)$
pour $i,j \geqslant 1$ et $i \ne j$. Alors $H$ est une matrice de Hadamard
d'ordre $q+1$.
\end{theoreme}

% cf Raghavarao: Constructions and Combinatorial Problems
% in Design of Experiments (Dover Publication)

\subsection{Codes linéaires}
% Lidl p 305

Alphabet fini: $\fq$ (en général $q = 2$). Codage: $\fq^k \rightarrow \fq^n$.
Soient $A \in \mathcal{M}_{n-k,k}(\fq)$ et $H = (A, I_{n-k})$. Message
$a_1 a_2 \cdots a_k \mapsto c = a_1 \cdots a_k c_{k+1} \cdots c_n$ avec
$H c^{\mathrm{T}} = 0$; $c_i$: symboles de contrôle.
$C = \mathrm{Im}(\fq^k)$.

% Ex: parity-check q = 2, H = (1 1 ... 1); répétition H = (-1, I_{n-1}).

$d_C = \min \{ w(c):\ c \in C\backslash\{0\} \}$ où $w(c)$ est le nombre de
composantes non nulles; $d_C \geqslant s+1$ ssi $s$ colonnes de $H$ sont
toujours linéairement indépendantes. $C$ peut corriger jusqu'à $t$ erreurs
si $d_C \geqslant 2t+1$.

Code cyclique: linéaire et stable par permutations circulaires.
$C$ est cyclique ssi $C$ est un idéal de $\fq[X]/(x^n-1)$.

%\subsection{Cryptographie}
% Lidl p 344, Menezes

\section*{Références}

Serre: Cours d'arithmétique. \\
Lidl: Introduction to finite fields and their applications. \\
Menezes: Application of finite fields. \\
Perrin.

\end{multicols}
\end{titlepage}
\end{document}