\documentclass{amsart}
\usepackage{amsfonts, amssymb, amsmath,amscd}

\usepackage[utf8]{inputenc}
\usepackage[french]{babel}
\usepackage{hyperref}
%%\usepackage{color}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{multicol}
\usepackage{amsmath}
\usepackage{graphicx}

\hypersetup{urlcolor=blue,
           linkcolor=black,
           citecolor=black,
          colorlinks=true
} 


\input langage.tex
\input  macros.tex
\def\grmul#1{{#1}^{\star}}
\def\GF{{\rm GF}\,}

\newtheorem{theoreme}{Th\'eorème}
\newtheorem{definition}{D\'efinition}
\newtheorem{conjecture}{Conjecture}
\newtheorem{proposition}{Proposition}
\newtheorem{lemme}{Lemme}
\newtheorem{scolie}{Scolie}
\newtheorem{corollaire}{Corollaire}
\newtheorem{remarque}{Remarque}
\newtheorem{exercice}{Exercice}
\newtheorem{tps}{Travaux-pratiques}

\title{Arithm\'etique Modulaire en Langage C sous LINUX\\
{\sl draft: 2013-14-15}}
\author{Philippe Langevin}
\date \today

\def\rsa{\textsc{rsa}}
\def\gen#1{\langle#1\rangle}
\def\ord#1{{\rm ord}\,(#1)}

\begin{document}

\maketitle


\begin{abstract}
Dans ce cours, nous détaillons quelques points
de l'algèbre et de la théorie des nombres  en 
liaison avec la construction d'une clé pour 
le cryptosystème \rsa : un système de chiffrement à clef  
publique fort célèbre. Une occasion d'implanter, en langage C,
quelques algorithmes fondamentaux de l'arithmétique, 
et par là même,  faire connaissance
avec la bibliothèque  multiprécision \gcc{gmp} et
quelques fonctionnalités de la commande 
\shell{openssl}.
\end{abstract}


\tableofcontents


\lstinputlisting[style=term]{infos.txt}


Nous éviterons de parler du plus étrange des nombres
premiers ! Sauf mention contraire, dans cette note, 
$p$ et $q$ désignent des nombres premiers impairs 
et $n$ un nombre composé impair.

\hfill Indeed, two is the oddest prime!\quad

\section{Fondation}

L'arithmétique  est une discipline
fondamentale initiée par les mathématiciens 
grecs : Pythagore, Euclide, Diophante. 
En passant, le mot grec \relief{mathêmas} signifie sciences et
\relief{arithmos} désigne un nombre. Les
recherche en arithmétique ont pour objectif
de comprendre les \relief{propriétés cachées} des 
nombres entiers. La résolution d'une enigme 
diophantienne peut prendre un certain temps,
voire un temps certain, rappelons par exemple 
que la résolution du grand théorème de Fermat 
s'appuie sur des travaux qui s'étalent sur 
plusieurs siècles. Le lecteur peut rechercher 
sur internet le documentaire réalisé par Simon Singh 
produit par la BBC dans la série horizons.
Dans l'apologie d'un mathématicien \annee{1940}, Hardy
déclare : 

\vspace{10mm}

{\sl... both Gauss and lesser 
mathematicians may be justified in rejoicing 
that there is one science (number theory) at 
any rate, and that their own, whose remoteness 
from ordinary human activities should keep 
it gentle and clean.}

\vspace{10mm}

Il encore souhaitable de penser comme le math\'ematicien 
Hardy mais un progrès  considérable dans le domaine de la 
cryptographie rélalisé au milieu des ann\'ees \annee{70} va  
bouleverser le statut de la reine des mathématiques.
En 1976, Diffie et Hellman décrivent un
procédé pour transmettre une clé secrète. Il est fondé sur
l'exponentiation modulaire qui, deux ans plus tard,
permet à Rivest, Shamir et Adelman de proposer le premier
système de chiffrement à clefs publiques, ces propositions 
s'appuient fortement sur la théorie des nombres. 



\section{cryptographie}


On peut distinguer quatre genre de cryptographie :
la cryptographie à clef secrète à flot ou par blocs,
la cryptographie à clefs publiques dont il est fortement question 
dans ce cours, la cryptographie de propriétaire qui ne fonctionne 
jamais, et une cryptographie physique  qui devrait faire parler d'elle
dans un futur plus ou moins proche. 


Soient $X$ un espace de clairs, $K$ un ensemble de clés. Convenons
d'appeler \emph{algorithme cryptographique} la donnée de deux paramétrisations
d'un ensemble de permutations des clairs par un ensemble de clés. La paramétrisation
de chiffrement $E\colon X \times K\rightarrow X$, et celle de déchiffrement 
$D\colon X\times K \rightarrow X$, en pratique $E=D$, 
telles  que pour toute clé $k\in K$, 
il existe une clé $k'$ vérifiant :

$$
\forall k\in K, \quad \exists k'\quad,	\forall x\in X, \qquad D(  E(x,k) , k' ) = x.
$$

Le système est dit asymétrique quand $k'\not=k$ en général, 
et symétrique dans le cas $k'=k$.
Un algorithme de chiffrement doit être 
efficace du point de vue calculatoire. 
Le système doit être prouvé robuste : 
la seule connaissance de quelques cryptogrammes $E(x_i, k)$ 
ne doit pas  suffire pour retrouver un des clairs $x_i$, et 
encore moins la clée utilisée, sans un effort calculatoire
passant par moins de $2^{80}$ étapes.




\begin{exercice}
Une idée ?
\end{exercice}


\section{Outils pour permuter ?}

\hfill Bijections are where it's at---Herb Wilf


\bigskip
 
D'aprés Pythagore, tout est nombre, et la cryptographie 
c'est l'art de permuter les nombres avec efficacité et
robustesse. Il y a $n^n$ applications d'un ensemble
à $n$ éléments dans lui-même, et $n!$ sont des permutations.
Rappelons, la formule d'équivalence de Stirling qui relie
de façon surprenante le nombre de bijections d'un ensemble 
à $n$ éléments à deux des nombres transcendants connus
de tous, $\pi$ et $e$ :

\[
\label{STIRLING}
n! \sim \sqrt{2\pi n}n^n e^{-n} 	
\] 

\begin{exercice}
D'aprés certains physiciens,
on peut estimer à $2^{256}$ le nombre de particules
dans l'univers. Quel  est le plus petit entier $n$ tel
que $n!>2^{256}$ ?
\end{exercice}

Mézalor, comment décrire une permutation dans la jungle des
applications ? L'algèbre  s'est rapidement imposée
comme un moyen approprié pour décrire des permutations 
sur un ensemble fini à partir de lois internes  qui vérifient 
des règles analogues aux lois additions et multiplications
sur les nombres, et qui nous sont familières  : 
associativité, distributivité, etc\ldots


\section{Structure algébrique}


Une structure algébrique est un ensemble 
muni de lois vérifiant des contraintes
plus ou moins fortes. Une loi interne $\star$
sur un ensemble $E$ est une application de
$E\times E$ dans $E$ qui envoie le couple
$(x,y)$ sur $x\star y$. Sur un ensemble  
$E$ de cardinal $n$, il existe autant de lois
internes que de tableaux $n\times n$ à valeurs
dans $E$, et donc, il est possible de former
$n^{n^2}$ lois internes mais trés peu d'entre
elles  possèdent un réel intérêt. On dit que
la loi est associative quand on peut associer
les termes dans n'importe quel ordre sans 
changer le résultat :

$$
\forall x,y,z \in E \quad (x\star y)\star z=x\star (y\star z)
$$


Un ensemble muni d'une loi interne sans condition
est un magma. Une structure de semi-groupe $(E,\star)$ est 
magma  dont la loi associative.

 
\begin{tps}
Ecrire un programme pour compter le nombre
de structure de semi-groupes à $n$ éléments, pour $n$ 
relativement petit : 1, 2, 3, 4. Puis utiliser
l'encyclopédie {Online Integer Sequence } de Sloane 
pour retrouver de l'information sur le sujet.
\end{tps}

Un morphisme de la structure $(E,\star)$
vers la structure $(F,\ast)$ est une 
application $f\colon E \rightarrow F$ qui
conserve les opérations 

$$
\forall x,y \in E \quad  f(x\star y) = f(x)\ast f(y).
$$ 

Dans ce contexte, il convient d'introduire 
la notion d'anti-morphisme.
On dit que $f$ est un monomorphisme, un epimorphisme,
un isomorphisme suivant que $f$ est une injection, une
surjection ou une bijection. On dit que deux structures
sont isomorphes quand il existe une isomorphisme de
l'une sur l'autre, on doit alors s'intéresser aux 
classes s'isomorphies. 


\begin{tps}
Ecrire un programme pour compter le nombre
de classes de semi-groupies à $n$ éléments. Il
y  a 3192 semi-groupes à 4 éléments et 126
classes à anti-isomorphismes prés.
\end{tps}


L'ensemble des applications de $E$ dans $E$
muni de la composition des applications est
un exemple de monoide. On remarque que l'application
identique est un neutre, que les bijections sont
précisément les éléments inversibles. L'ensemble
des bijections de $E$ dans $E$ muni de la composition
des applications forme une structure de groupe
généralement noté $( S(E), \circ )$ et que ce groupe
n'est pas commutatif dès que le cardinal de $E$ est
supérieur à 2.

\section{Ordre et Groupe}

Un groupe $(G,*)$ est ensemble $G$ sur lequel opère 
une loi interne : associative, possèdant un neutre $1_G$, 
tout élément de $G$ est inversible. Le groupe est dit abélien 
quand la loi est commutative.


\begin{exercice}
Dans un groupe $G$, il y a unicité du neutre et
des inverses. Tout élément est simplifiable
$$
\forall x,y,z \in G,
\quad
	x*y = x*z \Longrightarrow y = z.
$$
En particulier, pour tout $t\in G$,
l'application $x\mapsto tx$ est une
permutation de $G$.
\end{exercice}


Précisons qu'un groupe peut-être présenté comme
ci-dessus par une loi multiplicave, ou bien par
une loi additive. Dans le second cas, le neutre
est noté $0_G$ et les inverses sont des opposés.
On définit l'ordre de $x$ comme étant 
le plus petit entier non nul $n$ tel 
que $x^n=1_G$. On remarque sur le
champ que si $x^m = 1_G$ pour un autre
entier $m$ alors $n$ divise $m$.

\begin{proposition}
\label{ORDRE}
Dans un groupe abélien fini, l'ordre d'un élément 
divise le cardinal du groupe.
\end{proposition}
\begin{proof}
En effet, notons $n$ l'ordre de $G$ :
$$\prod_{y\in G} y 
= \prod_{y\in G} (x*y)
= x^n \prod_{y\in G} y.
$$
Aprés simplification, $x^n = 1_G$.
\end{proof}
 
\begin{exercice}
Déterminer les ordres des éléments du
groupe $S(3)$.
\end{exercice}


Une partie non vide $H\subset G$ stable
par la loi de $G$ est un sous-groupe. La
Propositioni~\ref{ORDRE} est en fait
un cas particulier du théorème de Lagrange.


\begin{theoreme}[Lagrange]
\label{LAGRANGE}
Dans un groupe fini, le cardinal d'un
sous-groupe divise le cardinal du groupe.
\end{theoreme}
\begin{proof}
Si $S$ est un sous groupe de $G$
alors les ensembles $t+S$ obtenus
en faisant varier $t$ dans $G$ sont 
deux à deux égaux ou disjoints.
\end{proof}

\begin{exercice}
La neutralité est préservée par morphisme. Généralisation
aux sous-groupes.
\end{exercice}


\section{Anneau et corps}

Une structure d'anneau $(A,+,\times)$ 
est la donnée d'un ensemble $A$ qui est  muni de 
deux lois internes, une addition pour laquelle
$(A,+)$ est un groupe et une multiplication
vérifiant les axiomes :
\begin{enumerate}
\item associativité  
\item existence d'un neutre $1_A$
\item distributivité de la multiplication sur l'addition.
\end{enumerate}

On pourra remarquer que :

\begin{exercice}
Dans un anneau, les neutres sont uniques,
le neutre additif est absorbant et que
le groupe $(A,+)$ est nécessairement abélien !
\end{exercice}




Quand la multiplication est commutative, 
l'anneau est dit commutatif. Quand tous les 
éléments non-nuls sont inversibles l'anneau
est un corps. Un célèbre théorème de Wedderburn
(1905) affirme qu'un corps avec un nombre fini 
d'élément est forcément commutatif, pour
simplifier notre propos, nous admettrons ce
résultat somme toute assez étonnant !!
Le plus petit des anneaux contenant 
deux éléments distincts $0$ et $1$ 
est $\F_2$ le corps à deux éléments, il
s'obtient en imposant la formidable
relation :

$$
        1+1 = 0.
$$

\begin{exercice}
Un pre-semicorps est un ensemble fini $\mathfrak S$ de deux lois internes, une 
multiplication distributive à gauche et à droite sur une addition
formant un groupe. La multiplication n'est pas nécessairement
associative. On suppose que pour tout $t\in\mathfrak S$,
la multiplication par $t$ est une bijection. Comme dans
le cas d'un anneau, le groupe  additif est abélien (commutatif). 
Prouvez le !
\end{exercice}

\section{Inversible et diviseur de zéro}

Un élément $t$ est un \emph{inversible} à droite
quand il existe un élément non nul 
$t'$ tel que $tt'=1$.
Un élément $z$ est un \emph{diviseur de zéro} à
à droite quand il existe 
un élément non nul $r$ tel que $zr=0$. Idem
à gauche. 

\begin{lemme} Dans un anneau fini, soit un élément
est inversible soit c'est diviseur de zéro.
\end{lemme}
\begin{proof}
Soit $y$ un élément de $A$. On considère la
multiplication par $y$ : $x\mapsto xy$. Si cette application
de $A$ dans lui-même est surjective alors 
$y$ est inversible sinon c'est un diviseur de
zéro à gauche et donc à droite.
\end{proof}

On remarque que si $t$ est inversible à gauche alors
il est inversible à droite, que les inverses à gauche
et à droite sont identiques. Par ailleurs, si $x$ et
$y$ sont inversibles d'inverse $x'$ et $y'$ alors $xy$
est inversible d'inverse $y'x'$. Les  éléments inversibles 
de $A$ forment un groupe noté $\grmul A$ : le groupe des inversibles
de $A$. 

\begin{exercice}[Ganesan] Soit $A$ un anneau avec 
$n\geq 2$  diviseurs de zéros. Montrer
que $A$ est fini et  d'ordre inférieur
à $(n+1)^2$.
\end{exercice}
\section{Arithmétique modulaire}

Nous notons $\zz n$ l'anneau des résidus
modulo $n$ i.e. l'ensemble des restes possibles
0,1,\ldots, $n-1$ d'une division d'un entier par $n$,
muni de deux  lois internes

$$
x\oplus y := [x+y]_n, \quad x\otimes y = \quad [x \times y]_n.
$$

où $[t]_n$ est une autre notation
pour désigner le reste de la division
de $t$  par  $n$. On montre que l'obtient un
anneau en s'appuyant sur la notion de congruence. Deux
entiers relatifs sont congruents modulo $n$ si $n$
divise la différence $y-x$.

$$
y \equiv x \mod n\quad\iff\quad \exists k, y-x = kn.
$$

La relation de congruence est une relation d'équivalence
compatible avec les lois d'addition et de multiplication.
Comme par ailleurs deux résidus congrus sont identiques
il vient que $\zz n$ est bien un anneau.



Comme dans tout anneau fini, un élément de
$\zz n$ est soit un  diviseur de zéro, soit
un élément inversible. 
Plus précisément, $x$ est inversible si et seulement 
si $x$ est  premier avec $n$.  Si $x$ est inversible 
modulo $n$ alors il existe $u$ tel que 

$$
                xu \equiv 1 \pmod n 
$$
Par définition, il existe $v$ tel que $xu = 1 + nv$
i.e. une relation de B\^achet-Bézout. Réciproquement, 
si $x$ et $n$ sont premiers entre eux, l'algorithme 
d'Euclide étendu fournit une paire  d'entiers $(u,v)$  
tel que :

$$
      xu + nv = (x,n) = 1.
$$

Ainsi, $x$ est inversible,  son inverse modulo $n$
est le résidu congru à $u$.

\begin{proposition}
L'anneau $\zz n$ est un corps si et seulement si $n$
est premier.
\end{proposition}

Nous verrons par la suite que ce fait d'apparence banale
contient quelques propriétées cachées! En général, pour $p$
premier,  le corps à $p$ éléments est noté $\fp$.


Du point de vue additif, les inversibles sont précisément
les éléments d'ordre $n$. L'usage est de noter $\varphi(n)$ 
le nombre d'éléments inversibles modulo $n$.

\begin{equation}
\label{VARPHI}
	n =  \sum_{d\mid n} \varphi(d).
\end{equation}

\begin{tps}
Analyser le temps de calcul d'une multiplication
modulaire implanter avec \gcc{gmp} en fonction
de la taille du module. On pourra faire une
comparaison avec un langage comme \gcc{python},
ou encore \shell{bc}. 
\end{tps}

\begin{exercice}[Wilson]
Montrer que l'entier $n$ est premier si et seulement si 
$$(n-1)! = -1 \pmod n.$$
\end{exercice}

\section{Analogie}

Considérons $\F_2[X]$ l'ensemble des polynômes à coefficients
dans le corps à deux éléments. Il s'agit d'un anneau infini
muni d'une addition et d'une multiplication définies comme
usuellement. Les anneaux $\F_2[X]$ et $\Z$ possèdent de profondes
analogies arithmétiques. En effet, on commence par dire que
le polynôme $B$ divise le polyôme $A$ s'il existe un troisième
$Q$ tel que $A = BQ$. On utilise la notion de degré pour définir
celle d'irréductibilité qui est l'analogue de la primalité. Un
polynôme $A$ de degré positif est dit irréductible quand

$$
A = BC \Longrightarrow \deg B \deg C=0  
$$

Dans ce contexte, il existe une division euclidienne
fondée sur le degré.
Si $B$ désigne un polynôme non nul alors pour tout polynôme
$A$, il existe une unique paire de polynômes $(Q,R)$,
quotient et  reste, tel que :

\begin{equation}
\label{DPOL}
A  = B Q + R,\qquad \text{avec}\quad R = 0, \quad\text{ou}\quad\deg R<\deg B.
\end{equation}

\begin{proposition}
Tout polynôme se décompose de manière essentiellement unique
en un produit de polynômes irréductibles.
\end{proposition}

On peut alors choisir  un  polynôme $M(T)\not=0$ de degré $f$, l'ensemble
des $2^f$ restes possibles d'une division par $M$ 
muni des lois internes 

$$
	A\oplus A'  := (A+A')     \pmod M,\quad
	A\otimes A' := (A\times A') \pmod M,
$$

est un anneau, noté $\F_2[T]/M(T)$.

\begin{exercice}
Construire les tables des 4 anneaux modulaires
pour les polynômes de degré 2. Déterminer
les classes d'isomorphimes.
\end{exercice}


\begin{proposition}
Si $M$ est irréductible alors l'anneau des polynômes modulo $M$
est un corps à $2^f$ éléments, c'est le corps de Galois 
$\GF( 2,f )$ (Galois Field).
\end{proposition}

\begin{exercice}
Vérifier que tout ce qui vient d'être dit s'applique
aux corps $\F_p$, $p$ premier impair.
\end{exercice}

Les auteurs du Rinjael (Advanced Encryption Standard)
décrivent le système de chiffrement par blocs en utilisant
un corps de Galois à 256 éléments. 

\begin{exercice}
Parcourir la spécification officielle
\href{http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf}{fips-197},
pour trouver le polynôme de degré 8 utilisé pour définir le
corps à 256 éléments.
\end{exercice}

\begin{figure}
\includegraphics[scale=0.5]{subaes.png}
\caption{\label{AES}La brique de substitution de l'AES 
opére sur le corps à 256 éléments en envoyant un élément
non nul sur son inverse multiplicatif.}
\end{figure}

\section{Invariant et caractéristique}


Un morphisme d'un anneau $(A,+,\times)$ dans un anneau $(B,\oplus,\otimes)$
est une application de $A$ dans $B$ qui envoie $1_A$ sur $1_B$ et qui
transporte les lois :
$$
	\forall x, y\in A,
\quad f(x\times y)=f(x)\otimes f(y) 
\quad f(x+y) = f(x)\oplus f(y) 
$$


\begin{exercice}
Montrer qu'il existe une  seule classe
d'isomorphie d'anneau à trois éléments.
\end{exercice}

Deux anneaux $A$ et $B$  sont isomorphes ($A\sim B$) s'il existe
un isomorphisme de $A$ sur $B$. Un invariant est une foncion $\mathfrak J$ 
définie sur l'ensemble des anneaux tel que :

$$
	A\sim B \Longrightarrow \mathfrak J (A) = \mathfrak J (B)
$$

L'ordre additif de l'unité est un invariant
appelé caractéristique de l'anneau. Si la caractéristique 
de $A$  est égale à $m$ alors $m$ divise 
le cardinal de l'anneau et  

$$
	\zz m \ni k\mapsto k1_A= \underbrace{1_A+1_A+\cdots+1_A}_{k\ \text{termes}} \in A
$$

définit un monomorphisme de $\zz m$ dans $A$. En particulier,
le cardinal de $A$ est égal à la caractéristique de $A$ 
si et seulement si il est isomorphe à $\zz m$. 


Le nombre d'éléments inversibles, l'ordre du groupe multiplicatif,
le nombre de diviseurs de zéro, la distribution des ordres sont 
des invariants.


\section{Zoologie}

On considère l'anneau des matrices carrées
à coefficients dans le corps à 2 éléments.

$$
\begin{bmatrix}
a  &c\\
b  &d\\
\end{bmatrix}
\times
\begin{bmatrix}
\alpha  &\gamma\\
\beta   &\delta\\
\end{bmatrix}
=
\begin{bmatrix}
a\alpha+c\beta  &a\gamma+c\delta\\
b\alpha+d\beta  &b\gamma+d\delta\\
\end{bmatrix}
$$ 


\begin{enumerate}
\item Quel est le cardinal de cet anneau ? 
\item L'anneau est-il commutatif ?
\item Caractériser les matrices inversibles.
\item Quels sont les diviseurs de zéros ?
\item Quels sont les éléments inversibles ?
\item Le groupe des inversibles est isomorphe
à un groupe de permutation. Lequel ?
\item Quelle est la nature de l'anneau engendré
par la matrice 
$
(
\begin{smallmatrix}
0  &1\\
1  &1\\
\end{smallmatrix}
)
$
?
\item Quelle est la nature de l'anneau engendré
par la matrice 
$
(
\begin{smallmatrix}
0  &1\\
1  &0\\
\end{smallmatrix}
)
$
?
\end{enumerate}


\begin{proposition} A isomorphisme prés, 
il y a quatre structures d'anneaux commutatifs 
à quatre éléments : le corps $\F_4$, l'anneau
modulaire $\zz 4$, le produit $\F_2\times\F_2$ et
l'anneau $\F_2[T]/(T^2)$.
\end{proposition}

On commence par montrer qu'un anneau à 
quatre éléments est forcément commutatif. En effet,
les 4 éléments sont 0, 1, $x$ et $y$. On vérifie
que $y=x+1$ aprés quoi
$$
	xy=x(x+1) = x^2 + x = (x+1)x = yx
$$  

Il y a une seule classe  d'anneau de caractéristique 4. Les classes
d'anneaux de caractéristique 2 sont caractérisée par l'ordre maximal
d'un élément inversible : 1 ($\F_2\times\F_2$), 
2 ($\F_2[T]/(T^2)$) ou 3 ($\F_4$). 
 
\section{Morphisme, cyclicité}

Un morphisme $f$ d'une structure albégrique $(X, \circ )$
vers une structure $(Y,\star )$ est une application de
$X$ vers $Y$ qui conserve les opérateurs :
$$
\forall x,x' \in X,\quad f( x \circ x' ) = f(x) \star f(x').
$$

On définit de ainsi des morphismes de groupes, et de 
façon similaire, des morphismes d'anneaux, de corps 
etc\ldots. Un isomorphisme est un morphisme bijectif.


Vous pouvez vous convaincre
rapidement que l'application qui suit un isomorphisme
remarquable entre le groupe $\cyclo 4$ et,  $\zzi 5$, le groupe
des inversibles modulo 5. 

$$
f\colon	0 \mapsto 1, \quad 1\mapsto 3,\quad 2\mapsto 4,\quad 3\mapsto 2.
$$

On a par exemple,
$$ 
f( 2 + 3 ) = f(1) = 3 = 4 \times 2 = f( 2) \times f( 3 ).
$$

Il nous faut avancer davantage dans notre exposé 
pour comprendre la finesse du petit exemple ci-dessus. 


On constate que la suite : $1$, $1+1$, $1+1+1$, \ldots etc
décrit tous les résidus modulo $n$. On dit que le groupe
$\cyclo n$ est cyclique et que $1$ est un générateur de ce groupe. Pour
$n$ fixé, tous les groupes cycliques d'ordre $n$ sont isomorphes,
et, $\varphi(n)$ est aussi le nombre de générateurs du groupe 
cyclique à $n$ éléments. En effet, $t$ est un
générateur du groupe  $\Z/n\Z$ si et
seulement si la multiplication par
$t$ est surjective.


\section{Exponentiation modulaire}

Soit $\gamma$ un élément inversible modulo $n$.
L'exponentiation modulaire de base $\gamma$ 
transforme l'entier $x$ 
$$
           x\mapsto \gamma^x \mod n.
$$



\begin{multicols}{2}
Quelques primitives cryptographiques célèbres 
reposent sur l'existence d'un algorithme
efficace pour caculer les exponentielles
modulaires.

Le temps de calcul d'un produit
modulo $n$ est quadratique en 
$\log n$. L'algorithme d'exponentiation
modulaire permet de caculer une 
$x^t$ modulo $n$ en $\bigo\big((\log n)^3\big)$. 


L'exponentiation modulaire est un atout d'efficacité mais
c'est aussi un point faible comme nous allons le montrer
tout à l'heure !
 
\columnbreak
\begin{lstlisting}[style=algo]
expmod( x, t, n : nombre )
var r : nombre = 1
debut
tantque ( t > 0 )
   si impair( t ) alors
        r := prod( r, x , n)
   fsi
   x := prd(x, x, n )
   t := t div 2
ftq
retourner r
fin
\end{lstlisting}
\end{multicols}

\begin{exercice} 
Soit $n$ un entier de 512-bits. 
Une implantation de l'exponentiation modulaire
calcule $x^t\pmod n$ en 1ms. Estimer le temps
de calcul pour un module de taille deux fois plus grande.
\end{exercice}

\begin{tps}
Analyser le temps de calcul de
l'exponentiation modulaire de 
\gcc{gmp}.
\end{tps}

\section{Petit théorème de Fermat}

\begin{theoreme}[Fermat] Si $p$ est premier
alors
$$
      \forall x\in\fp,\quad x^p = x,\quad x^{p-1}=\begin{cases}
1,&x\not=0;\\
0,&x=0.
\end{cases}
$$
\end{theoreme}

Les démonstrations de ce théorème font légion: 
combinatoire, Fermat, Lagrange...

\begin{exercice}
Pour $p$ premier, vérifier que  le nombre de parties
à $k$ éléments dans un ensemble à
$p$ éléments satisfait à $\binome kp = 1$ si
et seulement si $k=0$ ou $k=p$. En déduire
le petit théorème de Fermat.
\end{exercice}

Si $x$ est un résidu non nul l'application
$k\mapsto kx$ est une permutation des inversibles
et donc
$$
   (p-1)! =  1 . 2 . \ldots . (p-1)  
          = \prod_{k\not =0} k 
          = \prod_{k\not =0} (kx) 
          = x^{p-1} .  (p-1)! 
$$
Il ne reste plus qu'à simplifier par
$(p-1)!$ alias $-1$ pour terminer la
preuve de Fermat.

\section{Groupe multiplicatif}

On note $K$ un corps fini de cardinal $q$. L'ensemble
des éléments non nuls forme un groupe, noté $\grmul K$,
c'est le groupe multiplicatif de $K$.

Pour tout élément de $K$, il existe un entier positif
$r$ tel que $x^r=1$. Le plus petit d'entre-eux est
appelé l'ordre de $x$. 

\begin{figure}
\lstinputlisting[style=bash]{src/order.sh}
\caption{\label{ORDRE}Un script shell basé sur \shell{bc} pour calculer
l'ordre de 2 modulo un premier passé en argument sur la ligne de commande.}
\end{figure}

\begin{lemme} Si $f$ est l'ordre de $x$, et 
si $x^t=1$ alors $f$ divise $t$.
\end{lemme}
\begin{proof}
Utiliser la division de $n$ par $f$.
\end{proof}

\begin{theoreme}[Lagrange] Dans un groupe fini,
l'ordre d'un élément divise l'ordre du groupe.
\end{theoreme}
\begin{proof}
Faisons la démonstration dans le cas d'un
groupe commutatif fini d'ordre $n$. Considérons
un élément $x$ du groupe et $y_1$, $y_2$, \ldots,
$y_n$ une énumération des éléments de $G$. L'application
$y\mapsto yx$ est une permutation de $G$ et donc :
$$
\prod_{i=1}^n y_i = \prod_{i=1}^n (y_ix)
 = \big(\prod_{i=1}^n y_i\big) \times x^n.
$$
Il suffit alors de simplifier par le produit des $y_i$.
\end{proof}

\begin{exercice}
Faire une démonstration dans le cas 
d'un groupe non commutatif.
\end{exercice}

On peut montrer par induction que,
dans un corps commutatif, un polynôme
de degré $n$ possède au plus $n$ racine.
Pour tout diviseur $d$ de $q-1$,
le nombre d'éléments  d'ordre $d$ dans $\grmul K$
est majoré par $d$. Convenons de noter $\kappa(d)$ 
le nombre d'éléments d'ordre exactement égal à $d$ :

$$
 q-1 = \sum_{d\mid q-1} \kappa(d), \quad \kappa(d)\leq \varphi(d).
$$


\begin{theoreme}
Dans un corps fini d'ordre $q$, 
il existe un élément d'ordre $q-1$.
\end{theoreme}
\begin{proof}
Il suffit de rapprocher l'égalité précédente
avec \voireq{VARPHI}. 
\end{proof}

Les éléments d'ordre $q-1$ sont des \emph{racines primitives}
du corps. Il en existe $\varphi(q-1)$, si $\gamma$ est l'une
d'entre-elles, les autres sont $\gamma^t$ avec $(t,q-1)=1$. 
Par exemple, dans un corps à 11 éléments, il existe $\varphi(10)=4$ 
racines primitives.

\begin{exercice}
Un nompre premier de Sophie Germain est un nombre premier
$s$ tel que $p:=2s+1$ soit un nompre premier. On dit
alors que $p$ est un premier sûr. Montrer que
qu'un élément $x$ est d'ordre multiplicatif $p-1$ si et seulement si 
$x\not\equiv \pm 1$ et $x^s \not=1\pmod{p}$, et dans
ce cas, que vaut $x^s$ ? Quelle est la probabilité
qu'un résidu $x\in\grmul \fp$ soit d'ordre $p-1$ ?
\end{exercice}

\section{Logarithme discret}

On suppose que $p$ est un premier impair. Le
groupe des inversibles modulo $p$ est cyclique
d'ordre $p-1$. Etant donné un générateur 
$\gamma$, résoudre le problème discret de 
base $\gamma$ pour un résidu $y$ c'est déterminer
un entier $x$ tel que 
$$
	\gamma^x = y \mod p.
$$

Il n'existe d'algorithme efficace pour résoudre
le problème du logarithme discret. L'algorithme
de \voirfig{DLOG} dit :  "pas de bébés, pas de géants"
calcule le logarithme discret en ${\rm O}(\sqrt p) $ étapes.
Pour chaque étape, il s'agit de rechercher un élément
dans un ensemble de cardinalité ${\rm O}(\sqrt p)$
ce qui peut se faire à temps constant sur une machine
possédant suffisament de mémoire.

\begin{figure}
\centering
\begin{lstlisting}[style=algo, emph={baby, steps, giant}]
BSGS( entier p , residu g, residu y)
m := sqrt( p )
b := 1
i := 0
L := vide
// baby steps
tantque (i < m )
   stocker (i, b ) dans L
   b := b * g mod p  
   i := i + 1
ftq
j := 0
X := y 
b := inverse( b )
// giant steps
tantque X n'est pas dans L
     X := X * b modulo p
     j := j + 1    
ftq
i := index( X , L )  
retourner i + j*m
\end{lstlisting}
\caption{\label{DLOG} L'algorithme 
{\sl pas de bébés, pas de géants} calcule
le logarithme
discret en ${\rm O}(\sqrt p) $ étapes.}
\end{figure}

\begin{table}
\caption{\label{SOLOG}Solution de l'exercice pour $k\leq 15$.}
\begin{tabular}{rrrr}
\hline
$k$  &$p$   &$\gamma$ &$\log(1+\gamma)$\\
\hline
  3 &5 &2  &3 \\ 
  4 &11 &2  &8 \\ 
  5 &23 &5  &18 \\ 
  6 &47 &5  &38 \\ 
  7 &83 &2  &72 \\ 
  8 &167 &5  &134 \\ 
  9 &263 &5  &240 \\ 
 10 &563 &2  &530 \\ 
 11 &1187 &2  &646 \\ 
 12 &2063 &5  &150 \\ 
 13 &4127 &5  &1840 \\ 
 14 &8423 &5  &4222 \\ 
 15 &16487 &5  &14250\\
\end{tabular}
\end{table}

\begin{tps}
Il s'agit de coder une expérimentation
numérique autour du logarithme discret 
en langage C avec \gcc{gmp}, la bibliothèque de
calcul mulpiprécision de  \textbf{gnu} .
\begin{enumerate}
\item Ecrire une commande pour déterminer le  plus
petit premier $p$ de $k$ bits qui soit sûr.
\item Modifier la commande pour déterminer  le plus
petit générateur, disons $\gamma_p$, du groupe
mulptiplicatif $\grmul \fp$.
\item Implanter un algorithme naif pour déterminer le
logarithme discret du résidu $\gamma_p+1$.
\item Préciser le temps de calcul.
\item Estimer les limites.
\item Implanter l'algorithme "pas de bébés,  pas de géants" pour 
calculer le logarithme  discret pour des modules de
tailles raisonnable, disons  64-bits. 
\item Préciser le temps de calcul.
\item Estimer les limites.
\end{enumerate}
\end{tps}

\begin{figure}
\lstinputlisting[style=gcc]{sophie/sg.c}
\caption{\label{KBIT}Calcul du plus petit premier de $k$ bits en \gcc{gmp},
source à compiler avec la bibliothèque \gcc{lgmp}, comme 
dans ce \href{http://langevin.univ-tln.fr/cours/MLC/doc/sophie/makefile}{makefile}}
\end{figure}

\section{Diffie-Hellman}

Le protocole Diffie-Helleman s'appuie sur la difficulté
du problème du logarithme discret. Une fois fixé un entier
$\gamma$ d'ordre $p-1$ modulo $p$, Alice et Bob peuvent
s'échanger une quantité secrète :

\begin{enumerate}
\item Alice choisit un entier $a$. Calcule $A:=\gamma^a$ et envoie $A$ à Bob.
\item Bob choisit un entier $b$. Calcule $B:=\gamma^b$ et envoie $B$ à Alice.
\item Alice calcule $B^a$
\item Bob   calcule  $A^b$.
\end{enumerate}

L'associativité du produit modulaire montre que
les quantités calculées par Alice et Bob sont 
identiques. Les deux protagonistes
se sont inchangés une quantité $K$ secrète. Alice et Bob
doivent s'appuyer sur un tiers pour signer les éléments
échangés afin de ne pas se faire attaquer par 
un homme du milieu.

  
\begin{exercice}
Décrire un scénario d'attaque ``man in the midle''.
\end{exercice}



\section{Rivest-Shamir-Adleman}

Le cryptosystème \rsa\ est un système de chiffrement à clef publique
proposé \cite{RSA} par Rivest, Shamir et Adleman à la fin
des années 70 qui s'appuie sur certaines propriétés cachées
des nombres.


\begin{enumerate}
\item Bob définit la taille des messages, disons $2t$ bits.
\item Il construit au hasard deux nombres premiers $p$ et $q$
de $t$ bits.
\item Calcule les produits $n:=pq$ et $\phi:=(p-1)(q-1)$.
\item Choisit un entier $e$ premier avec $\phi$. 
\item Détermine $d$ l'inverse de $e$ modulo $\phi$.
\item Enfin, Bob publie la clé $(e,N)$.
\end{enumerate}

Alice utilise un algorithme d'exponentiation
modulaire pour calculer le chiffré $y$ d'un
clair  $x$, il s'agit de 
$$
       y := E( x ) := x^e \pmod n
$$ 

Bob effectue une tâche similaire pour
déchiffrer $y$, il calcule :
 
$$
       x := D( y ) = y^d \mod n
$$

La faisabilité du système s'appuie d'une part, sur la relative
abondance des nombres premiers, d'autre part sur l'existence
de tests de primalité probabiliste.
La correction du schéma repose sur un résultat d'arithmétique
: le théorème d'Euler. La  robustesse du système est attribuée
à l'apparente complexité du problème de factorisation des entiers. 
Enfin, l'exponentiation rapide permet une mise en oeuvre même
sur des machines modesres. 


\begin{tps}
D'aprés le manuel, la commande \shell{ssh} permet
d'identifier un utilisateur avec une clé \rsa\ pour
établir une connexion cryptée. Quels sont les noms des algorithmes
à clé symétrique disponibles ?
Aprés avoir construit une paire de clés \rsa\ avec \shell{ssh-keygen},
vérifié le fonctionnement de \shell{ssh-copy-id} et \shell{ssh},
vous utiliserez \shell{openssl} 
pour trouver les paramètres \rsa : module,
premiers etc\ldots de la clé privée \shell{id-rsa}.
Utilisez la commande \shell{bc} pour
vérifier les relations entre tous ces éléments. Refaire les mêmes
calculs avec \gcc{gmp}. Utilisez l'option \texttt{rsautl} de
\shell{openssl} pour crypter un petit fichier.
\end{tps}

\section{Correction de \rsa}

Soit $n=pq$ un entier \rsa. Les éléments non
inversibles sont les résidus qui sont des 
multiples de $p$ ou de $q$. Il y en a $p$+$q$-1,
le groupe des inversibles est d'ordre
$$
       \phi = pq - p - q + 1 = (p-1)(q-1)
$$ 

et donc, pour tout résidu inversible $z$,
le théorème d'Euler affirme que 

\begin{equation}
\label{REULER}
      z^\phi = 1.
\end{equation}

Par Bâchet, il existe $v$ tel que
$$
       ed =  1 + \phi v 
$$

Ainsi, pour tout inversible $z$

\begin{align*}
D( E( z ) ) &= D( z^e ) \\
           &= z^{ed} \\
           &= z^{1 + v\phi}\\
           &= z
\end{align*}

Le résultat tient aussi pour un élément non
inversible, c'est une conséquence du théorème Chinois.
Insistons que le fait que nous
aurions pu imaginer le contraire tant la probabilité
d'un clair non inversible est négligeable ! 

\begin{exercice}
Soit $p$ et $q$ deux nombres premier. Montrer le
nombre d'éléments inversibles modulo $pq$ est bien
égal à $(p-1)(q-1)$.
\end{exercice}

\section{Théorème d'Euler}

L'ensemble des inversibles modulo $n$ forme
un groupe  multiplicatif, généralement noté
$\zzi n$ son ordre est traditionnelement noté
$\varphi(n)$. En particulier, si $p$ est premier
alors 
$$
  \varphi(p) = p-1,\quad \varphi(p^r) = (p-1)p^{r-1}.
$$

\begin{exercice}
      $$ \varphi(p^r ) = p^{r-1} (p-1)$$
Expliquer !
\end{exercice}

La fonction Euler est multiplicative : 
si $m$ et $n$ sont premiers entre eux alors
\begin{equation}
\label{MULT}
      \varphi(mn) = \varphi(m)\varphi(n).
\end{equation}

\begin{theoreme}[Euler] Si $x$ est un résidu inversible
modulo $n$ alors
$$
      x^{\varphi(n)} = 1.
$$
\end{theoreme}
Il s'agit d'une manifestation du célèbre
théorème de Lagrange de la théorie des groupes. 

\begin{proof} Notons $y_1$, $y_2$,\ldots une énumération
des inversibles. Notons $w$ le produit de ces $\phi$ éléments.

\begin{align*}
   w &= (xy_1)(x y_2) \cdots (xy_\phi)\\
     &=  x^\phi w
\end{align*}
Il suffit alors de simplifier par $w$.
\end{proof}

\section{Répartition des premiers}

La toute première raison d'effectivité
concerne la bonne densité des nombres 
premiers. Il est facile de prouver la non finitude de
l'ensemble des nombres premiers.

Traditionnemlement, si on note $\pi(x)$ le nombre de premier inférieurs
à $x$, Legendre, puis Gauss, ont conjecturé la formule asymptotique :
$$
        \pi(x) \sim \frac x{\log x}
$$ 
Cette conjecture a été prouvée De La Vallée Poussin et Hadamard
à la fin du \siecle{19}, c'est le théorème des nombres premiers.
Le petit livre de Jean Itard \cite{itard}, contient une preuve
fausse mais fortement instructive d'Euler.

\begin{figure}
\includegraphics[scale=0.5]{src/prime.png}
\caption{\label{PI} Le calcul de $\pi(x)$ est facile à réaliser
avec le crible d'Eratostène, il permet de se convaincre
que $\pi(x) \log x \sim x$. }
\end{figure}

\begin{tps}
Implanter l'algorithme du crible d'Eratostène.
Vérifier  que $\pi(x)\sim\frac x{\log x}$
en reconstruisant la figure \voirfig{PI},
en utilisant \shell{gnuplot}.
\end{tps}

En 1912, Landau a présenté quatre problèmes difficiles,
100 ans aprés, ils sont toujours ouverts, Landau avait raison !

\begin{enumerate}
\item La conjecture de Goldbach : tout entier pair strictement supérieur à 2 peut s'écrire comme la somme de deux nombres premiers.
\item La conjecture des nombres premiers jumeaux : il existe une infinité de nombres premiers $p$ tels 
que $p+2$ est premier.
\item La conjecture de Legendre : il existe toujours au moins un nombre premier entre deux carrés parfaits consécutifs.
\item Il existe une infinité de nombres premiers de la forme $n^2 + 1$.
\end{enumerate}
\section{attaque par canal caché}
L'observation de la consommation
en courant d'une phase de chiffrement 
est le premier exemple d'attaque par canal 
caché, décrit par Paul Kocher dans les années
90. 
On suppose que le 
chiffrement \rsa\ est réalisé par un processeur qui sollicite un
co-processeur arithmétique pour effectuer les calculs modulaires.
Les opérations du co-processeur demandent plus de puissance,
et le produit modulaire de deux entiers différents demande
plus d'efforts qu'un carré modulaire \voirfig{SPA}.Au final,
l'analyse de la courbe révèle l'exposant secret
$s$ à acuse du traitement asymétrique des bits 
de l'exposant : un bit égal à 1 provoque une multiplication
et un carré, un bit nul génère un carré. Une simulation
de cette attaque utilisant \gcc{ltrace} est proposée dans \cite{DARK}.

\begin{figure}
\includegraphics[scale=0.5]{src/spa.png}
\caption{\label{SPA} L'analyse de la consomation
de courant révèle les bits de l'exposant secret.}
\end{figure}

\begin{exercice}
Donner la valeur de l'exposant secret utilisé dans
la phase de chiffrement de \voirfig{SPA}.
\end{exercice}


\section{Théorème chinois}

Soient $m$ et $n$ deux entiers. Avec les
anneaux  $\zz m$ et $\zz n$ on forme un
anneau produit  $\zz m \times \zz n$ en
opérant termes à termes :

\begin{align*}
(x,y)\oplus(x^\prime,y^\prime) &= (x+x^\prime, y+y^\prime)\\
(x,y)\otimes(x^\prime,y^\prime)&= (x\times x^\prime,  y\times y^\prime)\\
\end{align*}

L'application naturelle :
$$
           z\mapsto \Psi(z) := ( z \pmod m, z \pmod n )
$$
est un morphisme de l'anneau $\zz{mn}$ dans l'anneau
produit $\zz m \times \zz n$. 
$$
   \Psi(z+z^\prime) = \Psi(z) \oplus \Psi(z^\prime),
\quad
   \Psi(z\times z^\prime) = \Psi(z) \otimes \Psi(z^\prime).
$$


\begin{theoreme}
Si $m$ et $n$ sont premiers entre eux alors
$\Psi$ est un isomorphisme d'anneau.
\end{theoreme}
\begin{proof}
Comme les anneaux ont le même nombre d'éléments,
il suffit de montrer que nous sommes en présence
d'une injection. Le noyau est formé des résidus 
multiples de $m$ et $n$. 
\end{proof}

On retrouve des traces  du théorème dans
un traité de Qin Jiushao publié en 1247,
où le mathématicien chinois rapporte un
problème qui aurait été posé par le maître 
Sun Zi entre le \siecle 3 et le \siecle 5 :


{\sl Soit des objets dont on ignore le nombre. 
En les comptant 3 par 3 il en reste 2 ; 
en les comptant 5 par 5, il en reste 3 
et en les comptant 7 par 7, il en reste 2. 
Combien y a-t-il d'objets?
}


Le théorème de Bâchet-Bézout permet de construire
les antécédants de $(1,0)$ et $(0,1)$. En effet, une
relation $mu+nv=1$ montre que :
$$
mu\mapsto (0,1),\quad nv\mapsto (1,0).
$$

En particulier, l'antécédant de $(x,y)$ est $muy+nvx$.

Revenons sur les fonctions de chiffrement/déchiffrement
pour le module $pq$, dans le cas d'un clair non nécessairement
premier avec le module.

\begin{align*}
D( E( (x,y) ) ) &= D( (x^k,y^k) ) \\
           &= (x^{ks},y^{ks}) \\
           &= (x^{1 + v\phi},y^{1 + v\phi})\\
           &= (x,y)
\end{align*}
En effet, que $x$ soit inversible ou pas,
le petit théorème de Fermat montre que 
$x^{1 + v\phi} = x$, et c'est idem pour $y$.


On remarque que le théorème Chinois se généralise
sans peine. Si 
$$n = p_1^{r_1} p_2^{r_2}\cdots p_{f}^{r_f},$$
où les $p_i$ sont des nombres premiers alors

$$
\zz n \sim \zz {p_1^{r_1}}\times\zz {p_2^{r_2}}\times\cdots \times\zz {p_f^{r_f}}
$$

\begin{exercice}
Quels sont les antécédants de $(1,0,0)$, $(0,1,0)$ et
$(0,0,1)$ par l'isomorphisme naturel 

$$
\zz {30} \longrightarrow \zz {2}\times\zz {3}\times\zz {5}?
$$
\end{exercice}

\begin{exercice}
Soient des objets en nombre inconnu. Si on les compte par trois, il en reste deux ; par cinq, il en reste trois, et par sept, il en reste deux. Combien y a-t-il d’objets ?
\end{exercice}

\section{Attaque par faute}

On suppose qu'une boîte noire fait
du chiffrement \rsa\ en utilisant le
CRT pour calculer sur des nombres de
petite taille. Le déchiffrement de 
$z\in\zz n$ est calculé comme suit : 

\begin{enumerate}
\item décomposition de $z\mapsto (x,y)\in\zz p\times\zz q$
\item calcul de $X:=x^{sp}\pmod p$, où $sp=s\pmod {p-1}$
\item calcul de $Y:=y^{sq}\pmod q$, où $sq=s\pmod {q-1}$
\item fusion du résultat $Z$ par inversion $(X,Y)$
\end{enumerate}

\begin{center}
\includegraphics[scale=0.5]{crt.png}
\end{center}
L'attaque consiste à déchiffrer $z$, plusieurs fois en
essayant de provoquer des fautes lors du calcul sur une
composante. Dans le cas d'une puce electronique, 
le bombardement par des rayons X est un moyen
d'injection de faute. Si
la boîte envoie deux valeurs différentes $z'$ et $z''$, 
l'attaque est un succès, un des facteurs du module $n$ est tout
simplement :

$$
        \pgcd( z'' - z', n )
$$

En effet, si le calcul correct vérifie 
$\Psi(z') =(x',y')$, une erreur
de sur la première composante donne un
une autre valeur vérifiant 
$\Psi(z'')=(x'',y'')$ avec $x''\not=x'$ et
$y''=y'$. Ainsi, $\Psi(z'')-\Psi(z')$ 
est de la forme $(\not=0 , 0)$, et donc $z'' - z'$
est un multiple de $q$ mais pas de $p$.


Une simulation
de cette attaque utilisant \gcc{ptrace} est proposée dans \cite{DARK}.

\begin{tps}
Implanter le chiffrement RSA pour des
modules de $2t$ bits en langage \gcc{C}
sans utiliser de bibliothèque de calcul.
Il s'agit d'utiliser le CRT pour faire
les calculs modulo des premiers de $t$ bits. Le
paramètre $t$ dépend de l'architecture.
Utiliser \shell{gdb} pour simuler une attaque
par injection
de faute.
\end{tps}

\section{Racine carrée de l'unité}

\begin{proposition}
Soit $p$ un nombre premier impair, $r$ un
entier positif et $n=p^r$. L'équation 
$x^2 = 1$ possède exactement deux solutions
modulo $n$.
\end{proposition}

\begin{proof}
Soit $x$ une solution. Comme $p$ est premier
alors $x\equiv \pm1 \pmod p$. Notons $s$ le plus
grand entier tel que 
$x = \pm 1 + k {p^s}$, avec $(p,k)=1$. De la relation,

$$
x^2 = (\pm 1 + kp^s)^2 = 1 + 2kp^s + p^{2s}\equiv 1\pmod{p^r}
$$
on tire que $r\leq s$ i.e. $x=\pm 1\pmod{p^r}$.
\end{proof}

\begin{exercice}
Vérifier que l'énoncé précédent reste correcte pour
$p=2$ et $r\leq 2$ mais est erroné pour $r=3$ et
$r>3$.
\end{exercice}

\begin{corollaire}
Soit $n$ un entier impair. On note $f$ le
nombre de facteurs premiers divisant $n$.
L'équation
$$
          x^2 \equiv 1 \pmod n
$$
possède exactement $2^f$ solutions. 
\end{corollaire}

\begin{proof}
Il suffit d'appliquer le théorème des restes
chinois. En notant, $p_1$, $p_2$, \ldots, 
$p_f$ les premiers divisant $n$, l'isomorphisme
naturel :
$$
x\mapsto (x_1, x_2, \ldots, x_f)
$$
envoie une solution sur des composantes $x_i$ solutions
de $X^2 = 1 \pmod {p_i^{r_i}}$.
\end{proof}

\begin{exercice}
Quelles sont les racines de l'unité 
modulo 143 ?
\end{exercice}


\section{Théorème de Lagrange}

Soit $G$ un groupe multiplicatif. Le cardinal
de $G$ s'appelle l'ordre de $G$. Une partie $S$
de $G$ contenant $1$ est un sous-groupe de $G$
quand
$$
         \forall x,y\in S,\quad xy\in S
         \qquad \wedge \qquad
         \forall x\in S,\quad x^{-1}\in S.
$$
Les produits itérés
d'un élément $x$ forment un sous-groupe de $G$, on
le note $\gen x$, son ordre, qui est noté $\ord x$,
est appelé l'ordre de $x$.
Le groupe $G$ est dit cyclique
quand il existe un élément $x$ 
vérifiant 
$$
G = \ord x.
$$

\begin{exercice}
L'ordre de $x$ est égal au plus petit entier
non nul tel $r$ tel que $x^r$.
\end{exercice}

\begin{lemme}
Soit $x$ un élément d'un groupe $G$. Pour tout entier
$n$ tel que $x^n = 1$, l'ordre de $x$ divise $n$. 
\end{lemme}
\begin{proof}
Faire la division euclienne de
$n$ par l'ordre de $x$.
\end{proof}

\begin{exercice}
Soit $x$ d'ordre $n$, montrer que
$$
       \ord{x^t} = \frac{n}{(n,t)}
$$
\end{exercice}

\begin{theoreme}[Lagrange]
L'ordre d'un groupe est divisible par l'ordre
d'un sous-groupe arbitraire, et donc par celui
de l'ordre d'un élément arbitraire.
\end{theoreme}
\begin{proof}
On considère les ensembles 
$$
           t+S :=\{ t+s \mid s\in S\},\quad t\in G.
$$
Deux de ces ensembles sont égaux ou disjoints,
ils ont tous la même cardinalité.
\end{proof}

\begin{exercice}
Soit $n$ un entier positif. On note $S_n$
le groupe des permutations de $n$ lettres.
Ecrire un algorithme efficace pour calculer
l'ordre d'un élément de $S_n$.
\end{exercice}


\section{cycle des unités}


\begin{lemme}
\label{SU}
Soit $k$ un entier. Si $p$ est premier impair alors
$$
(1 + p)^{p^k} \equiv 1 + p^{k}p \pmod{p^{k}p^2}. \quad (*)
$$
\end{lemme}

\begin{proof}
Une induction sur $k$ ? Pourquoi pas! Tout d'abord, (*)
est vérifiée pour $k=0$ car $(1+p)^{p^0} = 1 + p$. Si
(*) est vraie pour un certain $k$ alors

\begin{align*}
    (1+p)^{p^{k+1}} &= (1 + p^{k}p + Xp^{k}p^2 )^p\\
                    &\equiv  1 + p^{k}p^2 \pmod{p^{k}p^3}
\end{align*}
\end{proof}

Le lemme précédent montre que $(1+p)$ est d'ordre
$p^{p-1}$ dans $\zzi{p^r}$.

\begin{exercice}
Montrer l'affirmation précédente. Comment ? 
En calculant $(1+p)^{p^{r-1}}$, et \ldots
\end{exercice}



Un groupe $G$ d'ordre $n$ est dit cyclique 
quand il est engendré par un élément. Un tel
groupe est possède $\varphi(n)$ générateurs car 
il est isomorphe au groupe $\zz n$, et
tous les inveribles modulo $n$ sont des  
générateurs de $\zz n$. En particulier,

\begin{equation}
\label{PHI}
\sum_{d\mid n } \varphi(d) = n
\end{equation}

Partant de cette formule, on montre qu'un groupe
abélien dans lequel il existe au plus $d$ éléments
d'ordre divisant $d$ est nécessairement cyclique.

\begin{theoreme} Le groupe multiplicatif de $\fp$ est cyclique.
\end{theoreme}
\begin{proof}
En effet , dans un corps commutatif, l'équation
$x^d=1$ possède au plus $d$ solutions!
\end{proof}

\section{structure multiplicative}

\begin{theoreme} [Gauss] 
Le groupe multiplicatif de $\zz {p^r}$ est cyclique.
\end{theoreme}
\begin{proof}
On  sait que son ordre est $\varphi(p^r)=(p-1)p^{r-1}$, il contient
un élément $x$ d'ordre $(p-1)$. Le lemme (\ref{SU}) montre que $(1+p)$ est 
d'ordre $p^{r-1}$, au final $(1+p)x$ engendre les inversibles.

\end{proof}

\begin{exercice}
Déterminer un élément d'ordre $4$ modulo $125$, puis un
élément d'ordre $100$.
\end{exercice}

\section{Nombre de Carmichael}

Un entier  composé $n$ est dit nombre de
Carmichael lorsque :
$$
        \forall x\in\zzi n,\quad x^{\varphi(n)} = 1.
$$
Ces nombres mettent en défaut le test de Fermat. Notons
qu'un tel nombre est nécessairement impair, ils sont
rares mais en nombre infini.

\begin{theoreme}[Korselt,1899] Un entier $n$ est 
de Carmichael si et seulement si $n$ est sans 
facteur premier double et pour tout diviseur 
premier $p$ de $n$, $p-1$ divise $n-1$.
\end{theoreme}
\begin{proof}
Supposons que $p^r$ divise $n$. Le groupe $\zzi {p^r}$
contient un élément d'ordre $p^{p-1}(p-1)$. Le théorème 
des restes chinois montre qu'il en est de même pour
$\zzi n$. L'ordre de cet élément divise $n-1$ et donc
$(p-1)$ divise $n-1$ mais aussi $r=1$.
Réciproquement, pour $x$ inversible modulo $n$, et pour
chaque diviseur $p$ de $n$, on a $x^{n-1}\equiv x^{p-1}\equiv 1\pmod{p}$.
Comme il existe un élément d'ordre $p-1$ modulo $p$, cette dernière
congruence montre que $p-1$ divise $n-1$.
\end{proof}

Les nombres de Carmichael possèdent au moins trois 
facteurs premiers.  Les premiers nombres de Carmichael 
sont : 561, 1105, 1729, 2465, 2821, 6601, 8911 etc\ldots 


\begin{exercice}
Soit $n$ un nombre de Carmichael. Montrer que $n$ possède
trois facteur premiers.
\end{exercice}


\section{Fermat, Solovay-Strassen}

Un test de primalité probabiliste s'appuie sur
un algorithme $T(x,n)$ qui prend en entrée un résidu $x$
modulo $n$ et renvoie VRAI ou FAUX. 

\begin{align*}
\exists x\not=0,\neg T(x,n)  &\limp n\,\text{composé}\\
\forall x\not=0, T(x,n) &\limp n\,\text{premier}\\
\end{align*}

Pour un entier composé $n$ (impair),
les résidus tels que $\neg T(x,n)$ 
sont des témoins de non-primalité,
les autres sont des menteurs. 
Nous notons $\mu( T, n )$ 
le nombre de menteurs pour l'entier $n$ 
du point de vue du test $T$, la probabilité
d'erreur aprés un test vaut : 
$$
\theta( T, n ) = \frac {\mu(T,n)}n 
$$
et le paramètre: 
$$
\Theta( T ) = \sup_{n\,\text{composé}} \theta( T,n )
$$
mesure l'efficacité du test. Quand $\Theta(T)<1$, 
il est possible de se convaincre 
du caractère premier d'un nombre,
cela d'autant plus rapidement 
que $\Theta(T)$ est petit.

Rappelons que, d'aprés Emile Borel, un individu 
néglige les évènements de probabilité moindre que 
$10^{-6}$, les terriens ceux de probabilité $10^{-15}$,
enfin  les évènements de probabilité moindre que 
$10^{-45}$ ne sont pas observables!

\subsection{Test de Fermat}

Il s'appuie directement sur le 
petit théorème de Fermat :

\begin{lstlisting}[style=algo]
Fermat( x, n )
y := expmod( x, n-1, n )
retourner y = 1
\end{lstlisting}

On constate que le test de Fermat est vraiment efficace
sur les nombres primaires. En effet, si $n=p^r$ avec
$p$ impair alors le groupe $\zzi n$ est cyclique d'ordre
$\phi(n)$. Un calcul direct montre que $\pgcd( n-1, \varphi(n) ) = p-1$,
le nombre menteurs de Fermat est majoré par $p-1$ et
$$
  \theta( F, p^r ) \leq \frac 1{p^{r-1}} \ll \frac 13.
$$

On constate que le test de Fermat se comporte assez bien
sur les nombres composés ayant au moin un témoin de
composition. Pour un tel nombre $n$, il existe un
élément $x$ tel que $x^n \not = 1$. Cet élément permet
de faire d'associé un témoin $xy$ à chaque menteur de Fermat,
au final 
$$
      \theta( F, n ) < \frac 12.
$$

Malheureusement, d'aprés les arithméticiens, il
existe une infinité de nombre entiers $n$ sans
témoin de Fermat. Il s'agit des nombres de Carmichael,
pour lesquels :

$$\theta(F, n) = \frac{\varphi(n)}n\rightarrow 1 = \Theta(F).$$


\subsection{Test de Solovay-Strassen}


$$
S(x,n) := x^{\frac{n-1}2} = \pm 1
$$

ce teste est plus efficace que le
test de Fermat, c'est le test 
de Solovay-Strassen "faible". Malheureusement,
on peut encore prouver que $\Theta(S) = 1$ ! La
version originale de ce test détecte tous les
nombres composés, mais elle utilise le symbole
de Jacobi qui est hors programme.

On peut comprendre intuitivement, les raisons qui
font que le test de Solovay-Strassen faible est 
meilleur que le test de Fermat. Si $x$ est un
Fermat-menteur pour l'entier $n$, $x^{n-1}=1$ mezalor 
$x^{\frac {n-1}2}$ est une racine carrée de l'unité,
et la probabilité que cette dernière soit égale 
à 1 est potentielement $2^{1-f}$, où $f$ désigne le nombre de diviseurs
premiers de $n$.

\begin{exercice}
Utiliser un programme pour déterminer les nombres
composés impair $n\leq 1024$ qui possèdent plus
de 0.25 menteurs.
\end{exercice}

\newpage

\section{Test de Rabin-Miller}

\begin{multicols}2
\begin{lstlisting}[style=algo]
Miller-Rabin( n : nombre )
var
    k := 0 
    m := n-1
    z := n-1
debut
tantque ( pair( m ) )
   m:= m / 2
   k:= k + 1
ftq
x := aleas( n )
y := expmod(x, m , n)

tantque ( k >= 0 )
   y := prd( y, y, n)
   si ( y = 1 ) 
      retourner 
         minus( z )
   fsi 
   z := y
   k := k-1
ftq
retourner faux
fin
\end{lstlisting}
\end{multicols}

\begin{theoreme} 
Pour un nombre de Carmichael $n$,
 on a : $\theta( MR, n) < \frac 14$.
\end{theoreme}
\begin{proof}
Pour $n-1=2^km$, $m$ impair, convenons de parler 
des témoins, et menteurs de niveau $0\leq l \leq 
k$. Un menteur $x$ de niveau 0 est caractérisé par
$x^m=1$, inversement, un témoin de niveau 0 par
$x^m\not=\pm 1$. Si $p$ est un premier divisant $n$
alors $(p-1)$ ne divise pas $m$ et donc il existe
des éléments vérifiant $x^m\not=1 \mod p$. Au final,
pour le niveau 0, la proportion de menteurs
est inférieur à 1/4. Si $x=(x_1,x_2,\ldots,x_r)$ est
un menteur au niveau $l$, alors pour chaque $j$,
$(\ldots,x_{j-1},1,x_{j+1},\ldots)$ est un témoin
de niveau $l$, à nouveau, la proportion des
menteurs de niveau $l$ est moindre que 1/4.
\end{proof}

\begin{remarque} 
Le théorème est valide pour tous
les nombres composés, au final :

$$\Theta( MR ) < \frac 14.$$

\end{remarque}

\begin{exercice}
Pour un impair $n$, montrer que :
$$
\theta(R, n) \leq \theta(S, n) \leq \theta( F, n) 
$$
\end{exercice}.


\section{Premiers industriels}



Le résultat de la section précédente montre qu'il n'y a pas de grand
risque à considérer premier un nombre passant le test
de Rabin 25 fois consécutives, évènement de probabilité
moindre que $2^{-50}$. Pour se faire une idée, c'est un événement
moins probable que de gagner deux fois de suite le gros
lot du loto!

\begin{exercice}
Vérifier ce qui vient d'être dit à propos du loto et du test
de Rabin.
\end{exercice}




\begin{figure}
\includegraphics[scale=0.5]{src/tests.png}
\caption{\label{COMP}comparaison des tests de Fermat, Solovay-Strassen et Rabin-Miller.
On constate que la proportion de menteurs pour le teste de Rabin est inférieur à 0.25.}
\end{figure}


\begin{tps}
Programmer l'expérience numérique de la figure \voirfig{COMP}. 
\end{tps}



\begin{tps}
Implanter votre propre algorithme de Rabin-Miller
en utilisant les fonctions arithmétiques de base
de la bibiothèque \gcc{gmp} pour construire
des nombres premiers industriels. 
\end{tps}


\begin{figure}
\lstinputlisting[style=gcc]{src/grand.c}
\caption{\label{GRAND}Un exemple de tirage aléatoire avec \gcc{gmp}}
\end{figure}

\nocite{*}
\bibliographystyle{plain}
\bibliography{mlc}

\end{document} 
