% Last modified: <arith_info.tex modifié par  Guillaume CONNAN le mercredi 6 février 2013 à 09h 15min 04s>


\chapterimage{wiles}
\chaptertext{En  1995,   le  mathématicien  Andrew   \textsc{Wiles}  fit
  sensation en démontrant le grand théorème de \textsc{Fermat}. Ce vieux
  problème  d'arithmétique  avait  tenu  les  mathématiciens  en  haleine
  pendant trois  siècles. Pour le vaincre,  \textsc{Wiles} travailla sur
  les  courbes elliptiques  dont l'étude  mêle  arithmétique, structures
  algébriques,  géométrie,  analyse. Ces  travaux  et  leurs dérivés  ont
  permis d'assurer la sécurité des cartes à puces, 
  des échanges  sur internet: la recherche  fondamentale en mathématiques
  sur   des   nombres   entiers   fit   faire  un   bon   en   avant   à
  l'informatique. Quoi de plus normal après tout:  un ordinateur n'est rien de
  plus qu'une machine calculant avec des zéros et des uns... }

\chapter{Arithmétique pour l'informatique}

\section{Structures mères}


\subsection{Lois de composition interne}


\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
  \includegraphics[width=3cm]{juge}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-4.6cm}
\begin{minipage}[t]{\linewidth}

La  notion  de loi  de  composition  interne  est primordiale,  tant  en
mathématiques  qu'en  informatique: la  notion  de  type en  informatique
impose un certain respect de la loi...

\caml
\begin{lstlisting}[caption={}]
        Objective Caml version 3.12.0

# 1 + 1.5 ;;
      ^^^
"Error: This expression has type float but an expression was expected of type int"
# 1. +. 1.5 ;;
- : float = 2.5
# 1 + 2 ;;
- : int = 3
\end{lstlisting}
\end{minipage}

On n'additionne pas n'importe qui  avec n'importe quoi: il ne faudra pas
confondre  la loi  \verb|+.| qui  opère sur  les flottants  avec  la loi
\verb|+| qui opère sur les entiers...

Formalisons la chose:

\begin{definition}[Loi de composition interne]
Un loi de composition interne $ \star$ définie sur un ensemble E est une
application de $E\times E$ vers E. On dit alors que $(E,\star)$ est un \textbf{magma}.
\end{definition}

Le plus souvent, si  $\star$ est la loi, on note $x  \star y$ au lieu de
$\star(x,y)$.

Par  exemple  $(\bbn,+)$, $(\PR(E),\cap)$,  un  langage  L  muni de  la
concaténation, sont trois magmas mais $(\bbn,-)$ n'est pas un magma.


\begin{definition}[Élément neutre]
C'est un élément de E qui  vérifie, pour tout élément $x$ de E, $$e\star
x=x\star e=x$$
\end{definition}


Quels sont les éléments neutres des  magmas cités plus haut? Si un magma
admet un élément neutre, celui-ci est unique: pouvez-vous le démontrer?

\begin{definition}[Monoïde]
On appelle monoïde  tout couple $(E,\star)$ tel que  la loi $\star$ soit
\textit{associative}. Si en plus le  monoïde admet un élément neutre, on
dit que le monoïde est \textbf{libre} (ou \textbf{unitaire}).
\end{definition}

Les  magmas  précédemment  cités  sont-ils des  monoïdes?  Des  monoïdes
libres?



\begin{theoreme}[Sous-monoïde]
Soit  $(E,\star)$  un   monoïde  et  $M\subseteq  E$  tel   que  M  soit
\textit{stable} par $\star$. Alors  $(M,\star)$ est un monoïde: c'est un
\textbf{sous-monoïde} de $(E,\star)$.
\end{theoreme}

Enfin,  le  définition suivante  introduit  une  notion fondamentale  en
arithmétique et en algèbre en général:

\begin{definition}[Élément inversible]
Soit $(E,\star)$  un monoïde unitaire d'élément neutre  $e$.  Un élément
$x$ de E est inversible (ou 
symétrisable)  par  rapport  à  $\star$  s'il  existe  $y$  dans  E  tel
que $$x\star y =y\star x=e$$
\end{definition}

Montrez que si l'élément neutre existe $a$ admet un symétrique, celui-ci
est unique. 

\subsection{Les groupes}


\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=3cm]{Evariste}
\caption{É. \textsc{Galois} (1811 - 1832)}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-4.6cm}
\begin{minipage}[t]{\linewidth}


Mort dans un duel à l'âge  de vingt ans, Évariste \textsc{Galois} a tout
de même  eu le temps de  révolutionner les mathématiques  et ses travaux
ont  eu une  très grande  influence sur  le développement  récent  de la
cryptographie depuis ces trente dernières années.

La notion  de groupe  a d'abord  été liée à  la recherche  des solutions
d'une équation:  peut-on trouver  un nombre entier  naturel $n$  tel que
$n+2=0$?

Comme  ce genre  de problème  a besoin  d'être résolu  (j'ai  monté deux
étages  et je  suis arrivé  au  rez-de-chaussée: de  quel étage  suis-je
parti?), la structure de groupe a été étudiée de près. 

Vous me direz,  ce genre de problème n'est  pas vraiment révolutionnaire
ni  utile. Pourtant,  nous  verrons  en TD  que  cette structure  permet
d'assurer la sécurité des cartes à puces et des échanges sur la toile...



\end{minipage}



Donnons-en tout d'abord une définition:


\begin{definition}[Groupe]
Un groupe est un monoïde unitaire tel que tout élément est inversible.
\end{definition}


Les lois de groupe sont souvent notées $\times$ ou $+$.

On note alors:

$$\underbrace{x+x+\cdots+x}_{k\text{ fois}}=k\cdot x\qquad\text{ou}\qquad
\underbrace{x\times x\times\cdots\times x}_{k\text{ fois}}=x^k$$

Que peut-on dire de $\bbz$ muni de l'addition?


Nous travaillerons en général avec des groupes ayant seulement un nombre
fini d'éléments:

\begin{definition}[Groupe fini]
  Soit $(G,+)$ un groupe d'élément neutre $0_E$ ayant un nombre fini d'éléments. Le cardinal de
  G est appelé l'\textbf{ordre du groupe} G.

Soit $x$ un élément de G.
L'\textbf{ordre de l'élément}  $x$ est le plus petit  entier $k$ tel que
$k\cdot x=0$.
\end{definition}

Étudions maintenant le groupe qui nous occupera le restant de notre chapitre...

\subsection{Le groupe (Z/nZ,+)}


\subsubsection{Congruence}

%Reparlons un moment de relation d'équivalence...

\begin{definition}[Congruence des entiers]
Soit $n$ un entier naturel non nul.

Deux  éléments $a$  et  $b$ du  groupe  $(\bbz,+)$ sont  \textbf{congrus
  modulo}  $n$ si,  et  seulement si,  ils  ont le  même  reste dans  la
division par $n$.
On note $$a\equiv b\ (\modu n)$$ et  on lit \og \textit{a est congru à b
  modulo n}\fg{}.
\end{definition}


\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3cm]{zorglub}
%\caption{É. \textsc{Galois} (1811 - 1832)}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-4.6cm}
\begin{minipage}[t]{\linewidth}

Cette notion  de \og modulo\fg{} est  entrée dans le  langage courant du
geek:


\begin{quote}
  {\it
\og Well, LISP seems to work okay now, modulo that GC bug.\fg{}

\og I feel fine today modulo a slight headache.\fg{}}
\begin{flushright}
  in \og The New Hacker's Dictionnary\fg{}\\
\href{http://outpost9.com/reference/jargon/jargon\_28.html\#SEC35}{http://outpost9.com/reference/jargon/jargon\_28.html\#SEC35}
\end{flushright}
\end{quote}


Vérifiez   tout  d'abord  que   la  relation   de  congruence   est  une
\textit{relation d'équivalence}.
On peut  donc définir un  ensemble quotient, c'est-à-dire  les relations
d'équivalence.

\end{minipage}


Prenons un exemple  innocent: travaillons modulo 2. Combien  y a-t-il de
classes d'équivalence? Quel est l'ensemble quotient?

On a pris l'habitude de noter $\ofr{\bbz}{n\bbz}$ l'ensemble quotient de
la  relation  de  congruence  modulo   $n$.  On  notera  dans  ce  cours
$\overline{k}^n$ la classe de $k$ modulo $n$.


\textbf{Attention!}
\caml
  La  plupart des  langages possèdent  une fonction  \verb+mod+  ou quelque
  chose d'équivalent.  Ainsi
  \verb+a mod n+ renvoie parfois l'élément de la classe d'équivalence de
  \verb+a+ compris entre 0 et  $n-1$, d'autre fois entre $-n+1$ et $n-1$
  selon le signe de $a$ mais dans tous les cas le nombre qui vérifie
  \verb|a = (a/n)*n + x mod n|.

  \begin{lstlisting}[caption={}]
        Objective Caml version 3.12.0

# 17 mod 3 ;;
- : int = 2
# -17 mod 3 ;;
- : int = -2
# -17/3;;
- : int = -5
# (-17 / 3)*3 + (-17 mod 3) ;;
- : int = -17
  \end{lstlisting}


\sage

\begin{lstlisting}[caption={}]
Python 2.7.2+ (default, Oct 4 2011, 20:06:09)
>>> 17 % 3
2
>>> -17 % 3
1
>>> -17/3
-6
>>> (-17 // 3)*3 + (-17 % 3)
-17
\end{lstlisting}


\caml

\subsubsection{Division euclidienne}

Pour éviter ce genre d'ambiguïté, nous allons nous mettre d'accord grâce
au théorème suivant:

\begin{theoreme}[Division euclidienne]
Soit $a$ un entier relatif et $b$ un entier naturel non
nul.

Il existe un unique couple d'entiers $(q,r)$ tels que
$$a=bq+r\quad\text{avec}\quad 0 \leqslant r<b$$

Déterminer $q$ et $r$, c'est effectuer la division euclidienne de
$a$ par $b$.

On appelle $a$ le dividende, $b$ le diviseur, $q$ le quotient et
$r$ le reste.
\end{theoreme}

\begin{remarque}
Si  l'on   remplace  la  condition   sur  le  reste  par   $0  \leqslant
\left|r\right|<b$,  il   n'y  a   plus  unicité  (c'est   d'ailleurs  la
formulation  habituelle   qui  permet  de  travailler   dans  les  mêmes
conditions   dans    des   structures   plus    vastes   qu'on   appelle
\textit{anneaux euclidiens}) ce qui explique que \textsf{Python} et \textsf{Ocaml} ne sont
pas d'accord...
\end{remarque}


\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=3cm]{euclide_papyrus}
\caption{Papyrus d'une  copie des éléments  d'\textsc{Euclide} datant du
  premier siècle après JC, quatre siècles après la mort du mathématicien grec.}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-4.4cm}
\begin{minipage}[t]{\linewidth}

Qui dit théorème dit démonstration. Le principe de celle qui va
suivre est le schéma suivant

\begin{center}
\includegraphics{analyse2.8}
\end{center}


qui traduit qu'un entier $a$ est soit un multiple de $b$, soit est
encadré par deux multiples consécutifs de $b$.

L'énoncé contient deux termes importants : <<~il $existe$ un
$unique$ couple~>>. Il va donc falloir prouver deux choses :

- qu'un tel couple existe

- qu'il est unique.
\end{minipage}
\sm

Traitons d'abord le cas particulier où $a\in\bbn$.
\begin{itemize}

\item[\textbf{Existence}]

Le monde des multiples de $b$ se sépare en deux catégories : ceux
qui sont inférieurs (ou égaux) à $a$ et les autres.

 En d'autres termes, appelons $\MR_i$ l'ensemble des multiples de
 $b$ inférieurs ou égaux à $a$. Cet ensemble $\MR_i$ est non vide
 car il contient au moins 0. De plus $\MR_i$ est majoré par $a$
 puisqu'on l'a défini comme ça.

 L'ensemble $\MR_i$ est donc une partie de $\bbn$ non vide et
 majorée : $\MR_i$ admet donc un plus grand élément d'après une
 propriété que vous avez démontrée.

 Appelons $\mu$ ce plus grand élément. C'est un multiple de $b$, donc il
 existe un entier $q$ tel que $\mu=qb$. 

 Le multiple suivant est $\mu+b=qb+b=(q+1)b$ qui n'appartient pas à $\MR_i$
 car il est strictement supérieur au maximum $\mu$.

 On en déduit que $$bq\ie a<bq+b$$

 C'est ce que nous <<~montrait~>> le dessin. Il nous indique aussi
 que le reste correspond en fait à la différence $a-bq$.

 Posons donc $r=a-bq$ : on a alors $a=bq+r$ et donc $bq\ie
 bq+r<bq+b$, c'est à dire $0\ie r<b$

 \sm

 Nous avons donc démontré l'existence de deux entiers $q$ et $r$
 tels que $a=bq+r$ avec $0\ie r<b$, \textit{inspirés} que nous
 étions par un joli dessin.

 Il reste à démontrer l'unicité d'un tel couple d'entiers.

\item[\textbf{unicité}]

Une méthode habituelle pour démontrer une unicité est \textit{supposer}
l'existence d'un second couple.

Supposons donc qu'il existe deux couples d'entiers $(b,q)$ et
$(b',q')$ vérifiant

\begin{align*}
a&=bq+r\quad\text{avec}\quad 0\ie r<b\\
a&=bq'+r'\quad\text{avec}\quad 0\ie r'<b
\end{align*}

Effectuons la différence membre à membre de ces égalités. On
obtient

$$0=b(q-q')+r-r'\quad\text{avec}\quad -b<r-r'<b$$

Vous en déduisez comme moi que $r-r'$ est un multiple de $b$, et
que ce multiple est strictement compris entre $-b$ et $b$.

%\dessin{3}

Le seul multiple qui convient est 0, donc $r-r'=0$ et par suite
$q-q'=0$, c'est à dire que $r=r'$ et $q=q'$. Dès lors il n'existe
qu'un seul couple solution.


\end{itemize}


\begin{definition}[Diviseur]
Un entier non nul $d$ divise (ou est un diviseur de) l'entier $a$ si, et
seulement si, le reste de la division euclidienne de $a$ par $d$ est nul.
\end{definition}


\begin{recherche}
Pourquoi  dit-on habituellement  qu'on  ne peut  pas  diviser par  zéro?
D'ailleurs, dans de  nombreux cas, le debugger de  votre langage préféré
renvoie des messages du type \verb+Exception: Division_by_zero+...

Vous traiterez ensuite le cas où $a$ est strictement négatif
connaissant bien sûr le résultat pour $a\in\bbn$.
\end{recherche}


En général, on prend  comme \textit{représentant principal} de la classe
de $a$ modulo $n$ le reste de la division de $a$ par $n$.
Par exemple, on notera:

$$\ofr{\bbz}{8\bbz}=\bigl\{\overline{0}^8,\overline{1}^8,\overline{2}^8,\overline{3}^8,\overline{4}^8,\overline{5}^8,\overline{6}^8,\overline{7}^8\bigr\}$$

\begin{DANGER}
  Notez  bien   que  $\overline{0}^8$,   $\overline{1}^8$,  etc.  sont   des  ensembles
  d'entiers!...

Ici, $\overline{0}^8=\bigl\{...,-16,-8,0,8,16,24,32,...\bigr\}$

Par  \textbf{ABUS DE  NOTATION},  on  écrira le  plus  souvent $k$  pour
désigner  $\overline{k}^n$ ce  qui  nous  amènera à  écrire  par exemple  que
$8=0$, voire $3\times 5 = 7 = -1$ comme nous le verrons plus loin...
\end{DANGER}




















Donnons quelques théorèmes importants que vous démontrerez en TD:

\begin{theoreme}
Soit $a$ et $b$ deux entiers et $n$ un entier naturel.

$a$ est congru à $b$ modulo $n$ si et seulement si $a-b$ est un
multiple de $n$
\end{theoreme}

Cette propriété nous permet en fait d'exploiter autrement les
congruences. En effet, si par exemple $x\equiv 5 (\modu 32)$, cela
signifie qu'il existe un entier $k$ tel que  $x-5=32k$, soit
encore que $x=5+32k$.


Voyons une autre formulation utile:

\begin{theoreme}
$$a\equiv b (\modu n)\ssi \exists k\in \bbz\ \mid 
\ a=b+kn$$
\end{theoreme}
Ça ressemble  à la division euclidienne de  $a$ par $n$ mais  ça peut ne
pas l'être : n'oubliez pas que le reste doit 
obligatoirement être positif et strictement inférieur au diviseur.

Par exemple on a bien $33\equiv 97 (\modu 32)$ mais 97 n'est certes pas
le reste de la division de 33 par 32.



Il faudrait maintenant pouvoir définir des opérations sur les classes de
congruences. On aurait envie de dire  que la somme des classes de $a$ et
de $b$ modulo $n$ est en fait la classe de la somme $a+b$
modulo $n$ et pareil pour la multiplication mais est-ce licite?


\subsubsection{Premières propriétés}

Nous aurons besoin des propriétés suivantes que vous allez prouver en TD:

\begin{theoreme}\label{th::congru}
  \begin{enumerate}
\item $\card \left(\ofr{\Z}{n\Z}\right)=n$
  \item $a\equiv a(\modu n)$
\item Si $a\equiv b(\modu n)$, alors $b\equiv a(\modu n)$
\item Si $a\equiv b(\modu n)$ et $b\equiv c(\modu n)$, alors $a\equiv c(\modu n)$
\item Si $a\equiv b(\modu n)$ et $a'\equiv b'(\modu n)$, alors $$a+a'\equiv
b+b'\ (\modu n)\quad a-a'\equiv b-b'\ (\modu n)\quad aa'\equiv bb'\ (\modu n)$$
\item Si $a\equiv b(\modu n)$, alors, pour tout $p\in\bbn$, $a^p\equiv
b^p(\modu n)$

  \end{enumerate}
\end{theoreme}

En fait, il faut retenir qu'on peut additionner, soustraire,
multiplier des congruences \textbf{de même module}.

Nous avons oublié la division et  pour cause: c'est une opération à haut
risque quand on travaille avec des entiers!

Par exemple $12\equiv 0(\modu 6)$, mais $\fr{12}{3}\not\equiv
\fr{0}{3}(\modu 6)$.


\subsubsection{Loi de groupe}



La propriété  5 du théorème\vref{th::congru} nous permet  de définir une
loi d'addition et une loi de multiplication sur $\ofr{\Z}{n\Z}$:

\begin{theoreme}
  $\forall           n\in          \N^*,\          \forall(x,y)\in\Z^2,\quad
  \overline{x}^n+\overline{y}^n=\overline{x+y}^n,\quad    \overline{x}^n\cdot
  \overline{y}^n=\overline{x\cdot y}^n$ 
\end{theoreme}

Écrivez  par  exemple  les  lois  d'addition  et  de  multiplication  de
$\ofr{\Z}{7\Z}$ et $\ofr{\Z}{8\Z}$: des remarques?

Est-ce           que          $\left(\ofr{\Z}{n\Z},+\right)$          et
$\left(\ofr{\Z}{n\Z},\cdot\right)$ sont des groupes? 


Dire que $p$ est \textbf{inversible modulo} $n$ signifie qu'il existe un
entier $p'$ tel que $p\cdot p' = 1 (\modu n)$, c'est-à-dire qu'il existe
un entier $k$ tel que $pp' =  1 +kn$. Nous venons de voir pour certaines
valeurs de $n$, cette recherche semble possible et qu'elle pose problème
dans d'autres  cas. Nous  allons avoir besoin  de quelques  théorèmes de
plus pour  conclure à coup  sûr, cette notion d'inverse  modulaire étant
centrale en cryptographie donc en sécurité informatique.


\subsubsection{Calcul modulaire en Caml}

On peut créer un type enregistrement pour travailler modulo un entier:

\begin{lstlisting}[caption={}]
type classe  =
  {representant : int ; modulo : int};;
\end{lstlisting}

Pour plus de commodité, on  va créer un opérateur infixe correspondant
à notre $\cdots\equiv\cdots[\cdots]$:

\begin{lstlisting}[caption={}]
let (%) a n = {representant = (a mod n); modulo = n};;
\end{lstlisting}

On obtient alors:

\begin{lstlisting}[caption={}]
# 13 % 3;;
- : classe = {representant = 1; modulo = 3}
\end{lstlisting}

On peut ensuite créer des lois induites:

\begin{lstlisting}[caption={}]
exception Classes_incompatibles;;

let loi_induite loi =  fun a  b -> 
  {modulo =
      if a.modulo = b.modulo
      then a.modulo 
      else raise Classes_incompatibles ;
   representant =
      (loi (a.representant) (b.representant)) mod (a.modulo)
  };; 

let ( +% ) = loi_induite  ( + ) ;;
let ( *% ) = loi_induite  ( * ) ;;
\end{lstlisting}


Alors, pour obtenir $9 + 7$ modulo 5:

\begin{lstlisting}[caption={}]
# (9%5) *% (7%5);;
- : classe = {representant = 3; modulo = 5}
\end{lstlisting}

\section{Divisibilité dans Z}


 \subsection{Propriété fondamentale de N}

Nous admettrons  la propriété suivante qui  nous sera très  utile par la
suite:

\begin{theoreme}
Toute partie non vide de $\bbn$ possède un plus petit
élément.
\end{theoreme}

Est-ce que cette propriété est encore vraie dans $\Z$? Dans $\R$?

\subsection{PGCD}


Considérons un entier relatif $a$. On notera $\DR(a)$ l'ensemble de ses diviseurs dans $\bbz$.

Par exemple, $\DR(0)=\bbz$, $\DR(1)=\ac{-1,1}$, $\DR(12)=\ac{-12,-6,-4,-3,-2,-1,1,2,3,4,6,12}$ et plus généralement $$\DR(a)=\ac{-|a|,...,-1,1,...,|a|}$$


\begin{definition}[PGCD]
  Soit $a$ et $b$ deux entiers. On appelle PGCD de $a$ et $b$ et on note $a\wedge b$ l'entier défini de la manière suivante:
\begin{itemize}
\item $0\wedge 0=0$
\item Si $a$ et $b$ ne sont pas simultanément nuls, $a\wedge b$ est le plus grand entier naturel qui divise simultanément $a$ et $b$.
\end{itemize}
\end{definition}


Le  PGCD   de  $a$   et  $b$   est  donc  le   plus  grand   élément  de
$\DR(a)\cap\DR(b)$ : la notation le rappelle. 
Comme toute  partie non vide  et majorée de  $\bbn$ admet un  plus grand
élément,  cette  définition  en  est  bien  une  car  $\DR(a)\cap\DR(b)$
contient au moins $1$. 


\subsection{\'Egalité de Bézout}


\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=3cm]{bezout_cours}
\caption{Première  page  du  cours  écrit  par  Étienne  \textsc{Bézout}
  (1730-1783)%   connu pour de  nombreux travaux  dont l'égalité  que nous
  %  allons découvrir  et la  division  des polynômes  que nous  verrons
  % bientôt.
}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-7cm}
\begin{minipage}[t]{\linewidth}
Voici la clé de notre section: nous allons montrer que notre PGCD est
en fait une  combinaison linéaire de $a$ et  de $b$. Considérons d'abord
le  cas  où  $a$ et  $b$  sont  non  nuls  et notons  $$S=\ac{au+bv\  |\
  (u,v)\in\bbz^2\ \text{ et } au+bv>0}$$

L'ensemble $S$ est constitué d'entiers naturels et est non vide car il contient au moins $a^2+b^2$ : il admet donc un unique \textbf{plus petit élément} que nous noterons $d$ qui s'écrit donc $d=au_0+bv_0$.\\
Notre mission  va bien sûr  consister à prouver  que $d$ est en  fait le
PGCD de $a$ et $b$. 
\end{minipage}


Nous allons pour cela utiliser une ficelle classique : introduire le reste de la division euclidienne de $a$ par $d$ et utiliser le fait que  $d$  est le plus petit élément de $S$ puis raisonner par l'absurde.

La division de $a$ par $d$ s'écrit:

$$a=dq+r \quad\text{avec}\quad 0\ie r<d$$


\textbf{Supposons} que $r>0$, alors
$$r=a-dq=a-q(au_0+bv_0)=a(1-qu_0)+b(-qv_0)>0$$
et donc  $r\in S$ or $r<d$. C'est  impossible car $d$ est  le plus petit
élément de $S$ : \textbf{contradiction}.

Notre supposition de départ est  donc fausse et $r=0$. Nous en déduisons
que $d$ divise $a$.

On montre de manière similaire que $d$ divise $b$. Ainsi
$$d \text{ est un diviseur commun de } a\text{ et } b$$

Il  nous reste  à montrer  que c'est  le plus  grand.  Soit  $\delta$ un
diviseur commun à $a$ et  $b$ quelconque.  On montre facilement qu'alors
$\delta$ divise toute combinaison linéaire 
de $a$ et  de $b$ donc en particulier  $\delta$ divise $au_0+bv_0$ donc
$d$. Alors $c \leqslant |d|=d$, donc $d$ est
bien le plus grand des diviseurs.

 \sm


Il  faut encore  vérifier que  le PGCD  est \textbf{unique}.  La méthode
habituelle  est  de  supposer  qu'il  existe un  deuxième  PGCD,  disons
$d'$. Alors $d\ie d'$ car $d'$ est le plus grand diviseur puis $d'\ie d$
car $d$ aussi et finalement $d=d'$ ce qui assure l'unicité.

\sm

Comme $|a|=\pm1\times a+0\times 0$,  l'égalité tient toujours si $b$ (ou
$a$) est nul, donc

\begin{theoreme}[Égalité de \textsc{Bézout}]
  Soit $a$ et $b$ deux entiers relatifs.
Si $d=a\wedge b$, alors il existe deux entiers $u$ et $v$ tels que: $$au+bv=d$$
\end{theoreme}


\subsection{Algorithme des différences}

Voyons maintenant une propriété qui va être à la base de la construction
algorithmique du PGCD:

\begin{theoreme}
Si $ab\neq 0$  et $k$ un entier quelconque $$a\wedge(b+ka)=a\wedge b$$ et en particulier $$a\wedge b=a\wedge(b-a)=a\wedge(a-b)$$
\end{theoreme}


Notons $a\wedge b=d$ et $a\wedge(b+ka)=d'$. Alors 

\begin{itemize}
\item $d$ divisant $a$ et $b$, $d$ divise $(ka+b)$  et $a$ donc divise $d'$ d'après une propriété précédente.
\item d'autre part, $d'$ divise $a$ et $b+ka$, donc divise $b+ka-ka$, donc $b$, donc $d'$ est un diviseur commun à $a$ et $b$ donc $d'$ divise $d$.
\end{itemize}

Comme $d|d'$ et $d'|d$, on a donc $d=d'$.

\sm

Cette propriété va  nous permettre de fabriquer un  algorithme de calcul
de  $a\wedge b$.  En effet,  si $a\se  b$, et  comme  $a\wedge b=b\wedge
(a-b)$,  on  calcule  le  PGCD  de  deux  entiers  plus  petits.  Et  on
réitère. Par exemple : 

$$15\wedge 12=12\wedge 3=9\wedge 3=6\wedge 3=3\wedge 3=3\wedge0=3$$


Comment se persuader que cette  descente aboutit ? Nous pouvons aisément
nous convaincre sans se perdre dans trop de formalisme que:


\begin{theoreme}[Suite strictement décroissante d'entiers naturels]
Toute suite strictement décroissante  d'entiers naturels est constante à
partir d'un certain rang.
\end{theoreme}

Et cette  constante ne pouvant être  par construction que 0,  le PGCD de
$a$ et $b$ sera la dernière valeur non nulle de cette suite car $k\wedge
0=k$ pour tout entier $k$. 

Ce   procédé   semble   assez   long  :   beaucoup   d'opérations   sont
inutiles. Malgré  tout   il n'utilise  que des
sommes   et  des   différences  qu'un   ordinateur   traite  extrêmement
rapidement. 


\subsection{Algorithme d'Euclide I}


C'est le  même principe que  ce que nous  venons de faire, mais  en plus
rapide   car   nous   remarquons   que,  en   notant   $$a=bq_0+r_0\quad
\text{avec  }0\ie r_0<b$$  la division  euclidienne de  $a$ par  $b$, on
obtient que 
$$a\wedge b = b\wedge (a-bq_0)=b\wedge r_0$$ 

Puis en notant $$b=r_0q_1+r_1\quad \text{avec }0\ie r_1<r_0$$

on obtient de même que $$a\wedge b=b\wedge r_0=r_0\wedge r_1$$

et  on continue  ainsi à  fabriquer une  suite  strictement décroissante
d'entiers naturels~:~elle est donc finie et son dernier terme $r_p= 0$. 

Alors  $$a\wedge b=r_{p-1}\wedge  r_p=r_{p-1}\wedge  0=r_{p-1}=\text{ le
  dernier reste non nul}$$ 
 
Soit,  à  la  mode  spaghetti,  en  supposant  déterminée  une  fonction
\verb+rem+ qui renvoie le reste de deux entiers:


\begin{algo}
\FUNC{euclide}{%
\pfarg{a, b}{entiers}}{entier}
\IF{b = 0}
\RETURN{a}
\ELSE
\RETURN{euclide(b,rem(a,b))}
\ENDIF
\end{algo}


\subsection{Algorithme d'Euclide II}

L'algorithme d'Euclide nous assure que le PGCD de $a$ et $b$ est le dernier reste non nul de la suite $(r_k)$ construite au paragraphe précédent. L'égalité de Bézout nous assure de l'existence de deux entiers $u$ et $v$ tels que $au+bv=a\wedge b$.

Nous allons essayer de combiner les deux en construisant deux suites $(u_k)$ et $(v_k)$ telles que $$r_k=au_k+bv_k$$

Voici le départ \begin{itemize}
\item $r_0=a=1\times a+0\times b$
\item $r_1=b=0\times a+1\times b$
\item $r_2=$\verb+rem+ $(r_0,r_1)$\\
$\vdots$
\item $r_{i+1}=$\verb+rem+ $(r_{i-1},r_i)$\\
$\vdots$
\item $r_{p-1}=a\wedge b$
\item $r_p=0$
\end{itemize}

Or par définition, comme $r_2=$\verb+rem+ $(r_0,r_1)$, on a $r_0=q_2r_1+r_2$, donc $r_2=1\times r_0-q_2\times r_1$, c'est à dire 
$$u_2=1 \ \text{ et } \ v_2=-q_2$$

On réitère le mécanisme. Supposons que $r_{k-1}=u_{k-1}\times a+v_{k-1}\times b$ et $r_{k}=u_{k}\times a+v_{k}\times b$

Comme $r_{k+1}=$\verb+rem+ $(r_k,r_{k-1})$, on a $r_{k-1}=q_{k+1}r_k+r_{k+1}$, donc $r_{k+1}=1\times r_{k-1}-q_{k+1}\times r_k$, c'est à dire $$r_{k+1}=1\times(u_{k-1}\times a+v_{k-1}\times b)-q_{k+1}\times(u_{k}\times a+v_{k}\times b)$$

Finalement

$$u_{k+1}=u_{k-1}-u_k\times q_{k+1} \ \text{ et } \ v_{k+1}=v_{k-1}-v_k\times q_{k+1}$$

\c Ca a l'air un peu brut comme  ça, au premier coup d'\oe il, mais en
fait il y a  une disposition pratique qui permet de  mieux voir ce qui
se passe. D'abord, dans algorithme  d'Euclide étendu il y a algorithme
d'Euclide, donc on  commence par rechercher le PGCD de  $a$ et $b$ par
l'algorithme  d'Euclide en  n'oubliant  pas cette  fois  de noter  les
quotients en remplissant le tableau suivant: 


\begin{center}
\begin{tabular}{|c||c|c|c||c|}
\hline $k$ & $u_k$ & $v_k$ & $r_k$ & $q_k$ \\ 
\hhline{=====} 0 & 1 & 0 &$r_0=a$& /  \\ 
\hline 1 & 0 & 1 &$r_1=b$& $q_1$  \\
\hline 2 & $u_0-u_1q_1$ & $v_0-v_1q_1$ &$r_2=r_0-r_1q_1$& $q_2$  \\ 
\hline 3 & $u_1-u_2q_2$ & $v_1-v_2q_2$ & $r_3=r_1-r_2q_2$&$q_3$  \\ 
\hline $\vdots$ &  &  & $\vdots$ & $\vdots$ \\ 
\hline $p-1$ &  &  & $r_{p-1}=a\wedge b$ & $q_{p-1}$ \\ 
\hline $p$ &  &  &   $r_p=0$ &\\
\hline 
\end{tabular} 
\end{center}

Et le secret tient dans le schéma 

\begin{center}
\begin{tabular}{ccccc}
 & \psframebox[fillstyle=solid,fillcolor=bleu_ciel]{$u_k$} & {\Large{\textbf{$-$}}} &  &    \\
 & & & &  \\ 
{\Large{\textbf{(}}} & \psframebox[fillstyle=solid,fillcolor=bleu_ciel]{$u_{k+1}$} & {\Large{\textbf{$\times$}}} & \psframebox[fillstyle=solid,fillcolor=vert_e]{$q_{k+1}$} & {\Large{\textbf{)}}}   \\
 & & & &  \\ 
{\Large{\textbf{$=$}}} & \psframebox{$u_{k+2}$} &  &  &    \\ 
\end{tabular} 
\end{center}


et pareil pour les $v_k$ et les $r_k$.


Par exemple, pour 19 et 15~:



\begin{center}
\begin{tabular}{|c||c|c|c||c|l}
\hhline{-----} $k$ & $u_k$ & $v_k$ & $r_k$ & $q_k$ &  \\ 
\hhline{=====} 0 & \psframebox[fillstyle=solid,fillcolor=bleu_ciel]{ 1} & \psframebox[fillstyle=solid,fillcolor=bleu_ciel]{ 0} & \psframebox[fillstyle=solid,fillcolor=bleu_ciel]{ 19} & / & $L_0$ \\ 
\hhline{-----} 1 & \psframebox[fillstyle=solid,fillcolor=bleu_ciel]{ 0} & \psframebox[fillstyle=solid,fillcolor=bleu_ciel]{ 1} & \psframebox[fillstyle=solid,fillcolor=bleu_ciel]{ 15} & \psframebox[fillstyle=solid,fillcolor=vert_e]{1} & $L_1$ \\ 
\hhline{-----} 2 & 1 & $-1$ & 4 & 3 & $L_2\leftarrow L_0-\psframebox[fillstyle=solid,fillcolor=vert_e]{1}\times L_1$ \\ 
\hhline{-----} 3 & $-3$ & 4 & 3 & 1 & $L_3\leftarrow L_1-3\times L_2$ \\ 
\hhline{-----} 4 & 4 & $-5$ & 1 & 3 & $L_4\leftarrow L_2-1\times L_3$ \\ 
\hhline{-----} 5 &  &  & 0 &  & $L_5\leftarrow L_3-3\times L_4$ \\ 
\hhline{-----} 
\end{tabular} 
\end{center}




Le   dernier   reste  non   nul   est   1   donc  $19\wedge   15=1$   et
$4\times19-5\times 15=1 $ 



En version récursive, on peut procéder en deux étapes:



\begin{algo}
\FUNC{euc}{%
\pfarg{u,v,r,u',v',r'}{entiers}}{liste d'entiers}
\IF{r' = 0}
\RETURN{[u,v,r]}
\ELSE
\RETURN{euc(u',v',r',u-\verb+quo+(r,r')*u',v-\verb+quo+(r,r')*v',r-\verb+quo+(r,r')*r')}
\ENDIF
\end{algo}

\begin{algo}
\FUNC{EUC}{%
\pfarg{a,b}{entiers}}{liste d'entiers}
\RETURN{euc(1,0,a,0,1,b)}
\end{algo}


\subsection{Nombres premiers entre eux}


\begin{definition}
Deux entiers $a$ et $b$ sont premiers entre eux si et seulement si $$a\wedge b=1$$
\end{definition}


L'égalité de \textsc{Bézout} vue  précédemment nous permet donc dénoncer
le théorème suivant:

\begin{theoreme}[Théorème de \textsc{Bézout}]
  Les entiers $a$ et $b$ sont premiers entre eux si et seulement s'il existe deux entiers $u$ et $v$ tels que $au+bv=1$  $$a\wedge b=1\ssi \text{ il existe } (u,v)\in\bbz^2 \text{ tel que } au+bv=1$$
\end{theoreme}

Nous  avons donc en  main tous  les éléments  pour étudier  les éléments
inversibles de $\ofr{\Z}{n\Z}$ mais avant, une petite digression...

\section{À la recherche des nombres premiers}

\subsection{Définition}
Quoi de plus simple qu'un nombre premier :

\begin{definition}
 Un entier naturel  est dit premier s'il est  supérieur ( i.e. supérieur
 ou égal ) à 2 et n'est 
divisible que par 1 et lui-même. 
\end{definition}

et pourtant, ils renferment tant de mystères que les plus grands esprits depuis 
des siècles n'ont toujours pas réussi à en percer tous
les secrets et ce malgré les énormes progrès technologiques et les  
investissements colossaux consentis par les pouvoirs tant civils que
militaires pour assurer ou percer la confidentialité des transmissions de toutes 
natures qui continuent de dépendre d'une meilleure
connaissance des nombres premiers, ce que nous verrons un peu plus loin. Qui 
sont-ils ? Combien sont-ils ? Où sont-ils ? À quoi
servent-ils ? Nous essaierons de donner quelques éléments de réponses à ces 
questions.


Mais tout d'abord, pourquoi jouent-ils un rôle si important ? Fondamentalement, 
il existe deux manières d'engendrer $\bbn$ : 
\begin{itemize}
\item si on veut engendrer $\bbn$ en utilisant l'addition, on s'aperçoit que le nombre 1 nous suffit : on <<~fabrique~>> 2  en additionnant 1 avec lui-même; 3 en additionnant 1 avec
2, etc.
\item si on veut engendrer $\bbn$ en utilisant la multiplication, là, les choses se compliquent. Pour <<~fabriquer~>> 2, il 
faut le créer; même problème pour  3. On fabrique  4 en multipliant  2
avec lui-même, mais il faut créer 5. On fabrique  6 en multipliant 3 avec 2. On crée 7. On fabrique 8 à partir de 2. On fabrique 9 à partir de 3. On fabrique 10 à partir de 2 et 5, etc.

 Les 
nombres que l'on est obligés de créer sont les briques nécessaires à
fabriquer tous les autres. C'est bien plus compliqué que l'addition me 
direz-vous, mais la multiplication est plus <<~puissante~>> et
nous permet d'aller bien plus vite et plus loin. 
\end{itemize}

\sm

Les nombres premiers sont donc ces éléments qui nous permettent de fabriquer tous 
les autres. Un des premiers problèmes étudiés à été de
savoir s'ils peuvent tenir dans une boîte. 
Euclide à répondu à cette question il y a vingt-trois siècles
et la réponse est non.

Pour le prouver, nous aurons besoin d'un résultat intermédiaire :

\begin{theoreme}\label{infinite}
  Tout entier naturel admet au moins un diviseur premier.
\end{theoreme}


Si ce nombre, appelons-le $n$, est premier, tout va bien.

Sinon, l'ensemble de ses diviseurs étant non vide ( $n$ est dedans ) et borné ( 
par 1 et lui-même), il admet un plus petit élément $p\neq 1$.
Ce nombre n'est pas divisible par un autre, sinon ce nombre plus petit que $p$ 
divisant $p$ diviserait $n$ et alors $p$ ne serait plus le
plus petit diviseur de $n$. Le nombre $p$ est donc premier et voilà.


\begin{theoreme}
  Il y a une infinité de nombres premiers.
\end{theoreme}



 \emph{Raisonnons par l'absurde} et 
supposons qu'il existe exactement $n$ nombres premiers qu'on
nommera $p_1$, $p_2,\cdots,\ p_n$ et appelons $N$ le nombre  \[N=p_1p_2\cdots 
p_n+1\]
%\footnote{Ce style de nombre réapparaîtra souvent}. 
Il
est plus grand que tous les $p_i$, donc il n'est pas premier d'après notre 
hypothèse, donc il admet un diviseur  premier $p$ qui est donc
un des $p_i$, puisqu'il n'y a qu'eux. Soit $i_0$ tel que $p=p_{i_0}$. Alors $p$ 
divise $p_1p_2\cdots p_n$. Or il divise $N$, donc il
divise leur différence $N-p_1p_2\cdots p_n$, c'est à dire 1, donc $p=1$ ce qui 
est absurde puisqu'il est premier. Ainsi, il n'existe pas
de plus grand nombre premier.


\sm


Il y en a donc une infinité et l'aventure ne fait que commencer. 



\subsection{Comment vérifier qu'un nombre est premier?} 


 Observons les diviseurs de 1321 par exemple: si aucune des 1319 divisions ne 
<<~tombe juste~>>, alors on pourra dire que 1321 premier.
Et puis d'abord, il est impair, il ne semble pas être divisible par 3, alors 
pourquoi pas...



\begin{center}
\footnotesize{ {\setlength{\tabcolsep}{0.1cm}
\begin{tabular}{IcIccccccccccccI}
\whline
 diviseur& 2& 3& 4& 5& 6&  7&8&9&10&11&12&13\\ \hline
  quotient&660,5&440,3&330,3&264,2
&220,2&188,7&165,1&146,8&132,1& 120,1& 110,1&101,6\\ \whline
 diviseur &14&15&16&17&18&19&20&21&22&23&24&25\\ \hline
quotient &94,36&88,07&82,56&77,71&73,39&69,53 &66,05&62,90&60,05&57,43
&55,04&52,84\\ \whline diviseur&26&27&28&29&30&31&32&33&34&35&36&37 \\ \hline
  quotient&50,81&48,93&47,18& 45,55& 44,03&42,61&41,28&40,03&38,85&37,74 &36,69& 
35,70\\ \whline

\end{tabular}}
}
\end{center}


Le tableau est incomplet: il reste encore à essayer les quotients de 38 à 1320, 
mais cela aurait été mauvais pour la planète.


 Tout d'abord,  nous n'avons pas trouvé  de quotient entier  en ce début
 d'enquête.  
Nous observons de plus que si la suite des diviseurs
 est  croissante,  celle  des  quotients  est  décroissante.  Vous  avez
 sûrement remarqué qu'à partir de 37, 
 les  quotients sont  inférieurs aux  diviseurs donc  nous  pouvons nous
 arrêter là: 
si pour un diviseur supérieur à 37, on trouvait un
 quotient entier $q$, alors en  divisant 1321 par $q$, qui est inférieur
 à 37, on devrait se trouver au début de notre liste de diviseurs et 
  ce diviseur serait entier. Le problème, c'est qu'aucune division par un 
entier inférieur à 37 n'a donné de quotient entier donc on
  peut s'épargner les 1283 divisions restantes.


\bigskip

  Mine de rien, nous venons de franchir un grand pas dans la théorie des
  nombres: pour tester si l'entier 1321 est premier, il nous a
  suffit  d'effectuer 36 divisions\footnote{Et  encore, nous  aurions pu
    faire mieux 
comme nous allons le voir tout de suite après.}. Deux
  problèmes se posent maintenant: pourquoi 36 et pouvons-nous généraliser ce 
résultat aux autres entiers? 

Un petit Joker : $\sqrt{1321}\simeq 36,3$...

Reprenons la  propriété \vref{infinite}. Tout naturel $n$  admet un plus
petit diviseur $p$ 
qui est premier. \'Ecartons le cas où $n$ est premier et
donnons un nom aux nombres qui restent :


\begin{definition}
  Un entier naturel \emph{autre que 1} qui n'est pas premier est dit 
\textbf{composé}.
\end{definition}


L'entier $n$ étant  composé, il s'écrit donc $n=pq$,  avec $q$ un entier
supérieur 
à $p$ (car $p$ est le plus petit diviseur). Ainsi $$
p \leqslant q\ \text{ et donc }\ p^2 \leqslant  pq=n\ \text{ c'est à dire }\
p \leqslant \sqrt{n}$$ 

Nous pouvons donc généraliser l'observation précédente

\begin{theoreme}
  Si un entier est composé, alors il admet un diviseur premier 
inférieur à sa racine carrée.
\end{theoreme}


\subsection{Tests et cribles}



\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3cm]{crible}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-2.4cm}
\begin{minipage}[t]{\linewidth}

La théorie des nombres (i.e. la partie des mathématiques qui étudie
  les nombres 
  premiers) est  actuellement intimement  liée à l'informatique  et vice
versa.  Même à 
notre petit 
niveau, nous ne pouvons donc pas passer à côté... 


\end{minipage}
\subsubsection{Tests naïfs}


On teste  tous les entiers de 2  à $\sqrt{n}$ en passant  par une petite
fonction locale récursive:


\begin{algo}
\FUNC{test1\_tmp}{%
\pfarg{t,n}{entiers}}{bool\'een}
\IF{t * t > n}
\RETURN{Vrai}
\ELSE
 \IF{rem(n,t) = 0}
 \RETURN{Faux}
 \ELSE
 \RETURN{test1\_tmp(t+1,n)}
 \ENDIF
\ENDIF
\end{algo}


\begin{algo}
\FUNC{test1}{%
\pfarg{n}{entier}}{bool\'een}
\RETURN{test1\_local(2,n)}
\end{algo}

On pourrait déjà diviser facilement le nombre de tests par 2, voire plus...




\subsubsection{Crible d'Ératosthène}


\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=3cm]{eratosthene}
\caption{Né  276
  années  avant JiCé,  directeur de  la Bibilothèque  d'Alexandrie, on  lui doit  aussi une
  approximation du diamètre de la Terre. Devenu aveugle, il s'est laissé mourir de faim...}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-6.8cm}
\begin{minipage}[t]{\linewidth}

Autre problème crucial: comment obtenir une
liste des entiers inférieurs à un \emph{petit} nombre donné $n$? 

Le   principe    est   ancien    puisqu'il   est   attribué    au   grec
\textsc{Ératosthène}

On écrit les entiers de 2 à  $n$ puis on barre les multiples des nombres
premiers inférieurs 
à $\sqrt{n}$. Les entiers restant sont premiers. 

\end{minipage}



La programmation  en \textsf{Ocaml} est  un peu plus délicate  donc nous
allons la détailler cette fois ensemble.


On crée une fonction  qui retire les multiples d'un entier dans
une liste donnée.  Pour cela, on utilise la  fonction \verb+filter+ du
module \verb+List+ dont voici la documentation:

\begin{lstlisting}
val filter : ('a -> bool) -> 'a list -> 'a list

filter p l returns all the elements of the list l that satisfy the predicate p. The order of the elements in the input list is preserved.
\end{lstlisting}

Complétez alors 

\begin{lstlisting}[caption={}]
let retmultiples = fun liste n -> ...
\end{lstlisting}

Pour enlever les multiples de 3 compris entre 2 et 12:

\begin{lstlisting}
# retmultiples [2;3;4;5;6;7;8;9;10;11;12] 3 ;;
- : int list = [2; 4; 5; 7; 8; 10; 11]
\end{lstlisting}


On  crée aussi  une  fonction  qui renvoie  la  liste  des entiers  de
\verb+min+ à \verb+max+:

\begin{lstlisting}[caption={}]
let liste_entiers = fun min max ->
  let rec aux = fun a acc ->
    if ...
    else ...
  in aux min [];;
\end{lstlisting}

Enfin, voici le c\oe ur de la procédure:


\begin{lstlisting}
let crible = fun m ->
  let rec crible_rec = fun n acc ->
      if n*n > m then 
        acc
      else 
        crible_rec (n+1) (retmultiples acc n)
  in crible_rec 2 (liste_entiers 2 m);;
\end{lstlisting}



\subsection{Décomposition des entiers en produit de nombres premiers}

Avant d'aller plus loin dans notre exploration, nous avons dit en introduction 
que les nombres premiers étaient les briques qui nous
permettaient de construire tous les autres : il serait bon de le vérifier.

\begin{theoreme}
  Tout entier $n$ supérieur à 2 se décompose en produit fini de nombres 
premiers.
\end{theoreme}

La démonstration la plus simple (mais pas la plus intéressante) consiste à 
raisonner par récurrence sur $n$.

Nous savons que 2 est premier.

\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3cm]{darkside}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-3.45cm}
\begin{minipage}[t]{\linewidth}

Supposons que tout entier inférieur ou égal à $n$ se décompose en produit de 
facteurs premiers.

L'entier suivant $n+1$ admet au moins un diviseur premier $p$ d'après la 
propriété \vref{infinite}. 

 Soit $q$ le quotient de $n+1$ par $p$. 

Si $q=1$, alors $n+1=p$ et donc $n+1$ est premier.

Si $q>1$, nous appliquons l'hypothèse de récurrence à $q$ : $q$ se décompose en 
produit fini de nombres premiers, et par suite $n+1$
aussi, car $n+1=p\times q$.
\end{minipage}
\sm

Par exemple, $50=2\times5^2$ : les facteurs premiers ne sont pas forcément 
distincts. On a donc l'habitude d'écrire la décomposition sous
la forme $$n=p_1^{\al_1}\times p_2^{\al_2}\times\cdots\times p_r^{\al_r}$$ Une 
petite chose reste à vérifier: cette décomposition
est-elle  unique?   Elle  a  l'air  de   l'être,  c'est  pourquoi...nous
l'admettrons:


\begin{theoreme}
  Tout entier $n$ supérieur à 2 admet une et une seule (à l'ordre près 
des termes) décomposition en produit fini de nombres
premiers
\end{theoreme}

Bon,  nous en  savons assez  pour revenir  au problème  de  recherche de
l'inverse  modulaire d'un  entier  qui  nous ouvrira  les  portes de  la
cryptographie. 


\section{Éléments inversibles de Z/nZ}


\subsection{Anneaux et corps}



\begin{definition}[Anneau]
Soit A un ensemble muni de deux lois $\cdot$ et + qu'on nommera addition
et multiplication. 

On dit que
$(A,+,\cdot)$ est un anneau si, et seulement si:
\begin{itemize}
\item $(A,+)$ est un groupe commutatif;
\item la multiplication est associative;
\item la multiplication est distributive sur l'addition.
\end{itemize}

Si   la  multiplication   est  commutative,   alors  l'anneau   est  dit
\textit{commutatif}. 

Si  la  multiplication  admet   un  élément  neutre,  l'anneau  est  dit
\textit{unitaire}. 

Les éléments  d'un anneau  unitaire qui admettent  un symétrique  par la
multiplication sont dits  \textit{inversibles}. On note $A^*$ l'ensemble
des éléments 
inversibles de A.
\end{definition}

\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3cm]{anneau}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{2.8cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}

Avez-vous déjà rencontré un anneau dans ce cours?

Dans un anneau, est-ce que tout élément est inversible?


Vous démontrerez facilement en TD le théoremm suivant:

\begin{theoreme}
$\Bigl(\left(\ofr{\Z}{n\Z}\right)^*,\cdot\Bigr)$ est un groupe.
\end{theoreme}

\begin{definition}[Corps]
Un corps est un anneau commutatif unitaire dans lequel tout élément non nul est
inversible.
\end{definition}

En anglais, le terme mathématique pour désigner les corps est \textit{field}.


Voici un bon théorème que vous pourrez démontrer en TD:


\begin{theoreme}[Deux théorèmes en un...]
  \begin{itemize}
  \item  Les  seuls éléments  inversibles  de  $\ofr{\Z}{n\Z}$ sont  les
    éléments premiers avec $n$.
\item Si  $n$ est premier,  $\ofr{\Z}{n\Z}$ est un  corps et on  le note
  dans ce cas $\bbf_n$.
  \end{itemize}
\end{theoreme}


\begin{definition}[Fonction indicatrice d'\textsc{Euler}]
On   note    $\varphi(n)$   le   nombre    d'éléments   inversibles   de
$\ofr{\Z}{n\Z}$.   C'est  donc   aussi   le  cardinal   (on  dit   aussi
l'\textit{ordre}) du groupe $\Bigl(\left(\ofr{\Z}{n\Z}\right)^*,\cdot\Bigr)$.
\end{definition}

Cette fonction  joue un rôle important en  cryptographie, notamment dans
le système RSA. 


\subsection{Comment calculer l'inverse modulaire d'un entier?}




C'est un problème important qui intervient souvent en cryptographie.

Avec  les   notations  habituelles,  le   but  est  de   trouver  $y\in
\bigl\{0,1,...,n-1\bigr\}$ tel que $x\cdot y \equiv 1 (\modu n)$.

% \vfill

% \eject

% %\vspace{-6.2cm}
% \setindent{0cm}
% \begin{flushleft}
% \begin{minipage}[t]{3cm}
% %\begin{figure}
%   \includegraphics[width=3cm]{euler.jpg}
% %\end{figure}
% \end{minipage}
% \end{flushleft}
% \setindent{\indentationcours}
% \vspace{-2.9cm}
% \begin{minipage}[t]{\linewidth}


% \end{minipage}
\begin{eqnarray*}
\overline{x}^n             \text{             est             inversible
  dans   }\ofr{\Z}{n\Z}&\Leftrightarrow&   \exists  \overline{y}^n   \in
\ofr{\Z}{n\Z}\quad\mid\quad  \overline{x}^n\cdot\overline{y}^n=\overline{1}^n\\
&\Leftrightarrow&\exists  y \in  \bigl\{0,1,...,n-1\bigr\}\quad\mid\quad  x\cdot  y \equiv  1 (\modu
n)\\
&\Leftrightarrow&\exists (y,k)\in \bigl\{0,1,...,n-1\bigr\}\times \Z\quad\mid\quad 
xy = 1 + kn\\
&\Leftrightarrow&\exists (y,k)\in \bigl\{0,1,...,n-1\bigr\}\times \Z\quad\mid\quad 
xy-kn=1\\
&\Leftrightarrow&x\wedge n=1
\end{eqnarray*}

Pouvez-vous  justifier cette  série d'équivalences?  Dans  quelle mesure
nous donne-t-elle un  moyen de déterminer $y$? Nous  reparlerons de tout
cela en TD...


Nous démontrerons également le théorème suivant:

\begin{theoreme}[Théorème d'\textsc{Euler}]
   $$a\wedge n=1 \Longrightarrow a^{\varphi(n)}\equiv 1 (\modu n)$$
\end{theoreme}

En quoi peut-il nous aider à déterminer l'inverse modulaire d'un entier?
Le  problème,  c'est  que   le  calcul  de  $\varphi(n)$  peut  s'avérer
compliqué...

Les propriétés suivantes vont nous aider:

\begin{theoreme}[Propriétés de $\bm{\varphi(n)}$]
  \begin{itemize}
  \item Si $p$ est premier, alors $\varphi(p)=p-1$;
\item si $m\wedge n=1$ alors $\varphi(mn)=\varphi(m)\varphi(n)$ (admis);
\item     Si    $p$    est     premier,    $\varphi(p^n)=p^n-p^{n-1}=p^n
  \left(1-\frac{1}{p}\right)$;
\item $\varphi(n)=n \displaystyle\prod_{p\in \PR_n}\left(1-\frac{1}{p}\right)$ avec $\PR_n$
  l'ensemble des diviseurs premiers de $n$.
  \end{itemize}
\end{theoreme}

C'est la dernière propriété  qui nous permettra de calculer $\varphi(n)$
avec \textsf{Ocaml}.

\subsection{Petit théorème de \textsc{Fermat}}

%\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3cm]{fermat}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-4.9cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}
Nous avons mis au point  avec le modèle du crible d'\textsc{Ératosthène}
une méthode 
permettant de tester si un entier est premier ou non. Cela
marche assez bien pour des petits nombres, mais cette méthode devient 
impraticable s'il s'agit de tester un entier d'une centaine de
chiffres. Nous allons nous occuper  dans cette section de deux problèmes
imbriqués 
: d'une part trouver des méthodes permettant de
vérifier rapidement si un nombre est premier et d'autre part réfléchir à 
d'éventuelles méthodes permettant de <<~fabriquer~>> des nombres
premiers aussi grands que l'on veut.

Nous avons besoin  pour cela d'un dernier résultat:  le fameux \og petit
théorème de \textsc{Fermat}\fg{}.S'il est qualifié de petit, c'est qu'une
conjecture célèbre du même Fermat, restée indémontrée pendant des siècles, s'est 
accaparée le titre de \textit{Grand Théorème de \textsc{Fermat}}.
$$ x^n+y^n=z^n\quad \text{n'a pas de solution dans }\bbn^3\quad\text{pour } n>2$$
Dans la marge d'un manuscrit, \textsc{Fermat} prétendait en avoir trouvé la démonstration 
mais manquer de place pour l'écrire. Il a pourtant fallu
attendre 1994 pour qu'Andrew \textsc{Wiles} le démontre en utilisant des
outils 
surpuissants: l'entêtement d'une multitude de chercheurs a abouti
à la démonstration de ce théorème, mais surtout a permis de développer 
d'importants outils en cryptographie donc en sécurité informatique.

Voici celui qui nous sera utile qui n'est en fait qu'une conséquence du théorème d'\textsc{Euler}...

\begin{theoreme}[Petit théorème de \textsc{Fermat}]
  \begin{itemize}
  \item  Si $p$ est premier et ne  divise pas $a$ alors $a^{p-1}\equiv 1 (\modu
  p)$;
\item Si $p$ est premier, $a^p\equiv a (\modu p)$.
  \end{itemize}
\end{theoreme}

\vfill

\eject

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\modeexercice % entre en mode exercice
\section{EXERCICES}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\small
%\begin{listeexercices}

\subsection{Structures mères}

%\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3cm]{maman}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-3.4cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}

\begin{exercice}
Donnez des exemples de couples  $(E,\star)$ avec $\star$ une application
définie sur $E\times E$ telle que $(E,\star)$ ne soit pas un magma.
\end{exercice}

  \begin{exercice}
Les    tables    ci-dessous    définies   sur    $E=\bigl\{a,b,c\bigr\}$
définissent-elles des monoïdes ? Unitaires ?

\begin{multicols}{2}
             \begin{tabularx}{0.7\linewidth}{Y{2}}
	     \whline
$\star$&$a$&$b$&$c$\\
\whline
$a$&$a$&$b$&$c$\\
\hline
$b$&$b$&$c$&$a$\\
\hline
$c$&$c$&$a$&$b$\\
             \whline
             \end{tabularx}



             \begin{tabularx}{0.7\linewidth}{Y{2}}
	     \whline
$\bot$&$a$&$b$&$c$\\
\whline
$a$&$a$&$c$&$c$\\
\hline
$b$&$b$&$c$&$a$\\
\hline
$c$&$c$&$a$&$a$\\
             \whline
             \end{tabularx}
\end{multicols}

Notons $A=\bigl\{a,b,c\bigr\}$.
Montrez que  $(A,\star)$ a une  structure de groupe. Comparer  ce groupe
avec $\left(\ofr{\Z}{3\Z},\overline{+}\right)$ et $\left(\bigl\{1,\mathrm{e}^{\ofr{2\pi}{3}},\mathrm{e}^{\ofr{-2\pi}{3}}\bigr\},\times\right)$.

  \end{exercice}


  \begin{exercice}
Soit  $A=\bigl\{a_1,a_2,...,a_p\bigr\}$ un  alphabet. Nous  avons  vu au
chapitre précédent que $A^\star$ muni  de la concaténation des chaînes a
une structure de monoïde (unitaire?). Les ensembles
suivants   sont-ils  des   sous-monoïdes   de  $A^\star$   muni  de   la
concaténation?  Unitaires?
\begin{enumerate}
\item L'ensemble des chaînes de longueur paire;
\item L'ensemble des chaînes de longueur impaire;
\item $\bigl\{(a_1a_2)^n\quad\mid\quad  n\in \bbn\bigr\}$;
\item $\bigl\{a_1^na_2^n\quad\mid\quad  n\in \bbn\bigr\}$;
\item L'ensemble  des chaînes ne  contenant que $a_1$ et  $a_2$, ceux-ci
  apparaissant un nombre égal de fois.
\end{enumerate}
  \end{exercice}


\subsection{Division euclidienne}





\begin{exercice}[Quotient et reste]
On s'occupe de la division euclidienne d'un entier quelconque $a$ par un
entier non nul $b$.

On voudrait écrire un  programme \textsf{Caml} le plus général possible,
i.e. qui fonctionne quelque soit le signe de $a$ ou de $b$.

Dans le cas où  $a$ et $b$ sont tous les deux  positifs, le petit dessin
avec les drapeaux nous invite à écrire:

\begin{lstlisting}[caption={}]
let rec quo_pos= fun a b ->
  if a < b then 0 
  else 1 + quo_pos (a-b) b ;;
\end{lstlisting}

Modifiez ce programme  pour qu'il traite aussi le cas  $a<0$ puis le cas
général.

Faites de même avec la fonction \verb+rem a b+ qui renvoie le reste de
la division de $a$ par $b$.
\end{exercice} 



\begin{exercice}[Nombre de chiffres]
Déterminez une fonction \verb+nb_chiffres n+ qui renvoie le nombre de
chiffres de l'écriture décimale de $n$.
\end{exercice}


\begin{exercice}[Décomposition en base quelconque]
Déterminez une fonction \verb+base b n+ qui renvoie la liste des
chiffres de l'écriture normalisée de n en base b.

\begin{lstlisting}[caption={}]
# base 2 97 ;;
- : int list = [1; 1; 0; 0; 0; 0; 1]
\end{lstlisting}
\end{exercice}



\begin{exercice}[Persistance d'un entier]
  Déterminez une fonction récursive qui renvoie la liste des chiffres de
  l'écriture décimale d'un nombre.

Un entier naturel $n$ étant donné, on calcule le produit \verb+prod n+
de  ses chiffres  dans  son écriture  en  base 10  puis  le produit  des
chiffres de \verb+prod n+ et on recommence ainsi l'application de
\verb+prod+ jusqu'à obtenir  un chiffre entre 0 et  9. Le nombre minimal
de fois  où on applique \verb+prod+  pour transformer $n$  en un chiffre
entre 0 et 9 est appelé  la \textit{persistance} de $n$. Par exemple, la
persistance  de  9 est  égale  à  0,  celle de  97  est  égale à  3  car
\verb+prod+$(97)=9\cdot     7=63$,     \verb+prod+$(63)=6\cdot    3=18$,
\verb+prod+$(18)=1\cdot 8=8$. et celle  de $\numprint{9575}$ est égale à
5.

On voudrait connaître le plus petit entier naturel de
persistance 5.

\end{exercice}


\begin{exercice}[Écriture littérale]
  Déterminez une  fonction qui renvoie l'écriture  littérale d'un nombre
 dont l'écriture décimale est comprise entre 1 et 999.
\end{exercice}


\begin{exercice}[Problème de calendrier]


%\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3cm]{calendrier}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-4.2cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}



Connaissant  une  date, à  quel  jour  de  la semaine  correspond-elle~?
L'allemand \textsc{Zeller} a proposé une formule en 1885.

On note  $m$ le numéro  du mois  à partir de  janvier, $s$ le  numéro du
siècle, $a$  le numéro de l'année dans  le siècle $s$, $j$  le numéro du
jour. Pour 1492, $s=14$ et $a=92$.


En fait, $m$ doit être modifié selon le tableau suivant:
{
\begin{center}
             \begin{tabularx}{\linewidth}{Y{11}}
	     \whline
             Mois& Jan. & Fév.  & Mars & Avril & Mai & Juin & Juil.  & Août &
             Sep. & Oct. & Nov. & Déc.\\
             \whline
             Rang &13* &14* & 3 &4 &5 &6 &7 &8 &9 &10 &11 &12\\

             \whline
             \end{tabularx}
             \end{center}
}

Les mois marqués d'une astérisque comptent pour l'année précédente.



Le nom du jour (0 correspondant à samedi) est alors déterminé en prenant
le reste (positif!) dans la division 
par 7 de $nj$ donné par la formule:


\[nj=j+a+{\rm quo}(a,4)+{\rm quo}(26(m+1),10)+{\rm quo}(s,4)-2s \]

Ceci est  valable à partir du 15  octobre 1582, date à  laquelle le pape
Grégoire XIII a modifié le  calendrier:~on est passé du jeudi 4 octobre
1582  au  vendredi  15  octobre  1582 (en  Grande-Bretagne  il  a  fallu
attendre 1752, au Japon en 1873, en Russie 1918, en Grèce 1924).

 L'année est alors de 365 jours, sauf quand elle est bissextile, i.e., divisible par 4, sauf les années séculaires (divisibles par 100), qui ne sont bissextiles que si divisibles par 400.
 

Avant le changement, il faut remplacer ${\rm quo}(s,4)-2s$
par $5-s$.

Pour  les  démonstrations, voir  l'article  original de  \textsc{Zeller}
disponible (en allemand...) à l'adresse:

   \href{http://www.merlyn.demon.co.uk/zel-86px.htm}{http://www.merlyn.demon.co.uk/zel-86px.htm}



Quel jour est né le petit Jésus? Quel jour a été prise la Bastille?

\end{exercice}



\begin{exercice}[Critères de divisibilité]
En  travaillant  modulo  le   bon  entier,  démontrer  les  critères  de
divisibilité usuels par 2, 3, 4, 5, 9, 10 et 11.

On rappelle que l'écriture en base 10 d'un nombre $n$ est définie par la
donnée de l'unique famille $(a_0,a_1,...,a_k)$ vérifiant:

$$n= a_k10^k+a_{k-1}10^{k-1}+\cdots+a_210^2+a_110+a_0$$

avec $a_k\neq 0$ et $0 \leqslant a_1 <10$ pour tout $i\in \bigl\{0,1,..,k\bigr\}$.

\end{exercice}

\begin{exercice}[Nombre de diviseurs]



%\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3cm]{hardy}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-3.5cm}
\begin{minipage}[t]{\linewidth}


 \end{minipage}



% Que renvoient les deux fonctions suivantes:
% \begin{multicols}{2}



% \begin{lstlisting}[caption={}]
% let rec myst(n) =
%   if n == 1 then 1 else
%   let rec myst_loc(n,k) =
%     if k*k > n then
%       1
%     else
%       if ((k==1) or ((n mod k == 0) & (k == n/k))) then
% 	1 + myst_loc(n,k+1)
%       else
% 	if n mod k == 0 then
% 	  2 + myst_loc(n,k+1)
% 	else
% 	  myst_loc(n,k+1)
%   in myst_loc(n,1);;
% \end{lstlisting}

% \begin{lstlisting}[caption={}]
% let rec mystere(n) =
%   let rec mystere_local(n,k) =
%     if k == n then
%       1
%     else
%       if n mod k == 0 then
% 	1 + mystere_local(n,k+1)
%       else
% 	mystere_local(n,k+1)
%   in mystere_local(n,1);;


% .
% \end{lstlisting}


% \end{multicols}


Déterminer  une fonction récursive  qui calcule  le nombre  de diviseurs
positifs d'un entier naturel donné.
On pourra commencer par créer une fonction: 


{
\centering 

\verb+nb_div_naif_loc nb_a_diviser candidat+ 

}

 qui  calcule   le   nombre  de
diviseurs de \verb+nb_a_diviser+ supérieurs à \verb+candidat+.

On pourra ensuite  tenter d'améliorer la fonction en  remarquant que les
diviseurs vont souvent deux par deux...

\end{exercice}


\begin{exercice}[Liste des diviseurs]


Déterminer une fonction récursive qui calcule la liste des diviseurs
positifs d'un entier naturel donné.
\end{exercice}

*
\begin{exercice}[Nombres parfaits]
Un nombre parfait est un nombre entier $n$ strictement supérieur à 1 qui
est égal à la somme de ses  diviseurs (sauf $n$ bien sûr) ou, de manière
équivalente, c'est un  nombre tel que son double est égal  à la somme de
ses diviseurs, lui-même compris.

On pourra créer une fonction \verb+som_div n+ qui
calcule la somme des diviseurs de $n$.

Il faut  ensuite créer  un  test  de  \og
perfection\fg{} \verb+parfait n+.

On  terminera par  dresser la  liste des  entiers parfaits  inférieurs à
$\numprint{100000}$.

On  connaît  une  quarantaine  de nombres  parfaits  actuellement,  tous
pairs. On ne sait toujours pas s'il en existe des impairs.

Cependant, \textsc{Euclide} avait déjà découvert la propriété suivante:

\og \textit{Lorsque la somme d’une  suite de nombres doubles les uns des
autres est un  nombre premier, il suffit de multiplier  ce nombre par le
dernier terme de cette somme pour obtenir un nombre parfait.}\fg{}

Qu'en pensez-vous?
Quel est la rapport avec $2^p-1$ et $2^{p-1}(2^p-1)$? 
Écrivez les nombres parfaits obtenus en binaire: joli, non?
\end{exercice}


\subsection{PGCD}





\begin{exercice}[PGCD]
Programmez sur \textsf{Caml} l'algorithme récursif d'\textsc{Euclide} I.
\end{exercice}


\begin{exercice}[Nombres premiers entre eux]
Déterminez une fonction qui teste si deux entiers sont premiers entre eux.
\end{exercice}

\begin{exercice}[Bézout]
Programmez sur \textsf{Caml} l'algorithme récursif d'\textsc{Euclide} II
qui calcule des coefficients de \textsc{Bézout} et le PGCD de deux nombres.
\end{exercice}

\begin{exercice}[Inverse modulaire]
Déterminez une fonction qui calcule  l'inverse d'un entier $a$ modulo un
entier $n$.
Vous ferez attention aux exceptions.
\end{exercice}

\subsection{Nombres premiers}

\begin{exercice}[Test naïf]
Programmez  le  test naïf  de  primalité  vu  en cours.  Modifiez  votre
programme pour réduire le nombre de tests effectués sachant qu'un entier
pair ou multiple de 3 autre que 2 et 3 n'est pas premier...
\end{exercice}


\begin{exercice}[Décomposition ]
Créez une fonction \verb+decompo n+ qui renvoie la liste des diviseurs
premiers de $n$.
\end{exercice}


\subsection{Complexité et relation de domination}


%\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3cm]{shadok}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-5cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}




Voici un autre standard du vocabulaire geek:

\begin{quote}
  {\it Brooks's Law [prov.]

\og Adding manpower to a late software project makes it later\fg{} -- a result
of  the fact that  the expected  advantage from  splitting work  among N
programmers is $O(N)$, but the complexity and
communications cost associated with  coordinating and then merging their
work is $O(N^2)$}
\begin{flushright}
  in \og The New Hacker's Dictionnary\fg{}\\
\href{http://outpost9.com/reference/jargon/jargon\_17.html\#SEC24}{http://outpost9.com/reference/jargon/jargon\_17.html\#SEC24}
\end{flushright}
\end{quote}

Les notations  de \textsc{Landau}(1877-1938) ont  en fait été  crées par
Paul 
\textsc{Bachmann}(1837-1920) en 1894, mais bon, ce sont tous deux des 
mathématiciens allemands.

Par exemple, si l'on considère l'expression: $$f(n)=n+1+\frac{1}{n}+\frac{75}{n^2}-\frac{765}{n^3}+\frac{\cos(12)}{n^{37}}-\frac{\sqrt{\numprint{765481}}}{n^{412}}$$


Quand  $n$  est  \og  grand\fg{}, disons  $\numprint{10000}$,  alors  on
obtient:

$$f(\numprint{10000})=\numprint{10000}+1+0,0001+0,00000000075-0,0000000000000765+\text{
  peanuts}$$

Tous les  termes après  $n$ comptent  pour du beurre  quand $n$  est \og
grand\fg{}.  Donnons une définition pour plus de clarté:

\begin{definition}[\og Grand O\fg{}]
Soit $f$ et $g$ deux fonctions  de $\bbn$ dans $\bbr$. On dit que $f$
est un \og grand O\fg{} de $g$ et on note $f=O(g)$ ou $f(n)=O(g(n))$ si,
et seulement si, il existe une constante strictement positive C telle que $|f(n)|\leqslant
C|g(n)|$ pour tout $n\in \bbn$.
\end{definition}



Dans  l'exemple précédent,  $\frac{1}{n} \leqslant  \frac{1}{1}\times 1$
pour tout entier $n$ supérieur à 1
donc $\frac{1}{n}=O(1)$.

De   même,  $\frac{75}{n^2}   \leqslant  \frac{75}{1^2}\times   1$  donc
$\frac{75}{n^2}=O(1)$ mais on peut dire mieux:
 $\frac{75}{n^2}\leqslant  \frac{75}{1}\times\frac{1}{n}$  et  ainsi  on
 prouve que $\frac{75}{n^2}=O \left(\frac{1}{n}\right)$.

En fait, un grand  O de $g$ est une fonction qui  est au maximum majorée
par un multiple de $g$.


Point  de vue  algorithmique, cela  nous donne  un renseignement  sur la
complexité au pire.


On peut  cependant faire  mieux si l'on a  aussi une
minoration.

C'est le moment d'introduire une nouvelle définition:

\begin{definition}[\og Grand Oméga\fg{}]
  Soit $f$ et $g$ deux fonctions  de $\bbr$ dans lui-même. On dit que $f$
est un \og grand Oméga\fg{} de $g$ et on note $f=\Omega(g)$ ou $f(n)=\Omega(g(n))$ si,
et seulement si, il existe une constante strictement positive C telle que $|f(n)|\geqslant
C|g(n)|$ pour tout $n\in \bbn^*$.
\end{definition}

\begin{remarque}
Comme   $\Omega$  est   une  lettre   grecque,  on   peut,   par  esprit
d'unification, parler de \og grand omicron\fg{} au lieu de \og grand O\fg{}...
\end{remarque}

\begin{remarque}
   $f=\Omega(g)\Longleftrightarrow g=O(f)$...
\end{remarque}

Si l'on a à la fois une minoration et une majoration, c'est encore plus précis et nous incite à
introduire une nouvelle définition:

\begin{definition}[\og Grand Théta\fg{}]
$f=\Theta(g)\Longleftrightarrow
  f=O(g)\ \ \wedge \ \ f=\Omega(g)
$
\end{definition}

%\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3cm]{grandbeta}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-5.75cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}

Voici maintenant une petite table pour illustrer les différentes classes
de complexité rencontrées habituellement:

\begin{center}
             \begin{tabularx}{\linewidth}{Y{3}}
	     \whline
             \backslashbox{coût}{$n$}&100&$\numprint{1000}$&$10^6$&$10^9$\\
             \whline
             $\log_2(n)$&$\approx7$&$\approx10$&$\approx 20$&$\approx 30$\\
             \hline
             $n\log_2(n)$&$\approx 665$&$\approx \numprint{10000}$&$\approx  2\cdot  10^{7}$&$\approx 3\cdot 10^{10}$\\
             \hline
             $n^2$&$10^4$&$10^6$&$10^{12}$&$10^{18}$\\
             \hline
             $n^3$&$10^6$&$10^9$&$10^{18}$&$10^{27}$\\
             \hline
             $2^n$&$\approx 10^{30}$&$>10^{300}$&$>10^{10^5}$&$>10^{10^8}$\\
             \whline
             \end{tabularx}
             \end{center}

Gardez en tête que l'âge de l'Univers est environ de $10^{18}$ secondes...











\subsection{Exercices \og papier-crayon\fg{}}

\begin{exercice}[Complexité de l'algorithme d'Euclide et nombre d'or...]
On suppose dans toute la suite que $a$ et $b$ sont deux entiers naturels
tels que $a \geqslant b$.
  \begin{enumerate}
  \item Rappeler le principe de l'algorithme et de sa preuve.
  \item  Soit $r_n=a\wedge  b$ avec  les notations  habituelles: $r_0=b$
        puis      $r_1=a     \modu      b$,     $r_2=      r_1     \modu
        r_0$ et plus généralement:
$$r_{k+1}=r_kq_k+r_{k-1},\quad 0 \leqslant r_{k-1}<r_k$$ 

    Montrez que
        pour  tout entier  $k\in \bigl\{1,2,...,n\bigr\}$,  on  a $q_k
        \geqslant 1$ puis que $q_n \geqslant 2$.
  \item Soit    $\Phi=\frac{1+\sqrt{5}}{2}$   le   fameux   nombre
        d'or. Comparez $\Phi$ et $1+\frac{1}{\Phi}$.
      \item Montrez  par récurrence que $r_k  \geqslant \Phi^{n-k}$ pour
            tout entier $k\in \bigl\{0,1,...,n\bigr\}$.
\item  Déduisez-en  que $b  \geqslant  \Phi^{n}$  puis  que le  nombre
      d'appels récursifs de 
      l'algorithme d'Euclide est au maximum de $\frac{\ln b}{\ln
      \Phi}$.

  \end{enumerate}
\end{exercice}


\begin{exercice}[Nombre de diviseurs]
  Déterminez le nombre de diviseurs de $2^n$.
\end{exercice}

\begin{exercice}[Opérations sur les O]
  On suppose  que $f$, $g$, $F$,  $G$ sont des fonctions  de $\bbn$ dans
  $\bbr_+$ et que $f=O(F)$ et $g=O(G)$.

Rappelez la définition  des O et trouvez $\varphi$  et $\psi$ telles que
$f+g = O(\phi)$ et $fg=O(\psi)$.
\end{exercice}

\begin{exercice}[Bases]
  Écrire 355 en base 2 et en base 16.
\end{exercice}


\begin{exercice}[Bibinaire]
 Boby   \textsc{Lapointe},  célèbre   chanteur   français,  était   aussi
mathématicien à ses heures. Ayant  trouvé le code binaire trop compliqué
à utiliser, il inventa le  code... bibinaire. Il suffit de remplacer les
chiffres  par des lettres.  On commence  par couper  le nombre  écrit en
binaire en  paquets de  2.  S'il y  a un  nombre impair de  chiffres, on
rajoute un zéro à gauche, ce qui ne modifie pas la valeur de nombre.  On
commence par le premier
groupe de deux chiffres  le plus à droite. On remplace 00  par O, 01 par
A, 10 par E, 11 par I.\\
Puis on  prend le paquet  de deux chiffres  suivants en se  déplaçant de
droite à gauche. On remplace 00
par H, 01 par B, 10 par K, 11 par D.\\
Pour le paquet suivant, on recommence avec les voyelles. S'il y a encore
un groupe, on remplace par une consonne, etc.




Écrivez  les nombres  de  0 à  25  en bibinaire.   Pourquoi Boby  a-t-il
finement choisi le H~?

Écrivez la table de 3 en bibinaire.


Écrivez les  nombres de  255 à 257  en bibinaire.   Quel est la  base du
bibinaire~? Écrivez 355 en bibinaire.

Écrivez KEKIDI et HEHOBOBI en base 10.

Pourquoi est-il pratique  d'écrire les nombres en base  2 avec un nombre
de chiffres multiple de 4 avant de les traduire en bibinaire~?


\end{exercice}



\begin{exercice}[Groupe]
   Soit $ A=\frac{1}{3}\begin{bmatrix}
0&-2&-2\\
2&0&-1\\
2&1&0
\end{bmatrix}
$.



\begin{enumerate}
\item
Calculer $A^2,A^3$ et $A^4$.
\item  Montrez que  $\{A,A^2,A^3,A^4\}$ est  un groupe  pour  le produit
matriciel de ${\MR}_3(\bbr)$.
\item(INFO 2) On appelle $GL_3(\bbr)$ l'ensemble des matrices de taille 3 à
coefficients         réels        inversibles.         Est-ce        que
$\left(GL_3(\bbr),\times\right)$  est un  groupe? Est-ce  que  le groupe
étudié précédemment est un sous-groupe de $\left(GL_3(\bbr),\times\right)$ ?
%\item Que peut-on dire de ce groupe ?
\end{enumerate}

\end{exercice}




\begin{exercice}[Puissance]
Calculez à la main en un minimum d'opérations les deux derniers chiffres
de l'écriture en base 10 de $7^{73}$ puis de $6^{73}$
\end{exercice}



\begin{exercice}[Indicatrice d'Euler]\label{exo::phi}

Un  vieux théorème  publié  en  1247 par  le  mathématicien chinois  Qin
Jiushao mais utilisé dès le troisième siècle après JC et appelé
communément  \textit{théorème   chinois}  en  référence   au  \og  Sunzi
suanjing\fg{},   permet   de   montrer   un   résultat   primordial   en
cryptographie:
\begin{center}
{\itshape Si $m$ et $n$ sont premiers entre eux, alors
$\varphi(mn)=\varphi(m)\varphi(n)$ .}
\end{center}
Nous admettrons ce résultat.

\begin{enumerate}


\item Soit $p$ un nombre premier et $n$ un entier naturel non nul. 

Prouvez que $\varphi
\left(p^n\right)=p^n-p^{n-1}$ puis que, pour tout entier naturel non nul
$k$, $$\varphi(k)=k
\displaystyle\prod_{p\mid k}\left(1-\frac{1}{p}\right)$$



\item Calculez $\varphi(200)$ et $\varphi(1000)$.


Trouvez, DE TÊTE, les trois derniers chiffres de:
{\small
$$7895875463786378378378345453646538978977^{208582714591458551455135135135147454098258258001}$$
}


\item 
Comment  utiliser  le   théorème  d'\textsc{Euler}  pour  calculer  plus
simplement $m^e (\modu n)$ lorsque $m$ et $n$ sont
premiers entre eux?


\item  Cela est  très  important pour  le  RSA. Soit  un couple  $(p,q)$
      d'entiers  premiers. On  note  $n=pq$ leur  produit.  Soit $m$  un
      nombre plus petit que $p$ et $q$.

      Comment calculer plus simplement $m^e (\modu n)$? Quelle condition
      doit  remplir  $e$  pour  qu'il  existe  un  entier  $d$  tel  que
      $\left(m^e\right)^d\equiv m(\modu n)$?




% \item Imaginez  une  fonction  OCAML  calculant  $\phi(n)$ à  l'aide  de  deux
% accumulateurs tout en disposant des
% fonctions suivantes:


% \begin{lstlisting}[caption={}]
% let fonction_1(n)=
%   let rec loop = function
%       | (0 | 1),liste,acc -> acc
%       | n,[],acc -> acc
%       | n,tete::queue,acc ->
% 	  if n mod tete = 0 
%             then loop(n/tete,tete::queue,tete::acc)
%             else loop(n,queue,acc)
%   in 
%   loop(n,crible(n),[]);; 

% let fonction_2(liste) =
%   let rec loop  = function
%   | [],acc -> acc
%   | t::[],acc -> t::acc
%   | a::b::queue,acc -> if a = b then
%       loop(b::queue,acc)
%     else
%       loop(b::queue,a::acc)
%   in loop(liste,[]);;
% \end{lstlisting}
  
\end{enumerate}

\end{exercice}



\begin{exercice}[Lemme de Gau\ss]
Démontrez le lemme suivant:
\begin{theoreme}[Lemme de Gau\ss]
 $$   \forall (a, b, c)\in\mathbb{Z}^3, ( a|bc \land \operatorname{PGCD}(a,b)=1 ) \Rightarrow a|c $$
  \end{theoreme}
\end{exercice}


\begin{exercice}[Restes chinois]
  Voici une ré-écriture du théorème chinois:

  \begin{theoreme}[Théorème du reste chinois]

   Soit $m_1,m_2,...,m_n$ des entiers positifs premiers entre eux deux
   à deux. Le système:
   \begin{eqnarray*}
x&\equiv& a_1[x_1]\\
x&\equiv& a_2[x_2]\\
\vdots&\vdots&\vdots\\
x&\equiv& a_n[x_n]
   \end{eqnarray*}

admet une unique solution unique $x$ modulo $m=m_1\times m_2\times\cdots\times m_n$.
  \end{theoreme}

Occupons-nous de démontrer qu'il existe bien une solution $x$ du
problème modulo $m$. Il restera à démontrer son unicité.

Considérons les  entiers $M_k=m/m_k$:  montrez qu'il existe  un entier
$y_k$ tel que $M_k y_k\equiv 1 [m_k]$.

Montrez ensuite que $x=a_1M_1y_1+\cdots+a_nM_ny_n$ est une solution du problème.


\end{exercice}

%\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3cm]{tsingtao}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-5.75cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}

\begin{exercice}[Pirates chinois]
  
15 pirates chinois se partagent un butin constitué de pièces d'or.
Mais une fois le partage (équitable) effectué, il reste 3 pièces. Que
va-t-on en faire ? La discussion s'anime. Bilan : 8 morts. Les 7
survivants recommencent le  partage, et il reste cette fois-ci
2 pièces ! Nouvelle bagarre à l'issue de laquelle il ne reste que
4 pirates. Heureusement, ils peuvent cette fois-ci se partager les
pièces sans qu'il n'en reste aucune.
Sachant que 32 Tsing-Tao (bière chinoise) coûtent une pièce
d'or, combien (au minimum) de Tsing-Tao pourra boire chaque survivant
?
\end{exercice}


\begin{exercice}[Caml chinois]
  Créez une fonction \verb+chinois+ de signature:

  \begin{lstlisting}[caption={}]
# chinois;;
- : classe list -> classe = <fun>
  \end{lstlisting}

qui résout le problème des restes chinois.

Par exemple:

\begin{lstlisting}[caption={}]
# chinois [3%15 ; 2%7 ; 0%4];;
- : classe = {representant = 408; modulo = 420}
\end{lstlisting}



\end{exercice}




\begin{exercice}[Opération sur les grands nombres version 1]
Soit  $(x_1,x_2,...,x_n)$ une  liste de  $n$ nombres  entiers premiers
entiers deux à deux et soit $m$ leur produit.

Démontrez que tout entier $a$ positif inférieur à $m$ peut être représenté
de manière unique par un $n$-uplet:

\begin{lstlisting}[caption={}]
[a%m_1 ; a%m_2 ; ... ; a%m_n]
\end{lstlisting}

avec les notations Caml habituelles.

Soit $b=[99;98;97;95]$. Décomposez $123684$ et $413456$ dans cette \og
base\fg{} puis  effectuez la somme  des quadruplets obtenus.  Que vous
inspire cette méthode?

Proposez des fonctions Caml effectuant ces calculs automatiquement.
\end{exercice}



\begin{exercice}[Ordre d'un élément dans un groupe fini]
  \begin{enumerate}
\item Comment justifier que pour tout élément $g$ d'un groupe fini G,
il existe  un plus petit  entier $n$ tel  que $g^n=1_G$? On  appelle $n$
l'ordre de $g$.
\item Déterminez l'ordre des éléments de $\left(\ofr{\bbz}{9\bbz}\right)^*$.
\item Calculez $2^{1200000000003000000000600000002000040000020}(\modu 7)$.
  \end{enumerate}
\end{exercice}

\begin{exercice}[Permutations]
  \begin{definition}[Permutation]
    Soit  E  un ensemble.  Une  permutation  de  E est  une  application
    bijective  de E  sur  E. On  note  $\mathfrak{S}(E)$ l'ensemble  des
    permutations de E.
  \end{definition}


Généralement, on  note les permutations  sous forme d'une matrice  où la
première  ligne correspond aux  éléments de  E et  où la  deuxième ligne
correspond aux images des éléments de E.

Par exemple:


$$
\begin{pmatrix}
  1&2&3&4&5\\
3&1&2&5&4
\end{pmatrix}
$$

est une permutation de $E=\bigl\{1,2,3,4,5\bigr\}$.


\begin{definition}
  Soit  $n\in\bbn$,   alors  $\mathfrak{S}_n$  désigne   l'ensemble  des
  permutations de $\bigl\{1,2,3,...,n\bigr\}$.
\end{definition}

\begin{theoreme}[Groupe des permutations]\label{th::groupe_perm}
  L'ensemble $\mathfrak{S}(E)$ des permutations  sur un ensemble E, muni
  de la loi $\circ$ de composition des applications, a une structure de groupe.
\end{theoreme}

\begin{theoreme}[Nombre de permutations]\label{th::nb_perm}
  Le groupe $\mathfrak{S}_n$ est d'ordre $n!$.
\end{theoreme}


\begin{enumerate}
\item Démontrez le théorème \vref{th::groupe_perm}.
\item Démontrez le théorème \vref{th::nb_perm}.  Vous pourrez procéder par
      récurrence.  Pour  l'hérédité,  distinguez  les  permutations  qui
      envoient 1 sur un élément quelconque $x$.
\item Décrivez explicitement les groupes $\mathfrak{S}_2$ et $\mathfrak{S}_3$.
\item    En    cryptographie,     on    travaillera    sur    l'alphabet
      $E=\bigl\{0,1\bigr\}^n$ et on  effectuera souvent des \textit{permutations
      de bits} : seuls les positions des bits sont permutées.

On formalise ces permutations ainsi:
$$
 f\colon \begin{array}{rll} \bigl\{0,1\bigr\}^n & \to & \bigl\{0,1\bigr\}^n\\
   b_1b_2\cdots b_n& \mapsto & b_{\pi(1)}b_{\pi(2)}\cdots b_{\pi(n)}
 \end{array}
 $$

avec $\pi\in \mathfrak{S}_n$.

Une \textit{permutation circulaire  gauche} \og décale\fg{} les éléments
d'un nombre fixé  de \og rangs\fg{}. Par exemple,  voici une permutation
circulaire gauche:

$$
\begin{pmatrix}
  1&2&3&4&5\\
  3&4&5&1&2
\end{pmatrix}
$$

Décrire $\pi(k)$ dans le cas d'une permutation circulaire de bits de $i$
rangs vers la gauche.

On définit de même des permutations circulaires droite.

Combien y a-t-il de permutations circulaires dans $\mathfrak{S}_n$?

\end{enumerate}

\end{exercice}


\begin{exercice}[Chiffrement par blocs]\label{exo::bloc}

Commençons par une définition:

\begin{definition}[Cryptosystème (ou système de chiffrement ou chiffre)]
Un cryptosystème est un quintuplet $(\PR,\CR,\KR,\ER,\DR)$ tel que:
\begin{itemize}
\item L'ensemble $\PR$ est l'espace des messages en clair (\textit{plaintext} en
      anglais);
\item L'ensemble $\CR$ est l'espace des messages chiffrés (\textit{cyphertext} en
      anglais);
\item L'ensemble $\KR$ est l'espace des clés (\textit{key});
\item $\ER$  est la  famille des fonctions  de chiffrement, qui  vont de
      $\PR$ dans $\CR$;
\item $\DR$  est la  famille des fonctions  de déchiffrement, qui  vont de
      $\CR$ dans $\PR$;
\end{itemize}

Pour chaque élément  $e\in\KR$, il existe un élément  $d\in\KR$ tel que,
pour  tout  message  clair  $m$  de  $\PR$,  il  existe  $D_d\in\DR$  et
$E_e\in\ER$  telles que  $D_d(E_e(m))=m$. Les  fonctions $D_d$  et $E_e$
sont des applications injectives. Il est entendu que $d$ doit
rester secret...

\end{definition}


\begin{enumerate}
\item On travaille sur des  mots formés des 26 minuscules non accentuées
      de notre alphabet latin et d'une espace qui sont modélisés par les
      entiers de $E=\bigl\{0,1,2,...,26\bigr\}$.

Dans ce  contexte, on  remplace une \og  lettre\fg{} $x$ par  $kx (\modu
27)$ avec $k\in E$. Définit-on ainsi un cryptosystème?
\item  Un  cryptosystème  est   un  \textit{chiffrement  par  blocs}  si
      $\PR=\CR=A_n$ avec  $A_n$ l'ensemble des  mots de l'alphabet  A de
      longueur  $n$.   Est-ce  que  le  chiffrement  ROT-13  est  un
      chiffrement par blocs?

\item Pourquoi  les fonctions de chiffrement d'un  chiffrement par blocs
      sont des permutations?
\end{enumerate}

Depuis 2001, le  chiffrement par blocs \og officiel  \fg{} est l'AES qui
opère par blocs de 128 bits.  Une présentation de l'algorithme de chiffrement associé,
\textsc{Rijndael}, et de sa résistance aux attaques est présentée ici :
\href{http://www.cryptis.fr/assets/files/Canteaut-25ans-Cryptis.pdf}{http://www.cryptis.fr/assets/files/Canteaut-25ans-Cryptis.pdf}.

\end{exercice}


\begin{exercice}[Mode ECB]
  ECB: \textit{Electronic  CodeBook}. C'est le plus  simple...et le plus
  vulnérable des modes de chiffrement par blocs.


Voyons sur  un exemple.  On considère une  chaîne de bits  quelconque que
l'on découpe en  blocs de longueur fixe, par exemple  7 (plus pratique
pour ensuite utiliser  l'ASCII: pourquoi?). On rajoute
éventuellement des zéros en bout de chaîne.

Considérons $m=1001001111011$. On rajoute un 0 en bout de chaîne:

$$m'=1001001\ 1110110 =\beta_1\beta_2$$

avec $\beta_1=1001001$ et $\beta_2=1110110$.


On choisit une clé de chiffrement dans 
$\mathfrak{S}_7$ car $\KR= \mathfrak{S}_7$:
$\pi=
\begin{pmatrix}
  1&2&3&4&5&6&7\\
  3&1&4&2&6&5&7
\end{pmatrix}
$

Alors $E_{\pi}(\beta_1)=0110001$ et $E_{\pi}(\beta_2)=1101110$.

\begin{enumerate}
\item Quelle est la principale faiblesse du mode ECB?

\item Chiffrez  \og maman\fg{} avec ce cryptosystème  en transformant la
      chaine de lettres en chaînes de bits constituée des codes ASCII de
      ses   caractères.   Le   tableau   ASCII  standard   (cf   tableau
      \vpageref{ascii}) est-il satisfaisant? Comment y remédier?
\item  Quelle est  la  fonction de  déchiffrement  associée à  l'exemple
      précédent?
\item Déchiffrer $10110111001111$ sachant que la clé de
      chiffrement est $k=
  \begin{pmatrix}
    1&2&3&4&5&6&7\\
    2&3&1&7&6&5&4
  \end{pmatrix}
$
\item Déchiffrez \og papa\fg{} sachant  que c'est le cryptosystème de la
      question 2. qui a été employé.
\end{enumerate}
\end{exercice}


\begin{exercice}[Mode CBC]
  CBC:  \textit{Cipher-Block  Chaining}.  Ce  mode  a  été  inventé  par
  \textsc{Ibm} en  1976. Pour  éviter la faiblesse  de l'ECB,  les blocs
  sont maintenant chaînés: chaque bloc en clair est \og XORé\fg{} ou \og
  OUEXé\fg{} avec le bloc crypté précédent avant d'être crypté lui-même.

Pour le premier bloc, on utilise un \textit{vecteur d'initialisation} public.
Avec   les  notations   habituelles,  on   a   donc  $$c_i=E_k(m_i\oplus
c_{i-1}),\quad c_0 = \ve{v_0}$$


\begin{enumerate}
\item Quel est le lien entre OUEX et $\bbf_2$?
\item Cryptez l' exemple traité avec ECB en prenant $\ve{v_0}=1010101$.
\item Faites de même avec \og Maman\fg{}.
\item Donnez  une formule  de déchiffrement. Déchiffrer  le cryptogramme
      $101101110011111$ sachant que la clé est $k= 
  \begin{pmatrix}
    1&2&3\\
    2&1&3
  \end{pmatrix}
$ et que $\ve{v_0}=001$.
\item Déchiffrez \og Papa\fg{} sachant  que c'est le cryptosystème de la
      question 2. qui a été employé.
\end{enumerate}


Ce  mode  est efficace  mais  nécessite  l'utilisation  de fonctions  de
chiffrement  et de  déchiffrement différentes  ce qui  peut  ralentir la
procédure.
\end{exercice}


\begin{exercice}[Mode CFB]
  CFB:  \textit{Cipher-FeedBack}. C'est un  mode dérivé  de CFB  qui est
  utilisé  par  OpenPGP,  format  pour  l'échange  sécurisé  de  données
  (paiements sécurisés par exemple)
  largement  utilisé actuellement  mais est  susceptible  d'être attaqué,
  même s'il est très difficile  de mettre en \oe uvre concrètement cette
  attaque:

{\scriptsize
  \href{http://www.cert-ist.com/fra/ressources/Publications\_ArticlesBulletins/Autres/FailledanslechiffrementCFBdOpenPGP/}{http://www.cert-ist.com/fra/ressources/Publications\_ArticlesBulletins/Autres/FailledanslechiffrementCFBdOpenPGP/}
}

Le mode CFB utilise un registre de décalage de taille $r$ inférieure à 
celle de la clé.

On a  besoin d'un vecteur d'initialisation $\ve{v_0}$.  Le message clair
est découpé  en blocs  de longueur $r$.  Ensuite on procède  comme suit,
sachant que  les $b_j$ sont les blocs  en clair de longueur $n$ (celle de la
clé) et $m_j$ sont les blocs en clair de longueur $r$:

\begin{itemize}
\item $t_0=\ve{v_0}$;
\item $s_j=E_k(t_j)$;
\item $g_j$ est  la chaîne constituée des $r$ bits les  plus à gauche de
      $s_j$;
\item $c_j=m_j\oplus g_j$;
\item $t_j=(2^rt_{j-1}+c_{j-1}) \modu 2^n$.
\end{itemize}

Le déchiffrement fonctionne de manière identique en échangeant les rôles
de $m_j$ et $c_j$ à la quatrième étape.

\begin{enumerate}
\item   Avec  l'exemple  habituel   et  $\ve{v_0}=1010101$,   vérifiez  que
      $t_0=1010101$,    $m_0=100$,   $s_0=1100011$,    $g_0=110$,   $c_0=010$,
      $t_1=1010010$ puis chiffrez le message complet.
\item Déchiffrer  le cryptogramme
      $101101110011111$ sachant que la clé est $k= 
  \begin{pmatrix}
    1&2&3\\
    2&1&3
  \end{pmatrix}
$, que $r=2$ et que $\ve{v_0}=001$.
\end{enumerate}



\end{exercice}












%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\subsection{Exponentiation rapide}

\begin{exercice}[Complexité]
 Voici deux algorithmes:

\begin{multicols}{2}
\begin{algo}
\FUNC{algo1}{%
\pfarg{a,n}{entiers naturels}}{entier naturel}
\BEGIN
\IF{n=0}
\RETURN{1}
\ELSE
\RETURN{a*algo1(a,n-1)}
\ENDIF
\END
\end{algo}


 \begin{algo}
 \FUNC{algo2}{%
 \pfarg{a,n}{entiers naturels}}{entier naturel}
 \VAR
 \DECLVAR{i,r}{entiers}
 \ENDVAR
 \BEGIN
 \STATE{r \recoit{} 1}
 \FOR{i}{1}{n}
 \STATE{r \recoit{} a*r}
 \ENDFOR
 \RETURN{r}
 \END
 \end{algo}
 \end{multicols}

Que calculent-ils? Quelle est leur complexité?

En voici un troisième:


\begin{algo}
\FUNC{algo3}{%
\pfarg{a,n}{entiers naturels}}{entier naturel}
\BEGIN
\IF{n=0}
\RETURN{1}
\ELSE
\IF{n=1}
\RETURN{a}
\ELSE
\IF{n est pair}
\RETURN{algo3(a*a,n/2)}
\ELSE
\RETURN{a*algo3(a*a,(n-1)/2)}
\ENDIF
\ENDIF
\ENDIF
\END
\end{algo}

Que calcule-t-il? Quelle est sa complexité?

Comparez  le temps  de  calcul de  algo3($\numprint{1000000000}$) et  de
algo1($\numprint{1000000000}$) sur un  ordinateur équipé d'un processeur
3GHz effectuant une opération arithmétique élémentaire en 100 cycles.


Programmer \verb+algo3+  sur \textsc{Caml}. On  l'appellera \verb+prap a n+.


Calculer $2^{10}$.

On peut améliorer  l'efficacité du programme en essayant  que le dernier
appel de la fonction soit la dernière instruction à être évaluée.

Or ici,  on a \verb+a*algo3(a*a,(n-1)/2)+: la  dernière instruction est
une  composition par la  fonction addition  qui fait  intervenir l'appel
récursif.  Il  va  donc  falloir  empiler  puis  dépiler  les  résultats
intermédiaires.  On peut s'en  passer en  rajoutant un  accumulateur qui
contiendra le résultat  intermédiaire. \textsf{Caml} ensuite pourra très
simplement  (en  interne)   transformer  cette  récursion  terminale  en
itération et gagner en efficacité.


\sm



Essayez maintenant de calculer $2^{29}$, $2^{30}$, $2^{30}-1$, $2^{30}+1$.

Que donne:

\begin{lstlisting}[caption={}]
# max_int;;
# 1 + max_int;;
\end{lstlisting}



%\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3cm]{thinkbig}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-5cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}

Arghhhh...  Trois solutions: étudiez  le calcul  polynomial, ce  que nous
ferons au prochain chapitre, ou  bien utiliser le module \verb+BigInt+ de
\textsf{Caml}  pour  calculer en  multiprécision,  ou  bien utiliser  un
langage   comme   \textsc{Sage}   qui   \og  masque\fg{}   le   problème
informatique.

Nous  sommes en formation  initiale d'informatique  donc nous  ne devons
rien masquer...

Pour info, avec \verb+Big_int+, la syntaxe est un peu lourde...

\begin{lstlisting}[caption={}]
# Big_int.string_of_big_int(Big_int.power_int_positive_int 2 100);;
- : string = "1267650600228229401496703205376"
\end{lstlisting}


Voici   un  moyen  d'y   remédier:  on   va  redéfinir   les  opérations
arithmétiques et les tests pour travailler avec des grands entiers.

\begin{lstlisting}[caption={}]
#load "nums.cma";;
open Big_int;;

(* On définit des opérateurs infixes.
   Pour les distinguer, on les fait précéder d'une esperluette.
   On écrira a &+ b par exemple pour la somme des grands entiers a et b *)

let (&+) a b = Big_int.add_big_int a b;;
let (&*) a b = Big_int.mult_big_int a b;;
let (&%) a n = Big_int.mod_big_int a n;;
let (&/) a b = Big_int.div_big_int a b;;
let (&-) a b = Big_int.sub_big_int a b;;
let (&=) a b  =  Big_int.eq_big_int a b ;;

(* transforme un petit entier en grand entier *)

let big(n) =
  Big_int.big_int_of_int n;;

(* les petits entiers basiques *)

let zero = zero_big_int;;
let un = unit_big_int ;;
let deux = big(2) ;;

(* pour afficher un grand entier sous forme de chaîne *)

let montre(b) =
  Big_int.string_of_big_int b;;

(* Le pgcd pour plus tard  *)

let bgcd a b =
  Big_int.gcd_big_int a b ;;
\end{lstlisting}


Réécrire \verb+prap+  en \verb+bprap+  pour pouvoir travailler  avec des
grands entiers.  

Attention! On  ne pourra plus  utiliser le  filtrage par
motif: il faudra revenir à des conditionnelles \verb+if+...\verb+then+...\verb+else+

Ensuite, on définira un opérateur infixe plus pratique:

\begin{lstlisting}[caption={}]
let (&^) a n = bprap(a,n);;
\end{lstlisting}

Par exemple, on obtiendra $2^{512}$ avec:

\begin{lstlisting}[caption={}]
# deux &^ big(512) ;;
- : Big_int.big_int = <abstr>
# montre(deux &^ big(512)) ;;
- : string =
"13407807929942597099574024998205846127479365820592393377723561443
721764030073546976801874298166903427690031858186486050853753882811
946569946433649006084096"
\end{lstlisting}

\end{exercice}


\subsection{Petit théorème de \textsc{Fermat} et test de primalité}


\begin{exercice}[Puissance modulaire et nombres pseudo-premiers]
Pour  nos  calculs en  cryptographie,  nous  aurons  besoin de  calculer
$a^{p-1}(\modu p)$ avec $a$ ou $p$ des \og grands\fg{} nombres entiers.

Par      exemple,     que      vaut     $97^{p-1}(\modu      p)$     avec
$p=2^{500}-1$?...

Cela  risque  de  prendre pas  mal  de  temps  si nous  calculons  cette
puissance naïvement.


On va donc redéfinir nos opérations arithmétiques mais cette fois modulo
un entier $p$.  Choisissons par exemple de créer  des opérateurs infixes
précédés  cette  fois  de  deux  esperluettes pour  les  distinguer  des
précédents.

Pour  gagner  du  temps,  on  peut créer  une  fonction  polymorphe  qui
redéfinit l'opération \texttt{op} modulo $p$:

\begin{lstlisting}[caption={}]
(* fonction polymorphe définissant une opération op modulo p*)
let modop = fun a b p op ->
  ((op) (a &% p)  (b &% p)) &% p;;

(* Version infixe de la multiplication modulaire
    a*b mod p  est obtenu par a &&* (b,p) *)
let (&&*) a (b,p) =
  modop a b p (&*);;
\end{lstlisting}



Déterminez ensuite une fonction \verb+mprap a m p+ qui calcule efficacement
$a^m(\modu p)$.  
Elle sera du type:

\begin{lstlisting}[caption={}]
val mprap:Big_int.big_int*Big_int.big_int*Big_int.big_int -> Big_int.big_int = <fun>
\end{lstlisting}

Il ne restera plus qu'à créer l'opérateur infixe afférent:

\begin{lstlisting}[caption={}]
let (&&^) a (n,p) = mprap a n p;;
\end{lstlisting}



Calculez maintenant $97^{p-1}(\modu p)$ avec
$p=2^{500}-1$.

Cela ne fait pas 1! Donc $p$ n'est pas premier (pourquoi?) et la réponse
a été donnée immédiatement! C'est
quand même  assez fort: on  arrive, grâce au \textit{petit}  théorème de
\textsc{Fermat}, à  démontrer qu'un entier de  113 chiffres (presque...)
pris au hasard n'est pas premier.


Maintenant, que se  passe-t-il si le résultat est  effectivement 1? Cela
fait-il de $n$ un nombre premier? 

Par  exemple,  calculez  $2^{341-1}(\modu  341)$.  Est-ce  que  341  est
premier? Comment expliquer ce résultat? 

On dit que 341 est \textbf{pseudo-premier} de base 2.

Créez   une  fonction   \verb+pseudo(a,n)+  qui   renvoie   les  entiers
pseudo-premiers de base $a$ inférieurs  à $n$. On travaillera cette fois
avec   des  petits   entiers   pour  avoir   à   disposition  la   liste
\texttt{crible(n)} des entiers premiers inférieurs à $n$.

On créera au préalable une fonction \texttt{appartient : 'a * 'a list ->
bool} qui  teste si  une variable appartient  à une liste  d'éléments de
même type.

Par exemple:

\begin{lstlisting}[caption={}]
# pseudo(2,10000);;
- : int list =
[8911; 8481; 8321; 7957; 6601; 5461; 4681; 4371; 4369; 4033; 3277; 2821;
 2701; 2465; 2047; 1905; 1729; 1387; 1105; 645; 561; 341]
\end{lstlisting}


Testez \verb+pseudo(3,10000)+, \verb+pseudo(5,10000)+, etc.



 Pour des nombres
plus grands,  il n'est pas facile  de savoir si  ceux-ci sont réellement
premiers. Puisqu'on ne sait pas a priori s'ils le sont, on les appelle 
des nombres  probablement premiers\index{nombre!probablement premier} de
base $a$.  Certains sont 
probablement premiers d'une seule base. Par exemple:

\begin{lstlisting}[caption={}]
# montre(mprap(2,big(340),big(341)));;
- : string = "1"
# montre(mprap(3,big(340),big(341)));;
- : string = "56"
\end{lstlisting}


Ainsi,   nous   pouvons   accumuler   les  bases   pour   éliminer   les
candidats. Malheureusement, il existe encore une infinité de nombres qui
sont 
probablement premiers dans toutes les bases, tout en étant composés:


\begin{definition}[Nombre de \textsc{Carmichael}]
Un entier composé $n$ est un \textbf{nombre de \textsc{Carmichael}} si $a^{n-1}\equiv 1(\modu n)$ pour tout entier $a$ premier avec $n$
\end{definition}

  
%\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=2.5cm]{carmichael}
\caption{ { Robert \textsc{Carmichael}\\ (1879 - 1967)}}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-5cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}


Pour se donner un ordre de grandeur,  il y a un peu plus d'un million de
nombres premiers inférieurs à 25 milliards, mais seulement 
$21\,853$ pseudo-premiers de base quelconque et parmi eux $2\,163$ nombres de
Carmichael. C'est peu, mais c'est toujours trop! 


Le  plus   petit  nombre  de  \textsc{Carmichael}  est   561.  En  1994,
\textsc{Alfort},    \textsc{Grandville}   et    \textsc{Pomerance}   ont
démontré qu'il y avait une infinité de nombres de \textsc{Carmichael}.

Il a de plus été démontré qu'un nombre de \textsc{Carmichael} $n$ est le
produit d'au moins trois facteurs premiers impairs $p_i$ distincts et pour
chacun des $p_i$, $n-1$ est divisible par $p_i-1$.

% Il  existe de merveilleux outils dédiés,  par exemple le
% logiciel
% \textsf{Aribas}(\href{http://www.mathematik.uni-muenchen.de/~forster/sw/aribas.html}{http://www.mathematik.uni-muenchen.de/~forster/sw/aribas.html}).


Il nous  faut des outils plus  performants donc il nous  faut creuser un
peu plus profondément dans la mine mathématique...


\end{exercice}







\subsection{Grands nombres premiers}


En  cryptographie à clé  publique, on  a besoin  de très  grands nombres
premiers car on travaille avec des nombres de l'ordre de 1024 bits voire
plus.

On adopte alors une approche probabiliste comme nous l'avons évoqué avec
le   test  de  \textsc{Fermat}   et  les   nombres  \textit{probablement
premiers}.



\begin{exercice}[Algorithme de \textsc{Rabin-Miller}]


%\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=3cm]{rabin}
\caption{Michael \textsc{Rabin} (1931)}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-3.85cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}


Gary \textsc{Miller}  est professeur  à l'université Carnegie  Mellon de
Pittsburgh.  Il mit au point un premier  test de primalité de complexité
polynomiale en  1975 pendant  qu'il était au  \textsc{Mit} Cependant,  ce test
dépendait d'une hypothèse non  encore démontrée (la fameuse hypothèse de
\textsc{Riemann} dont la démonstration est mise à prix un million de dollars...).
En visite au \textsc{Mit} au même moment, 
le  prix \textsc{Turing} israélien  Michael \textsc{Rabin}  s'inspira du
test  de  \textsc{Miller}  en   évitant  le  recours  à  l'hypothèse  de
\textsc{Riemann} mais en le rendant probabiliste. 



  


Nous allons le décortiquer et l'utiliser avec Ocaml.


Prenons un entier $a$ strictement inférieur  à un entier $n$. Si $n$ est
premier, nous avons vu que  $a^{n-1}\equiv 1 (\modu n)$ d'après le petit
théorème de  \textsc{Fermat} mais tester  cette opération sur  de grands
nombres peut être coûteuse.  Voici une idée pour éliminer plus rapidement certains
candidats.

Si  $n=2$, on  n'a  pas besoin  d'allumer  un ordinateur.  On peut  donc
considérer que $n$ est impair donc que $n-1$ est ....

\begin{recherche}
  \begin{enumerate}
  \item Déterminez une fonction qui calcule $s$ et $t$ tel que $n-1=2^ts$.
  \item Résolvez l'équation $x^2\equiv 1 (\modu n)$. Que se passe-t-il si $n$ est premier?
  \item Montrez que si $n$ est premier et impair, alors:

$
\begin{cases}
  a^s\equiv 1 (\modu n)\\
\text{ou}\\
\exists u \in \bigl\{0,1,..,t-2\bigr\}\mid a^{2^us}\equiv n-1 (\modu n)

\end{cases}
$
\item Comment en déduire un test de non-primalité sur $n$?
  \end{enumerate}
\end{recherche}

 Si $n$ ne passe pas
le test pour un certain $a$,  on dit que $a$ est un \textit{témoin fort}
pour la composition de $n$.  Sinon, il est
\textit{fortement   probablement   premier}.   Si  $n$   est   fortement
probablement  premier tout  en  étant composé,  on  dit que  $a$ est  un
\textit{menteur fort} et que $n$ est \textit{pseudo-premier fort}.

\smallskip

On peut montrer que pour chaque entier impair $n$ composé, au moins 75\%
des bases $a$ sont des témoins forts pour la composition de $n$.

Appelons $E_a$ l'évènement \og $n$ est pseudo-premier fort pour une
base $a$ donnée\fg{}.

On choisit \og au hasard\fg{} un nombre $n$ et une base $a$.

\begin{recherche}
  \begin{enumerate}
  \item Majorez $\Pr(E_a)$.
\item  On  suppose  qu'on  choisit  aléatoirement  les  bases  $a$  dans
      $\bigl\{0,1,...,n-1\bigr\}$ et que les évènement $E_a$ et $E_{a'}$
      sont \textbf{indépendants} pour tout couple $(a,a')$ de bases. Que
      peut-on en déduire sur $\Pr(E_a\cap E_{a'})$?
    \item  Combien de  bases va-t-on  tester au  maximum pour  avoir une
          probabilité d'obtenir un nombre pseudo-premier fort inférieure
          à $2^{-128}$? (soit environ la probabilité de gagner cinq fois
          de suite le gros lot  de l'euromillions en jouant une grille à
          chaque fois...)
  \end{enumerate}
\end{recherche}

Voici  maintenant une  fonction qui  renvoie un  grand  entier aléatoire
dans $[0,2^n[$:

\begin{lstlisting}[caption={}]
exception Taille_negative;;

(* nombres aléatoires (d'après le module numerix de Michel Quercia) *)
(* land est le ET logique bit à bit : plus rapide que mod
   1 lsl p effectue un décalage de 1 bit : plus rapide que 2^p
   0xn est l'entier écrit n en base 16
   On travaille donc par paquet de 16^4
   La fonction calcule un nombre < 2^n et >= 2*)
let nrandom n =
  if n < 0 then raise Taille_negative
  else if n = 0 then big(0)
  else begin
    let p = if n land 15 = 0 then 16 else n land 15 in
    let mask = (1 lsl p) - 1 in
    let r = ref(big(((Random.int(0xfffe)) land (mask-2))+2)) in
    for i=1 to (n-p)/16 do
        r := add_int_big_int (Random.int(0x10000)) (mult_int_big_int 0x10000 !r)
    done;
    !r
  end
;;
\end{lstlisting}

Par  exemple, on  obtient  un entier  aléatoirement  choisi inférieur  à
$2^{1024}$:

\begin{lstlisting}[caption={}]
# string_of_big_int (nrandom 1024);;
- : string =
"80656880405872425890276287356861322138632224126908132719794577622082089
570648391032886827216131476652080837091044633285960027260972618105376445
747915191582159520958877446837732340232267171589094471897323988030323601
722168712066726223056599223972610567014149632713729501105653037785316798
927182986135540715685"
\end{lstlisting}


Voici quelques fonctions mystérieuses:



\begin{lstlisting}[caption={}]
let fonction_1(n) =
  let rec loop(s,t) =
    if (s &% deux) &= zero then
      loop( s &/ deux , t &+ un )
    else
      [|s;t|]
  in loop(n &- un,zero);;

let fonction_2(v,n,t) =
  if v &= un then
    true
  else
    let rec loop(v,u) =
      if v &= (n &- un)  then
	true
      else
	if u &= (t &- un) then
	  false
	else
	  loop( v &&^ (deux,n) , u &+ un )
    in loop(v,zero);;

let fonction_3(n) =
  int_of_float(log(float_of_big_int(n))/.log(2.));;
\end{lstlisting}


\begin{recherche}
Analysez  les  fonctions précédentes  et  utilisez-les  dans une  fonction
\texttt{rabin\_miller(n)}  qui renverra \texttt{true}  si le  nombre est
fortement probablement premier et \textsc{false} sinon.




Une  remarque:  il  existe  une  valeur maximale  des  nombres  de  type
\texttt{float} donnée par  \texttt{max\_float} au-delà de laquelle toute
variable de ce type est considérée comme $\infty$.

En quoi cela peut-il limiter notre calcul? Comment y remédier?

Testez avec \verb+rabin_miller((deux &^ big(607)) &- un)+
\end{recherche}




\end{exercice}

\begin{exercice}[Test de primalité pour grands entiers]
Créez une fonction \texttt{est\_premier}  qui vérifie si un grand entier
est  \og fpp\fg{}  à l'aide  du  test de  \textsc{Rabin-Miller} mais  en
commençant tout  d'abord par  tester s'il est  divisible par  des petits
nombres premiers inférieurs à 1000.
\end{exercice}










\begin{exercice}[Génération de grands nombres premiers.]
Nous avons besoin  de déterminer une borne supérieure  de la probabilité
qu'un nombre testé et déclaré premier soit en fait composé.

Par exemple, on peut se demander quelle est la probabilité qu'un nombre $n$
de 2001 bits de long soit premier. 

Il est compris  entre $2^{2000}$ et $2^{2001}$ : il  y a donc $2^{2000}$
tels nombres.  Si l'on arrive à  estimer $\pi(n)$, le  nombre de nombres
premiers inférieurs  à $n$, nous allons  voir que cela  nous donnera une
estimation  de  la  probabilité  de  tomber sur  un  nombre  premier  en
choisissant un nombre au hasard dans l'intervalle $[2^{2000},2^{2001}[$.


\begin{recherche}
  On  notera   $\pi(n)$  le  nombre  de  nombres   premiers  inférieurs  à
$n$. Comment le calculer avec nos fonctions précédemment créées?
\end{recherche}


Existerait-il une loi régissant la fonction $\pi$~?

 À la fin du XVIII\eme siècle, \textsc{Gauss} conjecture que, lorsque $x$ tend vers  l'infini, $\pi(x)$ est équivalent à
$\text{Li}(x)=\ds\int_2^x\fr{{\rm d}t}{\ln t}$. À la même époque,\textsc{ Legendre} pense que $\pi(x)$ est équivalent à $\fr{x}{\ln x}$.

 Notez bien que dire que  $a(x)$ et $b(x)$ sont équivalents au voisinage
 de l'infini signifie, sous certaines conditions, que $\Lim{+\infty}\fr{a(x)}{b(x)}=1$.
 Mais attention, cela ne veut pas dire que $a(x)-b(x)$ est petit. Par exemple
$\Lim{+\infty}\fr{x^2+x}{x^2}=1$, mais leur différence $x^2+x-x^2=x$ tend vers l'infini.

 Cela veut juste dire que $\ln x/x$ et ${\rm Li}(x)$  seraient des approximations de
$\pi(x)$ au voisinage de $+\infty$. En fait, on peut employer n'importe quelle expression du type $\fr{x}{\ln x-a}$ avec $a$ une
constante arbitraire et on obtient le même résultat.

Le tableau suivant nous permet de nous faire une idée sur des petits (eh oui) nombres premiers:

\begin{center}
\begin{tabular}{|r||r|r|r|r|}
\hline
$x$& $\pi(x)$ & Li$(x)$ & $\frac{x}{\ln x} $ & $\frac{x}{\ln x-1}$\\
\hhline{=====} $1\,000$ & $168$ & $178$ & 172 &169\\
\hline $10\,000$ & $1\,229$ & $1\,246$ & $1\,231$ & $1\,218$\\
\hline $1\,000\,000$ & $78\,498$ & $78\,628$ & $78\,534$ & $78\,030$\\
\hline $10\,000\,000\,000$ & $455\,052\,511$& $455\,055\,614$ & $455\,743\,004$ & $454\,011\,971$\\
\hline
\end{tabular}
\end{center}



%\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=3cm]{hadamard}
\caption{Jacques \textsc{Hadamard } \\ (1865 - 1963)}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-5.5cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}


Le problème,  c'est que ces  conjectures n'avaient pas été  prouvées par
leurs  auteurs. Cinquante  ans plus  tard, le  russe \textsc{Tchebychev}
établit une estimation de $\pi(x)$:

$$(c_1+\e_1(x))\fr{x}{\ln x}\ie\pi(x)\ie\fr{6}{5}(c_1+\e_2(x))\fr{x}{\ln
  x}$$



avec
$c_1=\ln\pa{\fr{\sqrt{2}\times\sqrt[3]{3}\times\sqrt[5]{5}}{\sqrt[30]{30}}}\simeq0,92129$
et $\Lim{+\infty}\e_1(x)=\Lim{+\infty}\e_2(x)=0$

Il a fallu attendre 1896 pour que \textsc{Hadamard} et \textsc{La Vallée
  Poussin} prouvent,  suite à d'importants  travaux de \textsc{Riemann},
et indépendamment l'un de l'autre, le fameux théorème des nombres
premiers.

Il fut amélioré en 1901 par \textsc{Von Koch} sous la forme

$$\ab{\pi(x)-\int_2^x\fr{dt}{\ln  t}}\ie c\sqrt{x}\ln  x$$ avec  $c$ une
 constante  positive   mais  en   supposant  que  la   conjecture  de
 \textsc{Riemann} (mise à prix un million de dollars!) soit vraie...

Ce  théorème permet  en  particulier  de monter  que  le $n$\eme  nombre
premier  $p_n$   est  <<~de  l'ordre  de~>>  $n\ln(n)$   quand  $n$  est
suffisamment grand.

\begin{NB} 
En tant qu'informaticien, il sera  utile de retenir que, lorsque $n$ est
grand, $\pi(n)\approx \frac{n}{\ln(n)}$.
\end{NB}




\begin{recherche}
  
Revenons à notre problème probabiliste. Il y a $\pi(n)$ nombres premiers
entre  1 et  $n$.  Pour de  grandes  valeurs de  $n$,  par exemple  dans
l'intervalle   $[2^{2000},2^{2001}[$,  quelle   est  alors   la  densité
approximative de nombre premiers? 
Généralisez. Est-il licite de prendre comme approximation de la densité
$\frac{1}{\ln(2^n)}$?

\end{recherche}



Voici une  nouvelle fonction qui renvoie un  nombre aléatoirement choisi
dans l'intervalle $[2^{n-1},2^{n}[$:



\begin{lstlisting}[caption={}]
let nrandom1 n =
  if n < 0 then raise Taille_negative 
  else if n = 0 then zero_big_int
  else begin
    let p = if n land 15 = 0 then 16 else n land 15 in
    let mask = 1 lsl (p-1) in
    let r = ref(big_int_of_int((Random.int(0x10000) land (mask-1)) lor mask)) in
    for i=1 to (n-p)/16 do
        r := add_int_big_int (Random.int(0x10000)) (mult_int_big_int 0x10000 !r)
    done;
    !r
  end
;;
\end{lstlisting}



\begin{recherche}
Créez une fonction \texttt{genere\_premier} qui calcule un nombre premier
appartenant  à l'intervalle  $[2^{n-1},2^{n}[$. En  allant souvent  à la
ligne, huit petites lignes suffiront...
\end{recherche}

\end{exercice}







\subsection{Cryptographie}

\begin{exercice}[Ave César]
  
%\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3cm]{asterix1}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-3.85cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}

On veut créer  une fonction \lstinline+cesar cle message+  qui code  un message
rentré sous forme d'une chaîne selon la méthode bien connue de César, en
se  donnant la possibilité  de choisir  sa clé.  On travaillera  avec un
alphabet de 95 lettres décrit dans le tableau \vpageref{ascii}.



La  fonction \verb+int_of_char+  renvoie  le code  ASCII d'un  caractère
(non accentué:A comme \emph{american}...).

Il y a 95 caractères qui commencent  à 32 et finissent à 126 (les autres
codes  correspondent  à  des   touches  d'action  comme  le  \og  retour
chariot\fg{}).

Nous allons donc ajouter la clé  au code des caractère modulo 95 mais il
faudra avant enlever  32 puis le rajouter à la  fin pour travailler avec
des caractères et non pas des actions.






% %\vspace{-6.2cm}
% \setindent{0cm}
% \begin{flushleft}
% \begin{minipage}[t]{3cm}
% \begin{figure}
%   \includegraphics[width=3cm]{curry}
% \caption{Haskell \textsc{Curry}}
% \end{figure}
% \end{minipage}
% \end{flushleft}
% \setindent{\indentationcours}
% \vspace{-5cm}
% \begin{minipage}[t]{\linewidth}


% \end{minipage}

% \begin{idee}[CURRYFICATION]

% Le   mathématicien  américain   Haskell  \textsc{Curry}   (1900-1982)  a
% largement développé le 
% \textbf{lambda-calcul} d'Alonzo \textsc{Church} qui constitue la base théorique de la
% programmation fonctionnelle. Une fonction  curryfiée est une fonction de
% plusieurs  variables transformée  en une  fonction d'une  seule variable
% renvoyant une fonction.

% Par exemple, créons une fonction  curryfiée qui semble renvoyer la somme
% de deux entiers:

% \begin{lstlisting}[caption={}]
% # let biplus x y = x+y;;
% val biplus : int -> int -> int = <fun>
% \end{lstlisting}

% Cette définition est différente de celle-ci, plus habituelle:

% \begin{lstlisting}[caption={}]
% # let monoplus(x,y) = x+y;;
% val monoplus : int * int -> int = <fun>
% \end{lstlisting}

% mais est identique à celle d'un opérateur infixe:

% \begin{lstlisting}[caption={}]
% # let (++) x y = x+y ;;
% val ( ++ ) : int -> int -> int = <fun>
% \end{lstlisting}

% Notons $\FR(D,A)$ l'ensemble des fonctions de $D$ vers $A$. 

% Alors     $\mathtt{biplus}\in\FR
% \bigl(      \bbn,      \FR(\bbn,\bbn)        \bigr)$            mais
% $\mathtt{monoplus}\in\FR(\bbn\times\bbn,\bbn)$: ce n'est pas pareil!

% En  effet, \verb+biplus  x+ est  elle-même une  fonction de  $\bbn$ dans
% $\bbn$ qui à un entier $n$ associe l'entier $n+x$. Par exemple, avec 3:

% \begin{lstlisting}[caption={}]
% # let plus3 = biplus 3;;
% val plus3 : int -> int = <fun>
% # plus3 5;;
% - : int = 8
% \end{lstlisting}

% Cette  possibilité existe  aussi  dans des  langages non  spécifiquement
% fonctionnels  comme Python  qui dispose  de la  fonction \verb+lambda+
% qui renvoie une fonction \og anonyme\fg{}:

% \sage

% \begin{lstlisting}[caption={}]
% >>> def biplus(x): return lambda y: x+y
% ... 
% >>> biplus(2)(3)
% 5
% >>> def plus3(t): return biplus(3)(t)
% ... 
% >>> plus3(5)
% 8
% \end{lstlisting}
% \caml
% \end{idee}




\begin{NB}[char et string]
Il   faut   bien  distinguer   \verb+'a'+,   \verb+"a"+!
Mathématiquement, c'est la distinction  que l'on fait entre les éléments
de l'alphabet
$\Sigma$ et ceux du langage associé $\Sigma^\star$. 
\end{NB}



Créez une fonction \verb+code cle car+ qui satisfait à ces exigences.

\begin{lstlisting}[caption={}]
# code 13 'A';;
- : char = 'N'
\end{lstlisting}


\begin{DANGER}[mod et rem]
  Testez avec \verb+code # (-15)+.  Que se passe-t-il? Comment fonctionne
  le  \verb+mod+  d'OCaML?  Comparez  avec notre  \verb+rem+. 
\end{DANGER}

% \begin{lstlisting}[caption={codage numérique d'une chaîne}]
% # let code(car,cle) = 
%    String.make 1 (char_of_int(((int_of_char(car)-32+cle) % 95)+32));;
% \end{lstlisting}



%\begin{center}
\begin{table}[h!]\label{ascii}
{\footnotesize
\begin{tabularx}{\linewidth}{Il*{19}{|X}I}
\whline
Caractère&  & ! & " & \# & \$ & \% & \& & ' & (  & ) & * & + & , & - & . & / & 0 & 1 & 2 \\
\hline
Code & 32 & 33 & 34 & 35 & 36 & 37 & 38 & 39 & 40 & 41 & 42 & 43 & 44 & 45 & 46 & 47 & 48 & 49 & 50 \\
\hline
\end{tabularx}


\begin{tabularx}{\linewidth}{Il*{19}{|X}I}
\hline
Caractère&3 & 4 & 5 & 6 & 7 & 8 & 9 & : & ; & < & = & > & ? & @ & A & B & C & D & E \\
\hline
Code &51 & 52 & 53 & 54 & 55 & 56 & 57 & 58 & 59 & 60 & 61 & 62 & 63 & 64 & 65 & 66 & 67 & 68 & 69\\
\hline
\end{tabularx}



\begin{tabularx}{\linewidth}{Il*{19}{|X}I}
\hline
Caractère&F & G & H & I & J & K & L & M & N & O & P & Q & R & S & T & U & V & W & X \\
\hline
Code &70 & 71 & 72 & 73 & 74 & 75 & 76 & 77 & 78 & 79 & 80 & 81 & 82 & 83 & 84 & 85 & 86 & 87 & 88\\
\hline
\end{tabularx}





\begin{tabularx}{\linewidth}{Il*{19}{|X}I}
\hline
Caractère& Y & Z & [ & \verb+ \ + & ] & \verb+ ^ + & \verb+ _ + & \verb+ ` + & a & b & c & d & e & f & g & h & i & j & k \\
\hline
Code & 89 & 90 & 91 & 92 & 93 & 94 & 95 & 96 & 97 & 98 & 99 & 100 & 101 & 102 & 103 & 104 & 105 & 106 & 107 \\
\hline
\end{tabularx}



\begin{tabularx}{\linewidth}{Il*{19}{|X}I}

\hline
Caractère& l & m & n & o & p & q & r & s & t & u & v & w & x & y & z & \{ & | & \} & \verb+~+ \\
\hline
Code & 108 & 109 & 110 & 111 & 112 & 113 & 114 & 115 & 116 & 117 & 118 & 119 & 120 & 121 & 122 & 123 & 124 & 125 & 126\\
\whline
\end{tabularx}
}
\caption{Table des caractères ASCII affichables}
\end{table}

%\end{center}

Enfin, créez la fonction principale récursive \verb+cesar cle mot+. 


% \begin{lstlisting}[caption={codage de César en récursif}]
% # let rec cesar(mot,cle) =
%    if mot="" then ""
%    else  (code(mot.[0],cle))^cesar(queue(mot),cle);;
% \end{lstlisting}


Par exemple, si on code avec la clé $13$~:


\begin{lstlisting}[caption={}]
# cesar 13 "Je ne suis pas un numero ! Je suis un homme libre !!!";;
- : string = "Wr-{r-!#v!-}n!-#{-{#zr |-.-Wr-!#v!-#{-u|zzr-yvo r-..."
\end{lstlisting}

Comment  décode-t-on? 


\begin{remarque}
  La fonction  \verb+tr+ (comme translation) du shell  bash peut remplir
  ce rôle:

\verb+$ echo "Je ne" | tr '\!-~' '\.-~\!-\-'+

\verb+Wr {r+


\end{remarque}
\end{exercice}
















%%%%    


\begin{exercice}[Chiffrement affine]

Ce n'est pas trop dur de casser le code de \textsc{César}. Nous allons
essayer de faire mieux en utilisant nos outils arithmétiques.  


% %\vspace{-6.2cm}
% \setindent{0cm}
% \begin{flushleft}
% \begin{minipage}[t]{3cm}
% %\begin{figure}
%   \includegraphics[width=3cm]{casinoroyal}
% %\end{figure}
% \end{minipage}
% \end{flushleft}
% \setindent{\indentationcours}
% \vspace{-5cm}
% \begin{minipage}[t]{\linewidth}


% \end{minipage}

On considère toujours les 95 caractères affichables et on les associe aux nombres 0, 1, 2,...,94.

  On code ces nombres à
l'aide d'une fonction $f$ du type:
$$f : \ x\mapsto (ax+b) \modu 95$$
où $a$ et $b$ sont des entiers.  On aura remarqué que le chiffrement de César
est en fait un cas particulier du chiffrement affine avec $a=1$.

Si votre  César a été bien  conçu, il n'y  a pas grand chose  à modifier
pour créer une fonction \verb+chiffre_affine+:


Considérons par exemple $f(x)=(17x+22) \modu 95$ et le message \og La maîtresse en maillot
de bain\fg{}.


\begin{lstlisting}[caption={}]
# chiffre_affine 17 22 "La maitresse en maillot de bain";;
- : string = "*r6!r<9vW((W6W26!r<ooC96FW6r<2"
\end{lstlisting}



Comment décrypter ce message? On cherche $g$ telle que:


\[
\text{transmis }= f(\text{original})  \Leftrightarrow 
\text{original} g(\text{transmis}) \text{ dans }\bbz_{95}\]

On a donc
besoin de  connaître l'inverse  de $a$ dans  $\bbz_{95}$...en s'assurant
qu'il existe!


\begin{lstlisting}[caption={}]
# inv_mod (17 % 95);;
- : classe = {representant = 28; modulo = 95}
\end{lstlisting}

puis on décode:


\begin{lstlisting}[caption={}]
# dechiffre_affine 17 22  "*r6!r<9vW((W6W26!r<ooC96FW6r<2";;
- : string = "La maitresse en maillot de bain"
\end{lstlisting}


\end{exercice}



\begin{exercice}[Le système RSA]


% \vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
% \begin{figure}
\includegraphics[width=3cm]{rsa}
% \end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-3cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}


Ronald \textbf{R}\textsc{ivest}, Adi \textbf{S}\textsc{hamir} et Leonard
\textbf{A}\textsc{dleman} mirent  au point en 1977 un  système de codage
alors qu'ils  essayaient au départ  de démontrer que ce  qu'ils allaient
développer  étaient une  impossibilité  logique: aah,  la  beauté de  la
recherche...





Et savez-vous quel  est la base du système? Le  petit théorème de Fermat
bien sûr!  Mais replaçons dans son contexte les résultats de R, S et
A.  Il n'y a pas si longtemps, la cryptographie était l'apanage des
militaires et  des diplomates. Depuis, les banquiers,  les mega business
men et women, les consommateurs internautes, les barons de la drogue ont
de plus en plus recours aux  messages codés. Oui, et alors? Le problème,
c'est que jusqu'ici, l'envoyeur et le destinataire partageaient une même
clé secrète qu'il fallait faire  voyager à l'insu de tous: les appareils
d'état ont la valise diplomatique, mais les autres?

C'est  ici  que  Whitfield  \textsc{Diffie} et  Martin  \textsc{Hellman}
apparaissent un an auparavant, en 1976, avec leur idée de principe qu'on
peut résumer ainsi: votre amie  Josette veut recevoir de vous une lettre
d'amour mais  elle a peur que  le facteur l'intercepte et  la lise. Elle
fabrique donc  dans son petit atelier  une clé, un cadenas  et une boîte
vide .   Elle vous envoie  le cadenas, ouvert  mais sans la clé,  par la
poste, donc  à la  merci du facteur:  le cadenas est  appelé \textit{clé
  publique}. Vous recevez le cadenas et l'utilisez pour fermer une boîte
contenant votre lettre:  le facteur ne peut pas l'ouvrir  car il n'a pas
la  clé. Josette  reçoit  donc la  boîte  fermée: elle  utilise sa  clé,
qu'elle seule possède, pour ouvrir la boîte et se pâmer devant vos élans
épistolaires.


En  termes plus  mathématiques, cela  donne :  je fabrique  une fonction
$\pi$ définie sur $\bbn$ qui possède une réciproque $\sigma$. On suppose
qu'on peut fabriquer de telles fonctions mais que si l'on ne connaît que
$\pi$, il est (quasiment)  impossible de retrouver $\sigma$. La fonction
$\pi$ est donc  la clé publique: vous envoyez  $\pi$(message) à Josette.
Celle-ci         calcule        $\sigma\bigl(\pi(\text{message})\bigr)=$
message. Josette est  la seule à pouvoir décoder  car elle seule connaît
$\sigma$.

Tout  ceci   était  très  beau   en  théorie  mais   \textsc{Diffie}  et
\textsc{Hellman} n'arrivèrent  pas à proposer de  telles fonctions. Mais
voici qu'arrivent Ronald, Adi et Leonard...


Nous utiliserons des fonctions  \verb+code+ et \verb+decode+ dérivées de
celles vues précédemment.



Avant d'envoyer un message,  on doit connaître la \textit{clé publique},
connue de tous et constituée d'un couple de nombres $(n,e)$.

Et avant de connaître cette clé, il faut la fabriquer - secrètement
- de la manière suivante:

On  commence  par  fabriquer  deux  nombres  premiers  quelconques  mais
suffisamment grands, par  exemple de l'ordre de 1000  bits (300 chiffres
décimaux):

\begin{lstlisting}[caption={}]
let p = genere_premier 1000;;
let q = genere_premier 1000;;
\end{lstlisting}


Ces deux nombres ne sont connus que d'une personne: c'est la \textit{clé
  privée}.  Pour plus  de clarté, nous appellerons la  personne qui crée
la  clé Aliona  et la  personne  qui va  utiliser la  clé publique  pour
envoyer le message Boris.


Aliona forme le produit de ces deux nombres.


\begin{lstlisting}[caption={}]
let n = p &* q ;; 
\end{lstlisting}



Ce nombre  $n$ est  le module  publique d'Aliona. Il  reste à  former le
nombre $e$ qui est la puissance de cryptage publique. Là encore, cela se
fait par étapes.


Aliona  commence par  former le  nombre  \verb+phi_n+ (  en référence  à
l'indicatrice  d'\textsc{Euler}  et en  utilisant  le  théorème du  même
\textsc{Euler} : voir \vref{exo::phi}) de la manière suivante:


\begin{lstlisting}[caption={}]
let phi_n = (p &- un) &* (q &- un) ;;
\end{lstlisting}

C'est là qu'il faut jouer avec la chance : Aliona doit choisir un nombre
\verb+e+ premier avec \verb+phi_n+.   En pratique, elle choisit un grand
nombre premier au hasard :


\begin{lstlisting}[caption={}]
let e = genere_premier 1000;;
\end{lstlisting}


Il  faut vérifier que  \verb+e+ et  \verb+phi_n+ sont  premiers entre
eux.

\begin{lstlisting}[caption={}]
montre(bgcd e phi_n);;
\end{lstlisting}


% \vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
% \begin{figure}
\includegraphics[width=3cm]{rsa2}
% \end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-3cm}
\begin{minipage}[t]{\linewidth}

\end{minipage}

Il reste  à Aliona à calculer  sa puissance de  décryptage secrète: elle
l'obtient en cherchant l'inverse de \verb+e+ modulo \verb+phi_n+.



Aliona est  maintenant prête  à recevoir des  messages cryptés  selon le
protocole RSA  et Boris  est prêt à  lui en  envoyer car Aliona  a rendu
publique sa clé \verb+(e,n)+.

D'abord Boris numérise son message.


Il faut  encore vérifier que  notre nombre à  crypter est plus  petit que
\verb+p+ et \verb+q+  (pourquoi ?).  En pratique, on  découpe le message
en morceaux avec une méthode de chiffrement par blocs (cf
\vref{exo::bloc}).

Ensuite, Boris calcule ce nombre puissance \verb+e+ modulo \verb+n+:


Aliona  reçoit ce  message et  le décrypte  grâce à  sa clé  secrète $d$
qu'elle est la seule à connaître dans tout l'univers.

\begin{recherche}
Déterminez une fonction \texttt{bbezout} du type :

\begin{lstlisting}[caption={}]
val inv_mod : Big_int.big_int * Big_int.big_int -> Big_int.big_int = <fun>
\end{lstlisting}

pour créer une fonction \texttt{binv\_mod} du type:

\begin{lstlisting}[caption={}]
val binv_mod : Big_int.big_int * Big_int.big_int -> Big_int.big_int = <fun>
\end{lstlisting}

qui  calculera l'inverse  de $a$  modulo $n$  puis coder  et  décoder un
message.


\end{recherche}
\end{exercice}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \end{listeexercices}
\modenormal % restaure les définitions de sections, sous-sections, etc;






%%% Local Variables: 
%%% TeX-master: "Poly_Alg_Ana_info1"
%%% End: 
