%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt]{article}
\usepackage[francais]{babel}
\usepackage[latin1]{inputenc}
\usepackage{times}
% A tribute to the worthy AMS:
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
%
\usepackage{mathrsfs}
\usepackage{wasysym}
\usepackage{url}
%
\theoremstyle{definition}
\newtheorem{comcnt}{Tout}[subsection]
\newcommand\thingy{%
\refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} }
\newtheorem{defn}[comcnt]{Définition}
\newtheorem{prop}[comcnt]{Proposition}
\newtheorem{lem}[comcnt]{Lemme}
\newtheorem{thm}[comcnt]{Théorème}
\newtheorem{cor}[comcnt]{Corollaire}
\newtheorem{rmk}[comcnt]{Remarque}
\newtheorem{exmps}[comcnt]{Exemples}
\newcommand{\limp}{\mathrel{\Rightarrow}}
\newcommand{\liff}{\mathrel{\Longleftrightarrow}}
\newcommand{\pgcd}{\operatorname{pgcd}}
\newcommand{\ppcm}{\operatorname{ppcm}}
\newcommand{\signe}{\operatorname{signe}}
\newcommand{\tee}{\mathbin{\top}}
\renewcommand{\qedsymbol}{\smiley}
%
%
%
\begin{document}
\title{Rappels maths pour crypto}
\author{David A. Madore}
\maketitle
{\footnotesize
\begin{center}
CVS: \verb=$Id: rappels-maths.tex,v 1.5 2008-10-14 11:04:11 david Exp $=
\end{center}
\par}
\pretolerance=10000
\tolerance=8000
%
%
%
\section{Entiers}

\subsection{L'anneau des entiers}

$\mathbb{Z}=\{\ldots,-3,-2,-1,0,1,2,3,\ldots\}$ ensemble des
entiers relatifs.  Sous-ensemble $\mathbb{N}$.

Opérations : $+$, $\times$.

Rappeler : $(\mathbb{Z},0,+)$ est un groupe abélien,
$(\mathbb{Z},0,+,1,\times)$ est un anneau commutatif.

Mieux : anneau intègre.

Éléments inversibles : $1$ et $-1$.

Relation d'ordre...

%
\subsection{Écriture $b$-adique}

Si $b\geq 2$ est un entier naturel, tout entier naturel $A$ s'écrit de
façon unique $A = \sum_{i=0}^{+\infty} a_i b^i$ avec $0\leq a_i<b$
entiers naturels « presque tous nuls » (expliquer).

Écriture usuelle : $b=10$.  Informatique : $b=2$.  Un nombre « de $n$
bits » signifie : inférieur à $2^n$.

Multiplier par $b$ revient à décaler tous les chiffres d'un cran vers
la gauche.

On passe pour l'instant sur l'écriture des nombres négatifs.

%
\subsection{Remarques sur la complexité des opérations}

Addition de nombres de $n$ bits : algorithme naïf en $O(n)$.

Multiplication : plus compliqué.

Algorithme naïf en $O(n^2)$.

\emph{Multiplication de Karatsuba} : utilise récursivement
l'identité ${(a_1 w + a_0)} \penalty0 {(b_1 w + b_0)} = a_1 b_1 w^2 +
[(a_1+a_0)(b_1+b_0)-a_1 b_1-a_0 b_0] w + a_0 b_0$ pour une complexité
en $O(n^{\frac{\log 3}{\log 2}})$ (soit $O(n^{1.58\ldots})$).  Facile
à implémenter.

\emph{Multiplication de Strassen} : par transformée de Fourier
rapide, complexité en $O(n\,\log^2 n)$, difficile à implémenter.
Amélioration de Schönhage : $O(n\,\log n\,\log\log n)$ ---
complètement théorique.

%
\subsection{Divisiblité (exacte)}

Définition.  Terminologie « diviseur de », « multiple de ».  Relation
réflexive, transitive.  Pas tout à fait antisymétrique (mais vrai dans
les entiers naturels).

Note : Les entiers $1$ et $-1$ divisent tous les entiers.  L'entier
$0$ est divisible par tous les entiers.

%
\subsection{Nombres premiers}

Un \textbf{nombre premier} $p$ est un entier (par convention :
positif) divisible seulement par $1$, $-1$, lui-même et son opposé ;
mais par convention, $1$ et $-1$ (et $0$...) ne sont pas premiers.

Les premiers nombres premiers sont donc : $2$, $3$, $5$, $7$, $11$,
$13$, $17$, $19$, $23$, $29$, $31$, $37$, $41$, $43$, $47$, $53$,
$59$, $61$, $67$, $71$, $73$, $79$, $83$, $89$, $97$...

\medbreak

Sur leur répartition :

Il y en a une infinité (Euclide).

Pour tout $x>1$, il y a toujours un nombre premier $p$ tel que
$x\leq p < 2x$ (\v Ceby\v sëv : « postulat de Bertrand »).

Le nombre $\pi(x)$ de nombres premiers $\leq x$ est équivalent à
$\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$.

Beaucoup de questions ouvertes.  Par exemple : Conjecture des nombres
premiers jumeaux : existe-t-il une infinité de nombres premiers $p$
tels que $p+2$ soit aussi premier (tels que $3$, $5$, $11$, $17$,
$29$, $41$, $59$, $71$...) ?

\smallbreak

\textbf{Lemme de Gauß :} pour $p$ premier, si $p$ divise $ab$ alors
$p$ divise $a$ ou $p$ divise $b$.

%
\subsection{Décomposition en facteurs premiers}

Pour tout entier $n$ \emph{non nul}, il existe une écriture
\emph{unique} (à l'ordre près) de $n$ comme produit d'une \emph{unité}
($1$ ou $-1$) et de nombres premiers : en regroupant les facteurs
premiers $p$,
\[
n = u\, 2^{v_2(n)} \, 3^{v_3(n)} \cdots p^{v_p(n)}\cdots
\]

Ici, $v_p(n)$ (un entier naturel) est l'exposant de la plus grande
puissance de $p$ qui divise $n$ : on l'appelle \emph{valuation
$p$-adique} de $n$.  Presque tous ces nombres sont nuls, ce qui permet
de donner un sens au produit infini.  Dire que $b|a$ signifie $v_p(b)
\leq v_p(a)$ pour tout $p$.

Quant à $u$, c'est simplement le signe de $n$.

%
\subsection{Remarques sur la complexité}

Toujours pour des nombres de $n$ bits.

\textbf{Tests de primalité :} \emph{polynomiaux}.  Un test polynomial
\emph{déterministe} est connu depuis seulement récemment
(Agrawal-Kayal-Saxena), démontrablement en $O(n^{12})$, sans doute
meilleur ($O(n^3)$ ?).  En pratique, des tests probabilistes sont
suffisants et plus efficaces (p.e., Miller-Rabin « pratiquement » en
$O(n^2)$) éventuellement complétés par des certificats de primalité
(p.e., test d'Atkin).

\textbf{Algorithmes de factorisation :} \emph{lents}.  Font appel à
des résultats difficiles de théorie algébrique et analytique des
nombres.  La meilleure méthode connue (« méthode du crible général de
corps de nombres ») a une complexité « attendue » (et heuristique) en
$O(e^{n^{1/3}\,(\log n)^{2/3}\,(\textrm{cte}+o(1))})$ (avec
$\textrm{cte} \approx 2$).

On ne pourra donc pas envisager d'utiliser la décomposition en
facteurs premiers pour calculer les pgcd.

%
\subsection{Valuation $p$-adique}

Si $n$ est un entier et $p$ un nombre premier, $v_p(n)$ est l'exposant
de la plus grande puissance de $p$ qui divise $n$.  Si $a/b$ est un
rationnel, on pose $v_p(a/b) = v_p(a)-v_p(b)$ (ne dépend pas de la
représentation $a/b$ choisie).  Par convention, $v_p(0) = +\infty$.

Quelle est la valuation $2$-adique de $192$ ?  $3$-adique ?
$5$-adique ?  Quelles sont les valuations $p$-adiques de
$-\frac{24}{11}$, pour tous les $p$ possibles ?

Propriétés de $v_p$ : produit (cf. lemme de Gauß), inégalité sur la
somme (et cas d'égalité)...  Dire que $x \in \mathbb{Q}$ est entier
signifie exactement $v_p(x) \geq 0$ pour tout $p$.

%
\subsection{Division euclidienne}

Si $a$ est un entier relatif et $b$ un entier naturel \emph{non nul},
il existe un unique couple $(q,r)$ tel que :
\begin{itemize}
\item $q$ est un entier relatif,
\item $r$ est un entier naturel tel que $0\leq r<b$, et
\item $a = bq + r$.
\end{itemize}
On dit que $q$ est le \emph{quotient} et $r$ le \emph{reste} de la
\textbf{division euclidienne} de $a$ par $b$.  (On appelle aussi $a$
le \emph{dividende} et $b$ le \emph{diviseur}.)

Si $b\geq 2$, dans l'écriture $b$-adique de $a$, le dernier chiffre
($a_0$ avec les notations précédentes) est égal au reste $r$ de la
division euclidienne de $a$ par $b$.

Dire que $r=0$ signifie exactement que $b$ divise $a$ (la division
euclidienne est alors \emph{exacte}).

\medbreak

\textbf{Algorithme naïf :} (celui de l'école primaire) en $O(n^2)$.

\textbf{Algorithme sophistiqué :} en $O(n\,\log n\,\log\log n)$ avec
Schönhage-Strassen + méthode de Newton (+ subtilités).

Méthode de Newton : on inverse $b$ (en précision fixe) en itérant $x
\leftarrow 2x - bx^2$.

Souvent implémentée \textbf{en matériel} pour certaines tailles
d'entiers (p. ex., division entière de 128 bits par 64 bits).

%
\subsection{PGCD}

Si $m_1,\ldots,m_\ell$ sont des entiers, on dit qu'un entier $c$ est
un \textbf{plus grand commun diviseur} (en abrégé : \emph{pgcd}) des
$m_i$ lorsque :
\begin{itemize}
\item $c$ divise chaque $m_i$ (i.e, $c$ est un diviseur commun
  des $m_i$), et
\item tout entier $d$ qui divise chaque $m_i$ (i.e., tout diviseur
  commun des $m_i$) divise aussi $c$.
\end{itemize}
En principe, le pgcd des $m_i$ est défini au signe près (si $c$ est un
pgcd des $m_i$ alors $-c$ l'est aussi) : en imposant qu'il soit
positif il devient unique et on parle alors \emph{du} pgcd des $m_i$.

Exemple : le pgcd de $6$ et $10$ est $2$ ; le pgcd de
  $6$, $10$ et $15$ est $1$.

\medbreak

Le pgcd \emph{existe} toujours : on peut le trouver à partir de la
décomposition en facteurs premiers par
\[
v_p(\pgcd(m_1,\ldots,m_\ell)) = \min(v_p(m_1),\ldots,v_p(m_\ell))
\]
(pour tout nombre premier $p$).  Mais ce n'est pas une méthode
efficace de calcul !

\textbf{Notation :} Parfois $m_1\wedge \cdots \wedge m_\ell$, mais
cette notation peut être utilisée pour d'autres sortes de bornes inf.
Certains textes anglais utilisent $(m,m')$ pour le pgcd de deux
entiers.  La notation $\pgcd(\cdots)$ est évidemment la plus claire.

\medbreak

\textbf{Quelques propriétés :}
\begin{itemize}
\item le pgcd d'un seul entier $m$ est lui-même (et le pgcd de zéro
entiers est $0$),
\item le pgcd est associatif (par exemple\\
  $\pgcd(m_1,m_2,m_3) = \pgcd(\pgcd(m_1,m_2),m_3)$),
\item le produit est distributif sur le pgcd\\
  ($\pgcd(cm_1,\ldots,cm_\ell) = |c|\,\pgcd(m_1,\ldots,m_\ell)$),
\item on peut toujours effacer des $0$ d'un pgcd,
\item dès qu'un des entiers est $1$ ou $-1$, le pgcd est $1$,
\item le pgcd d'une famille infinie se définit sans difficulté.
\end{itemize}

%
\subsection{Entiers premiers entre eux}

Lorsque $\pgcd(m_1,\ldots,m_\ell)=1$, on dit que les $m_i$ sont
\textbf{premiers entre eux} \emph{dans leur ensemble}.

Lorsque $\pgcd(m_i,m_j)=1$ pour tous $i\neq j$, on dit que les $m_i$
sont premiers entre eux \emph{deux à deux}.

\textbf{Lemme de Gauß amélioré :} Si $m$ et $n$ sont premiers entre
eux, être multiple de $m$ et de $n$ équivaut à être multiple de $mn$.

\textbf{Dirichlet :} La probabilité pour que deux entiers « tirés au
  hasard » soient premiers entre eux est $\frac{6}{\pi^2}$.

%
\subsection{PPCM}

Définition analogue au PGCD.  Exemple : le ppcm de $6$ et $10$
est $30$ ; le ppcm de $6$, $10$ et $15$ est aussi $30$.  Lien avec la
DFP (pour un nombre fini d'entiers).  Le ppcm d'une famille infinie
d'entiers est défini, mais parfois surprenant (quel est le PPCM de
tous les nombres premiers ?).

%
\subsection{Relation de Bézout}

Si $a$ et $b$ sont premiers entre eux (c'est-à-dire $\pgcd(a,b) = 1$)
il existe des entiers $u$ et $v$ tels que $au + bv = 1$ (on verra
pourquoi plus loin) : on appelle cette égalité une \textbf{relation de
  Bézout}\footnote{Étienne Bézout (1730--1783), avec un accent aigu.}
entre $a$ et $b$.

Réciproquement, l'existence d'une relation de Bézout entre $a$ et $b$
implique que $a$ et $b$ sont premiers entre eux (et alors les
coefficients, $u$ et $v$, sont aussi premiers entre eux).  En effet,
tout diviseur commun de $a$ et $b$ doit diviser $au+bv$.

Exemple : $42\times 38 - 55 \times 29 = 1$ constitue une relation de
Bézout entre $42$ et $55$.  On verra plus loin comment obtenir une
relation de Bézout.

Naturellement, ajouter $b$ à $u$ et $-a$ à $v$ donne une nouvelle
relation de Bézout entre $a$ et $b$.  Donc il n'y a pas unicité.

Si $au + bv = \pm 1$ on dit parfois que les rationnels $a/b$ et $-v/u$
(écrits sous forme irréductible) sont \emph{adjacents}.

\medbreak

Plus généralement, si $\pgcd(a,b) = d$, on peut trouver $u$ et $v$
tels que $au+bv = d$.

%
\subsection{Algorithme d'Euclide}

Soit à calculer le pgcd de deux entiers $a$ et $b$.
\textbf{L'algorithme d'Euclide} pour ce faire est le suivant :
\begin{itemize}
\item Initialiser : $(m,n) \leftarrow (|a|,|b|)$.
\item Tant que $n\neq 0$, répéter :
\begin{itemize}
\item Faire $(m,n) \leftarrow (n,r)$ où $r$ est le reste de la division
  euclidienne $m=nq+r$ de $m$ par $n$.
\end{itemize}
\item Renvoyer $m$ (le pgcd recherché).
\end{itemize}

\smallskip
\textbf{Invariant :} $\pgcd(m,n) = \pgcd(a,b)$ (constant)

\medbreak
Exemple : soit à calculer le pgcd de $a=98$ et
$b=77$ :
\begin{itemize}
\item $(m,n)=(98,77)$ ; division euclidienne $98 = 77\times 1 + 21$ ;
\item $(m,n)=(77,21)$ ; division euclidienne $77 = 21\times 3 + 14$ ;
\item $(m,n)=(21,14)$ ; division euclidienne $21 = 14\times 1 + 7$ ;
\item $(m,n)=(14,7)$ ; division euclidienne $14 = 7\times 2 + 0$ ;
\item $(m,n)=(7,0)$ ; on renvoie $7$.
\end{itemize}

\medbreak
\textbf{Algorithme d'Euclide « étendu »} : L'idée est
de « remonter » les coefficients dans l'algorithme d'Euclide : la
dernière division $m=nq+1$ donne une relation $1 = m-nq$ puis on
remplace $n$ (qui est lui-même un reste de division euclidienne) et
ainsi de suite jusqu'à trouver une relation entre les entiers $a$ et
$b$ de départ.

En mémoire constante, cela donne :

Soit à calculer une relation de Bézout entre deux entiers $a$ et $b$
(premiers entre eux) :
\begin{itemize}
\item $(m,n,u,v,u',v') \leftarrow (|a|,|b|,\signe(a),0,0,\signe(b))$.
\item Tant que $n\neq 0$, répéter :
\begin{itemize}
\item Division euclidienne de $m$ par $n$ : soit $m =
nq+r$.
\item Remplacer $(m,n,u,v,u',v') \leftarrow (n,r,u',v',u-qu',v-qv')$.
\end{itemize}
\item Vérifier $m=1$ (le pgcd est bien $1$).
\item Les coefficients recherchés sont $u$ et $v$ (on a $au+bv = 1$).
\end{itemize}

\textbf{Invariants :} $au+bv=m$ et $au'+bv'=n$.

%
\subsection{Exercices}

\thingy Montrer que si $a, b \in \mathbb{Z}$ vérifient $a^2 = 2b^2$
alors $a=b=0$.  Comment interpréter ce résultat sur le
nombre $\sqrt{2}$ ?

\thingy Montrer que, si $n \geq 2$ alors $\sum_{i=1}^n \frac{1}{i}$
n'est pas un entier.  (Indication : montrer que sa valuation
$2$-adique est strictement négative ; ou bien : montrer que sa
valuation $p$-adique vaut $-1$ avec $p$ le plus grand nombre premier
inférieur à $n$, en utilisant le postulat de Bertrand.)

\thingy Montrer que, pour tout $p$ premier et $n$ entier naturel,
$v_p(n!) = \sum_{i=i}^{+\infty} \lfloor\frac{n}{p^i}\rfloor$ (où
$\lfloor\cdot\rfloor$ désigne la partie entière.

\thingy Montrer que pour $a, b$ entiers, on a $\pgcd(a,b)\, \ppcm(a,b)
= ab$.

\thingy On définit par récurrence les nombres de Fibonacci : $F_0 =
0$, $F_1 = 1$ et $F_{n+1} = F_n + F_{n-1}$.  Écrire une relation de
Bézout entre $F_8$ et $F_9$.  Montrer que $F_n$ et $F_{n+1}$ sont
premiers entre eux pour tout $n$.

%
\section{Congruences et entiers modulaires}

\subsection{Congruence}

Soit $m$ un entier fixé pour le moment :

Si $x$ et $x'$ sont entiers, on dit que $x$ et $x'$ sont
\textbf{congrus} modulo $m$, noté $x \equiv x' \pmod{m}$, lorsque
$x-x'$ est multiple de $m$.  Relation réflexive, symétrique,
transitive.

Compatibilité avec les opérations : (à $m$ fixé,) si $x\equiv x'$ et
$y \equiv y'$ alors $x+y \equiv x'+y'$ et $xy \equiv x'y'$.  À $m$
variable : si $m|m'$ alors $x \equiv x' \pmod{m'}$ implique $x\equiv
x' \pmod{m}$ (la congruence modulo $m'$ est \emph{plus fine} que
modulo $m$).

Représentants : si $m \geq 1$ alors chaque entier est congru
modulo $m$ à l'un des nombres $0,1,2,\ldots,(m-1)$ (le reste de sa
division euclidienne par $m$ !).

Exemple de $\mathbb{Z}/2\mathbb{Z}$ avec pair=$\bar 0$ et impair=$\bar
1$.

On veut définir $\mathbb{Z}/m\mathbb{Z} = \{\bar 0, \bar 1, \bar 2,
\ldots, \overline{m-1}\}$ de façon analogue : pour ajouter $\bar x$ et
$\bar y$, on consière $\bar x + \bar y = \overline{x+y}$ et $\bar x\,
\bar y = \overline{xy}$.  Reste à savoir ce que la barre veut dire !

%
\subsection{Généralité sur les quotients}

Généralité : soit $E$ un ensemble et $\sim$ une relation d'équivalence
(i.e., réflexive, symétrique, transitive) sur $E$, on appelle
$E/{\sim}$ l'ensemble des classes d'équivalence de $E$ modulo $\sim$
(la classe d'équivalence d'un élément $x\in E$ est l'ensemble des
éléments $x'\in E$ tels que $x\sim x'$).  On note $\pi \colon E \to
(E/{\sim})$ la fonction qui envoie $x\in E$ sur sa classe
d'équivalence $\pi(x) = \bar x$.  Ainsi : $\pi(x) = \pi(x')$ ssi $x
\sim x'$.  (Moralement : on a transformé la relation d'équivalence
$\sim$ en une vraie égalité.)

Si on a sur $E$ une opération binaire, disons, $\tee$, telle que $x
\sim x'$ et $y \sim y'$ impliquent $(x\tee x') \sim (y\tee y')$ (on
dit que $\sim$ est \emph{compatible} avec l'opération $\tee$), alors
on peut définir une opération binaire $\mathbin{\bar\top}$ sur
$E/{\sim}$ par $\pi(x) \mathbin{\bar\top} \pi(x') = \pi(x\tee x')$.

L'application $\pi\colon E \to (E/{\sim})$ préserve alors l'opération
$\tee$ et on dit qu'il s'agit d'un \emph{morphisme} (d'ensembles munis
d'une opération binaire $\tee$).

%
\subsection{Calculs dans $\mathbb{Z}/m\mathbb{Z}$}

Vision concrète de $\mathbb{Z}/m\mathbb{Z}$ pour $m\geq 1$ : on
travaille avec les nombres $0,\ldots,m-1$ (qui sont des
\emph{représentants} arbitraires des $m$ classes de congruences
modulo $m$).  Les opérations sont faites dans les entiers mais ensuite
on se ramène à une classe représentée par un entier entre $0$ et $m-1$
en effectuant une division euclidienne par $m$.

Exemple : si $m=10$, on a $\bar 8 + \bar 5 = \bar 3$ et $\bar 8 \times
\bar 5 = \bar 0$.

(Note : en fait, pour l'addition, il suffit de soustraire
éventuellement $m$ si le résultat l'excède : pas besoin de faire une
vraie division euclidienne.)

Les ordinateurs travaillent naturellement dans
$\mathbb{Z}/2^r\mathbb{Z}$ avec $r$ valant typiquement $16$, $32$ ou
$64$.

Note importante : Le choix des représentants $0,\ldots,m-1$ est
arbitraire : on pourrait tout aussi bien choisir $1,\ldots,m$ ou bien
$-\lfloor\frac{m-1}{2}\rfloor,\ldots,\lfloor\frac{m}{2}\rfloor$ (ou
encore des choses tout à fait arbitraires).

\medbreak

Et si $m\leq 1$ ?
\begin{itemize}
\item On a $\mathbb{Z}/1\mathbb{Z} = \{\bar 0\}$, et les opérations
  sont triviales ($\bar 0 + \bar 0 = \bar 0$ et $\bar 0 \times \bar 0
  = \bar 0$).
\item On a $\mathbb{Z}/0\mathbb{Z} = \mathbb{Z}$.
\item Si $m<0$ alors $\mathbb{Z}/m\mathbb{Z} =
  \mathbb{Z}/(-m)\mathbb{Z}$.
\end{itemize}

En général quand on parle de $\mathbb{Z}/m\mathbb{Z}$ on sous-entend
$m\geq 1$, parfois même $m \geq 2$ !

%
\subsection{Premières propriétés de $\mathbb{Z}/m\mathbb{Z}$}

C'est un anneau commutatif.  Il n'est \emph{pas intègre} en général :
on peut avoir $ab=\bar 0$ dans $\mathbb{Z}/m\mathbb{Z}$ alors que $a
\neq \bar 0$ et $b \neq \bar 0$ (exemple : $\bar 2 \times \bar 5 =
\bar 0$ dans $\mathbb{Z}/10\mathbb{Z}$).

Surjection canonique : c'est l'application $\pi\colon \mathbb{Z} \to
\mathbb{Z}/m\mathbb{Z}$ qui envoie $x\in\mathbb{Z}$ sur sa classe de
congruence modulo $m$.  C'est un \emph{morphisme d'anneaux}, i.e., il
préserve l'addition et la multiplication et envoie $0$ et $1$ sur
$\bar 0$ et $\bar 1$.

Si $m|m'$, il y a une application naturelle $\mathbb{Z}/m'\mathbb{Z}
\to \mathbb{Z}/m\mathbb{Z}$ car les classes modulo $m'$ sont plus
fines que modulo $m$.  (Exemple : connaître la congruence modulo $4$
permet de connaître la congruence modulo $2$.)  C'est également un
morphisme d'anneaux.

%
\subsection{Inversibles de $\mathbb{Z}/m\mathbb{Z}$}

Si $a$ et $m$ sont premiers entre eux, alors on sait qu'on peut
trouver une relation de Bézout $au + mv = 1$.  On a alors $\bar a \bar
u = \bar 1$ : on dit que $\bar a$ est \emph{(multiplicativement)
  inversible} dans $\mathbb{Z}/m\mathbb{Z}$, ou est une \emph{unité}
de cet anneau.  Réciproquement, si on peut trouver $\bar u$ tel que
$\bar a \bar u = \bar 1$, alors $a$ est premier à $m$.

On appelle $(\mathbb{Z}/m\mathbb{Z})^\times$ l'ensemble des
inversibles multiplicatifs de $\mathbb{Z}/m\mathbb{Z}$.  C'est un
groupe pour la multiplication (plus généralement, dans tout anneau
commutatif $A$, l'ensemble des inversibles/unités de $A$ forme un
groupe noté $A^\times$).

Si $\bar a$ est inversible dans $\mathbb{Z}/m\mathbb{Z}$, on pourra
noter $\bar a^{-1}$ son inverse (qui est évidemment de nouveau
inversible...).  On le calcule à partir d'une relation de Bézout.
Attention, il n'est pas évident de relier $\bar a^{-1}$ avec le
rationnel $1/a$ !

Exemple : dans $\mathbb{Z}/10\mathbb{Z}$, les éléments $\bar 1, \bar
3, \bar 7, \bar 9$ sont inversibles, et leurs inverses sont $\bar
1^{-1} = \bar 1, \bar 3^{-1} = \bar 7, \bar 7^{-1} = \bar 3, \bar
9^{-1} = \bar 9$.

On note $\varphi(m)$ le cardinal de
$(\mathbb{Z}/m\mathbb{Z})^\times$ : la fonction $\varphi$ s'appelle
\emph{fonction indicatrice d'Euler} (exemple : $\varphi(10) = 4$).  On
verra plus loin comment la calculer.

Note : on a deux involutions importantes sur
$(\mathbb{Z}/m\mathbb{Z})^\times$ : l'une est $\bar a \mapsto -\bar
a$, et l'autre est $\bar a \mapsto \bar a^{-1}$.  Comme la première
n'a pas de point fixe, $\varphi(m)$ est toujours \emph{pair} (sauf
pour $m=2$).

Si $p$ est premier, alors tous les nombres entre $1$ et $p-1$ sont
premiers avec $p$ : $(\mathbb{Z}/p\mathbb{Z})^\times = \{\bar
1,\ldots, \overline{p-1}\}$ (et notamment $\varphi(p) = p-1$).  Tous
les éléments de $\mathbb{Z}/p\mathbb{Z}$ sont inversibles sauf $\bar
0$ : on dit que l'anneau $\mathbb{Z}/p\mathbb{Z}$ est un \emph{corps}
et on le note $\mathbb{F}_p$.

%
\subsection{Théorème chinois}

Si $m$ et $n$ sont deux naturels non nuls \textbf{premiers entre eux},
considérons l'application dont les composantes sont les deux
surjections canoniques :
\[
\mathbb{Z}/(mn)\mathbb{Z} \to (\mathbb{Z}/m\mathbb{Z})
\times (\mathbb{Z}/n\mathbb{Z})
\]

Il s'agit d'un \emph{morphisme d'anneaux} (car les surjections
canoniques en sont !) :
\begin{itemize}
\item il est injectif car un entier multiple de $m$ et de $n$
est multiple de $mn$ (lemme de Gauß),
\item il est surjectif car les cardinaux coïncident ($mn$ au départ et
à l'arrivée),
\end{itemize}
c'est donc un \textbf{isomorphisme}.

Dresser la table d'isomorphisme de $\mathbb{Z}/10\mathbb{Z}$ avec
$(\mathbb{Z}/2\mathbb{Z}) \times (\mathbb{Z}/5\mathbb{Z})$...

%
\subsection{Théorème chinois explicite}

Si on a une relation de Bézout $um+vn=1$, alors l'isomorphisme chinois
a pour réciproque
\[
\begin{array}{c}
(\mathbb{Z}/m\mathbb{Z}) \times (\mathbb{Z}/n\mathbb{Z}) \to
\mathbb{Z}/(mn)\mathbb{Z}\\
(x,y) \mapsto umy+vnx\\
\end{array}
\]

Exemple : trouver le nombre entre $0$ et $100$ congru à $9$
modulo $11$ et à $3$ modulo $13$.  (Relation de Bézout : $6\times 11 -
5 \times 13 = 1$ ; ensuite, $6 \times 11 \times 3 - 5 \times 13 \times
9 \equiv 5\times 11 - 1\times 13 \equiv 42 \pmod{11\times 13}$.)

\medskip

Plus généralement, connaissant la classe d'un entier modulo
$m_1,\ldots,m_k$, on peut retrouver sa classe modulo
$\ppcm(m_1,\ldots,m_k)$.

%
\subsection{Calcul de l'indicatrice d'Euler}

Si $m$ et $n$ (naturels non nuls) sont premiers entre eux, par le
théorème chinois on a $(\mathbb{Z}/(mn)\mathbb{Z})^\times \cong
(\mathbb{Z}/m\mathbb{Z})^\times \times
(\mathbb{Z}/n\mathbb{Z})^\times$, donc
\[
\varphi(mn) = \varphi(m)\,\varphi(n)
\]

Si $p$ est premier alors $\varphi(p^r) = (p-1)\,p^{r-1}$ (car être
premier avec $p^r$ équivaut à être premier à $p$, et c'est le cas de
$p-1$ entiers sur $p$).

On en déduit :
\[
\varphi(n) = n\,\prod_{p|n}\left(1-\frac{1}{p}\right)
\]
où $p$ parcourt les premiers divisant $n$.

\textbf{Algorithmiquement :} \emph{lent} en général (demande de
connaître la d.f.p.).

%
\subsection{Notions de théorie des groupes}

Rappel de la définition d'un groupe (notations multiplicative,
additive).  Morphisme, isomorphisme de groupes.

Ordre d'un groupe = son cardinal.  Ordre d'un élément $g$ dans un
groupe = le plus petit $m\geq 1$ tel que $g^m = 1$ (en notation
multiplicative ; en notation additive, cela s'écrirait : $mg = 0$,
i.e., un multiple de $g$).

Notion de sous-groupe.  Sous-groupe engendré par une partie = plus
petit sous-groupe la contenant.  Sous-groupe engendré par un
élément $g$ : c'est l'ensemble des puissances de $g$ (en notation
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
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$.

%
\subsection{Groupes cycliques}

On dit qu'un groupe fini $G$ est \textbf{cyclique} lorsqu'il existe un
élément $g$ (appelé \emph{générateur} de $G$) tel que tout élément de
$G$ soit de la forme $g^k$ (une puissance de $g$, en notation
multiplicative ; en notation additive, cela s'écrirait : $kg$, i.e.,
un multiple de $g$), autrement dit : le sous-groupe engendré par $g$
est $G$ tout entier.

Le groupe \emph{additif} $\mathbb{Z}/m\mathbb{Z}$ est cyclique, avec
pour générateur $1$ (mais ce n'est pas le seul possible !
cf. ci-dessous).  Réciproquement, tout groupe cyclique est isomorphe à
$\mathbb{Z}/m\mathbb{Z}$, avec $m$ l'ordre d'un générateur $g$ (qui
est donc aussi l'ordre du groupe et ne dépend pas du générateur).
D'où une autre définition possible : un groupe cyclique $G$ [de
  générateur $g$] est un groupe isomorphe à $\mathbb{Z}/m\mathbb{Z}$
[avec $1$ correspondant à $g$].

Les générateurs de $\mathbb{Z}/m\mathbb{Z}$ (comme groupe additif !)
sont précisément les inversibles de $\mathbb{Z}/m\mathbb{Z}$ (comme
anneau !).  Démonstration...  Attention ! on parlera aussi, plus loin,
des générateurs du groupe \emph{multiplicatif}
$(\mathbb{Z}/m\mathbb{Z})^\times$ (et de la question de savoir s'il y
en a).

Moralité : $\varphi(m)$ est aussi le nombre d'éléments d'un groupe
cyclique (quelconque) d'ordre $m$ qui en sont générateur.

%
\subsection{Théorème d'Euler}

Si $m$ est un entier naturel non nul et $a$ un entier premier à $m$,
alors
\[
a^{\varphi(m)} \equiv 1 \pmod{m}
\]

Démonstration : l'élément $\bar a \in (\mathbb{Z}/m\mathbb{Z})^\times$
a un ordre qui doit diviser l'ordre du groupe, i.e. $\varphi(m)$.

Attention ! ne pas confondre l'ordre d'un élément du groupe additif
$\mathbb{Z}/m\mathbb{Z}$ et l'ordre d'un élément du groupe
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
\[
a^p \equiv a \pmod{p}
\]
Ceci fournit une condition \emph{nécessaire} mais non suffisante pour
qu'un nombre soit premier.

%
\subsection{Éléments primitifs}

Soit $m$ un entier naturel non nul.  On dit que $g \in
(\mathbb{Z}/m\mathbb{Z})^\times$ est (un résidu) \textbf{primitif}
(modulo~$m$) lorsqu'il engendre $(\mathbb{Z}/m\mathbb{Z})^\times$
(comme groupe abélien multiplicatif) --- ce qui entraîne que
$(\mathbb{Z}/m\mathbb{Z})^\times$ est cyclique.

Autrement dit, $g^{\varphi(m)}=1$ est optimal ($\varphi(m)$ est
exactement l'ordre de $g$).

Exemple : les puissances de $\bar 2$ modulo $9$ sont : $\bar 2,\bar
4,\bar 8,\bar 7,\bar 5,\bar 1$ ; il y en a bien $\varphi(9)=6$ donc
$2$ est primitif modulo $9$.

\smallbreak
\textbf{Attention !} Ne pas confondre :
\begin{itemize}
\item $\mathbb{Z}/m\mathbb{Z}$ (groupe \emph{additif}, d'élément
neutre $0$) est d'ordre $m$ et est \emph{toujours} cyclique (avec pour
générateurs au moins $1$ et $-1$, et tous les éléments de
$(\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}).
\end{itemize}

\medbreak

\textbf{Théorème :}
\begin{itemize}
\item Si $p$ est un nombre premier impair, alors
  $(\mathbb{Z}/p\mathbb{Z})^\times$ est cyclique, i.e., il existe des
  éléments primitifs modulo $p$.  (Il en existe exactement
  $\varphi(p-1)$.)
\item Si $p$ est un nombre premier impair et $r\geq 2$, alors
  $(\mathbb{Z}/p^r\mathbb{Z})^\times$ est cyclique, i.e., il existe
  des éléments primitifs modulo $p^r$.  (Il en existe exactement
  $\varphi(p^{r-1}(p-1))$.)  \emph{Mieux} : $g$ est primitif modulo
  $p^r$ si et seulement si il l'est modulo $p^2$.
\item Si $p=2$ et $1\leq r\leq 2$, alors
  $(\mathbb{Z}/2^r\mathbb{Z})^\times$ est trivialement cyclique.
\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$.
\end{itemize}

%
\subsection{Exercices}

\thingy Que vaut $10^{1000}$ modulo $7$ ?  (Réponse : $4$.)  Que vaut
$10^{1000}$ modulo $6$ ?  (Réponse : $4$.)  Que vaut $10^{10^{1000}}$
modulo $7$ ?  (Réponse : toujours $4$.)

\thingy Quels sont les deux derniers chiffres (en base $10$) de
$2^{1000!}$ ?

\thingy Montrer que pour tout $a\in \mathbb{Z}$ on a $a^{1729} \equiv
a \pmod{1729}$ (indication : $1729 = 7\times 13 \times 19$ ; utiliser
le théorème chinois).

\thingy À quoi est isomorphe le groupe
$(\mathbb{Z}/56\mathbb{Z})^\times$ ?  Quel est le plus grand ordre
possible d'un élément de ce groupe ?

\thingy \textbf{Théorème de Wilson :} $p$ est premier si, et seulement
si, $(p-1)! \equiv -1 \pmod{p}$.

\thingy \textbf{Théorème de Wolstenholme :} si $p\geq 5$ est premier,
le numérateur de
$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{p-1}$ est
divisible par $p^2$.  (Indications : on pourra regrouper $\frac{1}{k}$
et $\frac{1}{p-k}$, diviser par $p$, et chercher à étudier une
congruence modulo $p$ ; on pourra faire usage du fait que
$1^2+2^2+3^2+\cdots+(p-1)^2 = \frac{1}{6}p(p-1)(2p-1)$.)

%
\section{Polynômes}

\subsection{Définition, structure d'anneau et degré}

Soit $k$ un anneau commutatif quelconque, typiquement un corps
(exemples importants : $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$ ou bien
$\mathbb{Q}$, $\mathbb{R}$, $\mathbb{C}$).

Un \textbf{polynôme} en $t$ à coefficients dans $k$ est une somme
formelle $f = a_0 + a_1 t + a_2 t^2 + \cdots$ avec $a_i \in k$ où
\emph{seul un nombre fini} des $a_i$ est non nul (sinon on parle de
\textbf{série formelle}).

\textbf{Opérations :}
\begin{itemize}
\item Addition : terme à terme ($c_i = a_i+b_i$).
\item Multiplication : « produit de Cauchy » en développant
formellement ($c_i = \sum_{j=0}^{j=i} a_j b_{i-j}$).
\end{itemize}

Si $k$ est un anneau commutatif, alors $k[t]$ aussi.

\textbf{Degré} d'un polynôme : $\deg f =$ le plus grand $i$ tel que
$a_i \neq 0$ (le degré du polynôme nul est question de convention).
On peut donc écrire un polynôme de degré $\leq N$ comme $a_0 + \cdots
+ a_N t^N$ ; si $a_N = 1$ on dit que $f$ est \textbf{unitaire}.

\textbf{Propriétés} du degré :
\begin{itemize}
\item $\deg (f+g) \leq \max(\deg f, \deg g)$ (avec égalité si $\deg f
\neq \deg g$)
\item $\deg (fg) = \deg f + \deg g$ (dès que $k$ est \emph{intègre},
  en particulier sur un corps)
\end{itemize}

Si $k$ est un anneau commutatif intègre, alors $k[t]$ aussi.

Attention, $k[t]$ n'est jamais un corps !  (Car $t$ n'a pas d'inverse
pour la multiplication.)

\medbreak

À souligner : \emph{analogie} importante entre les polyômes, notamment
dans $\mathbb{F}_p[t]$, et l'écriture en base $p$ des entiers.
Différence importante : pas de retenue pour les polynômes.

Complexité des opérations : cf. entiers.

%
\subsection{Opérations spécifiques aux polynômes}

\textbf{Évaluation} de polynômes : si $f = a_0 + \cdots + a_N t^N$ et
$x \in A$ (une $k$-algèbre, par exemple $k$ ou $k[t]$), on définit
$f(x) = a_0 + \cdots + a_N x^N$.

Cas particulier : \textbf{composition} : si $g \in k[t]$, on note
$f\circ g$ plutôt que $f(g)$.

\medbreak
\textbf{Dérivée :} si $f = a_0 + a_1 t + \cdots + a_N t^N$ alors $f' =
a_1 + 2 a_2 t + \cdots + N a_N t^{N-1}$.

\textbf{Attention :} On peut avoir $f'=0$ sans avoir $f$ constant
(e.g., $f = t^p$ dans $\mathbb{F}_p[t]$).

\textbf{Dérivées successives :} $f^{(i+1)} = (f^{(i)})'$ pour $i \in
\mathbb{N}$.

%
\subsection{Polynôme interpolateur, formule de Taylor}

Dans cette section, soit $k$ un \emph{corps} et $f \in k[t]$.

\medskip

Soient $a_0,\ldots,a_N
\in k$ deux à deux distincts, où $N \geq \deg f$, et $b_i = f(a_i)$,
alors
\[
f = \sum_{i=0}^N b_i \frac{\prod_{j\neq i}(t-a_j)}{\prod_{j\neq i}(a_i-a_j)}
\]

Permet de reconstruire un polynôme à partir de ses valeurs en
suffisamment de points.

\medbreak

Si $N \geq \deg f$ et $N!$ n'est pas nul dans $k$, alors pour tout
$a\in k$ :
\[
f = f(a) + (t-a)\,f'(a) + \frac{(t-a)^2}{2}\,f''(a) +
\cdots + \frac{(t-a)^N}{N!}\,f^{(N)}(a)
\]

Permet de reconstruire un polynôme à partir de ses dérivées
successives en un point.

%
\subsection{Division euclidienne de polynômes}

Sauf mention du contraire, $k$ est maintenant un \textbf{corps}.

\smallskip

\textbf{Division euclidienne} analogue à celle des entiers :

Si $f\in k[t]$ et $g\in k[t]$ est \emph{non nul},
il existe un unique couple $(q,r)$ tel que :
\begin{itemize}
\item $q \in k[t]$,
\item $r \in k[t]$ est (nul ou) de degré $\deg r < \deg g$ et
\item $f = gq + r$.
\end{itemize}

\medbreak

\textbf{Algorithme « naïf »} de division euclidienne : procéder par
puissances \emph{décroissantes} :

Soit $f = a_N t^N + \cdots + a_0$ et $g = b_D t^D + \cdots + b_0$ où
$b_D \neq 0$ (donc $\deg g = D$) :
\begin{itemize}
\item si $N<D$ on renvoie $q = 0$ et $r = f$ ;
\item sinon, on pose $c = a_N/b_D$, on définit $f^* = f - c t^{N-D}
g$, donc $\deg(f^*) < N$, on applique l'algorithme pour diviser $f^*$
par $g$, soit $f^* = gq^* + r$ et on a $f = gq + r$ où $q = c t^{N-D}
+ q^*$.
\end{itemize}

\smallbreak

\textbf{Cas très important :} Le reste de la division euclidienne de
$f$ par $t-a$ (où $a \in k$ est une constante) est $f(a)$.
(Pourquoi ?)

\smallbreak

\textbf{Exercice :} Effectuer la division euclidienne de $t^7$ par $2
t^3+1$ dans $\mathbb{F}_7[t]$.  (Réponse : $t^7 = (2 t^3+1) (4 t^4 + 5
t) + 2 t$.)

%
\subsection{Arithmétique des polynômes}

Relation de \textbf{divisibilité} : exactement analogue aux entiers.
Les \textbf{unités} de $k[t]$ sont les éléments de $k^\times$
(polynômes constants non nuls).

Polynômes \textbf{irréductibles} : définition analogue aux nombres
premiers.  On les choisira normalement \emph{unitaires} ; par
convention, $0$ et les constantes ne sont pas irréductibles.  Les
polynômes $t-a$ (unitaires de degré $1$) sont \emph{toujours}
irréductibles.  Lorsque ce sont les seuls, le corps $k$ est dit
\emph{algébriquement clos}.

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
$\mathbb{F}_p$ déjà vu) ne sont pas algébriquement clos (« encore
  moins » que $\mathbb{R}$).

\medbreak

\textbf{Décomposition en facteurs irréductibles :} Écriture unique de
tout $f\in k[t]$ non nul comme $c \prod_P P^{v_P(f)}$ où $c \in
k^\times$ est le coefficient dominant de $f$ et $v_P(f)\in \mathbb{N}$
pour tout $P$ irréductible (presque tous nuls).

Cas où $k$ est algébriquement clos : tout $f \in k[t]$ non nul s'écrit
de façon unique comme $c \prod_{a\in k} (t-a)^{v_a(f)}$ où $c \in
k^\times$ est le coefficient dominant de $f$ et $v_a(f)\in \mathbb{N}$
est l'ordre du zéro de $f$ en $a$.

\medbreak

PGCD, algorithme d'Euclide, relations de Bézout, Euclide étendu :
exactement analogue aux entiers.

%
%
%
\end{document}