%  En préambule,  les  sources metapost.  Si  vous lancez  latex  sur ce  fichier,  il vous  placera
% automatiquement le fichier .mp dans le répertoire courant. 
\begin{filecontents*}{RoueCesar.mp}

%input newcourbes;
%input couleur;
input geometriesyr16;
%input TEX;
%input latexmp;



verbatimtex
%&latex
\documentclass{article}
\usepackage[upright]{fourier}
\usepackage{preambule}
\begin{document}
etex

beginfig(1);

  vardef Cesar(expr d) =
    
  
  
  pair o;
  o:=(-5cm,0);
  path c;
  c:=fullcircle  scaled 5cm shifted(-5cm,0);
  draw c withpen pencircle scaled 1.3bp withcolor blue ;

  for i=0 upto 25 :
    numeric r;
    r:=(i+d) mod 26;
   label(char(65+i),pointarc(c,90-i*360/26)) rotatedaround(pointarc(c,90-i*360/26),-i*360/26) shifted 0.1(pointarc(c,90-i*360/26)-o);
   label(char(65+r ),pointarc(c,90-i*360/26)) rotatedaround(pointarc(c,90-i*360/26),-i*360/26) shifted -0.1(pointarc(c,90-i*360/26)-o) withcolor green;
  endfor;
  


  enddef;

  Cesar(3);
  
endfig;


end



\end{filecontents*}


\RequirePackage{atbegshi}
\documentclass[french]{beamer}
\usepackage{etex}
\usepackage[beamer,utf8,fourier,pstricks]{preambuleTrm}
\usepackage[off]{auto-pst-pdf}
%\usepackage[french,vlined,boxed]{algorithm2e}
\usepackage{bookmark,multido,colortbl}
\usepackage{xlop}
\usepackage{tkz-graph,tkz-berge}
\usepackage{tikz}
\usetikzlibrary{automata,fit,trees,matrix,arrows,decorations.pathmorphing,shapes.arrows,chains,positioning}
\usepackage{caption}
\captionsetup{labelformat=empty,font=footnotesize}

%\usepackage{multimedia}
% \usepackage{cclicenses}
% \usepackage{cclicence}
\setbeamertemplate{theorems}[numbered]

\usepackage{algo}

\renewcommand{\algocommentfont}{\small\ttfamily\itshape}

\newcommand\nor{\downarrow}
\newcommand\nand{\mid}


\newcommand\blanc{ \square{} }



\newcommand\vide{\mathds{1}}



\newtheorem{exercice}{Exercice}


\setlength{\columnseprule}{0pt}


\graphicspath{{/home/moi/Lycee/TDmaple/2006_7/}{/home/moi/Figures/Arbres_Graphes/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigMaple/}{/home/moi/Photos/Maths/}{/home/moi/Photos/Tehessin/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigSeconde/}{/home/moi/Lycee/Informatique/XCAS/2008_9/}{/home/moi/Lycee/TDmaple/2008_9/}{/home/moi/IUT/Thierry/Conversions/}{/home/moi/Photos/informathix/}{/home/moi/Lycee/Informatique/PafAlgo/}}




\newcommand\caml{\lstset{numbers=none,language=caml,xleftmargin=10pt,%
keywordstyle =\small\color{blue!40}\usefont{OT1}{cmtt}{b}{n},basicstyle=\small\ttfamily\color{white},commentstyle=\normalfont\scriptsize\slshape\color{black!50!white},breaklines=true,backgroundcolor=\color{black!90!blue},frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,showstringspaces=false,stringstyle=\slshape,captionpos=b}
}


\newcommand\sage{\lstset{numbers=none,language=sage,xleftmargin=10pt,%
keywordstyle =\small\color{red!40}\usefont{OT1}{cmtt}{b}{n},basicstyle=\small\ttfamily\color{white},commentstyle=\normalfont\scriptsize\slshape\color{black!50!white},breaklines=true,backgroundcolor=\color{black!90!red},frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,showstringspaces=false,stringstyle=\slshape,captionpos=b}
}


\DeclareMathOperator*{\boxsum}{\raisebox{-0.6ex}{\scalebox{2.5}{$\boxplus$}}}





\setcounter{tocdepth}{2} %\setcounter{page}{0}


\renewcommand\FancyVerbFormatLine[1]{\colorbox{green}{#1}}


\mode<presentation>
{
  \usetheme[secheader]{Madrid}
  % or ...Warsaw

  \setbeamercovered{highly dynamic}
  % or whatever (possibly just delete it)
}
\usepackage{elephantbird}



\begin{document}


\title[] % (optional, use only with long paper titles)
{Mathématiques discrètes IV \\ Arithmétique}

\subtitle{INFO1 - Semaine 4}

\author[] % (optional, use only with lots of authors)
{Guillaume CONNAN }
% - Give the names in the same order as the appear in the paper.
% - Use the inst{?} command only if the authors have different
%   affiliation.

\institute{\textsc{IUT} de Nantes - Dpt d'informatique }% (optional, but mostly needed)

\logo{\includegraphics[scale=0.15]{logo_iut}}

%\logo{\includegraphics[scale=0.15]{big_connan}}

\date[] % (optional, should be abbreviation of conference name)
{Dernière mise à jour: \today}
% - Either use conference name or its abbreviation.
% - Not really informative to the audience, more for people (including
%   yourself) who are reading the slides online

\subject{ }


\beamerdefaultoverlayspecification{<+->}

\AtBeginSubsubsection[]
{
  \begin{frame}<beamer>
    \frametitle{Sommaire}
 {\scriptsize
\begin{multicols}{2}
    \tableofcontents[currentsection,currentsubsection]
       \end{multicols}
}

  \end{frame}
}




\AtBeginSubsection[]
{
  \begin{frame}<beamer>
    \frametitle{Sommaire}
 {\scriptsize
\begin{multicols}{2}
    \tableofcontents[currentsection,currentsubsection]
       \end{multicols}
}

  \end{frame}
}





\AtBeginSection[]
{
  \begin{frame}<beamer>
    \frametitle{Sommaire}
 {\scriptsize
\begin{multicols}{2}
    \tableofcontents[currentsection]
       \end{multicols}
}

  \end{frame}
}


% If you wish to uncover everything in a step-wise fashion, uncomment
% the following command: 

\beamerdefaultoverlayspecification{<+->}







\begin{frame}
  \titlepage
\end{frame}

\begin{frame}
 \frametitle{Sommaire}
{\scriptsize
\begin{multicols}{2} 
 \tableofcontents
\end{multicols}
}

 
 \end{frame}



\section{Structures mères}


\subsection{Lois de composition interne}


\begin{frame}
  
\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}

\pause

\begin{itemize}
\item $(\bbn,+)$
\item $(\PR(E),\cap)$
\item $(\bbn,-)$
\end{itemize}


\end{frame}




\begin{frame}
  

\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}

\pause

\begin{itemize}
\item $(\bbn,+)$
\item $(\PR(E),\cap)$
\item $(\bbn,-)$
\end{itemize}


\end{frame}

\begin{frame}
  
\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}

\pause


\begin{itemize}
\item $(\bbn,+)$
\item $(\PR(E),\cap)$
\item $(\bbn,-)$
\end{itemize}

\end{frame}


\begin{frame}
  

\begin{theorem}[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{theorem}

\end{frame}


\begin{frame}
  
\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}

\end{frame}




\subsection{Les groupes}


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

\pause

\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}


\end{frame}



\subsection{Division euclidienne}


\begin{frame}
  
\begin{theorem}[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{theorem}




\end{frame}







\begin{frame}[fragile]

  \begin{alertblock}{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+...
  \end{alertblock}




\end{frame}



















\begin{frame}
  \begin{alertblock}{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{alertblock}

\pause


  \begin{alertblock}{recherche}
    Que devient le théorève de la division euclidienne dans le cas où $a<0$?
  \end{alertblock}



\end{frame}



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


\subsubsection{Congruence}




\begin{frame}
  
\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}


\pause


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

\pause

\og I feel fine today modulo a slight headache.\fg{}}

\pause


\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}



\end{frame}


\begin{frame}[fragile]
\caml


  \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}

\pause

\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}


  
\end{frame}




\begin{frame}
  

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\}$$





\end{frame}



\begin{frame}
  \begin{alertblock}{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\}$


\pause

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{alertblock}
\end{frame}




\begin{frame}
  
\begin{theorem}
$$a\equiv b (\modu n)\ssi \exists k\in \bbz\ \mid 
\ a=b+kn$$
\end{theorem}
\end{frame}


\begin{frame}
  
\begin{theorem}\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{theorem}




\end{frame}



\begin{frame}
  \begin{alertblock}{Attention!}
     $12\equiv 0(\modu 6)$ \pause $\fr{12}{3}\not\equiv
\fr{0}{3}(\modu 6)$.
  \end{alertblock}
\end{frame}

\begin{frame}
 
\begin{theorem}
  $\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{theorem}


\pause


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

\pause


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

\end{frame}



\subsection{Caml}
 \caml

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

\pause

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

\pause


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


 \caml

\begin{frame}[fragile]

\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}

\pause

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

  
\end{frame}




\section{Divisibilité dans Z}


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

\pause


\begin{theorem}
Toute partie non vide MAJORÉE de $\bbn$ possède un plus GRAND
élément.
\end{theorem}


\pause


\begin{theorem}
  Si $d$ divise $a$ et $b$ alors $d$ divise toute COMBINAISON LINÉAIRE
  de $a$ et  $b$.
\end{theorem}


\end{frame}


\begin{frame}


\begin{theorem}
  Si $d$ divise $a$ alors $|d| \leqslant |a|$.
\end{theorem}

\pause


\begin{theorem}
  Si $d$ divise $d'$ et $d'$ divise $d$ alors $d'=d$.
\end{theorem}

\pause

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

\end{frame}



\section{PGCD}

\begin{frame} \frametitle{PGCD}
  
\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}


\pause

$$\DR(a)\cap\DR(b)$$


\end{frame}





\begin{frame}

\begin{theorem}[É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{theorem}

\end{frame}


\begin{frame}
  
\begin{theorem}
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{theorem}


\end{frame}



\begin{frame} \frametitle{Algorithme des différences}
\begin{theorem}
  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{theorem}
  
\end{frame}



\begin{frame} \frametitle{Algorithme d'Euclide I}

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




\begin{frame} \frametitle{Algorithme d'Euclide II}

\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}
  
\end{frame}

\begin{frame}[fragile]
  \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}

\end{frame}


\begin{frame}[fragile]


\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-\texttt{quo}(r,r')*u',v-\texttt{quo}(r,r')*v',r-\texttt{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}

\end{frame}



\begin{frame} \frametitle{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}


\pause

\begin{theorem}[Théorème de \textsc{Bézout}]
  Les entiers $a$ et $b$ sont premiers entre eux si, et seulement si, 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{theorem}




\end{frame}




\section{À la recherche des nombres premiers}





\begin{frame}
\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}

\pause



%\begin{figure}
\begin{center}
  \includegraphics[height=5cm]{brick}
\end{center}
%\end{figure}



\end{frame}


\begin{frame}


\begin{center}
{\tiny {\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}


\pause



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




\end{frame}


\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics{crible}
\end{center}
%\end{figure}

\end{frame}


\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[height=0.7\textheight]{eratosthene}
\end{center}
%\end{figure}

\end{frame}

\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[height=0.7\textheight]{erastosterre}
\end{center}
%\end{figure}

\end{frame}




\begin{frame}[fragile]
  
\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}


\pause


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


\pause



\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}



\end{frame}


\begin{frame}[fragile]

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


  
\end{frame}









\begin{frame}[fragile]
  
\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}


\pause

\begin{lstlisting}[caption={}]
# crible 100;;
- : int list =
[97; 89; 83; 79; 73; 71; 67; 61; 59; 53; 47; 43; 41; 37; 31; 29; 23; 19; 17; 13; 11; 7; 5; 3; 2]
\end{lstlisting}

\end{frame}

\begin{frame}

\begin{theorem}
  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{theorem}

\end{frame}

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







\begin{frame}
 
\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}
\end{frame}




\begin{frame}

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

\end{frame}



\begin{frame}
 
\begin{theorem}
  \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{theorem}

\end{frame}







\begin{frame}
  
\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}

\end{frame}

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

\pause


\begin{theorem}[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{theorem}


\end{frame}




\begin{frame}
  
\begin{theorem}[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{theorem}

\end{frame}




\begin{frame}
 $$      x^n+y^n=z^n\quad      \text{n'a     pas      de      solution  dans }\bbn^3\quad\text{pour } n>2$$


\pause



%\begin{figure}
\begin{center}
  \includegraphics[height=5cm]{wiles}
\end{center}
%\end{figure}

\end{frame}



\section{Chiffrements}

\subsection{Cesar}


\begin{frame}
\begin{center}
  \includegraphics[height=0.6\textheight]{asterix1}
\end{center}

\end{frame}


\begin{frame}

Comme le disait Suétone (70-127) dans La vie des 12 Césars:


\begin{quote}
Extant et ad Ciceronem, item ad familiares domesticis de rebus, in quibus, si qua occultius perferenda erant, per notas scripsit, id est sic structo litterarum ordine, ut nullum uerbum effici posset: quae si qui inuestigare et persequi uelit, quartam elementorum litteram, id est D pro A et perinde reliquas commutet.
\end{quote}


\end{frame}




\begin{frame}

Ce que César aurait peut-être écrit sous cette forme:

\begin{quote}

Rkgnag rg nq Pvprebarz, vgrz nq snzvyvnerf qbzrfgvpvf qr erohf, va dhvohf, fv dhn bpphygvhf
cresreraqn renag, cre abgnf fpevcfvg, vq rfg fvp fgehpgb yvggrenehz beqvar, hg ahyyhz hreohz rssvpv
cbffrg: dhnr fv dhv vahrfgvtner rg crefrdhv hryvg, dhnegnz ryrzragbehz yvggrenz, vq rfg Q ceb N rg
crevaqr eryvdhnf pbzzhgrg.

\end{quote}


\end{frame}




\begin{frame}[fragile]

Ou sous celle-ci si Rome avait été colonisé par des informaticiens américains:

\begin{verbatim}
"H{wdqw#hw#dg#Flfhurqhp/#lwhp#dg#idplolduhv#grphvwlflv#gh#uhexv/#lq#
txlexv/#vl#txd#rffxowlxv#shuihuhqgd#hudqw/#shu#qrwdv#vfulsvlw/#lg#hv
w#vlf#vwuxfwr#olwwhuduxp#ruglqh/#xw#qxooxp#xhuexp#hiilfl#srvvhw=#txdh
#vl#txl#lqxhvwljduh#hw#shuvhtxl#xholw/#txduwdp#hohphqwruxp#olwwhudp/#
lg#hvw#G#sur#D#hw#shulqgh#uholtxdv#frppxwhw1"
\end{verbatim}


\end{frame}





\begin{frame}
  Ceux qui ne  font pas de latin de spécialité  seront sûrement plus à
  l'aise avec cette nouvelle transcription du même texte: 

  \begin{quote}
    On possède enfin de César des lettres à Cicéron, et sa correspondance avec ses amis 
sur ses affaires domestiques. Il y employait, pour les choses tout à fait secrètes, une espèce de chiffre qui en rendait le sens inintelligible (les  lettres étant disposées de manière à ne pouvoir jamais former un mot), et qui consistait, je le dis pour ceux qui voudront les déchiffrer, à changer le rang des lettres dans l'alphabet, en écrivant la quatrième pour la première, c'est-à-dire le D pour l'A, et ainsi de suite.
  \end{quote}

\end{frame}


\begin{frame}\frametitle{Vous êtes César}
  Vous voulez transmettre cet important message:

  \begin{quote}
    Les sanglots longs des violons de l'automne
  \end{quote}
\end{frame}

\begin{frame}\frametitle{Vous êtes Vercingétorix}
  Vous voulez traduire ce message intercepté par vos espions~:

  \begin{quote}
    eohvvhqw\#prq\#frhxu\#g*xqh\#odqjxhxu\#prqrwrqh
  \end{quote}

\end{frame}

\begin{frame}\frametitle{La règle ou la roue?}
  Que vous inspire ce dessin:

\begin{center}
  \includegraphics{RoueCesar}
\end{center}
\end{frame}


\begin{frame}[fragile]
  \begin{lstlisting}[caption={}]
# List.map int_of_char ['a';'b';'c';'d';'e';'f';'g';'h'];;
- : int list = [97; 98; 99; 100; 101; 102; 103; 104]
\end{lstlisting}

\pause

\begin{lstlisting}[caption={}]
# List.map char_of_int [65; 66; 67; 68; 69; 70; 71; 72];;
- : char list = ['A'; 'B'; 'C'; 'D'; 'E'; 'F'; 'G'; 'H']
  \end{lstlisting}
\end{frame}

\begin{frame}
  \begin{table}[h!]\label{ascii}
{\tiny
\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{frame}


\begin{frame}[fragile]
  \begin{lstlisting}[caption={}]
# decalage 3 97;;
- : int = 100
  \end{lstlisting}

\pause

\begin{lstlisting}[caption={}]
# decalage 3 125;;
- : int = 33
\end{lstlisting}

\pause

\begin{lstlisting}[caption={}]
# code 3 'a';;
- : char = 'd'
\end{lstlisting}

\pause

\begin{lstlisting}[caption={}]
# code 3 '}';;
- : char = '!'
\end{lstlisting}

\end{frame}


\begin{frame}[fragile]
  \begin{lstlisting}[caption={}]
# cesar 3 "Les sanglots longs des violons de l'automne";;
- : string = "Ohv#vdqjorwv#orqjv#ghv#ylrorqv#gh#o*dxwrpqh"
  \end{lstlisting}

\pause

et pour déchiffrer \og \textit{ eohvvhqw\#prq\#frhxu\#g*xqh\#odqjxhxu\#prqrwrqh}\fg{}?

\pause

\begin{lstlisting}[caption={}]
# cesar (-3) "eohvvhqw#prq#frhxu#g*xqh#odqjxhxu#prqrwrqh";;
- : string = "blessent mon coeur d'une langueur monotone"
\end{lstlisting}


\pause

\begin{lstlisting}[caption={}]
# String.map;;
- : (char -> char) -> string -> string = <fun>
\end{lstlisting}

\end{frame}



\subsection{Chiffrement affine}

\begin{frame}
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.  

\pause


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

\pause

  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.

\pause

Quid du code de César?




\end{frame}


\begin{frame}[fragile]
  
  \begin{lstlisting}[caption={}]
# chiffre_affine 17 22 "abcd";;
- : string = "r$5F"
  \end{lstlisting}

\pause


Comment décrypter un message? \pause On cherche $g$ telle que:


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

\pause

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



\end{frame}


\begin{frame}[fragile]
  \begin{lstlisting}[caption={}]
# chiffre_affine 17 22 "aaaa";;
- : string = "rrrr"
  \end{lstlisting}
\end{frame}




\subsection{Chiffrement par blocs}

\subsubsection{Permutations}

\begin{frame}
   \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}

\pause


\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}


\end{frame}



\begin{frame}


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

\end{frame}



\begin{frame}

\begin{theorem}[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{theorem}

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

\end{frame}


\begin{frame}
  
Une \textit{permutation circulaire  gauche} \og décale\fg{} les éléments
d'un nombre fixé de \og rangs\fg{}. 


\pause


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

\end{frame}


\subsubsection{Chiffrement par blocs}

\begin{frame}
 
\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}

\pause

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$.


\pause


Depuis 2001, le  chiffrement par blocs \og officiel  \fg{} est l'AES qui
opère par blocs de 128 bits.

\end{frame}


\subsubsection{ECB}

\begin{frame}
  \textit{Electronic CodeBook}

\pause


 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.



\end{frame}


\begin{frame}

Considérons $m=1001001111011$. \pause

On rajoute un 0 en bout de chaîne:

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

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

\pause

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}
$

\pause

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


\subsubsection{CBC}

\begin{frame}
   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.

\pause

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}$$


\end{frame}


\subsubsection{Mode CFB}


\begin{frame}
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.




\end{frame}


\begin{frame}

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

\pause

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$:

\pause

\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}


\pause

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

\end{frame}


\subsubsection{ECB avec OCaml}





\begin{frame}[fragile]
  \begin{lstlisting}[caption={}]
exception Non_defini;;

let pi = function
  |1 -> 3
  |2 -> 1
  |3 -> 4
  |4 -> 2
  |5 -> 6
  |6 -> 5
  |7 -> 7
  |_ -> raise Non_defini;;
  \end{lstlisting}

\pause


\begin{lstlisting}[caption={}]
(* l'inverse de pi *)
let pi_inv = 
   true
;;
\end{lstlisting}
\end{frame}








\begin{frame}[fragile]
  \begin{lstlisting}[caption={}]
(* quid ? *)
let  liste_n = fun n ->
  let rec listentier = fun (m,n,acc) ->
    if m > n then
      List.rev acc
    else
      listentier (m+1,n,m::acc)
  in listentier (1,n,[]);;

  \end{lstlisting}
\end{frame}















\begin{frame}[fragile]
  \begin{lstlisting}[caption={}]
(* quid ? *)
let permute = fun e liste ->
  List.rev (List.fold_left2 (fun acc el rg -> (List.nth liste ((e rg) - 1))::acc ) [] liste (liste_n (List.length liste)));;
  \end{lstlisting}


\pause

\begin{lstlisting}[caption={}]
(* quid ?*)
let ecb = fun e liste ->
  List.map (permute e) liste;;
\end{lstlisting}
\end{frame}









\begin{frame}[fragile]
  \begin{lstlisting}[caption={}]
(* quid ? *)
let paquets = fun n liste ->
  let rec aux = fun i li acc acc_tmp ->
    match li with
    |[]   -> if (i mod n = 0) then List.rev ((List.rev acc_tmp)::acc)
             else aux (i+1) ([]) acc (0::acc_tmp)
    |t::q -> if i = 0 then aux 1 q [] [t]
             else if i mod n = 0 then
	               aux (i+1) q ((List.rev acc_tmp)::acc) [t]
                  else aux (i+1) q acc (t::acc_tmp)
  in aux 0 liste [] [];;
  \end{lstlisting}
\end{frame}












\begin{frame}[fragile]
  \begin{lstlisting}[caption={}]
(* quid ? *)
let explose = fun chaine ->
  let rec aux = fun ch acc ->
    match ch with
    |"" -> List.rev acc
    |_  -> aux (String.sub ch 1 (String.length ch -1)) ((ch.[0])::acc)
  in aux chaine [];;
  \end{lstlisting}


\pause


\begin{lstlisting}[caption={}]
(* quid ? *)
let chaine_to_int_list = fun chaine ->
  let ex = explose chaine in
  List.flatten (List.map (base2_of_10) (List.map int_of_char ex));;
\end{lstlisting}
\end{frame}













\begin{frame}[fragile]
  \begin{lstlisting}[caption={}]
(* quid ? *)
let ecb_chaine = fun e chaine ->
  let liste_ini = paquets 7 (chaine_to_int_list chaine) in
  let liste_perm = paquets 7 (List.flatten (ecb e liste_ini)) in
  let liste_10 = List.map base10_of_2 liste_perm
  in List.map char_of_int liste_10;;
  \end{lstlisting}
\end{frame}










\begin{frame}[fragile]
\begin{lstlisting}[caption={}]
(* quid ? *)
let rec str_of_list = fun liste ->
  match liste with
  |[] -> ""
  |t::q -> (String.make 1 t)^(str_of_list q);;
\end{lstlisting}
\end{frame}











\subsection{RSA}


\begin{frame}
\begin{center}
\includegraphics[width=6cm]{rsa2}
\end{center}
\end{frame}


\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[width=\linewidth]{rsa}
\end{center}
%\end{figure}

\end{frame}



\begin{frame}
  \begin{itemize}
  \item  Votre amie  Josette veut recevoir de vous une lettre
d'amour mais elle a peur que le facteur l'intercepte et la lise.

\item   Elle
fabrique donc  dans son petit atelier  une clé, un cadenas  et une boîte
vide . 
\item  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}.
\item  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é. 
\item  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.
  \end{itemize}

\end{frame}

\begin{frame}
  Le principe se ramène à:

  \begin{itemize}
  \item  je fabrique  une fonction
$\pi$ définie sur $\bbn$ qui possède une réciproque $\sigma$.
\item  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$.
\item  La fonction
$\pi$ est donc la clé publique: vous envoyez $\pi$(message) à Josette.
\item Celle-ci         calcule        $\sigma\bigl(\pi(\text{message})\bigr)=$
message. 
\item  Josette est  la seule à pouvoir décoder  car elle seule connaît
$\sigma$.
  \end{itemize}
\end{frame}



\begin{frame}
 Comment faire cela informatiquement?...
\end{frame}



\begin{frame}
  \begin{itemize}
  \item 
On  commence  par  fabriquer  deux  nombres  premiers  quelconques  mais
suffisamment grands, par  exemple de l'ordre de 1000  bits (300 chiffres
décimaux).
\item 
Ces deux nombres $p$ et $q$ ne sont connus que d'une personne: c'est la \textit{clé
  privée}. 
\item Josette forme le produit de ces deux nombres: $n=p\times q$.
\item Ce nombre $n$ est le module publique de Josette.
\item Il  reste à  former le
nombre $e$ qui est la puissance de cryptage publique.
\item Josette commence par former le nombre $\varphi_n=(p-1)(q-1)$.
\item Josette doit choisir un nombre
$e$ premier avec $\varphi_n$.   En pratique, elle choisit un grand
nombre premier au hasard.
\item 
Il reste  à Josette à calculer  sa puissance de  décryptage secrète: elle
l'obtient en cherchant l'inverse $d$ de $e$ modulo $\varphi_n$.

  \end{itemize}
\end{frame}

\begin{frame}
  \begin{itemize}
  \item Vous avez donc reçu $(e,n)$, la clé publique de Josette. Vous découpez
votre message en petits morceaux à l'aide d'un chiffrement par blocs.
\item Vous calculez chaque bloc à la puissance $e$ modulo $n$.
\item Josette 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...
  \end{itemize}

\end{frame}

\end{document}
%%% Local Variables: 
%%% TeX-master: t
%%% End: 
