%\RequirePackage{atbegshi}
\documentclass[french]{beamer}
\usepackage{etex}

\usepackage[beamer,utf8,arabe]{preambuleTrm}
%\usepackage[french,vlined,boxed]{algorithm2e}
\usepackage{bookmark,multido}
%\usepackage{xlop}


\usepackage{tikz}
\usetikzlibrary{automata,fit,trees,matrix,arrows,decorations.pathmorphing,shapes,arrows,chains,positioning,intersections,backgrounds,calc,through,mindmap}
\newcommand{\myunit}{1.1cm}
\usepackage{tkz-graph}
\usepackage{circuitikz}


\usepackage{caption}
\captionsetup{labelformat=empty,font=footnotesize}


\usepackage{media9}

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




\usepackage{algo}

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

\newcommand\nor{\downarrow}
\newcommand\nand{\uparrow}
\newcommand\xor{\oplus}

\newcommand\foncpart{\rightarrow\!\!\!\!\!\!\shortmid}
\newcommand\fonctot{\rightarrow}
\newcommand\injpart{\rightarrowtail\!\!\!\!\!\!\!\shortmid}
\newcommand\injtot{\rightarrowtail}
\newcommand\surjpart{\twoheadrightarrow\!\!\!\!\!\!\!\shortmid}
\newcommand\surjtot{\twoheadrightarrow}
\newcommand\bijpart{\rightarrowtail\!\!\!\!\!\!\!\shortmid\!\!\!\!\twoheadrightarrow}
\newcommand\bijtot{\rightarrowtail\!\!\!\!\!\!\!\!\!\twoheadrightarrow}


\newtheorem{exercice}{Exercice}


\setlength{\columnseprule}{0pt}

%\setlength{\parskip}{0pt}


\graphicspath{{/home/moi/IUT/Figures/}{/home/moi/VISA_III/figures_visa/}{/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/}{/home/moi/Figures/figuresAlice/}{/home/moi/Figures/FigSeconde/}{/home/moi/Biocam/robot/}{/home/moi/Biocam/CoursIni3d/}{/home/moi/Biocam/central/figures/}{/home/moi/Biocam/central/}{/home/moi/IUT/INFO2/Images/}{/home/moi/IUT/INFO2/2011_12/graphes/}{/home/moi/IUT/INFO1/CM1/}{/home/moi/Figures/figuresTS/}{/home/moi/Photos/Tehessin/}{/home/moi/Figures/FigSTI/}{/home/moi/Alice/figures3/}{/home/moi/Alice/figures3/newcourbes/}{/home/moi/Alice/figures/}{/home/moi/Figures/figuresAlice/}{/home/moi/Photos/Maths/}{/home/moi/Lycee/TS/}{/home/moi/Lycee/TS/2009_10/}{/home/moi/Figures/FigMaple/}{/home/moi/Figures/figuresTS/newcourbes/}{/home/moi/Figures/FigEspace/}{/home/moi/PROG/HASKELL/FLOAT/}}


\setcounter{tocdepth}{1} %\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{beamercolorthemeelephantbird}

\newcommand{\triangleup}{\Delta}

\begin{document}


\title[] % (optional, use only with long paper titles)
{Structures algébriques et programmation}

\subtitle{INFO1 - Semaines 45 à 3}

\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{} à \now}
% - 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[]
% {\scriptsize
%   \begin{frame}<beamer>
%     \frametitle{Sommaire}
%  {\tiny
% \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{<+->}




\newcommand{\TR}{\mathcal{T}}


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

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

 
 \end{frame}


\haskell








\section{Loi de composition}

\subsection{Définitions}





%
\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[height=0.8\textheight]{aljabr}
\end{center}
%\end{figure}
\begin{otherlanguage}{arabic}
الجبر
\end{otherlanguage}

\end{frame}



\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[height=0.8\textheight]{al-khwarizmi}
\end{center}
%\end{figure}
\begin{otherlanguage}{arabic}
كتاب المختصر في حساب الجبر والمقابلة
\end{otherlanguage}
\end{frame}








\haskell




\begin{frame}[fragile]
\begin{lstlisting}
λ> versMin 'A'
'a'
.
.
\end{lstlisting}
  
\end{frame}


\begin{frame}[fragile]
\begin{lstlisting}
λ> versMin 'A'
'a'
λ> map versMin "TRALALAHOP"
"tralalahop"
\end{lstlisting}
  
\end{frame}



\begin{frame}[fragile]
  \begin{lstlisting}
import Data.Char
import Data.Bits

.
.
.
.
.
.
.
.
.
.
.
.
.
.

  \end{lstlisting}
  
\end{frame}


\begin{frame}[fragile]
  \begin{lstlisting}
import Data.Char
import Data.Bits

λ> ord 'A'
.
.
.
.
.
.
.
.
.
.
.
.
.
  \end{lstlisting}
  
\end{frame}

\begin{frame}[fragile]
  \begin{lstlisting}
import Data.Char
import Data.Bits

λ> ord 'A'
65
.
.
.
.
.
.
.
.
.
.
.
.
  \end{lstlisting}
  
\end{frame}

\begin{frame}[fragile]
  \begin{lstlisting}
import Data.Char
import Data.Bits

λ> ord 'A'
65
λ> ord 'a'
.
.
.
.
.
.
.
.
.
.
.
  \end{lstlisting}
  
\end{frame}

\begin{frame}[fragile]
  \begin{lstlisting}
import Data.Char
import Data.Bits

λ> ord 'A'
65
λ> ord 'a'
97
.
.
.
.
.
.
.
.
.
.
  \end{lstlisting}
  
\end{frame}

\begin{frame}[fragile]
  \begin{lstlisting}
import Data.Char
import Data.Bits

λ> ord 'A'
65
λ> ord 'a'
97
λ> chr 65
.
.
.
.
.
.
.
.
.
  \end{lstlisting}
  
\end{frame}

\begin{frame}[fragile]
  \begin{lstlisting}
import Data.Char
import Data.Bits

λ> ord 'A'
65
λ> ord 'a'
97
λ> chr 65
'A'
.
.
.
.
.
.
.
.

  \end{lstlisting}
  
\end{frame}

\begin{frame}[fragile]
  \begin{lstlisting}
import Data.Char
import Data.Bits

λ> ord 'A'
65
λ> ord 'a'
97
λ> chr 65
'A'
λ> chr (65 + 32)
.
.
.
.
.
.
.
  \end{lstlisting}
  
\end{frame}

\begin{frame}[fragile]
  \begin{lstlisting}
import Data.Char
import Data.Bits

λ> ord 'A'
65
λ> ord 'a'
97
λ> chr 65
'A'
λ> chr (65 + 32)
'a'
.
.
.
.
.
.
  \end{lstlisting}
  
\end{frame}

\begin{frame}[fragile]
  \begin{lstlisting}
import Data.Char
import Data.Bits

λ> ord 'A'
65
λ> ord 'a'
97
λ> chr 65
'A'
λ> chr (65 + 32)
'a'
λ> 65 .|. 32
.
.
.
.
.
  \end{lstlisting}
  
\end{frame}

\begin{frame}[fragile]
  \begin{lstlisting}
import Data.Char
import Data.Bits

λ> ord 'A'
65
λ> ord 'a'
97
λ> chr 65
'A'
λ> chr (65 + 32)
'a'
λ> 65 .|. 32
97
.
.
.
.
  \end{lstlisting}
  
\end{frame}

\begin{frame}[fragile]
  \begin{lstlisting}
import Data.Char
import Data.Bits

λ> ord 'A'
65
λ> ord 'a'
97
λ> chr 65
'A'
λ> chr (65 + 32)
'a'
λ> 65 .|. 32
97
λ> setBit 65 5
.
.
.
  \end{lstlisting}
  
\end{frame}

\begin{frame}[fragile]
  \begin{lstlisting}
import Data.Char
import Data.Bits

λ> ord 'A'
65
λ> ord 'a'
97
λ> chr 65
'A'
λ> chr (65 + 32)
'a'
λ> 65 .|. 32
97
λ> setBit 65 5
97
.
.
  \end{lstlisting}
  
\end{frame}

\begin{frame}[fragile]
  \begin{lstlisting}
import Data.Char
import Data.Bits

λ> ord 'A'
65
λ> ord 'a'
97
λ> chr 65
'A'
λ> chr (65 + 32)
'a'
λ> 65 .|. 32
97
λ> setBit 65 5
97
λ> 97 .&. (complement 32)
.
  \end{lstlisting}
  
\end{frame}

\begin{frame}[fragile]
  \begin{lstlisting}
import Data.Char
import Data.Bits

λ> ord 'A'
65
λ> ord 'a'
97
λ> chr 65
'A'
λ> chr (65 + 32)
'a'
λ> 65 .|. 32
97
λ> setBit 65 5
97
λ> 97 .&. (complement 32)
65
  \end{lstlisting}
  
\end{frame}



\begin{frame}[fragile]
\begin{lstlisting}
versMin :: Char                      -> Char 
versMin    c
  | (c < 'A') || (c > 'Z') = error "Pas majuscule !" 
  | otherwise              = chr (setBit (ord c) 5)
\end{lstlisting}
  
\end{frame}








%
\begin{frame}
  

\begin{definition}[Loi de composition interne (LCI)]
Une loi de composition interne définie sur un ensemble E est une fonction totale
(ou application) de $E\otimes E$ dans E.
On dit alors que E \textbf{muni de cette loi} est un \textbf{magma}.
\end{definition}

\end{frame}











% 
\begin{frame}
  
\begin{definition}[Stabilité]
  Un ensemble E est stable par une opération $\star$ si, et seulement si:

$$\Bigl(\forall              \langle
x,y\rangle\Bigr)\Bigl(\bigl(\langle x,y\rangle \in E\otimes E\bigr)\limp \bigl(x\star y \in E\bigr)\Bigr)$$
\end{definition}


\end{frame}



\begin{frame}[fragile]
\begin{lstlisting}
somCar :: (Char,Char) -> Char
somCar    (a   ,b)    =  chr ((ord a) + (ord b)) 
\end{lstlisting}

\pause


\begin{lstlisting}
λ> somCar ('A',' ')
'a'
λ> somCar ('3','2')
'e'
\end{lstlisting}



\end{frame}


\begin{frame}[fragile]
\begin{lstlisting}
infix @+

(@+) a b = somCar (a,b)  
\end{lstlisting}

\pause

\begin{lstlisting}
λ> 'A' @+ ' '
'a'
\end{lstlisting}

  
\end{frame}


%
\begin{frame}
  

\begin{definition}[Loi de composition externe (LCE)]
Une loi de composition externe définie sur un ensemble E et à opérateurs dans un
ensemble K est une fonction totale
(ou application) de $K\otimes E$ dans E.
  
\end{definition}

\end{frame}


\begin{frame}[fragile]
  \begin{lstlisting}
data Vect2D = Vect(Double,Double) deriving Show
.
.
.
  \end{lstlisting}
  
\end{frame}

\begin{frame}[fragile]
  \begin{lstlisting}
data Vect2D = Vect(Double,Double) deriving Show

(.@) :: Double -> Vect2D       -> Vect2D
(.@)    k       (Vect(x,y)) = Vect(k*x,k*y)
  \end{lstlisting}
  
\end{frame}


\begin{frame}[fragile]

  \begin{lstlisting}
λ> let v = Vect(2,3)
λ> 5 .@ v
Vect (10.0,15.0)
  \end{lstlisting}
  
\end{frame}


%
\begin{frame}
  
\begin{definition}[Morphisme]

Soit  $\langle  E,\star\rangle $  et
$\langle F,\dagger\rangle $ deux magmas et $\varphi$ une fonction totale de $E$
dans $F$.
On dit que $\varphi$ est un morphisme de E dans F si, et seulement si:

$$\bigl(\forall x\bigr)\bigl(\forall y\bigr)\bigl(\varphi(x\star y) = \varphi(x)\dagger \varphi(y)\bigr)$$
\end{definition}

\end{frame}


\begin{frame}[fragile]

  \begin{lstlisting}
λ> :t (++)
.
.
.
.
.
.
.
  \end{lstlisting}
\end{frame}


\begin{frame}[fragile]

  \begin{lstlisting}
λ> :t (++)
(++) :: [a] -> [a] -> [a]
.
.
.
.
.
.
  \end{lstlisting}
\end{frame}


\begin{frame}[fragile]

  \begin{lstlisting}
λ> :t (++)
(++) :: [a] -> [a] -> [a]
λ> :t (+)
.
.
.
.
.
  \end{lstlisting}
\end{frame}


\begin{frame}[fragile]

  \begin{lstlisting}
λ> :t (++)
(++) :: [a] -> [a] -> [a]
λ> :t (+)
(+) :: Int -> Int -> Int
.
.
.
.
  \end{lstlisting}
\end{frame}


\begin{frame}[fragile]

  \begin{lstlisting}
λ> :t (++)
(++) :: [a] -> [a] -> [a]
λ> :t (+)
(+) :: Int -> Int -> Int
λ> :t length
.
.
.
  \end{lstlisting}
\end{frame}


\begin{frame}[fragile]

  \begin{lstlisting}
λ> :t (++)
(++) :: [a] -> [a] -> [a]
λ> :t (+)
(+) :: Int -> Int -> Int
λ> :t length
length :: [a] -> Int
.
.
  \end{lstlisting}
\end{frame}


\begin{frame}[fragile]

  \begin{lstlisting}
λ> :t (++)
(++) :: [a] -> [a] -> [a]
λ> :t (+)
(+) :: Int -> Int -> Int
λ> :t length
length :: [a] -> Int
λ> length ("Ti" ++ "Poney") == length "Ti" + length "Poney"
.
  \end{lstlisting}




\end{frame}


\begin{frame}[fragile]

  \begin{lstlisting}
λ> :t (++)
(++) :: [a] -> [a] -> [a]
λ> :t (+)
(+) :: Int -> Int -> Int
λ> :t length
length :: [a] -> Int
λ> length ("Ti" ++ "Poney") == length "Ti" + length "Poney"
True
  \end{lstlisting}




\end{frame}


%
\begin{frame}
  
\begin{definition}[Isomorphisme]
Soit  $\langle  E,\star\rangle $  et
$\langle F,\dagger\rangle$ deux magmas et $\varphi$ une fonction totale de $E$
dans $F$.
On dit  que $\varphi$  est un  isomorphisme de  E dans F  si, et  seulement si,  c'est un
morphisme BIJECTIF de E dans F.  
\end{definition}

\end{frame}







\begin{frame}[fragile]
  \begin{lstlisting}
somL :: [Double] -> [Double] -> [Double]
somL    l1          l2       =  zipWith (+) l1 l2
.
.
.
.
.
.
  \end{lstlisting}

\end{frame}

\begin{frame}[fragile]
  \begin{lstlisting}
somL :: [Double] -> [Double] -> [Double]
somL    l1          l2       =  zipWith (+) l1 l2

somV :: Vect2D     -> Vect2D       -> Vect2D
somV    (Vect (x,y)) (Vect (x',y')) = Vect (x + x', y + y')
.
.
.
  \end{lstlisting}

\end{frame}


\begin{frame}[fragile]
  \begin{lstlisting}
somL :: [Double] -> [Double] -> [Double]
somL    l1          l2       =  zipWith (+) l1 l2

somV :: Vect2D     -> Vect2D       -> Vect2D
somV    (Vect (x,y)) (Vect (x',y')) = Vect (x + x', y + y')

vectToList :: Vect2D       -> [Double]
vectToList    (Vect (x,y)) =  [x,y]
  \end{lstlisting}

\end{frame}


\begin{frame}[fragile]
  \begin{lstlisting}
λ> let v1 = Vect (1,2)
λ> let v2 = Vect (10,15)
λ> vectToList (v1 `somV` v2) == vectToList v1 `somL` vectToList v2
True
  \end{lstlisting}
\end{frame}


\subsection{Propriétés des lois (de composition interne)}

%
\begin{frame}
  
\begin{definition}[Commutativité]
  Une LCI $\star$ sur E est commutative si, et seulement si
$$(\forall x)(\forall y)(x\star y = y \star x)$$

\end{definition}


\end{frame}


%
\begin{frame}
  

\begin{definition}[Associativité]
  Une LCI $\star$ sur E est associative si, et seulement si
$$(\forall x)(\forall y)(\forall z)(x\star (y\star z) = (x\star y ) \star z)$$
Un magma muni  d'une loi associative est appelé... un
magma associatif.
\end{definition}

\end{frame}

%
\begin{frame}
  

\begin{definition}[Élément neutre]
 Un élément  neutre $e$  d'une LCI $\star$  sur E est  un élément  $e_\star$ qui
 vérifie:

$$(\forall x)(x\star e_\star = e_\star\star x = x)$$

Un magma associatif admettant un élément neutre est un \textbf{monoïde} (ou un magma
associatif \textbf{unifère}).
\end{definition}


\pause

Pouvez-vous démontrer que si l'élément neutre existe, il est unique?


\end{frame}








%
\begin{frame}
  
\begin{definition}[Élément symétrisable]
  Soit $x$ un élément de E. Il est inversible
  (ou symétrisable) par $\star$ si, et seulement si, 

$$(\exists y)(x\star y =  y \star x = e_\star)$$
\end{definition}

\pause

Pouvez-vous démontrer que si $x$ admet un symétrique, alors ce symétrique est unique?

\end{frame}










%
\begin{frame}
  

\begin{definition}[Régularité]
Un élément $a$ de E est  dit \textbf{régulier à gauche} (ou \textbf{simplifiable
  à gauche}) si, et
seulement si:

$$\bigl(\forall x\bigr)\bigl(\forall y\bigr)\bigl((a\star x = a\star y)\limp (x=y)\bigr)$$

On a une définition similaire de la régularité à droite.

Un élément à la fois régulier à gauche et à droite est dit \textbf{régulier}.

Une loi telle que tout élément soit régulier est dite régulière.

\end{definition}

\pause

Un élément symétrisable est régulier (vérifiez-le). Un élément régulier est-il symétrisable?


\end{frame}





%
\begin{frame}
  
\begin{definition}[Distributivité]
  On dit que la loi $\star$ définie sur E est distributive sur $\dagger$ définie
  sur E si, et seulement si:

$$\Bigl(     \forall     x\Bigr)\Bigl(     \forall     y\Bigr)\Bigl(     \forall
z\Bigr)\Bigl( \bigl( x\star (y\dagger z) =  (x\star y) \dagger (x \star z)\bigr)
\land \bigl((y\dagger z)\star x = (y\star x) \dagger (z \star x)\bigr) \Bigr)$$
\end{definition}
\end{frame}














%
\begin{frame}
  

\begin{definition}[Élément absorbant]
 Un élément  absorbant  d'une LCI $\star$  sur E est  un élément  $a_\star$ qui
 vérifie:

$$(\forall x)(x\star a_\star = a_\star\star x = a_\star)$$

  
\end{definition}

\pause

Montrez que si un tel élément existe, il est unique.

\end{frame}












%
\begin{frame}
  
\begin{definition}[Élément involutif]
  Soit $\star$ une loi sur un ensemble E admettant un élément neutre $e_\star$.

Alors $x$ est \textbf{involutif} si, et seulement si, $x\star x=e_\star$.
\end{definition}

\pause

\begin{definition}[Élément idempotent]
  Soit $\star$ une loi sur un ensemble E.

Alors $x$ est \textbf{idempotent} si, et seulement si, $x\star x=x$.
\end{definition}



\end{frame}



\section{Groupes}





%
\begin{frame}
  \begin{figure}
  \includegraphics[height=0.8\textheight]{Evariste}
\caption{É.\textsc{Galois} (1811-1832)}
\end{figure}
\end{frame}









%
\begin{frame}
  

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


\pause

\begin{definition}[Sous-groupe]
  $\langle  H,\star\rangle$  est  un
  sous-groupe       de      $\langle
  G,\star\rangle$ si, et seulement si, H est une
  partie de G et $\langle H,\star\rangle$ est un groupe.
\end{definition}


\end{frame}


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



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

ou

$$a\equiv_n b$$
 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}
# 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

\pythonc

\begin{lstlisting}
>>> 17 % 3
2
>>> -17 % 3
1
>>> -17/3
-6
>>> (-17 // 3)*3 + (-17 % 3)
-17
\end{lstlisting}

  
\end{frame}

\haskell





\begin{frame}[fragile]
\begin{lstlisting}
λ> mod 17 3
2
λ> mod (-17) 3
1
λ> div (-17) 3
-6
λ> 3 * (div (-17) 3) + (mod (-17) 3)
-17
λ> rem (-17) 3
-2
λ> quot (-17) 3
-5
λ> 3 * (quot (-17) 3) + (rem (-17) 3)
-17
λ> 3 * (quot (-17) 3) + (mod (-17) 3)
-14
λ> 3 * (div (-17) 3) + (rem (-17) 3)
-20
\end{lstlisting}
  
\end{frame}



\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}
  \begin{center}
    \includegraphics[width=\linewidth]{euclide_papyrus}
  \end{center}
\end{frame}


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


\pause

\begin{theorem}
$$a\equiv_n b \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_n a$
\item Si $a\equiv_n b$, alors $b\equiv_n a$
\item Si $a\equiv_n b$ et $b\equiv_n c$, alors $a\equiv_n c$
\item Si $a\equiv_n b$ et $a'\equiv_n b'$, alors $$a+a'\equiv_n
b+b'\quad a-a'\equiv_n b-b'\quad aa'\equiv_n bb'$$
\item Si $a\equiv_n b$, alors, pour tout $p\in\bbn$, $a^p\equiv_nb^p$

  \end{enumerate}
\end{theorem}
\end{frame}







\begin{frame}
  \begin{alertblock}{Attention à la division !}
    $12\equiv_6 0$, \pause mais $\fr{12}{3}\not\equiv_6
\fr{0}{3}$ !
  \end{alertblock}
\end{frame}





\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[scale=0.4]{classe1}
\end{center}
%\end{figure}

\end{frame}



\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[scale=0.35]{classe2}
\end{center}
%\end{figure}

\end{frame}



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


\begin{frame}
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}{Attention!}
     Notez  bien   que  $\overline{0}^8$,   $\overline{1}^8$,  etc.  sont   des  ensembles
  d'entiers!...
  \end{alertblock}

\pause


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


\end{frame}




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





\subsection{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}
 \begin{center}
\begin{tabular}{ccccc}
 & \Colorbox{blue!50!black}{$u_k$} & {\Large{\textbf{$-$}}} &  &    \\
 & & & &  \\ 
{\Large{\textbf{(}}} & \Colorbox{blue!50!black}{$u_{k+1}$} & {\Large{\textbf{$\times$}}} & \Colorbox{yellow!50!black}{$q_{k+1}$} & {\Large{\textbf{)}}}   \\
 & & & &  \\ 
{\Large{\textbf{$=$}}} & \psframebox{$u_{k+2}$} &  &  &    \\ 
\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 & \Colorbox{blue!50!black}{ 1} & \Colorbox{blue!50!black}{ 0} & \Colorbox{blue!50!black}{ 19} & / & $L_0$ \\ 
\hhline{-----} 1 & \Colorbox{blue!50!black}{ 0} & \Colorbox{blue!50!black}{ 1} &\Colorbox{blue!50!black}{ 15} & \Colorbox{yellow!50!black}{1} & $L_1$ \\ 
\hhline{-----} 2 & 1 & $-1$ & 4 & 3 & $L_2\leftarrow L_0-\Colorbox{yellow!50!black}{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]
{\footnotesize

\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{Anneaux et corps}

\subsection{Anneaux}

%
\begin{frame}
  \includegraphics[width=\linewidth]{lord_ring}
\end{frame}



%
\begin{frame}
  \begin{definition}[Anneau]
  Soit A un ensemble muni de deux lois $\boxdot$ et $\boxplus$. 

On dit que
$\langle A,\boxplus,\boxdot\rangle$ est un anneau si, et seulement si:
\begin{itemize}
\item $\langle A,\boxplus\rangle$ est un groupe commutatif;
\item $\boxdot$ est associative;
\item $\boxdot$ est distributive sur $\boxplus$.
\end{itemize}

\pause

Si   $\boxdot$   est  commutative,   alors  l'anneau   est  dit
\textit{commutatif}. 

\pause

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

\pause

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

\end{frame}



\subsection{Corps}


%
\begin{frame}
  \begin{definition}[Corps]
Soit $\bbk$ un ensemble muni de deux LCI $\boxplus$ et $\boxdot$.
Le  triplet  $\langle  \bbk,\boxplus,\boxdot\rangle$ possède  une  structure  de
\textbf{corps} si, et seulement si, 
\begin{itemize}
\item                       $\langle
  \bbk,\boxplus,\boxdot\rangle$    a
  une structure  d'anneau 
  unitaire;
\item                       $\langle
  \bbk\setminus\{e_\boxplus\},\boxdot\rangle$
  a une structure de groupe.
\end{itemize}
\end{definition}


\pause




Combien d'éléments a au minimum un corps?


\end{frame}


\subsection{La classes numériques sur Haskell}


%
\begin{frame}[fragile]

\begin{lstlisting}
class  (Eq a, Show a) => Num a  where
    (+), (-), (*)  :: a -> a -> a
    negate         :: a -> a
    abs, signum    :: a -> a
    fromInteger    :: Integer -> a
\end{lstlisting}

\pause

À quelle structure algébrique peut-on associer la classe \verb+Num+?

\end{frame}


%
\begin{frame}[fragile]
\begin{lstlisting}
class  (Num a) => Fractional a  where
    (/)          :: a -> a -> a
    recip        :: a -> a
    fromRational :: Rational -> a
\end{lstlisting}

\pause


À quelle structure algébrique peut-on associer la classe \verb+Frational+?


\end{frame}


\section{Calcul modulaire en Haskell}


\begin{frame}[fragile]

\begin{lstlisting}
data Classe = 
  Zero_c
  |Un_c
  |Classe {modulo :: Int, representant :: Int} 
\end{lstlisting}

  
\end{frame}



\begin{frame}[fragile]
\begin{lstlisting}
instance Eq Classe where
  a == Zero_c = (mod (representant a) (modulo a) == 0)
  a == Un_c   = (mod (representant a) (modulo a) == 1)
  a == b      = (mod (representant a) (modulo a) == mod (representant b) (modulo b))
                && ((modulo a) == (modulo b))
\end{lstlisting}
  
\end{frame}




\begin{frame}[fragile]

\begin{lstlisting}
instance Show Classe where
  show Zero_c = "0%"
  show Un_c = "1%"
  show a = (show (representant a)) ++ "%" ++ (show (modulo a))
\end{lstlisting}

  
\end{frame}


\begin{frame}[fragile]
\begin{lstlisting}
(%) :: Int -> Int -> Classe 
(%) a n = Classe {representant = (mod a n), modulo = n}
\end{lstlisting}

\pause

\begin{lstlisting}
λ> 13 % 3
1%3
\end{lstlisting}


\end{frame}

\begin{frame}[fragile]
  \begin{lstlisting}
-- somme induite
(%+) :: Classe -> Classe -> Classe
(%+) Zero_c a = a
(%+) a Zero_c = a
(%+) Un_c   a = Classe {representant = (representant a) + 1, modulo = modulo a}
(%+) a Un_c   = Classe {representant = (representant a) + 1, modulo = modulo a}
(%+) a b      = 
  Classe{
    modulo =
       if (modulo a) == (modulo b) 
       then modulo a
       else error "Classes incompatibles" ,
    representant = mod ( (representant a) + (representant b)) (modulo a)
    }
  \end{lstlisting}

\end{frame}



\begin{frame}[fragile]
  \begin{lstlisting}
-- produit induit
(%*) :: Classe -> Classe -> Classe
(%*) Zero_c Un_c = Zero_c
(%*) Zero_c a    = 0%(modulo a)
(%*) a Zero_c    = 0%(modulo a)
(%*) Un_c a      = a
(%*) a Un_c      = a
(%*) a b         = 
  Classe{
    modulo =
       if (modulo a) == (modulo b) 
       then modulo a
       else error "Classes incompatibles" ,
    representant = mod ( (representant a) * (representant b)) (modulo a)
    }    
  \end{lstlisting}

\end{frame}


\begin{frame}[fragile]
\begin{lstlisting}
instance Num Classe where
  (+)           = (%+)
  (*)           = (%*)
  negate Zero_c = Zero_c
  negate b      = Classe{representant = mod (- (representant b)) (modulo b), modulo = (modulo b)} 
  fromInteger 0 = Zero_c
  fromInteger 1 = Un_c
  abs a         = a
  signum a      = 1
\end{lstlisting}

  
\end{frame}

\begin{frame}[fragile]
\begin{lstlisting}
λ> 9%5 + 7%5
1%5
\end{lstlisting}
\end{frame}



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

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

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



\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}
λ> map ord ['A'..'H']
[65,66,67,68,69,70,71,72]
\end{lstlisting}

\pause

\begin{lstlisting}
λ> map chr [65..90]
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
  \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{lstlisting}
λ> cesar 3 "Les sanglots longs des violons de l'automne"
"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}
λ> cesar (-3) "eohvvhqw#prq#frhxu#g*xqh#odqjxhxu#prqrwrqh"
"blessent mon coeur d'une langueur monotone"
\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}




\section{Structure d'espace vectoriel}

%
\begin{frame}
\begin{figure}
   \includegraphics[height=0.8\textheight]{grassmann}
\caption{Hermann \textsc{Gra\ss mann} (1809-1877)}
 \end{figure}
\end{frame}


%
\begin{frame}
  \begin{figure}
  \includegraphics[width=3.2cm]{banach}
\caption{Stefan \textsc{Banach} (1892-1945)}
\end{figure}
\end{frame}





%\begin{figure}
\begin{center}
  \includegraphics[height=\textheight]{marty_endroit}
\end{center}
%\end{figure}






%\begin{figure}
\begin{center}
  \includegraphics[height=\textheight]{marty_bruit}
\end{center}
%\end{figure}




%\begin{figure}
\begin{center}
  \includegraphics[height=\textheight]{marty_moyenne_9}
\end{center}
%\end{figure}







%\begin{figure}
\begin{center}
  \includegraphics[height=\textheight]{marty_mediane_9}
\end{center}
%\end{figure}











%
\begin{frame}
  \begin{center}
  \includegraphics[height=0.8\textheight]{marystein21}
\end{center}

\pause

$3\times      \text{Marylin}      +
 \text{Albert}$

\end{frame}

%
\begin{frame}
  \begin{center}
  \includegraphics[height=0.8\textheight]{marystein11}
\end{center}

\pause

$   \text{Marylin}    +
      \text{Albert}$

\end{frame}




%
\begin{frame}
  \begin{center}
  \includegraphics[height=0.8\textheight]{marystein13}
\end{center}


\pause

$ \text{Marylin} + 3\times\text{Albert}$
\end{frame}


%
\begin{frame}[fragile]
  \begin{definition}[$\bbk$-espace vectoriel]
Un $\bbk$-espace vectoriel $V$ sur un corps commutatif $\langle \bbk,\oplus,\odot\rangle$ est un groupe
abélien  $\langle V,\dagger\rangle$  muni  d'une  loi de  composition
\textit{externe}  $\cdot$  de  $\bbk\otimes V$  dans  $V$  vérifiant
les  quatre  axiomes  suivant,  $\lambda$ et  $\mu$  désignant  des  scalaires
quelconques, $\mathbf{u}$ et $\mathbf{v}$  des vecteurs quelconques et
$1_\odot$ l'élément neutre de la loi $\odot$ sur $\bbk$:

\begin{tabular}{ll}
  $(\lambda\oplus \mu)\cdot \mathbf{u}=\lambda\cdot\mathbf{u}\dagger \mu\cdot\mathbf{u}$ &(distributivité
    vectorielle);\\
  $\lambda\cdot(\mathbf{u}\dagger\mathbf{v})=\lambda\cdot\mathbf{u}\dagger \lambda\cdot\mathbf{v}$ &(distributivité
    scalaire);\\
 $(\lambda\odot \mu)\cdot\mathbf{u}=\lambda\cdot(\mu\cdot\mathbf{u})$ &(associativité);\\
 $1_\odot\cdot\mathbf{u}=\mathbf{u}$ &(axiome d'identité)\\
\end{tabular}

On dit que le corps $\bbk$ \textit{opère} sur le groupe  $\langle V,\dagger\rangle$.
 
\end{definition}



\pause



\begin{lstlisting}
imshow(3 * marilyn + einstein, cmap = cm.gray)
\end{lstlisting}

\end{frame}


\subsection{Un exemple de F$_{\text 2}$-espace vectoriel}


%
\begin{frame}

$$\langle b_1,b_2,b_3\rangle  \dagger \langle  b'_1,b'_2,b'_3\rangle =
\langle b_1\oplus b'_1,b_2\oplus b'_2,b_3\oplus b'_3\rangle$$

\pause
$$
 (\cdot)\ \colon \begin{array}{rll} \bbf_2\otimes T& \to & T\\
   \big\langle  \lambda,\langle   b_1,b_2,b_3\rangle\big\rangle&  \mapsto  &
   \langle \lambda\odot b_1,\lambda\odot b_2,\lambda\odot b_3\rangle
 \end{array}
 $$



\end{frame}




%
\begin{frame}[fragile]
  \begin{lstlisting}
data BoolInt = O | I deriving(Show,Read,Eq)

type BitChaine = [BoolInt]

bPlus :: BoolInt -> BoolInt -> BoolInt
bPlus    b1         b2 
  |b1 == b2                 = O
  |otherwise                = I
               
bFois :: BoolInt -> BoolInt -> BoolInt
bFois    I          I       =  I
bFois    _          _       =  O
         
cPlus :: BitChaine -> BitChaine -> BitChaine
cPlus    c1           c2        =  zipWith bPlus c1 c2

prodExt :: BoolInt -> BitChaine -> BitChaine
prodExt    b          c         =  map (\x -> bFois b x) c
\end{lstlisting}


\end{frame}

\begin{frame}[fragile]



\begin{lstlisting}
λ> bPlus O I
I
λ> cPlus [O,O,I] [I,O,I]
[I,O,O]
λ> prodExt I [O,O,I]
[O,O,I]
λ> prodExt O [O,O,I]
[O,O,O]
\end{lstlisting}



\end{frame}










%
\begin{frame}[fragile]


\begin{lstlisting}
lesBits = [O,I]

lesTrios = [[x,y,z] | x <- lesBits, y <- lesBits, z <- lesBits]

and [prodExt (bPlus b1 b2) t == cPlus (prodExt b1 t) (prodExt b2 t) 
    | b1 <- lesBits, b2 <- lesBits, t <- lesTrios ]
\end{lstlisting}



  
\end{frame}




\subsection{Ensemble des combinaisons linéaires d'une famille de vecteurs}




%
\begin{frame}
  \begin{definition}[Combinaison linéaire de vecteurs]
Soit $\langle\bbk,\oplus,\odot\rangle$ un corps  opérant sur le groupe
$\langle V,\dagger\rangle$ pour former  un espace vectoriel de produit
externe $\bullet$.

Soit   $\langle   \mathbf{u_0},\mathbf{u_1},\cdots,\mathbf{u_p}\rangle$   une
famille de vecteurs de $V$.


Un  vecteur $\mathbf{v}$  de $V$  est une  combinaison linéaire  de la
famille des $\langle \mathbf{u_i}\rangle_{0 \leqslant i \leqslant p}$ si, et
seulement si, il existe une famille 
$\langle \lambda_0,\lambda_1,\cdots,\lambda_p\rangle$ de  scalaires
de $\bbk$ vérifiant:

$$
\mathbf{v}            =            \displaystyle\daggersum_{i=0}^{i=p}\lambda_i\bullet
\mathbf{u_i}=\lambda_0\bullet\mathbf{u_0}\dagger
\lambda_1\bullet\mathbf{u_1}\dagger\cdots\dagger \lambda_p\bullet\mathbf{u_p}
$$


L'ensemble de ces combinaisons linéaires est noté:

$$\sev{\mathbf{u_0},\mathbf{u_1},\cdots,\mathbf{u_p}}$$
  
\end{definition}


\end{frame}




%
\begin{frame}[fragile]

\begin{lstlisting}
u = [O,I,I]
v = [I,O,I]
vect = [cPlus (prodExt b1 u) (prodExt b2 v) | b1 <- lesBits, b2 <- lesBits]
\end{lstlisting}

\pause


\begin{lstlisting}
λ> vect
[[O,O,O],[I,O,I],[O,I,I],[I,I,O]]
\end{lstlisting}

  
\end{frame}



\multido{\n=0+1}{21}{
\begin{frame}
\begin{center}
  \includegraphics[height=\textheight]{ow\n}
\end{center}
\end{frame}
}

\pythonc

\begin{frame}[fragile]

\begin{lstlisting}
o = imread('ouzbek.png')

w = imread('welsh.png')

def fondu(n):
    for k in range(n+1):
        t = k / float(n)
        imshow(t*o + (1-t)*w)
        savefig("ow" + str(k) + ".jpg")
\end{lstlisting}

\lat

\pause

\begin{lstlisting}
\multido{\n=0+1}{21}{
\begin{frame}
\begin{center}
  \includegraphics[height=\textheight]{ow\n}
\end{center}
\end{frame}}
\end{lstlisting}

\end{frame}

\haskell

%


\subsection{Sous-espace vectoriel}







%
\begin{frame}
  \begin{definition}[Sev]
Soit $\langle\bbk,\oplus,\odot\rangle$ un corps  opérant sur le groupe
$\langle V,\dagger\rangle$ pour former  un espace vectoriel de produit
externe $\bullet$.

Soit $W$ un sous-ensemble de $V$.

Si,  muni  des mêmes  opérations  que  $V$,  $W$  a une  structure  de
$\bbk$-espace   vectoriel,    alors   on   dit   que    $W$   est   un
\textbf{sous-espace vectoriel} de $V$.
  
\end{definition}

\end{frame}





%
\begin{frame}
  \begin{theorem}[Caractérisation (1) des sous-espaces vectoriels]\label{sev1}
Soit $\langle\bbk,\oplus,\odot\rangle$ un corps  opérant sur le groupe
$\langle V,\dagger\rangle$ pour former  un espace vectoriel de produit
externe $\bullet$.

Soit $W$ un sous-ensemble de $V$.

$W$ est un sous-espace vectoriel (sev) de $V$ si, et seulement si:

\begin{itemize}
\item $W\neq \emptyset$
\item      $(\forall      \mathbf{u})(\forall      \mathbf{v})(\langle
  \mathbf{u},\mathbf{v}\rangle   \in    W^2   \limp   \mathbf{u}\dagger
    \mathbf{v}\in W)$
\item $(\forall \lambda)(\forall      \mathbf{u})(\langle
  \lambda,\mathbf{u}\rangle \in \bbk\otimes W \limp \lambda\bullet \mathbf{u} \in W)$
\end{itemize}
  
\end{theorem}

\end{frame}






%
\begin{frame}
  \begin{theorem}[Caractérisation (2) des sous-espaces vectoriels]\label{sev2}
Soit $\langle\bbk,\oplus,\odot\rangle$ un corps  opérant sur le groupe
$\langle V,\dagger\rangle$ pour former  un espace vectoriel de produit
externe $\bullet$.

Soit $W$ un sous-ensemble de $V$.

$W$ est un sous-espace vectoriel (sev) de $V$ si, et seulement si:

\begin{itemize}
\item $\mathbf{0}\in W$

\item $(\forall \lambda)(\forall      \mathbf{u})(\forall      \mathbf{v})(\langle
  \lambda,\mathbf{u},\mathbf{v}\rangle   \in  \bbk\otimes   W\otimes  W\limp
  \mathbf{u}\dagger \lambda\bullet \mathbf{v} \in W)$
\end{itemize}
  
\end{theorem}
\end{frame}


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