%% Last modified: <introStructures.tex modifié par  Guillaume CONNAN le jeudi 30 octobre 2014 à 16h 47min 28s>
\haskell

%\(\\verb[\+\|]\)\(\ca*\)\([\+\|]\)
%\\Colorbox{blue!10}{\\lstinline{\2}}

\chapterimage{juge}
\chaptertext{Les langages  de programmation modernes sont  très algébriques: ils
  puisent  dans ce  domaine  mathématique,  développé surtout  depuis  la fin  du
  XIX\eme siècle, la  rigueur et les structures qui leur  permettent de créer des
  programmes sûrs et vérifiables a priori.
Les structures algébriques sont aussi les outils qui servent de base au codage
de l'information,  en cryptographie,
elles sont aussi le point de départ des outils de transformation en infographie, en
traitement d'image, elles offrent des outils indispensables à la théorie des langages, de la
compilation, des types.

Bref, elles sont un passage obligé pour bien saisir l'informatique moderne..}


\chapter{Opérations, lois et structures}


\section{Opération}


Une opération  est un concept à  la fois simple  (on l'utilise depuis le  CP) et
compliqué  : en  mathématique actuelle  et en  informatique théorique,  ce terme
recouvre des notions très abstraites.

Comme  nous  n'avons  guère  vu   que  des  ensembles,  nous  nous  contenterons
\textit{pour l'instant} de dire ici qu'il s'agit d'une \textbf{fonction} dont 
les paramètres seront appelés \textit{opérandes}.  On utilise le plus souvent un
symbole pour désigner cette fonction : c'est l'\textit{opérateur}.


\subsection{Opération unaire}

C'est simplement un autre nom d'une fonction d'un ensemble dans un autre...

On dit aussi dans ce cas que l'opération est d'\textbf{arité} 1.

Par exemple, la  négation d'une proposition sur l'ensemble  des propositions, la
fonction qui renvoie
l'opposé d'un  entier sur l'ensemble des  entiers mais on peut  imaginer tout ce
qu'on veut...

Considérons la  fonction \Colorbox{blue!10}{\lstinline{versMin}} de  l'ensemble des
caractères dans lui-même qui à une lettre majuscule renvoie la lettre 
minuscule associée. 


\begin{aparte}
Pourquoi le 'A' est codé 65 et le 'a' 97 en \textsc{Ascii}? 

Vous avez remarqué que $97-65=32=2^5$.

Mais il vaut mieux voir les choses ainsi:

'A' -> [1,0,0,0,0,0,1]

'a' -> [1,1,0,0,0,0,1]

'Z' -> [1,0,1,1,0,1,0]

'z' -> [1,1,1,1,0,1,0]

Qu'en pensez-vous?

\end{aparte}

En  Haskell,  la bibliothèque  \Colorbox{blue!10}{\lstinline{Data.Bits}}  permet
d'effectuer des opérations bit à bit, notamment:

\begin{lstlisting}[caption=Doc Data.Bits]
(.&.) :: a -> a -> a -- infixl 7

Bitwise "and"

(.|.) :: a -> a -> a -- infixl 5 

Bitwise "or"

xor :: a -> a -> a -- infixl 6 

Bitwise "xor"

complement :: a -> a 

Reverse all the bits in the argument 

bit :: Int -> a 

bit i is a value with the ith bit set and all other bits clear.

See also zeroBits.

setBit :: a -> Int -> a 

x `setBit` i is the same as x .|. bit i
\end{lstlisting}


\begin{lstlisting}
import Data.Char
import Data.Bits

versMin :: Char                      -> Char 
versMin    lettre 
  | (lettre < 'A') || (lettre > 'Z')  =  error "Ce n'est pas une majuscule !!!" 
  | otherwise                         =  chr (setBit (ord lettre) 5)
\end{lstlisting}




On utilise  deux fonctions fondamentales  dont on aura besoin  en cryptographie,
\Colorbox{blue!10}{\lstinline{chr}}  et  \Colorbox{blue!10}{\lstinline{ord}}  du
module \Colorbox{blue!10}{\lstinline{Data.Char}} qui font le lien entre un 
caractère et son code \textsc{Ascii}. 


\begin{recherche}
  Donnez  au   moins  deux   autres  implémentations   de  \Colorbox{blue!10}{\lstinline{versMin}}   puis  trois
  implémentations de \Colorbox{blue!10}{\lstinline{versMax}}
\end{recherche}


\begin{lstlisting}
λ> ord 'a'
97
λ> ord 'A'
65
λ> map ord ['a'..'z']
[97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,
 118,119,120,121,122]
λ> map ord ['A'..'Z']
[65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90]

λ> chr 97
'a'
λ> map chr [32 .. 126] 
" !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]
  ^_`abcdefghijklmnopqrstuvwxyz{|}~"
\end{lstlisting}

Par exemple:

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


Bon, cette fonction existait déjà...

\begin{lstlisting}
λ> map toLower ['A'..'Z']
"abcdefghijklmnopqrstuvwxyz"
\end{lstlisting}

mais fonctionne autrement:

\begin{lstlisting}
λ> map toLower "HO ! TU VAS TE METTRE EN MINUSCULE ! #@$ $ %*$"
"ho ! tu vas te mettre en minuscule ! #@$ $ %*$"
\end{lstlisting}

Comment   modifier  notre   \Colorbox{blue!10}{\lstinline{versMin}}   pour   qu'elle  fonctionne   comme
\Colorbox{blue!10}{\lstinline{to_Lower}}?






\subsection{Opération binaire}

Une opération binaire  est une fonction de  signature $A\otimes B \to  C$. On dit
qu'elle est d'arité 2.

Par exemple, que pensez-vous de: 

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

dont voici des réalisations:

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




On n'est pas obligé de travailler dans le même ensemble:

\begin{lstlisting}
estCode :: (Char,Int) -> Bool
estCode (car,nb) = (ord car == nb)
\end{lstlisting}

Par exemple:

\begin{lstlisting}
λ> estCode ('a', 97)
True
\end{lstlisting}


Mais  la \textit{curryfication}  nous permet  de transformer  toute fonction  de
plusieurs variables en une fonction d'une variable:

\begin{lstlisting}
estCode_c :: Char -> Int -> Bool
estCode_c    car     nb  =  ord car == nb
\end{lstlisting}

Cette fonction curryfiée, donc d'une seule variable, sera malgré tout considérée
comme une opération binaire.

Ici, l'opérateur est placé avant ses arguments:  on dit qu'il est dénoté par une
notation \textbf{préfixée}.

D'habitude,   les   opérateurs   binaires   sont  dénotés   par   une   notation
\textbf{infixée}. C'est possible aussi en Haskell :

\begin{lstlisting}
infix @+

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

On peut maintenant utiliser une syntaxe plus habituelle:

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


On  peut  utiliser  une  notation  \textbf{postfixée}  comme  pour  la  \textit{Notation
Polonaise Inversée} utilisée en assembleur, en postscript,...

Par exemple, $3$ $2$ $+$ désigne la somme de 3 et de 2.



\subsection{Opération d'arité supérieure}

On peut continuer ainsi.

Prenons par exemple l'opération ternaire définie sur $\bbz$ par:


\begin{itemize}
\item Version non curryfiée:

\begin{lstlisting}
f :: (Int,Int,Int) -> Int
f    (a  ,b  ,c  ) =  a^2 + b^2 + c^2
\end{lstlisting}

\begin{lstlisting}
λ> f (1,2,3)
14
\end{lstlisting}


\item Version curryfiée:

  \begin{lstlisting}
f :: Int -> Int -> Int -> Int
f    a      b      c   =  a^2 + b^2 + c^2
  \end{lstlisting}

  \begin{lstlisting}
λ> f 1 2 3
14
  \end{lstlisting}


\end{itemize}


On  peut aussi  la  considérer  comme opération  d'arité  1  sur l'ensemble  des
triplets de $\bbz^3$...





\section{Loi de composition}

\subsection{Définitions}

Une loi est une opération d'arité 2 qui est une fonction totale. On étudiera deux
cas: les lois de compoition internes et externes.



\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 est un \textbf{magma}.
\end{definition}


Donnez vous-mêmes de nombreux exemples....


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




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




Donnez vous-mêmes de nombreux exemples....


Voici enfin une notion primordiale dont nous reparlerons souvent:

\begin{definition}[Morphisme de magma]

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

$$\bigl(\forall x\bigr)\bigl(\forall y\bigr)\bigl(\phi(x\star y) = \phi(x)\dagger \phi(y)\bigr)$$

  
\end{definition}

Pouvez-vous donner quelques exemples?


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


C'est une notion primordiale!!! Cela permet  de simplifier (si si) énormément de
situations  qui  paraissent  différentes  mais  qui  sont  les  mêmes  \textit{à
  isomorphisme près}...



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


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



\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3cm]{abel}
%\caption{N.\textsc{Abel} (1802-1829)}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-2.2cm}
\begin{minipage}[t]{\linewidth}
Un magma  muni d'une  loi commutative  est dit  \textit{abélien} (en  hommage au
mathématicien norvégien Niels Henrik \textsc{Abel} (1802 - 1829)).
\end{minipage}



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

\begin{aparte}
  Il  y a  une grosse  bataille franco-anglo-saxonne  au sujet  de ce  qu'est un
  semi-groupe ou un demi-groupe.
  Nous allons nous conformer à la dernière référence en date, même si elle n'est
  pas  française:  \og Homotopy  Type  Theory\fg{}  disponible à  cette  adresse
  \href{http://homotopytypetheory.org/book/}{http://homotopytypetheory.org/book/}.1
  Un magma associatif y est défini page 122 comme un semi-groupe.
\end{aparte}

Quand des lois sont associatives, on peut se passer de parenthèses et on peut noter plus simplement leurs
itérations.  

Par exemple,  depuis le collège, vous  notez $a^n$ la multiplication  itérée $n$
fois de $a$ par lui-même.







Certaines lois ne sont pas associatives mais on peut \textit{décider}, pour se simplifier
la  vie au  moment de  les  créer, qu'elles  sont  associatives à  droite (ou  à
gauche).

Sur  Haskell  par  exemple, l'opérateur  \Colorbox{blue!10}{\lstinline{->+}} entre  domaine et  codomaine d'une
fonction est  associatif à droite. En  effet, les concepteurs de  Haskell  ont décidé
que \Colorbox{blue!10}{\lstinline{Char -> Int -> Bool}} signifie en fait \Colorbox{blue!10}{\lstinline{Char -> (Int -> Bool)}}.

On peut ainsi se passer de parenthèses mais il faudra bien garder à l'esprit que
l'associativité n'est effective qu'à droite.

Par exemple, commentez ce qui passe ici:

\begin{lstlisting}
estCode :: Char -> Int -> Bool
estCode car nb = ord car == nb
\end{lstlisting}

\begin{lstlisting}
λ> :t estCode 'a'
estCode 'a' :: Int -> Bool
λ> :t ord
ord :: Char -> Int
λ> :t estCode (ord)

<interactive>:1:11:
    Couldn't match expected type `Char' with actual type `Char -> Int'
    In the first argument of `estCode', namely `(ord)'
    In the expression: estCode (ord)
\end{lstlisting}




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

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



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

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

On note souvent ce symétrique $x^{-1_\star}$ ou bien ${-}_\star x$.


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


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


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

\begin{remarque}
  Une loi  de composition externe peut  être distributive par rapport  à une loi
  interne: cherchez un exemple...
\end{remarque}




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


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


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



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






\section{Groupes}


\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=2.6cm]{Evariste}
\caption{É.\textsc{Galois} (1811-1832)}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-5.2cm}
\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 la mathématique  et ses travaux
ont eu une très grande influence  sur le développement de nombreux domaines liés
à l'informatique: la théorie de
l'information, la spécification, la compilation,etc.



La notion  de groupe  puis d'anneau  et de corps  que nous  allons voir  dans ce
chapitre permettent également d'organiser  très efficacement notre programmation
et de nous initier aux notions de polymorphisme.


Nous    verrons    que   nous    pourrons    également    aborder   la    notion
d'\textit{instantiation} de classes en Haskell  et de \textit{surcharge} d'opérateur.

Il existe  également de nombreuses  applications en infographie, en  théorie des
langages formels, de la compilation...

\end{minipage}



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

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


Nous travaillerons souvent avec des groupes ayant seulement un nombre
fini d'éléments:


\begin{definition}[Ordre d'un groupe fini]
  Soit $G$ un groupe ayant un nombre fini d'éléments. Le cardinal de
  G est appelé l'\textbf{ordre du groupe} G.
\end{definition}



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

ou

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

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

Avec \textsf{Caml}:


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


Avec Python:

\pythonc

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


Avec Haskell , on a les deux :)

\haskell

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



\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 qui traduit la division de 37 par 4:

\begin{center}
\includegraphics{div_euc}
\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 \leqslant  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\leqslant 
 bq+r<bq+b$, c'est à dire $0\leqslant  r<b$

 \sm

 Nous avons donc démontré l'existence de deux entiers $q$ et $r$
 tels que $a=bq+r$ avec $0\leqslant  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\leqslant  r<b\\
a&=bq'+r'\quad\text{avec}\quad 0\leqslant  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: divide 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.


\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\leqslant  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\leqslant  d'$ car $d'$ est le plus grand diviseur puis $d'\leqslant  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\geqslant  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\leqslant  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\leqslant  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:

\begin{algo}
\FUNC{euclide}{%
\pfarg{a, b}{entiers}}{entier}
\IF{b = 0}
\RETURN{a}
\ELSE
\RETURN{euclide(b,(mod 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+mod+ $(r_0,r_1)$\\
$\vdots$
\item $r_{i+1}=$\verb+mod+ $(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+mod+ $(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+mod+ $(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 
%\Colorbox{blue!10}{\lstinline{}}
\begin{center}
\begin{tabular}{ccccc}
 & \Colorbox{blue!20}{$u_k$} & {\Large{\textbf{$-$}}} &  &    \\
 & & & &  \\ 
{\Large{\textbf{(}}} & \Colorbox{blue!20}{$u_{k+1}$} & {\Large{\textbf{$\times$}}} & \Colorbox{Green!20}{$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 & \Colorbox{blue!20}{ 1} & \Colorbox{blue!20}{ 0} & \Colorbox{blue!20}{ 19} & / & $L_0$ \\ 
\hhline{-----} 1 & \Colorbox{blue!20}{ 0} & \Colorbox{blue!20}{ 1} &\Colorbox{blue!20}{ 15} & \Colorbox{Green!20}{1} & $L_1$ \\ 
\hhline{-----} 2 & 1 & $-1$ & 4 & 3 & $L_2\leftarrow L_0-\Colorbox{Green!20}{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+div+(r,r')*u',v-\verb+div+(r,r')*v',r-\verb+div+(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{Anneaux et corps}

\subsection{Anneaux}

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

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

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

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}


\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3.2cm]{lord_ring}
%\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?


\subsection{Corps}


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




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


Quand $\langle
  \bbk\setminus\{e_\boxplus\},\boxdot\rangle$
  est  un groupe  abélien, le  corps
  $\langle
  \bbk,\boxplus,\boxdot\rangle$  est
  dit commutatif.

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

Il  existe  un   corps  très  important  en  théorie  de   l'information  et  en
cryptographie:  le  corps  $\ofr{\bbz}{2\bbz}$  muni  de  l'addition  et  de  la
multiplication modulaire. On le note
habituellement $\bbf_2$  en français
et $GF(2)$ en anglais.

Vérifiez  qu'il   s'agit  bien  d'un
corps muni des lois habituelles...



\subsection{Les classes numériques sur Haskell}

%\(\\verb\+\)\(\w\)\(\+\)
%\\Colorbox{blue!10}{\\lstinline{\2}}
La classe \Colorbox{blue!10}{\lstinline{Num}} de \Colorbox{blue!10}{\lstinline{Prelude}} regroupe les types numériques usuels (\Colorbox{blue!10}{\lstinline{Int}},
\Colorbox{blue!10}{\lstinline{Integer}}, \Colorbox{blue!10}{\lstinline{Float}} et \Colorbox{blue!10}{\lstinline{Double}}) mais avec des opérations basiques :

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


À quelle structure algébrique peut-on associer la classe \Colorbox{blue!10}{\lstinline{Num}}?

Il existe \og  au-dessus\fg{} une classe \Colorbox{blue!10}{\lstinline{Fractional}} qui  est définie avec
les opérations suivantes:

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

sachant qu'un \Colorbox{blue!10}{\lstinline{Rational}} est, comme son  nom l'indique un élément de $\bbq$
c'est-à-dire le rapport entre deux entiers.

\begin{lstlisting}
Prelude> toRational 1.25
5 % 4
\end{lstlisting}

Mais nous n'insisterons pas sur ce type de données car nous allons...le recréer nous-mêmes!

À quelle structure algébrique peut-on associer la classe \Colorbox{blue!10}{\lstinline{Frational}}?

Voici enfin deux autres classes utiles:

\begin{lstlisting}
class  (Num a, Ord a) => Real a  where
    toRational ::  a -> Rational

class  (Real a, Enum a) => Integral a  where
    quot, rem, div, mod :: a -> a -> a
    quotRem, divMod     :: a -> a -> (a,a)
    toInteger :: a -> Integer

class  (Fractional a) => Floating a  where
    pi                  :: a
    exp, log, sqrt      :: a -> a
    (**), logBase       :: a -> a -> a
    sin, cos, tan       :: a -> a
    asin, acos, atan    :: a -> a
    sinh, cosh, tanh    :: a -> a
    asinh, acosh, atanh :: a -> a

class  (Real a, Fractional a) => RealFrac a  where
    properFraction   :: (Integral b) => a -> (b,a)
    truncate, round  :: (Integral b) => a -> b
    ceiling, floor   :: (Integral b) => a -> b
\end{lstlisting}

\subsection{Un nouveau type numérique}

Il  est  possible  de  créer  un nouveau  type  numérique.  Selon  sa  structure
algébrique, on en fera une instance de \Colorbox{blue!10}{\lstinline{Num}} ou de \Colorbox{blue!10}{\lstinline{Fractional}}.



\subsection{Calcul modulaire en Haskell}

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

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

On fait de \verb+Classe+ une instance de \verb+Eq+ pour gérer les égalités:

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


On fait de \verb+Classe+ une instance de \verb+Show+ pour gérer l'affichage

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



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

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

On obtient alors:

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

On peut ensuite créer des lois induites:

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

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


On fait  alors de \verb+Classe+ une  instance de \verb+Num+ pour  surcharger les
opérateurs \verb|+| et \verb+*+, gérer les opposés:

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


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

\begin{lstlisting}
λ> 9%5 + 7%5
1%5
\end{lstlisting}



\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 Haskell.









\section{Structure d'espace vectoriel}


\subsection{Un peu d'histoire}



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


Hermann \textsc{Gra\ss mann} (1809-1877) est un mathématicien allemand
hors du  commun. Il enseigna  principalement au lycée  des disciplines
aussi  diverses que  les  mathématiques, la  physique, l'allemand,  le
latin et la théologie. Il commence  à publier les fondements de ce qui
deviendra la théorie des espaces  vectoriels mais le rapporteur de ses
travaux les lit d'un \oe il distrait et passe totalement à côté.

\textsc{Gra\ss  mann}  persiste  et  publie en  1844  \og  \textit{Die
  lineale  Ausdehnungslehre,  ein  neuer  Zweig  der  Mathematik}\fg{}
(l'enseignement de  l'extension linéaire,  une nouvelle branche  de la
mathématique) qui passe encore inaperçu car \textsc{Gra\ss mann} n'est
pas un universitaire. Ses travaux  ne seront reconnus qu'après sa mort
lorsque  l'italien \textsc{Peano}  donne une  présentation axiomatique
des espaces vectoriels dérivée des travaux de \textsc{Gra\ss mann}.

Enfin c'est un  jeune polonais, Stefan \textsc{Banach},  qui, en 1920,
propulsa  les  espaces vectoriels  en  dehors  de la  sphère  purement
géométrique  et  en  fit  un   des  outils  majeurs  de  développement
scientifique.



\end{minipage}

\subsection{Vers une définition}


Considérons le vecteur Marylin et le
vecteur Albert. Voici trois nouveaux
vecteurs  obtenus   par  différentes
combinaisons: 
 $3\times      \text{Marylin}      +
 \text{Albert}$, 
       $   \text{Marylin}    +
      \text{Albert}$ et $ \text{Marylin} + 3\times\text{Albert}$
    
\hspace{-1cm}
\setindent{0cm}

\begin{center}
\begin{multicols}{3}
  

%\begin{figure}
\begin{center}
  \includegraphics[height=8cm]{marystein21}
\end{center}
%\end{figure}



%\begin{figure}
\begin{center}
  \includegraphics[height=8cm]{marystein11}
\end{center}
%\end{figure}




%\begin{figure}
\begin{center}
  \includegraphics[height=8cm]{marystein13}
\end{center}
%\end{figure}


\end{multicols}
\end{center}

\setindent{\indentationcours}


% %\vspace{-6.2cm}
% \setindent{0cm}
% \begin{flushleft}
% \begin{minipage}[t]{3cm}
% \begin{figure}
%   \includegraphics[width=3.2cm]{banach}
% \caption{S. \textsc{Banach} (1892-1945)}
% \end{figure}
% \end{minipage}
% \end{flushleft}
% \setindent{\indentationcours}
% \vspace{-5.375cm}
% \begin{minipage}[t]{\linewidth}


On voit clairement  apparaître la notion de produit externe  : ici les
vecteurs sont des  images qui peuvent être additionnées  et rester des
images. De  plus, on peut multiplier  une image par un  nombre et cela
reste une image.

On est souvent confronté à cette  situation: un groupe, un corps et un
produit externe des éléments du corps sur les éléments du groupe.

On peut par  exemple combiner des octets, des  fonctions...et même des
vecteurs du plan.

Mais il  ne faut pas lier  des opérations de manière  trop hasardeuse:
cela  pourrait  réserver de  fâcheuses  surprises.  C'est pourquoi  on
impose des  liens étroits  entre les deux  opérations, comme  pour les
corps.


Un \textbf{espace  vectoriel $V$  sur un corps  $\bbk$} est  un groupe
additif muni d'une loi de composition externe. 

Les  éléments  du  corps  sont  appelés  les  \textbf{scalaires},  les
éléments de $V$ sont appelés les \textbf{vecteurs}.


Bon, soyons plus formels:



\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,  $λ$ et  $μ$  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}
  $(λ\oplus μ)\cdot \mathbf{u}=λ\cdot\mathbf{u}\dagger μ\cdot\mathbf{u}$ &(distributivité
    vectorielle);\\
  $λ\cdot(\mathbf{u}\dagger\mathbf{v})=λ\cdot\mathbf{u}\dagger λ\cdot\mathbf{v}$ &(distributivité
    scalaire);\\
 $(λ\odot μ)\cdot\mathbf{u}=λ\cdot(μ\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}


On pourrait se  demander pourquoi on n'a pas poussé  $V$ jusqu'à avoir
une multiplication, tant qu'à  faire....Mouais...mais s'il est naturel
d'additionner des  images en leur  affectant des coefficients,  il est
moins naturel  d'imaginer une  multiplication d'images (et  c'est même
mathématiquement compromis).

Il est donc plus naturel de se contenter d'un groupe.

Souvent sur papier (mais pas sur machine :-) ), par paresse, on omet
les symboles de produit externe et  de produit interne, mais cela peut
prêter à confusion, surtout lors  de notre phase d'apprentissage, donc
nous n'en ferons rien.

% \begin{remarque}
%   Pour  obtenir  les  combinaisons d'images  précédentes,  nous  avons
%   utilisé  \Colorbox{blue!10}{\lstinline{NumPy}}  et  la   syntaxe  est  très  orientée  espace
%   vectoriel:


% \pythonc

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

% \haskell

% \end{remarque}


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


On  considère l'ensemble $T$ des chaînes  de  3 bits  muni de  l'addition
canonique:

$$\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$$
avec $\oplus$ l'addition sur $\bbf_2$: 

$$0\oplus 0=1\oplus 1=0 \quad \text{et} \quad 0\oplus 1= 1\oplus 0 =1$$


On muni $\bbf_2$ de sa multiplication canonique:

$$0\odot 0=0\odot 1=1\odot 0 =0 \quad \text{et} \quad 1\odot 1= 1$$

Ainsi  $\langle \bbf_2,\oplus,\odot\rangle$  est un  corps, $\langle
T,\dagger\rangle$ est un groupe abélien.

Le produit externe est:
$$
 (\cdot)\ \colon \begin{array}{rll} \bbf_2\otimes T& \to & T\\
   \big\langle  λ,\langle   b_1,b_2,b_3\rangle\big\rangle&  \mapsto  &
   \langle λ\odot b_1,λ\odot b_2,λ\odot b_3\rangle
 \end{array}
 $$


Il reste à vérifier les quatre axiomes (faites-le...)

Sur Haskell :


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


donne par exemple:

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



On peut alors tester l'axiome de distributivité scalaire par exemple :

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

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


Dans  un  espace vectoriel,  les  opérations  \og linéaires\fg{}  sont
l'addition du groupe et le produit externe.

\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 λ_0,λ_1,\cdots,λ_p\rangle$ de  scalaires
de $\bbk$ vérifiant:

$$
\mathbf{v}            =            \displaystyle\daggersum_{i=0}^{i=p}λ_i\bullet
\mathbf{u_i}=λ_0\bullet\mathbf{u_0}\dagger
λ_1\bullet\mathbf{u_1}\dagger\cdots\dagger λ_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}


Par exemple,  prenons le $\bbr$-espace  vectoriel $\bbr^2$ muni  de la
somme et du produit externe canonique.

On peut  dire que $\mathbf{v}=\langle 4,3\rangle$  est une combinaison
linéaire   de    $\mathbf{u_1}=\langle   2,1\rangle$    et   $\mathbf{u_2}=\langle
0,3\rangle$:

$$\mathbf{v}= 2\mathbf{u_1}+ \frac{1}{3} \mathbf{u_2}$$


On peut  alors légitimement se  demander ce que  représente l'ensemble
des combinaisons linéaires d'une famille fixée de vecteurs.

Par  exemple, travaillons  dans $\bbf_2^3$  en tant  que $\bbf_2$-espace
vectoriel  muni des  opérations  canoniques. Quelles  sont toutes  les
combinaisons linéaires des vecteurs $\langle 0,1,1\rangle$ et $\langle 1,0,1\rangle$?

Vérifiez les résultats  donnés par Haskell  avec  les fonctions introduites
précédemment:

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

Donne:

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

\subsection{Sous-espace vectoriel}

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



Il   serait   bête   de   vérifier   tous   les   critères   pour   un
sous-espace. Démontrez les caractérisations suivantes:

\begin{theoreme}[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 λ)(\forall      \mathbf{u})(\langle
  λ,\mathbf{u}\rangle \in \bbk\otimes W \limp λ\bullet \mathbf{u} \in W)$
\end{itemize}
  
\end{theoreme}


Démontrez qu'on peut être plus synthétique:

\begin{theoreme}[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 λ)(\forall      \mathbf{u})(\forall      \mathbf{v})(\langle
  λ,\mathbf{u},\mathbf{v}\rangle   \in  \bbk\otimes   W\otimes  W\limp
  \mathbf{u}\dagger λ\bullet \mathbf{v} \in W)$
\end{itemize}
  
\end{theoreme}




%%%%
%
%                                      E X E R C I C E S 
%
%%%%%%%%


\vfill

\eject

\modeexercice
\section{TD}

%
\subsection{LCI}
%
\begin{exercice}
  Répondez aux  questions posées  dans le  premier paragraphe  du cours  sur les
  opérateurs d'arité 1.
\end{exercice}



\begin{exercice}[Have  you  got  the
  power?]\label{exo::1}

On considère la LCI $\star$ définie sur
$\bbz$ par:

$$a\star b = a - b$$



L'écriture $a^3=a\star a\star a$ a-t-elle un sens? Quel est le sens de cette question?
\end{exercice}

\begin{exercice}[Have  you  got  the
  power now?]\label{exo::2}


On considère la LCI $\star$ définie sur
$\bbz$ par:

$$a\star b = \underbrace{a\times a \times \cdots \times a}_{b \text{ facteurs}}$$

L'écriture $a^3=a\star a\star a$ a-t-elle un sens?

\end{exercice}

\begin{exercice}[And now?]\label{exo::3}
  On considère la LCI définie sur $\bigl\{A,B,C,D\bigr\}$ par:

  \begin{center}
    \begin{tabularx}{0.5\linewidth}{Y{3}}
      \whline
      $\star$&$A$&$B$&$C$&$D$\\
      \whline
      $A$&$B$&$C$&$D$&$A$\\
      \hline
      $B$&$D$&$A$&$B$&$C$\\
      \hline
      $C$&$A$&$B$&$C$&$D$\\
      \hline
      $D$&$C$&$D$&$A$&$B$\\
      \whline
    \end{tabularx}
  \end{center}

L'écriture $A^3=A\star A\star A$ a-t-elle un sens?

\end{exercice}






\begin{exercice}[Pliage]
On définit la fonction pliage par:


\begin{lstlisting}
pliage :: (t -> t -> t) -> t   -> [t]       -> t
pliage     _               acc    []        =  acc
pliage loi acc (t:queue) = pliage loi (loi acc t) queue 
\end{lstlisting}

Quelles sont les valeurs des expressions suivantes:

\begin{lstlisting}
λ> pliage (+) 0 [1..10]
??
λ> pliage (*) 1 [1..10]
??
λ> pliage (\acc w -> acc ++ " " ++ w) "" ["J'aime", "Petit", "Poney"]
??
\end{lstlisting}

Que se passe-t-il ici?

\begin{lstlisting}
λ> pliage (\ acc x -> acc ++ [x*x]) [] [1..10] 
\end{lstlisting}

Comment       y      remédier?       Proposer      alors       une      fonction
\Colorbox{blue!10}{\lstinline{pliage'}}              qui              généralise
\Colorbox{blue!10}{\lstinline{pliage}} et évite l'erreur précédente.

Comment  qualifier \Colorbox{blue!10}{\lstinline{loi}}  dans le  premier pliage?
Dans le second?


Définissez  la  fonction  \Colorbox{blue!10}{\lstinline{map}}  à  l'aide  de  la
fonction \Colorbox{blue!10}{\lstinline{pliage'}}.


\end{exercice}






\begin{exercice}[Relations d'équivalence et d'ordre]


On  rappelle qu'une  relation  binaire  est une  relation  d'équivalence si,  et
seulement si, elle est réflexive, symétrique et transitive.


On  définit  un type  sur  Haskell  pour représenter  les  vecteurs  du plan  en
dimension 2:

\begin{lstlisting}
data Vect2D = Vect(Double,Double)
\end{lstlisting}

Définissez une fonction 
\Colorbox{blue!10}{\lstinline{egal :: Vect2D -> Vect2D -> Bool}}
 qui  teste  si  deux vecteurs  sont  égaux.  Est-ce une  relation
d'équivalence?

On  peut  faire de  \Colorbox{blue!10}{\lstinline{Vect2D}}  une  instance de  la
\textit{classe de type} \Colorbox{blue!10}{\lstinline{Eq}} ainsi:

\begin{lstlisting}
instance Eq Vect2D where
    (==) = egal
\end{lstlisting}

Alors:

\begin{lstlisting}
λ> Vect(2,3) == Vect(4,6)
True
\end{lstlisting}
  

On décide ensuite de classer les vecteurs en comparant leurs normes.

On  rappelle  qu'une  relation  d'ordre  est une  relation  binaire  à  la  fois
réflexive, antisymétrique et transitive.

Est-ce que la relation choisie pour classer les vecteurs est une relation d'ordre?


On choisit un autre moyen de comparer des vecteurs en comparant leurs abscisses. Si les
abscisses sont égales, on compare alors leurs ordonnées.

Est-ce que cette nouvelle relation est une relation d'ordre?

Il existe sur Haskell une classe \Colorbox{blue!10}{\lstinline{Ord}}. Pour faire
de       \Colorbox{blue!10}{\lstinline{Vect2D}}       une      instance       de
\Colorbox{blue!10}{\lstinline{Ord}},    il     faut    créer     une    fonction
\Colorbox{blue!10}{\lstinline{compare}}   qui   devra   avoir   pour   signature
\Colorbox{blue!10}{\lstinline{Vect2D  ->   Vect2D  ->  Ordering}}   sachant  que
\Colorbox{blue!10}{\lstinline{Ordering}}  est  un  type  constitué  d'uniquement
trois             constructeurs:             \Colorbox{blue!10}{\lstinline{LT}},
\Colorbox{blue!10}{\lstinline{EQ}}  et \Colorbox{blue!10}{\lstinline{LT}}:  vous
qui êtes bilingues, qu'est-ce que ces initiales peuvent vouloir dire?

Les entiers sont une instance de \Colorbox{blue!10}{\lstinline{Ord}}:

\begin{lstlisting}
λ> compare 3 5
LT
λ> compare 5 3
GT
λ> compare 5 5
EQ
\end{lstlisting}

À   vous  de   jouer   pour   les  vecteurs   du   plan:   créez  une   fonction
\Colorbox{blue!10}{\lstinline{ordre :: Vect2D -> Vect2D -> Ordering}} puis:

\begin{lstlisting}
instance Ord Vect2D where
    compare = ordre
\end{lstlisting}

Alors vous devez obtenir par exemple:

\begin{lstlisting}
λ> Vect(1,2) < Vect(1,3) 
True
\end{lstlisting}

\setindent{\indentationcours}

\begin{remarque}
En fait, l'ordre précédent correspond à l'ordre \textit{lexicographique} des n-uplets qui
existe déjà sur
\Colorbox{blue!10}{\lstinline{Prelude}}:


\begin{lstlisting}
λ> compare (1,2,3,4) (1,2,3,5)
LT
\end{lstlisting}

\end{remarque}

\setindent{0cm}


\end{exercice}






\begin{exercice}[Vision algébrique des listes]

Quelle strcuture algébrique possède $\langle$\Colorbox{blue!10}{\lstinline{[a],++}}$\rangle$?
  
\end{exercice}

\begin{exercice}[Vision algébrique des arbres]

Rappelez-vous le dernier DS ;-)


\begin{lstlisting}
data Arbre = Vide | Noeud (Arbre , Int , Arbre)
\end{lstlisting}


Voici une jolie loi:

\begin{lstlisting}
(%%) :: Arbre -> Arbre -> Arbre
(%%)    a        Vide  = a
(%%)    (Noeud(g,n,d)) (Noeud(g',n',d'))
           | n < n'    = Noeud(Noeud(g,n,d) %% g' ,n', d'                  )
           | otherwise = Noeud(g'                 ,n', (Noeud(g,n,d)) %% d')
\end{lstlisting}

Voici cinq jolis arbres:

\begin{lstlisting}
λ> let a = Noeud(Noeud(Vide,1,Vide), 2, Noeud(Vide,3,Vide))
λ> let b = Noeud(Noeud(Vide,-1,Vide), 0, Noeud(Vide,3,Vide))
λ> let c = Noeud(Vide,1,Vide)
λ> let d = (a %% b) %% c
λ> let e = a %% (b %% c)
\end{lstlisting}

Dessinez-les!

Quelle est la structure algébrique de $\langle$\Colorbox{blue!10}{\lstinline{Arbre,%%}}$\rangle$?

Moralité: les arbres, c'est plus simple que les listes...
  
\end{exercice}


\begin{exercice}[Tester n'est pas jouer]
On peut facilement  construire une classe définissant les magmas:  c'est un type
(qui  correspond pour  nous à  un ensemble)  qu'on notera  de manière  générique
\Colorbox{blue!10}{\lstinline{t}},
muni d'une loi qu'on notera de manière
générique \Colorbox{blue!10}{\lstinline{<+>}}. 

\begin{lstlisting}
class Magma t where
  (<+>) :: t -> t -> t
\end{lstlisting}

Cela traduit qu'un ensemble de variables de  type \Colorbox{blue!10}{\lstinline{t}} est un magma quand il
est muni d'une LCI ( qui est donc de signature \Colorbox{blue!10}{\lstinline{t -> t -> t}})



On peut alors faire de \Colorbox{blue!10}{\lstinline{Integer}} une instance de notre classe
\Colorbox{blue!10}{\lstinline{Magma}} en  prenant comme loi l'addition  des entiers: on remplace  le type
inconnu \Colorbox{blue!10}{\lstinline{t}} par \Colorbox{blue!10}{\lstinline{Integer}} et on définit la LCI générique \Colorbox{blue!10}{\lstinline{<+>}}
comme étant la classique addition des entiers:

\begin{lstlisting}
instance Magma Integer where
  (<+>) = (+)
\end{lstlisting}

On peut de  même faire de \Colorbox{blue!10}{\lstinline{String}} une instance  de \Colorbox{blue!10}{\lstinline{Magma}} en prenant
cette fois comme LCI la concaténation des chaînes qui est \Colorbox{blue!10}{\lstinline{++}} sur Haskell .

\begin{lstlisting}
instance Magma String where
  (<+>) = (++)
\end{lstlisting}


...mais on  se fait  insulter par le  compilateur! Il faut  en effet  passer une
option au compilateur  pour qu'il accepte les instances à  partir de types comme
\Colorbox{blue!10}{\lstinline{String}}.

Il faut donc  rajouter \textbf{sur la première ligne de  votre fichier} la ligne
suivante :

\begin{lstlisting}
{-# LANGUAGE TypeSynonymInstances, FlexibleInstances #-}
\end{lstlisting}


Pour que notre ensemble muni de sa loi soit un magma associatif, il faut et il suffit que
cette loi soit associative. On crée donc un test:

\begin{lstlisting}
isMagmaAssociatif :: (Magma t, Eq t) => (t,t,t) -> Bool
isMagmaAssociatif                       (a,b,c) = (a <+> b) <+> c == a <+> (b <+> c)
\end{lstlisting}

Comment fait un mathématicien pour vérifier  que \Colorbox{blue!10}{\lstinline{Integer}} muni de la somme
\Colorbox{blue!10}{\lstinline{+}} a une structure de magma associatif? Il démontre que la loi est associative.

Que fait un informaticien qui a dormi en cours? Il fait des tests.

Il existe sur Haskell  un module \Colorbox{blue!10}{\lstinline{QuickChek}} qui va nous aider ici:

\begin{lstlisting}
import Test.QuickCheck
\end{lstlisting}

La documentation est là:

\href{http://hackage.haskell.org/package/QuickCheck-2.1.0.1/docs/Test-QuickCheck.html}{http://hackage.haskell.org/package/QuickCheck-2.1.0.1/docs/Test-QuickCheck.html}

Écrivons  notre  test (\Colorbox{blue!10}{\lstinline{quickCheck}}  qui fait   100  tests sur  des  triplets
aléatoirement choisis selon une loi uniforme):

\begin{lstlisting}
test1 = quickCheck (isMagmaAssociatif :: (Integer,Integer,Integer) -> Bool)
\end{lstlisting}

C'est bon pour 100, c'est bon pour tous dit un apprenti informaticien:

\begin{lstlisting}
λ> test1
+++ OK, passed 100 tests.
\end{lstlisting}


Pour tester l'associativité du magma définit sur les \Colorbox{blue!10}{\lstinline{String}}, on change la signature:


\begin{lstlisting}
test2 = quickCheck (isMagmaAssociatif :: (String,String,String) -> Bool)
\end{lstlisting}



Mais, comme le disait Edsger \textsc{Dijkstra} (1930 - 2002), prix \textsc{Turing} 1972:

\begin{quote}
  {\itshape
Program testing can be used to show the presence of bugs, but never to show their absence! 
}
\end{quote}
\begin{flushright}
 in \og Notes On Structured Programming, corollary at the end of section 3, On The Reliability of Mechanisms\fg{} (EWD249).
\end{flushright}


Maintenant,  faites  un  \Colorbox{blue!10}{\lstinline{quickCheck}}  sur les  exercices  \ref{exo::1}  et
\vref{exo::2}.


Pour l'exercice \vref{exo::3}, on ne va pas utiliser \Colorbox{blue!10}{\lstinline{quickCheck}}  car le type est inconnu.

On va donc construire les tests nous-mêmes.

Définissons notre loi et son ensemble:

\begin{lstlisting}
data Truc = A | B | C | D deriving(Show,Eq)

lesTrucs = [A,B,C,D]

plus :: Truc -> Truc -> Truc
plus A A = A
plus A B = C
plus A C = D
plus A D = A
plus B A = D
plus B B = A
plus B C = B
plus B D = C 
plus C A = A
plus C B = B
plus C C = C 
plus C D = D
plus D A = C
plus D B = D
plus D C = A
plus D D = B

instance Magma Truc where
  (<+>) = plus
\end{lstlisting}

Construisons tous les triplets d'éléments de \Colorbox{blue!10}{\lstinline{Truc}} à l'aide d'une liste par compréhension:

\begin{lstlisting}
lesTripletsTrucs = [(a,b,c) | a <- lesTrucs, b <- lesTrucs, c <- lesTrucs]
\end{lstlisting}



Maintenant, on peut tester toutes les possibilités:

\begin{lstlisting}
testa = all isMagmaAssociatif  lesTripletsTrucs
\end{lstlisting}

Argh:

\begin{lstlisting}
λ> testa
False
\end{lstlisting}

Quel est le premier cas qui pose problème? Quels sont les triplets qui ne posent pas de problème?

Pour répondre à ces questions, nous allons construire une fonction \Colorbox{blue!10}{\lstinline{filtre}} et une fonction \Colorbox{blue!10}{\lstinline{trouve}}.

La première va filtrer une liste selon un prédicat. Sa signature sera donc:

\begin{lstlisting}
filtre :: (a -> Bool) -> [a] -> [a]
\end{lstlisting}



Expliquez cette signature.

Expliquez ce que fait cette fonction et comment elle le fait:

\begin{lstlisting}
filtre    foncFiltre     []  =  []
filtre    foncFiltre   (t:q) = if (foncFiltre t) 
                               then  t : (filtre foncFiltre q) 
                               else       filtre foncFiltre q
\end{lstlisting}

Créez  alors une  fonction \Colorbox{blue!10}{\lstinline{trouve}}  qui renvoie  le premier  élément d'une
liste qui vérifie un prédicat donné en argument. 


Appliquez ces fonctions à nos \Colorbox{blue!10}{\lstinline{Trucs}}.

Créez à présent un test \Colorbox{blue!10}{\lstinline{isMagmaSimplifiableGauche}} qui teste si un triplet
vérifie la propriété:

$$a \star b = a \star c \limp b = c$$

Vous aurez sûrement besoin du ET logique \Colorbox{blue!10}{\lstinline{&&}}, du OU inclusif \Colorbox{blue!10}{\lstinline{||}}, de la
négation de l'égalité \Colorbox{blue!10}{\lstinline{/=}}.

Créez     de     même      un     \Colorbox{blue!10}{\lstinline{isMagmaSimplifiableDroite}}     et     un
\Colorbox{blue!10}{\lstinline{isMagmaSimplifiable}}.

Appliquez ce test aux \Colorbox{blue!10}{\lstinline{Trucs}}.

Créez une  fonction \Colorbox{blue!10}{\lstinline{isNeutre  e liste}}  qui teste  si \Colorbox{blue!10}{\lstinline{e}}  est neutre
vis-à-vis de tous les éléments de la liste \Colorbox{blue!10}{\lstinline{liste}}.

Créez enfin une  liste \Colorbox{blue!10}{\lstinline{trouveNeutre liste}} qui trouve  un éventuel élément
neutre dans la liste \Colorbox{blue!10}{\lstinline{liste}}.




On peut maintenant créer un type correspondant au corps $\bbf_2$ qui est la base
de travail en théorie de l'information  et en faire une instance de \Colorbox{blue!10}{\lstinline{Magma}}
en lui associant une loi:

\begin{lstlisting}
data Z2 = O | I deriving(Eq,Show)

fois2 :: Z2 -> Z2 -> Z2
fois2 I I = I
fois2 _ _ = O
\end{lstlisting}





Est-ce que  ce magma est  associatif? Admet-il un  élément neutre? Y  a-t-il des
éléments simplifiables? Symétrisables?


Faites de même avec $\ofr{\bbz}{4\bbz}$.




Tout  ceci n'est  qu'un balbutiement!  Ce que  l'on vient  de faire  est un  peu
embêtant car on n'est pas sûr de l'associativité: on pourrait créer des monoïdes
qui n'en sont pas.

Peut-on changer notre mode de construction ? Haskell est là, ne vous inquiétez pas.

Considérons le type et les fonctions suivants:

\begin{lstlisting}
data Monoide a
    = Colle a (Monoide a)
    | Neutre

single :: a  -> Monoide a
single    el =  Colle el Neutre

op :: Monoide a -> Monoide a -> Monoide a
op    Neutre       el        =  el
op   (Colle h m)   el        =  Colle h (op m el)
\end{lstlisting}

Est-ce que \Colorbox{blue!10}{\lstinline{op}} est associative?

Est-ce que \Colorbox{blue!10}{\lstinline{Neutre}} est neutre?

Qui                  est                 \Colorbox{blue!10}{\lstinline{Neutre}},
\Colorbox{blue!10}{\lstinline{Colle}}  et \Colorbox{blue!10}{\lstinline{op}}  si
\Colorbox{blue!10}{\lstinline{Monoide a}} est \Colorbox{blue!10}{\lstinline{[a]}}?



\end{exercice}














 \begin{exercice}[Monoïdes: niveau 2...voire 3]
  On a remarqué que \Colorbox{blue!10}{\lstinline{elem}}, \Colorbox{blue!10}{\lstinline{sum}},
  \Colorbox{blue!10}{\lstinline{length}},  \Colorbox{blue!10}{\lstinline{map}},  \Colorbox{blue!10}{\lstinline{foldl}},  \Colorbox{blue!10}{\lstinline{filter}},
  etc. fonctionnaient toutes selon le même principe et que l'on avait tendance à
  se répéter un peu.

La lumière va venir de l'algèbre  et plus particulièrement des homomorphismes de
monoïdes (derrière se cache en fait la notion de \textit{catégorie}...).

Nous  remarquons en  effet  que  toutes ces  fonctions  sont  des morphismes  de
monoïde.

Soit \Colorbox{blue!10}{\lstinline{a}} notre type de base. Notons \lstinline{[a]} le type des listes d'éléments de
type  \Colorbox{blue!10}{\lstinline{a}}. Si  on munit  \Colorbox{blue!10}{\lstinline{[a]}} de  la concaténation  des
chaînes (que nous noterons \Colorbox{blue!10}{\lstinline{++}}), on obtient un
 monoïde dont l'élément neutre est la liste vide.

Considérons par exemple la fonction  \Colorbox{blue!10}{\lstinline{length}}. Elle est à valeurs dans
\Colorbox{blue!10}{\lstinline{Nat}}, le type  des entiers non signés, qui, muni  de l'addition, est
aussi un monoïde.

$$
\mathtt{length(lst1      ++      lst2)}      =      \mathtt{length(lst1)}      +
\mathtt{length(lst2)}\qquad \text{ et } \qquad \mathtt{length(Vide)}=0
$$


Pour  chaque  élément,  on  peut  considérer  la  fonction  $\  x\  →\  1$  dont
\Colorbox{blue!10}{\lstinline{length}}  est le  \og gonflement\fg{}  (une liste  ne contenant  qu'un
élément est de longueur 1).

On a donc le diagramme suivant:

$$
\begin{tikzcd}
\mathtt{a} \arrow{rr}{\text{injection canonique}} \arrow[swap]{dr}{\ x\ → \ 1}& & \mathtt{[a] (++,Vide)}\arrow{dl}{\mathtt{length}}\\
& \mathtt{Nat(+,0)} & 
\end{tikzcd}    
$$

L'injection canonique transforme un élément  quelconque en la liste constituée
de cet unique élément.

Cela  nous donne  alors  un  moyen d'imaginer  une  construction d'une  fonction
générale qui construira le morphisme en fonction  de la fonction de gauche et du
morphisme du bas.

\begin{lstlisting}
gonfle f loiMonoide neutreMonoide =
   {-
    crée le morphisme de monoïde entre [a] et b si b est un monoïde
    i.e.  gonfle la fonction f : a -> b en le morphisme f' : [a] -> b
    loiMonoide : b -> b -> b
    neutreMonoide : le neutre de b
    f traite les éléments, f' traite les listes de ces éléments
    f'([a])          = f(a)
    f'([as] ++ [as]) = f'([as]) `loiMonoide` f'([as])
    f'([])           = neutreMonoide
    ex:
    longueur = gonfle (\ x ->1) (+) 0
   -}
    ?????
\end{lstlisting}

Construisez cette fonction.

Tracez les diagrammes de \Colorbox{blue!10}{\lstinline{elem}}, \Colorbox{blue!10}{\lstinline{sum}},
    \Colorbox{blue!10}{\lstinline{map}},  \Colorbox{blue!10}{\lstinline{foldl}}, \Colorbox{blue!10}{\lstinline{filter}}  puis définissez-les
    sur Haskell à l'aide de la fonction \Colorbox{blue!10}{\lstinline{gonfle}}. 

Démontrez  par  récurrence  que  toute fonction  créée  avec  \Colorbox{blue!10}{\lstinline{gonfle}}
renvoie le morphisme de monoïde défini par le diagramme général: \textit{une preuve pour
les démontrer toutes...
}


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

  

 \end{exercice}



















\begin{exercice}
  On considère l'opération définie sur $\bbz$ par:
  $$a\top b = a + 2b$$
  Cette opération est-elle une LCI?  Est-elle commutative? Associative? Y a-t-il
  un élément neutre? Y a-t-il
  des éléments simplifiables? Symétrisables? 

Mêmes questions avec la loi définie sur $\bbq$ par $a\dagger b = (a+b)/2$.
\end{exercice}


\begin{exercice}
  On considère l'opération $\nand$ définie sur $\bbn_1$ par:
  $$ a\nand 1 = a,\quad a\nand b = a \times (a \nand (b-1))$$
  Cette opération vous  rappelle-t-elle quelque chose? Est-ce  une LCI? Est-elle
  commutative? Associative? etc.

Cherchez un élément régulier à droite mais pas à gauche.
\end{exercice}


\begin{exercice}
  On considère l'opération  de concaténation de listes dont  l'opérateur sur Haskell 
  est \Colorbox{blue!10}{\lstinline{++}}. Est-elle commutative? Associative?
\end{exercice}

\begin{exercice}
  A, B et C étant des ensembles, que pensez-vous de $A \cap B \cup C$?
\end{exercice}

\begin{exercice}
  Que  pensez-vous de  la soustraction  des  entiers? Du  produit cartésien  des
  ensembles? De la composition des  relations? De la multiplication d'un vecteur
  du plan par un réel? etc.
\end{exercice}



\begin{exercice}
  On définit une opération sur les quadruplets de nombres réels:
  $$\langle a,b,c,d\rangle \odot \langle \alpha,\beta,\gamma,\delta\rangle = \langle a\alpha + b\gamma,a\beta+b\delta,c\alpha+d\gamma,c\beta+d\delta\rangle$$
  Est-elle commutative? Associative? 
\end{exercice}


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



\begin{exercice}
  Soit  $A=\bigl\{a_1,a_2,...,a_p\bigr\}$ un  ensemble  de  caractères. On  note
  $A^\star$  l'ensemble  des chaînes  de  caractères  construites à  partir  des
  caractères de A.
  \begin{enumerate}
  \item $A^\star$ muni de la concaténation des chaînes a-t-il 
    une structure de magma associatif? de monoïde?
  \item  Les ensembles
    suivants munis de la
    concaténation sont-ils des magmas associatifs?  Des monoïdes?
    \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{enumerate}
\end{exercice}


\begin{exercice}
Soit $\bbb_2=\bigl\{0,1\bigr\}$ l'ensemble des  booléens. Est-ce que $\bbb_2$ muni
de NAND est un monoïde? Muni de NOR?
\end{exercice}



\begin{exercice}[Avec Haskell]
  Comme  nous  l'avons   fait  avec  les  magmas,  on  peut   créer  une  classe
  \Colorbox{blue!10}{\lstinline{Monoide}}  dérivant de  \Colorbox{blue!10}{\lstinline{Magma}} et  créer  les tests  qui vont  bien:
  \Colorbox{blue!10}{\lstinline{Just}} do it!
\end{exercice}

\begin{exercice}
  Soit l'opération  $\intercal$ définie  par $x\intercal y=  \sqrt{x^2+y^2}$. Est-ce
  que $\langle \bbr,\intercal\rangle
  $ est un magma associatif?  Un monoïde? Un monoïde simplifiable? Y a-t-il un élément absorbant?
\end{exercice}

\begin{exercice}
Soit une fonction $\FR(E)$ l'ensemble des fonctions de $E$ dans $E$.

On dit que  $f$ est inversible à  gauche s'il existe une fonction  $g$ telle que
$g\circ f= \mathrm{Id}_E$.

Montrez que $f$ inversible à gauche si,  et seulement si, $f$ est injective puis
que $f$ est inversible à droite si, et seulement si, $f$ est surjective.


\end{exercice}


\begin{exercice}[Curryfication, parenthèse et associativité]

On  considère  une fonction  

$$
 f\colon \begin{array}{rll} E\otimes F & \to & G\\
   \langle x,y\rangle & \mapsto & f(\langle x,y\rangle)
 \end{array}
 $$



Pour chaque $x$ de $E$, on peut donc définir une fonction $f_x$:

$$
f_x\colon \begin{array}{rll} F & \to & G\\
   y & \mapsto & f(\langle x,y\rangle)
 \end{array}
$$

Que pouvez-vous dire de la fonction: $\varphi : x \mapsto f_x$ (domaine, codomaine,lien avec $f$)?

Pouvez-vous, inversement, associer une fonction $f$ à une fonction du type $\varphi$?

Notons $C$ la fonction qui à une fonction $f$ de $E\otimes F$ dans $G$ associe la fonction $\varphi$ selon le mécanisme précédent.

Quelle est la signature de $C$? Quelle propriété intéressante possède $C$ concernant notre utilisation de Haskell ? 

On dit que $C(f)$ est la fonction currifiée de $f$

Ici, vous entamez un débat avec vos camarades et votre professeur au sujet de ces problèmes et vous les liez à votre cours :)

Notez pour finir que Haskell  a tout prévu...

\begin{lstlisting}
Prelude> :t curry
curry :: ((a, b) -> c) -> a -> b -> c
Prelude> :t uncurry
uncurry :: (a -> b -> c) -> (a, b) -> c
\end{lstlisting}

\end{exercice}




% \begin{exercice}[Notation polonaise]



% %\piccaption{Jan \textsc{\L ukasiewicz} \\ (1878-1956)}

%  \parpic{ \includegraphics[width=2.5cm]{lukasiewicz} }


% En   1920,   le   mathématicien-logicien-philosophe  polonais   Jan   \textsc{\L
%   ukasiewicz}  invente  la  notation  préfixée   alors  qu'il  est  ministre  de
% l'éducation (on a le droit de rêver...).

% 35 ans  plus tard, le philosophe  et informaticien (!) australien  (!!!) Charles
% \textsc{Hamblin} (1922 - 1985) s'en inspire.

% Il a en effet en sa possession  l'un des deux ordinateurs présents à l'époque en
% Australie. Il  se rend compte  que la saisie de  calculs avec les  opérateurs en
% notation  infixée  induit   de  nombreuses  erreurs  de  saisie   par  oubli  de
% parenthèses.  Il pense  aussi  à la  (très petite)  mémoire  des ordinateurs  de
% l'époque.

% % \end{minipage}
% % \setindent{0cm}

% %\piccaption{Charles \textsc{Hamblin} \\ (1922-1985)}
% \parpic[r]{ \includegraphics[width=2.5cm]{hamblin}}



% Il trouve alors  son inspiration dans le travail de  \textsc{\L ukasiewicz} pour
% éviter les parenthèses et il
%  pense à mettre les opérateurs en position préfixée:
% ainsi  il   introduit  la   notion  de   \textit{pile}  (ou   \textit{stack}  ou
% \textsc{Lifo}) qui économise le nombre d'adresses mémoire nécessaire.


% C'est  la  naissance de  la  Notation  Polonaise  Inversée  (NPI ou  RPN).  Elle
% économise également la taille des composants électroniques des portes logiques.

% Son seul inconvénient:  les mauvaises habitudes prises  d'utiliser des notations
% infixées.




% Un autre grand avantage: il faut comprendre le calcul avant de l'exécuter :)

% Ouvrez emacs  et tapez \Colorbox{blue!10}{\lstinline{M-x  calc RET}}.  Vous pouvez alors  faire n'importe
% quel  calcul  arithmétique  en  voyant chaque  résultat  intermédiaire  et  sans
% parenthèse.


% \begin{multicols}{2}
% Par exemple, la séquence
% %\begin{center}
%   \Colorbox{blue!10}{\lstinline{2 3 4 + *}}
% %\end{center}
% donne::

% \emacs


% \begin{lstlisting}
% --- Emacs Calculator Mode ---
% 3:  2
% 2:  3
% 1:  4
% --- Emacs Calculator Mode ---
% 2:  2
% 1:  7
% --- Emacs Calculator Mode ---
% 1:  14
% \end{lstlisting}

% Mais 
% %\begin{center}
%   \Colorbox{blue!10}{\lstinline{2 3 + 4 *}}
% %\end{center}
% donne:

% \begin{lstlisting}
% --- Emacs Calculator Mode ---
% 2:  2
% 1:  3
% --- Emacs Calculator Mode ---
% 2:  5
% 1:  4
% --- Emacs Calculator Mode ---
% 1:  20
%     .
% \end{lstlisting}
% \end{multicols}


% Que donne \Colorbox{blue!10}{\lstinline{10 4 3 + 2 * -}}?


% Entraînez-vous à passer de la notation infixe à la NPI et vice-versa. Donnez vos
% exemples à votre voisin(ne) à titre d'exercice.


% {\itshape
% En Haskell , une machine à calculer fonctionnant en NPI se programme en 5 lignes
% comme vous pourrez  le voir sur le  tutoriel \og apprendre Haskell  vous fera le
% plus grand bien\fg{}...
% }
% \haskell


% \end{exercice}






\begin{exercice}[En-tête IPV4]

Voici un en-tête IPV4:

\Colorbox{blue!10}{\lstinline{4500 003c 1c46 4000 4006 b1e6 ac10 0a63 ac10 0a0c}}

  Voici un extrait de l'article de Wikipedia consacré au protocole IPV4:

  \begin{quote}
{\itshape

Pour reconstituer l'information, on utilise les champs suivants dans l'en-tête IPv4 :
\begin{description}
\item[Version (4 bits)] : version d'IP utilisée. Ici, 4.
\item[Longueur de l'en-tête ou IHL (pour Internet Header Length) (4 bits)] : nombre de mots de 32 bits, soit 4 octets (ou nombre de lignes du schéma). La valeur est comprise entre 5 et 15, car il y a 20 octets minimum et on ne peut dépasser 40 octets d'option (soit en tout, 60 octets).
\item[Type de service ou ToS (pour Type of Service) (8 bits)] : ce champ permet de distinguer différentes qualité de service différenciant la manière dont les paquets sont traités. Composé de 3 bits de priorité (donc 8 niveaux) et trois indicateurs permettant de différencier le débit, le délai ou la fiabilité.
\item[Longueur totale en octets ou Total Length (16 bits)] : nombre total d'octets du datagramme, en-tête IP comprise. Donc, la valeur maximale est (216)-1 octets.
 \item[Identification (16 bits)] : numéro permettant d'identifier les fragments d'un même paquet.
 \item[Indicateurs ou Flags (3 bits)] :
\begin{enumerate}
   \item  actuellement inutilisé.
   \item  DF (Don't Fragment) : lorsque ce bit est positionné à 1, il indique que le paquet ne peut pas être fragmenté. Si le routeur ne peut acheminer ce paquet (taille du paquet supérieure à la MTU), il est alors rejeté.
    \item  MF (More Fragments) : quand ce bit est positionné à 1, on sait que ce paquet est un fragment de données et que d'autres doivent suivre. Quand il est à 0, soit le fragment est le dernier, soit le paquet n'a pas été fragmenté.
\end{enumerate}
    \item[Fragment offset (13 bits)] : position du fragment par rapport au paquet de départ, en nombre de mots de 8 octets.
    \item[Durée de vie ou TTL (pour Time To Live) (8 bits)] : initialisé par l'émetteur, ce champ est décrémenté d'une unité généralement à chaque saut de routeur. Quand TTL = 0, le paquet est abandonné et un message ICMP est envoyé à l'émetteur pour information.
    \item[Protocole (8 bits)] : numéro du protocole au-dessus de la couche réseau : TCP = 6, UDP = 17, ICMP = 1.
    \item[Somme de contrôle de l'en-tête ou Header Checksum (16 bits)] : complément à un de la somme complémentée à un de tout le contenu de l'en-tête afin de détecter les erreurs de transfert. Si la somme de contrôle est invalide, le paquet est abandonné sans message d'erreur.
    \item[Adresse source (32 bits)] : adresse IP de l'émetteur sur 32 bits.
    \item[Adresse destination (32 bits)] : adresse IP du récepteur 32 bits.
    \item[Options (0 à 40 octets par mots de 4 octets)] : facultatif.
    \item[Remplissage ou Padding] : de taille variable comprise entre 0 et 7 bits. Il permet de combler le champ option afin d'obtenir un en-tête IP multiple de 32 bits. La valeur des bits de bourrage est 0.
    \end{description}
  }
  \end{quote}

Créez sur Haskell  une fonction qui vérifie la somme de contrôle.

Par exemple:

\begin{lstlisting}
Ok, modules loaded: IPV4.
*IPV4> verifIPheader ["4500","003c","1c46","4000","4006","b1e6","ac10","0a63","ac10","0a0c"]
True
\end{lstlisting}


Vous   pourrez   utiliser   au   choix   les   fonction   \Colorbox{blue!10}{\lstinline{intToDigit}}   et
\Colorbox{blue!10}{\lstinline{digitToInt} du module \Colorbox{blue!10}{\lstinline{Data.Char}}.
\end{exercice}









%
\subsection{Groupes}
%



\begin{exercice}
\begin{enumerate}
\item   $\bbb_2$ muni des opérations suivantes est-il un groupe:

  \begin{multicols}{3}
    \begin{enumerate}
    \item $\land$? \item $\lor$? \item $\oplus$?
    \end{enumerate}
  \end{multicols}

\item Résoudre dans $\bbb_2$ l'équation $a\oplus x = b$.
\end{enumerate}
\end{exercice}

\begin{exercice}
  Soit $\langle G,\star\rangle $ un groupe et $a$ et $b$ deux éléments de $G$.  Exprimez
  l'inverse de $a\star b$ en fonction des inverses de $a$ et de $b$.
\end{exercice}






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

  \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        $\langle
  A,\star\rangle $ a une structure de groupe. Comparer ce groupe
  avec 
  \begin{itemize}
  \item                $\left\langle
      \ofr{\Z}{3\Z},\overline{+}\right\rangle
    $ 
  \item               $\left\langle              \bigl\{1,\mathrm{e}^{\ofr{2{\rm
            i}\pi}{3}},\mathrm{e}^{\ofr{-2{\rm i}\pi}{3}}\bigr\},\times\right\rangle$.
  \end{itemize} 
\end{exercice}



\begin{exercice}[Isomorphisme]
Montrez que $\langle \bbf_2,+\rangle $ et $\langle \ofr{\bbz}{4\bbz}^\star , \cdot\rangle $ sont isomorphes.

Est-ce que $\langle \ofr{\bbz}{4\bbz} , +\rangle $ et $\langle \ofr{\bbz}{5\bbz}^\star , \cdot\rangle $ sont
isomorphes?

Est-ce que $\langle \ofr{\bbz}{4\bbz} , +\rangle $ et $\langle \ofr{\bbz}{8\bbz}^\star , \cdot\rangle $ sont
isomorphes?

Est-ce que $\langle \bbf_2\otimes \bbf_2, +\rangle $ et $\langle \ofr{\bbz}{8\bbz}^\star , \cdot\rangle $ sont
isomorphes?
\end{exercice}




\begin{exercice}[Avec Haskell]
  Comme nous l'avons fait avec les magmas et les monoïdes, on peut créer une classe
  \Colorbox{blue!10}{\lstinline{Groupe}}  dérivant de  \Colorbox{blue!10}{\lstinline{Monoide}} et  créer  les tests  qui vont  bien:
  \Colorbox{blue!10}{\lstinline{Just}} do it!
\end{exercice}



\begin{exercice}[Déplacement à partir du pavé numérique]

À  chaque  touche  du  pavé  numérique,  on  fait  correspondre  un  déplacement
élémentaire d'un point  sur l'écran: 6 pour un déplacement  unitaire à droite, 2
pour un déplacement unitaire vers le bas, etc.

On  note $D$  l'ensemble  de  ces dix  déplacements  et  $D^\star$ l'ensemble  des
séquences de déplacements.

Définir $D^*$ comme un monoïde. Montrez que c'est un groupe abélien.
  

Que se passe-t-il si  au lieu de déplacements on considère  la trace laissée par
ces déplacements? 
\end{exercice}


\begin{exercice}[Caractérisation d'un sous-groupe]

La programmation, c'est l'efficacité... La définition d'un sous-groupe n'est pas
efficace: pouvez-vous en donner une caractérisation plus synthétique?
  
\end{exercice}







\begin{exercice}
 Est-ce que l'ensemble $\bigl\{x+y \sqrt{2} \mid (x,y)\in \bbq^2\bigr\}$ muni de
 la multiplication des réels a une structure de groupe?
\end{exercice}


% \begin{exercice}[Du CM1 à la 6\eme :-)]
  
% %\begin{figure}
% \begin{center}
%   \includegraphics[scale=1.1]{groupe_cm1}
% \end{center}
% %\end{figure}


% Adaptez le texte précédent aux notations introduites lors de l'étude des classes
% d'équivalence..

% Comment  généraliser les  résultats en  terme  de groupe?  (Attention, on  passe
% maintenant au programme de 6\eme des années 1970...)


% Nous en aurons besoin pour implémenter le calcul modulaire en Haskell ....


% \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,\cdot)$,
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}[7]$.
  \end{enumerate}
\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+chiffreAffine+:


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


\begin{lstlisting}
λ> chiffreAffine 17 22 "La maitresse en maillot de bain"
"*r6!r<9vW((W6W26!r<ooC96FW6$r<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}
λ> invMod 17 95
28
λ> invMod 25 95
*** Exception: 25 non inversible modulo 95
\end{lstlisting}

puis on décode:


\begin{lstlisting}
λ> dechiffreAffine 17 22 "*r6!r<9vW((W6W26!r<ooC96FW6$r<2"
"La maitresse en maillot de bain"
\end{lstlisting}


\end{exercice}



\begin{exercice}[Permutations]
\setindent{\indentationcours}
  \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}
\setindent{0cm}

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

\setindent{\indentationcours}
\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}
\setindent{0cm}

\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:
\setindent{\indentationcours}
\begin{definition}[Cryptosystème (ou système de chiffrement ou chiffre)]
Un  cryptosystème est  un quintuplet
$\langle \PR,\CR,\KR,\ER,\DR\rangle $ 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}
\setindent{0cm}

\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 [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]\label{exo::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   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  $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$. Quelle est l'opération arithmétique associée?
\item $c_j=m_j\oplus g_j$;
\item  $t_j=(2^rt_{j-1}+c_{j-1})   \modu  2^n$  (attention!   Il  faut
  travailler en base 2).
\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: démontrez-le!

\begin{enumerate}
\item Chiffrez \og \textit{ Papa is cool}\fg{} sachant que la clé est $k= 
  \begin{pmatrix}
    1&2&3&4\\
    4&1&3&2
  \end{pmatrix}
$, que $\ve{v_0}=0101$ et que $r=3$.


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



\begin{exercice}[ECB et CBC en Haskell]
Il ne reste plus qu'à programmer nos petites activités...Nous ne chercherons pas
à être  très efficaces : nous  nous contenterons d'une approche  naïve utilisant
les caractères ASCII.

\begin{enumerate}
\item Commencez par  écrire une fonction qui  convertit un entier en  base 10 en
  une liste de sept bits en base 2. Par exemple:

  \begin{lstlisting}
*CryptoSys> toBin 97
[1,1,0,0,0,0,1]
*CryptoSys> toBin 15
[0,0,0,1,1,1,1]
*CryptoSys> toBin 1
[0,0,0,0,0,0,1]
  \end{lstlisting}

\item Créez  une fonction réciproque  qui convertit une chaîne  de 7 bits  en un
  entier en base 10:

  \begin{lstlisting}
*CryptoSys> toDec [0,0,0,1,1,0,1]
13
*CryptoSys> toDec [1,1,1,1,1,1,1]
127
  \end{lstlisting}

\item Nous utiliserons un codage adapté à nos besoins. Les codes ASCII
 sont accessibles  via les
  fonctions \Colorbox{blue!10}{\lstinline{chr}} et \Colorbox{blue!10}{\lstinline{ord}} de la bibliothèque \Colorbox{blue!10}{\lstinline{Data.Char}}.

On prendra comme alias \Colorbox{blue!10}{\lstinline{C}} pour cette bibliothèque:

\begin{lstlisting}
import qualified Data.Char as C
\end{lstlisting}

Par exemple:

\begin{lstlisting}
*CryptoSys> map C.chr [0..127]
"\NUL\SOH\STX\ETX\EOT\ENQ\ACK\a\b\t\n\v\f\r\SO\SI\DLE\DC1\DC2\DC3\DC4\NAK\SYN\ETB\CAN\EM\SUB\ESC\FS
\GS\RS\US !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvw
xyz{|}~\DEL"
\end{lstlisting}

Au-delà, c'est moins drôle:

\begin{lstlisting}
*CryptoSys> map C.chr [128 .. 140]
"\128\129\130\131\132\133\134\135\136\137\138\139\140"
\end{lstlisting}

Mais  on  peut  avoir  une  sortie   correspondant  à  l'UTF8  via  la  fonction
\Colorbox{blue!10}{\lstinline{putStrLn}} qui a une signature un peu étrange:

\begin{lstlisting}
*CryptoSys> :t putStrLn
putStrLn :: String -> IO ()
\end{lstlisting}

et qui n'est pas trop explicable à notre niveau. Disons que \Colorbox{blue!10}{\lstinline{IO}} est ce qui
correspond aux entrées/sorties en Haskell.

Mais   il  faut   passer  une   option   au  compilateur.   Or  nous   utilisons
GHCi... Heureusement,  il existe un  moyen pour passer une  option à GHC  via le
fichier d'extension hs. Il faut mettre en en-tête du fichier:

\begin{lstlisting}
{-# LANGUAGE OverloadedStrings #-}
\end{lstlisting}


Alors, par exemple:

\begin{lstlisting}
*CryptoSys> C.ord 'à'
224
*CryptoSys> C.chr 224
'\224'
*CryptoSys> putStrLn [C.chr 224]
à
\end{lstlisting}

Pour  faciliter   notre  tâche,  nous  allons   \og  \textit{remapper}\fg{}  nos
caractères  accentués et  écraser  les touches  d'actions  correspondant aux  32
premiers codes ASCII.

\begin{lstlisting}
chr 0  = 'à'
chr 1  = 'â'
chr 2  = 'é'
chr 3  = 'è'
chr 4  = 'ê'
chr 5  = 'ë'
chr 6  = 'î'
chr 7  = 'ï'
chr 8  = 'ô'

...

ord  'à' = 0
ord  'â' = 1
ord  'é' = 2
ord  'è' = 3
ord  'ê' = 4
ord  'ë' = 5
ord  'î' = 6
ord  'ï' = 7
ord  'ô' = 8 

...
\end{lstlisting}

Maintenant:

\begin{lstlisting}
*CryptoSys> ord 'à'
0
*CryptoSys> chr 0
'\224'
*CryptoSys> putStrLn [chr 0]
à
\end{lstlisting}

ce qui  va faciliter  notre travail  : on  se limitera  à 7  bits mais  avec les
caractères qui nous intéressent.


\item  Créez  une  fonction  \Colorbox{blue!10}{\lstinline{stringToBin}}  qui  convertit  une  chaîne  de
  caractère en la liste  des chaînes de 7 bits des caractères
  qui la composent. Par exemple:

  \begin{lstlisting}
*CryptoSys> stringToBin "Aïe"
[[1,0,0,0,0,0,1],[0,0,0,0,1,1,1],[1,1,0,0,1,0,1]]
  \end{lstlisting}

\item Il faut maintenant s'occuper des permutations.

Une permutation sera tout simplement une fonction de signature \Colorbox{blue!10}{\lstinline{Int -> Int}}

\begin{lstlisting}
*CryptoSys> per 4
2
*CryptoSys> per 8
*** Exception: Non_defini
\end{lstlisting}

On définira ensuite une fonction \Colorbox{blue!10}{\lstinline{permBits}} qui prend en argument une liste
et renvoie la liste permutée:

\begin{lstlisting}
*CryptoSys> permBits per ['a'..'g']
"cadbfeg"
\end{lstlisting}

avec \Colorbox{blue!10}{\lstinline{per}} désignant la permutation introduite dans l'exercice \vref{exo::ecb}.


\item Il  ne reste  plus qu'à créer  une fonction \Colorbox{blue!10}{\lstinline{ecb}}  qui va  crypter un
  message selon le cryptosystème ECB:

  \begin{lstlisting}
*CryptoSys> ecb per "maman"
";);)>"
  \end{lstlisting}

On utilisera les fonctions précédentes et l'incontournable \Colorbox{blue!10}{\lstinline{map}}.

Comment déchiffrer \Colorbox{blue!10}{\lstinline{";);)>"}} connaissant la clé?

\item Un peu plus sportif: le CBC...

On commencera par créer une fonction \Colorbox{blue!10}{\lstinline{xor}}:

\begin{lstlisting}
*CryptoSys> xor 1 1
0
*CryptoSys> xor 1 0
1
\end{lstlisting}

On s'occupera ensuite de la fonction de déchiffrement qui est un peu plus simple
à écrire. On utilisera à bon escient les fonctions \Colorbox{blue!10}{\lstinline{zipWith}}, \Colorbox{blue!10}{\lstinline{map}} et
\Colorbox{blue!10}{\lstinline{init}}.

\begin{lstlisting}
*CryptoSys> putStrLn (cbc_decrypt iper [1,0,1,0,1,0,1] "Papa")
Mâ9!
*CryptoSys> putStrLn (cbc_decrypt iper [1,0,1,0,1,0,1] "Père")
MU_!
\end{lstlisting}

Pour le chiffrement, on pourra utiliser \Colorbox{blue!10}{\lstinline{foldl}} et \Colorbox{blue!10}{\lstinline{reverse}}.

\begin{lstlisting}
*CryptoSys> putStrLn (cbc_crypt per [1,0,1,0,1,0,1] "Maman")
PIù=e
*CryptoSys> putStrLn (cbc_crypt per [1,0,1,0,1,0,1] "Mâ9!")
Papa
\end{lstlisting}



\item Comment expliquer le phénomène suivant:

  \begin{lstlisting}
*CryptoSys> putStrLn $ (cbc_crypt per [1,0,1,0,1,0,1] "aaaaaaaaaaaaaaaaaaaaaaaa")
JÇzUJÇzUJÇzUJÇzUJÇzUJÇzU
  \end{lstlisting}





\end{enumerate}

\end{exercice}



\begin{exercice}[\textsc{Hamilton} et les couples]
  
Le  mathématicien irlandais  William Rowan  \textsc{Hamilton}  (1805-1865) publie en
1837    \textit{Theory   of    Conjugate    Functions,   or    Algebraic
  Couples}                                                    :
   (\href{http://www.maths.tcd.ie/pub/HistMath/People/Hamilton/PureTime/PureTime.pdf}{http://www.maths.tcd.ie/pub/HistMath/People/Hamilton/PureTime/PureTime.pdf}).


En voici un extrait:


\begin{quote}
  {\itshape\small

\begin{center}
On the Addition, Substraction, Multiplication, and Division, of
Number-Couples, as
combined with each other.
\end{center}

%\nobreak\bigskip
6.
Proceeding to operations upon number-couples, considered in
combination with each other, it is easy now to see the
reasonableness of the following definitions, and even their
necessity, if we would preserve in the simplest way, the analogy
of the theory of couples to the theory of singles:
$$\langle b_1, b_2\rangle  + \langle a_1, a_2\rangle  = \langle b_1 + a_1, b_2 + a_2\rangle ;
   \eqno ( 52.)$$
$$\langle b_1, b_2\rangle  - \langle a_1, a_2\rangle  = \langle b_1 - a_1, b_2 - a_2\rangle ;
   \eqno (53.)$$
$$\langle b_1, b_2\rangle  \langle a_1, a_2\rangle 
    = \langle b_1, b_2\rangle  \cdot \langle a_1, a_2\rangle 
    = \langle b_1 a_1 - b_2 a_2, b_2 a_1 + b_1 a_2\rangle ;
   \eqno (54.)$$
$${\langle b_1, b_2\rangle  \over \langle a_1, a_2\rangle }
    = \left\langle 
         {b_1 a_1 + b_2 a_2 \over a_1^2 + a_2^2}, \,
         {b_2 a_1 - b_1 a_2 \over a_1^2 + a_2^2}
      \right\rangle .
   \eqno (55.)$$
Were these definitions even altogether arbitrary, they would at
least not contradict each other, nor the earlier principles of
Algebra, and it would be possible to draw legitimate conclusions,
by rigorous mathematical reasoning, from premises thus
arbitrarily assumed: but the persons who have read with attention
the foregoing remarks of this theory, and have compared them with
the Preliminary Essay, will see that these definitions are really
{\it not arbitrarily chosen}, and that though others might have
been assumed, no others would be equally proper.

With these definitions, addition and subtraction of
number-couples are mutually inverse operations, and so are
multiplication and division; and we have the relations,
$$\langle b_1, b_2\rangle  + \langle a_1, a_2\rangle  = \langle a_1, a_2\rangle  + \langle b_1, b_2\rangle ,
   \eqno (56.)$$
$$\langle b_1, b_2\rangle  \cdot \langle a_1, a_2\rangle  = \langle a_1, a_2\rangle  \cdot \langle b_1, b_2\rangle ,
   \eqno (57.)$$
$$\langle b_1, b_2\rangle  ( \langle a_1', a_2'\rangle  + \langle a_1, a_2\rangle  )
   =  \langle b_1, b_2\rangle  \langle a_1', a_2'\rangle  + \langle b_1, b_2\rangle  \langle a_1, a_2\rangle :
   \eqno (58.)$$
we may, therefore, extend to number-couples all those results
respecting numbers, which have been deduced from principles
corresponding to these last relations.  For example,



$( \langle b_1, b_2\rangle  + \langle a_1, a_2\rangle  ) \cdot
  ( \langle b_1, b_2\rangle  + \langle a_1, a_2\rangle  )
   =  \langle b_1, b_2\rangle  \langle b_1, b_2\rangle 
    + 2 \langle b_1, b_2\rangle  \langle a_1, a_2\rangle \\
    + \langle a_1, a_2\rangle  \langle a_1, a_2\rangle ,
   \hfill (59.)$


in which


$$2 \langle b_1, b_2\rangle  \langle a_1, a_2\rangle 
   =  \langle 2, 0\rangle  \langle b_1, b_2\rangle  \langle a_1, a_2\rangle 
   =  \langle b_1, b_2\rangle  \langle a_1, a_2\rangle  + \langle b_1, b_2\rangle  \langle a_1, a_2\rangle ;
   \eqno (60.)$$
for, in general, we may {\it mix the signs of numbers with those
of number-couples}, if we consider every single number~$a$ as
equivalent to a pure primary number-couple,
$$a = \langle a, 0\rangle .
   \eqno (61.) $$
When the pure primary couple $\langle 1, 0\rangle $ is thus considered as
equivalent to the number~$1$, it may be called, for shortness,
the {\it primary unit\/}; and the pure secondary couple $\langle 0, 1\rangle $
may be called in like manner the {\it secondary unit}.

We may also agree to write, by analogy to notations already
explained,


\begin{eqnarray*}
  \langle 0, 0\rangle  + \langle a_1, a_2\rangle  &=& + \langle a_1, a_2\rangle ,\\
\langle 0, 0\rangle  - \langle a_1, a_2\rangle  &=& - \langle a_1, a_2\rangle ;
   \quad (62.)\\
\end{eqnarray*}


and then $+ \langle a_1, a_2\rangle $ will be another symbol for the
number-couple $\langle a_1, a_2\rangle $ itself, and $- \langle a_1, a_2\rangle $ will be a
symbol for the {\it opposite number-couple\/} $\langle - a_1, - a_2\rangle $.
The {\it reciprocal\/} of a number-couple $\langle a_1, a_2\rangle $ is this
other number-couple,
$${1 \over \langle a_1, a_2\rangle }
   =  {\langle 1, 0\rangle  \over \langle a_1, a_2\rangle }
   =  \left\langle 
         {a_1 \over a_1^2 + a_2^2},
         {- a_2 \over a_1^2 + a_2^2}
      \right\rangle 
   =  {\langle a_1, - a_2\rangle  \over a_1^2 + a_2^2}.
   \eqno (63.)$$
It need scarcely be mentioned that the insertion of the sign of
coincidence~$=$ between any two number-couples implies that those
two couples coincide, number with number, primary with primary,
and secondary with secondary; so that {\it an equation between
number-couples is equivalent to a couple of equations between
numbers}.

}
\end{quote}


Vous ferez de ce texte un commentaire composé :)




\end{exercice}





\begin{exercice}[\textsc{Hamilton} is back : ze quaternions]


\parpic{\includegraphics[width=7cm]{hamilton}}
Après avoir  travaillé, comme nous  l'avons vu,  sur les nombres  complexes, Sir
William (il a été anobli en 1835) voulut étendre ses travaux à la dimension 3. 
Il n'arrivait cependant pas à  imaginer une multiplication qui puisse satisfaire
des critères intéressants, notamment la conservation des normes.\\
Un  jour qu'il  se promenait  avec son  épouse dans  un parc  dublinois, il  eut
soudain un  éclair qu'il  s'empressa de  graver sur  la pierre  du pont  le plus
proche :

$${\rm i}^2 = {\rm j}^2={\rm k}^2= {\rm ijk} = -1$$

Remplissez alors la table de multiplication suivante:

\begin{center}
  \begin{tabularx}{0.4\linewidth}{Y{3}}
    \whline
    $\times$ & 1 & i & j & k \\
    \whline
    1        &  &  &  &  \\
    \hline
    i        &  &  &  &  \\
    \hline
    j        &  &  &  &   \\
    \hline
    k        &  &  &  &   \\
    \whline
  \end{tabularx}
\end{center}


\textsc{Hamilton} définit alors  un \textit{quaternion} par la  donnée de quatre
réels $a$,  $b$, $c$ et  $d$ car un quaternion  peut s'écrire de  manière unique
comme combinaison des quatre quaternions élémentaires:

$$q = a1 + b{\rm i} + c{\rm j} + d{\rm k}$$

Le nombre  $a$ est  la partie  scalaire et  le triplet  $(b,c,d)$ est  la partie
vectorielle  (c'est \textsc{Hamilton}  qui  a  en effet  introduit  le terme  de
\textit{vecteur} en mathématique).

Quelles propriétés possède ou ne possède pas la multiplication des quaternions?


{\itshape
  Il y a énormément  de choses à dire sur les quaternions  mais nous manquons un
  peu de recul mathématique...

  Point  de vue  informatique, il  faut  cependant noter  qu'ils sont  largement
  utilisés  en  infographie,  en  traitement  du signal  et  dans  tout  domaine
  utilisant des rotations et entraînant de nombreux calculs. 

  En  physique,  ces  calculs  sont traditionnellement  traités  par  du  calcul
  matriciel mais nous verrons bientôt  que celui-ci induit de nombreuses erreurs
  d'arrondis qui peuvent être atténuées en passant par les quaternions.


  Un site  à visiter :  \href{http://www.alcys.com/}{http://www.alcys.com/}. Les
  quaternions  apparaissent  sous  vos   yeux  ébaubis....
}


\end{exercice}



\subsection{Anneaux et corps}

\begin{exercice}[C'est fini]
  Soit $E=\bigl\{1,2,3,5,6,10,15,30\bigr\}$.

Pour tout couple $\langle a,b\rangle$ d'éléments de $E$, on note $a\wedge b$ le PGCD de $a$ et $b$ et $a\vee b$
le PPCM de $a$ et $b$. 

Quelle est la  structure de $\langle
E,\wedge,\vee\rangle $?  De $\langle
E,\vee,\wedge\rangle $?
\end{exercice}


\begin{exercice}[Les Bool]
Quelle    structure     possède    $
\left\langle \bigl\{\Colorbox{blue!10}{\lstinline{True}} ,
  \Colorbox{blue!10}{\lstinline{False}}\bigr\},\land,\lor\right\rangle $ ? Et $ \left\langle\bigl\{\Colorbox{blue!10}{\lstinline{True}} ,
  \Colorbox{blue!10}{\lstinline{False}}\bigr\},\lor,\land\right\rangle $
\end{exercice}

\begin{exercice}[Les parties]
  Soit $E$ un ensemble. Quelle structure possède $ \left\langle\PR(E),\cap,\cup\right\rangle 
$? $ \left\langle\PR(E),\cup,\cap\right\rangle 
$? 
\end{exercice} 






\begin{exercice}[Corps finis]

  On considère la relation définie sur $\bbz$:
$x\equiv_n y \Leftrightarrow x  \text{ et } y \text{ ont le  même reste dans la
  division par } n$.

Montrez qu'il s'agit d'une relation d'équivalence.

On appelle  classe de $x$  modulo $n$ l'ensemble  des nombres équivalents  à $y$
modulo $n$. 

Combien y a-t-il de classes modulo 3? Modulo 4? Modulo 5? Révisons le cours de CM1...

%\setindent{0cm}
\begin{multicols}{2}
%\begin{figure}
\begin{center}
  \includegraphics[scale=0.75]{classe1}
\end{center}
%\end{figure}


%\begin{figure}
\begin{center}
  \includegraphics[scale=0.75]{classe2}
\end{center}
%\end{figure}
\end{multicols}



On  note  $\bbz/n\bbz$  l'ensemble  des  classes  modulo  $n$  (on  parle  aussi
d'ensemble quotient de la relation d'équivalence).

Étudiez la structure de $\langle \bbz/n\bbz, +_n,\times_n\rangle$.

\end{exercice}
















\begin{exercice}[Un type Rationnel sur Haskell]
 Qu'est-ce qu'un  rationnel? \textit{Ratio}  est un mot  latin, qui  désignait un
 calcul  mais  qui   a  donné  en  français  le  mot   \textit{raison}.  Le  mot
 \textit{ratio} est passé en anglais pour désigner un indice en comptabilité: le
 rapport entre deux quantités de même nature.
 Ce mot a été importé de l'anglais de spécialité par les financiers.

 En mathématique, un \textit{nombre rationnel} est \og \textbf{construit}\fg{} à partir d'un couple d'entiers
 relatifs, le deuxième étant non nul.  
 Le premier est appelé \textit{numérateur}, le second \textit{dénominateur}.
 
 Oui  mais  comment  s'effectue  cette  \og construction\fg{}?  On  a  une  idée
 intuitive  de  la réponse:  on  veut  qu'un \textit{ratio}nnel  représente  une
 proportion. Par exemple, si  Daniel a 5 billes bleues parmi ses  8 billes et si
 Fabienne a 10 billes  bleues parmi ses 16 billes, les deux  enfants ont la même
 proportion  de billes  bleues.  On  voudrait alors  que  cette proportion  soit
 désignée par le même nombre rationnel.

On voudrait donc  mettre en \textit{relation} tous les  couples $\langle$ nombre
de billes bleues, nombre total de  billes $\rangle$ qui \og représentent\fg{} la
même proportion de billes bleues.

On va donc modéliser cela en considérant la relation:

$$                 \Big(\forall                  \langle                 a,b\rangle{}
\in\bbz\otimes(\bbz\setminus\left\{0\right\})\Big)\Big(\forall    \langle    c,d\rangle{}
\in\bbz\otimes(\bbz\setminus\left\{0\right\})\Big)\Big(        \langle        a,b\rangle
\,\mathcal{R}\,\langle c,d\rangle \lequiv ad=bc\Big) $$


Il est facile de vérifier que $\RR$ est une relation d'équivalence.

Une proportion est alors une classe modulo cette relation d'équivalence.


 On désigne par $\bbq$ l'ensemble quotient de $\bbz\otimes (\bbz\setminus\{0\})$
 modulo $\RR$.

 Cette notation a été
 introduite par  le mathématicien  italien Guiseppe  \textsc{Peano} en  1895 car
 c'est l'initiale du mot italien \og \textit{quoziente}\fg{}.

 $$ \bbq = \ofr{\bbz\otimes (\bbz\setminus\{0\})}{\RR} =
 \bigl\{\big[\langle n, d\rangle\big]_\RR\ |\ \langle n, d\rangle \in \bbz\otimes
 (\bbz\setminus\{0\}) \bigr\}$$

Un nombre rationnel est donc une classe d'équivalence, c'est-à-dire un ensemble!!!


 Sur  Haskell ,  on  pourrait  garder  telle quelle  cette  idée  et  construire  les
 rationnels à  partir d'ensembles  infinis, mais  c'est informatiquement  un peu
 dangereux.

 On va plutôt adapter cette idée en commençant par \textit{construire} un rationnel à partir d'un
 couple $\langle$ \Colorbox{blue!10}{\lstinline{Integer}}, \Colorbox{blue!10}{\lstinline{integer}} $\rangle$. 

Pour ne pas  trop perturber nos habitudes, nous allons  utiliser un constructeur
infixe:

\begin{lstlisting}
data Rationnel =  Integer :/ Integer
\end{lstlisting}

Ici, \Colorbox{blue!10}{\lstinline{:/}} est le \textit{constructeur}  du type \Colorbox{blue!10}{\lstinline{Rationnel}}: c'est en
fait une fonction (bien sûr !!):

\begin{lstlisting}
Prelude> :t (:/)
(:/) :: Integer -> Integer -> Rationnel
\end{lstlisting}


 On  aura  souvent besoin  d'utiliser  le  numérateur  ou le  dénominateur  d'un
 rationnel.  

Remarquons tout d'abord que dans chaque classe, il y a un élément plus intéressant que les autres:
lequel? Comment l'obtenir? Comment pensez-vous définir le signe d'un rationnel?




On va donc créer deux fonctions \Colorbox{blue!10}{\lstinline{num}} et
\Colorbox{blue!10}{\lstinline{den}} qui, pour un rationnel donné, vont renvoyer le numérateur et le
dénominateur simplifiés.



Ainsi, on voudrait que le numérateur de \Colorbox{blue!10}{\lstinline{10 :/ 8}} soit 5
et son numérateur soit...?

On dispose de quelques fonctions  utiles définies dans la classe \Colorbox{blue!10}{\lstinline{Integral}}
dont voici un extrait de la documentation:

\begin{lstlisting}
Integral numbers, supporting integer division.

Methods

quot :: a -> a -> a
  integer division truncated toward zero

rem :: a -> a -> a
  integer remainder, satisfying (x `quot` y)*y + (x `rem` y) == x

div :: a -> a -> a
  integer division truncated toward negative infinity

mod :: a -> a -> a
  integer modulus, satisfying (x `div` y)*y + (x `mod` y) == x

quotRem :: a -> a -> (a, a)
  simultaneous quot and rem

divMod :: a -> a -> (a, a)
  simultaneous div and mod

toInteger :: a -> Integer
  conversion to Integer 
\end{lstlisting}

\Colorbox{blue!10}{\lstinline{Prelude}} dispose également de la fonction suivante:

\begin{lstlisting}
gcd             :: (Integral a) => a -> a -> a
gcd x y         =  gcd' (abs x) (abs y)
                   where gcd' a 0  =  a
                         gcd' a b  =  gcd' b (a `rem` b)
\end{lstlisting}


Complétez alors les pointillés:

\begin{lstlisting}
num :: Rationnel -> Integer 
num    (x :/ 0)  = error "divide by zero"
num    (x :/ y)  = (...) * (...)


den :: Rationnel -> Integer 
den    (x :/ 0)  = error "divide by zero"
den    (x :/ y)  = ... (...)
\end{lstlisting}

Par exemple, désignons par \Colorbox{blue!10}{\lstinline{x}} le rationnel $\langle 5,3,\rangle$:

\begin{lstlisting}
Prelude> let x = 10 :/ 8
Prelude> num x
5
Prelude> den x
4
\end{lstlisting}


Cependant, on  est un  peu embêté si  l'on veut savoir  si deux  rationnels sont
égaux, c'est-à-dire deux classes d'équivalence sont égales:

\begin{lstlisting}
Prelude> let x = 10 :/ 8
Prelude> let y = 20 :/ 16
Prelude> x == y

<interactive>:31:3:
    No instance for (Eq Rationnel)
      arising from a use of `=='
    Possible fix: add an instance declaration for (Eq Rationnel)
    In the expression: x == y
    In an equation for `it': it = x == y
\end{lstlisting}

Le débugueur de Haskell   a été conçu par des gens  tellement intelligents et gentils
qu'il nous  explique comment  faire: on  va faire  du type  \Colorbox{blue!10}{\lstinline{Rationnel}} une
\textit{instance} de la classe de type \Colorbox{blue!10}{\lstinline{Eq}} qui contient tous les types
qui sont des classes d'équivalence.

\begin{lstlisting}
Prelude> :t (==)
(==) :: Eq a => a -> a -> Bool
\end{lstlisting}

Pour cela, on utilise la fonction \Colorbox{blue!10}{\lstinline{instance}}:


\begin{lstlisting}
instance Eq Rationnel where
   f1 == f2 = (num f1) * (den f2) == (den f1) * (num f2)
\end{lstlisting}

Maintenant, on peut tester si deux rationnels sont égaux ou non:

\begin{lstlisting}
Prelude> 10 :/ 8 == 20 :/ 16
True
\end{lstlisting}

Pour  améliorer notre  confort  d'utilisation  de GHCi,  nous  allons créer  une
fonction  d'affichage  des rationnels  (un  \og  \textit{pretty print}\fg{})  et
instancier   \Colorbox{blue!10}{\lstinline{Rationnel}}  dans   la  classe   \Colorbox{blue!10}{\lstinline{Show}}  des   types  \og
montrables\fg{}...


\begin{lstlisting}
instance Show Rationnel where
  show f  
     |den f == 0 = error "divide by zero" 
     |den f == 1 = show (num f) 
     |otherwise  = (show (num f)) ++ "/" ++ (show (den f))
\end{lstlisting}

Par exemple:

\begin{lstlisting}
λ> 10 :/ (-8)
-5/4
λ> 10 :/ (-5)
-2
\end{lstlisting}


Il ne reste plus qu'à donner une structure algébrique à \Colorbox{blue!10}{\lstinline{Rationnel}}: est-ce
que $\langle \bbq,+,\times\rangle$ a une structure d'anneau? De corps?

Commençons par la structure d'anneau.

Il faut définir une addition et une multiplication: complétez les pointillés...

\begin{lstlisting}
r_plus :: Rationnel -> Rationnel -> Rationnel
r_plus    f1           f2        =  ... :/ ...

r_mult :: Rationnel -> Rationnel -> Rationnel
r_mult    f1           f2        =  ... :/ ...
\end{lstlisting}

Nous pouvons à présent faire de \Colorbox{blue!10}{\lstinline{Rationnel}} une instance de \Colorbox{blue!10}{\lstinline{Num}}

Comme évoqué en cours, il nous faut donc définir le sept fonctions de la classe \Colorbox{blue!10}{\lstinline{Num}}

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

avec \Colorbox{blue!10}{\lstinline{a}} notre type \Colorbox{blue!10}{\lstinline{Rationnel}} pour que celui-ci en fasse partie.

Complétez alors les pointillés:

\begin{lstlisting}
instance Num Rationnel where
  (+) = ...
  (*) = ...
  negate f =  ... :/ ...
  fromInteger k = ... :/ ...
  abs f = ... :/ ...
  signum f = ... :/ ...
\end{lstlisting}

Alors, par exemple:

\begin{lstlisting}
λ> 5 :/ 3 + 1 :/ 2
13/6
λ> 5 :/ 3 - 1 :/ 2
7/6
λ> 5 :/ 3 * 1 :/ 2
5/6
\end{lstlisting}

Bon, que pensez-vous de l'inverse d'un \Colorbox{blue!10}{\lstinline{Rationnel}}?

\begin{lstlisting}
r_inv :: Rationnel -> Rationnel
r_inv f
  |num f == 0 = ...
  |otherwise  = ...
\end{lstlisting}

On peut donc instancier \Colorbox{blue!10}{\lstinline{Fractional}} avec notre \Colorbox{blue!10}{\lstinline{Rationnel}}:

\begin{lstlisting}
instance Fractional Rationnel where
  (/) f1 f2 = ...
  fromRational r = (Ratio.numerator r) :/ (Ratio.denominator r)
\end{lstlisting}

La dernière ligne est un peu bizarre: en fait, il existe déjà dans \Colorbox{blue!10}{\lstinline{Prelude}} un type pour les rationnels...
Cette ligne permet donc de passer d'un \Colorbox{blue!10}{\lstinline{Rational}} de \Colorbox{blue!10}{\lstinline{Prelude}} à un élément de type \Colorbox{blue!10}{\lstinline{Rationnel}}.

\begin{lstlisting}
λ> (5 :/ 3) / (7 :/ 6)
10/7
\end{lstlisting}

Reprenons  maintenant nos  classes \Colorbox{blue!10}{\lstinline{Magma}},  \Colorbox{blue!10}{\lstinline{Monoide}}, \Colorbox{blue!10}{\lstinline{Groupe}}:
qu'elles nous  inspirent pour  créer des  classes \Colorbox{blue!10}{\lstinline{Anneau}}  et \Colorbox{blue!10}{\lstinline{Corps}}
avec les  tests qui vont avec.  Est-ce qu'on peut faire  de \Colorbox{blue!10}{\lstinline{Rationnel}} une
instance de \Colorbox{blue!10}{\lstinline{Anneau}}?  De \Colorbox{blue!10}{\lstinline{Corps}}?


\end{exercice}



\begin{exercice}[Anneau des booléens]
  Pouvez-vous   faire   de   \Colorbox{blue!10}{\lstinline{Bool}}   une  instance   de   \Colorbox{blue!10}{\lstinline{Num}}?   de
  \Colorbox{blue!10}{\lstinline{Fractional}}? de \Colorbox{blue!10}{\lstinline{Groupe}}? de \Colorbox{blue!10}{\lstinline{Anneau}}? de \Colorbox{blue!10}{\lstinline{Corps}}?
\end{exercice}





\subsection{Espaces vectoriels}


\begin{exercice}[Les canons]
  Montrez que $\bbk^n$ a une structure de $\bbk-$espace vectoriel.

Comment  organiseriez-vous,   de  manière   très  informelle,  une   classe  \og
$\bbk-EV$ \fg{}?

Il sera utile, surtout pour des informaticiens, de garder cette image en tête.
\end{exercice}



\begin{exercice}
On travaille dans $\bbk^3$ considéré comme $\bbk$-espace vectoriel muni des lois canoniques.

Résolvez dans $\bbr^3$ puis dans $\bbf_2^3$ l'équation:

$$\langle  2,-3,4\rangle =  x\langle 1,1,1\rangle  + y\langle  1,1,0\rangle +  z
\langle 1,0,0\rangle $$ 
\end{exercice}


\begin{exercice}[RVB/CJMN]
  Comment  modéliseriez-vous  les  systèmes  RVB   et  CJMN  en  terme  d'espace
  vectoriel?

  Comment passer en niveau de gris ? En codage 24 bits ?
\end{exercice}



\begin{exercice}[A bit of dice]
On voudrait dessiner ce dé:
\drawdie{8}


Pour cela, on dispose de 6 dés un peu spéciaux:

\drawdie{1}
\drawdie{2}
\drawdie{3}
\drawdie{4}
\drawdie{5}
\drawdie{6}


On peut les additionner selon la  règle suivante: on superpose les dés
et un  point apparaît  si, et seulement  si, un et  un seul  point est
présent par position.

En fait, le  jeu est constitué de  petites lumières. Quand on appuie  sur une de
ces lumières, cela change l'état (allumé  ou éteint) des lumières voisines. Quel
lien y a-t-il entre la situation réelle et la modélisation proposée?

Par exemple, 1\drawdie{1} + 1\drawdie{2}=\fancydie{0}{0}{1}{1}{0}{0}

Quel  est le  rapport avec  notre cours?  Dessinez le  dé demandé.  Et
celui-ci \drawdie{7}? Et celui-là \fancydie{1}{0}{0}{0}{0}{0}?

Pour aller plus loin, aller jouer au \textit{Lights Out} : \href{http://www.jaapsch.net/puzzles/lights.htm}{http://www.jaapsch.net/puzzles/lights.htm}


Pourra-t-on  résoudre  toutes  les  énigmes? Est-ce  qu'il  est  vraiment  utile
d'appuyer sur certaines touches?

\end{exercice}

\begin{exercice}[Espaces vectoriels pour les nuls]

Avec les notations usuelles, que pensez-vous des égalités suivantes:

\begin{enumerate}
\item $0_\oplus \cdot \mathbf{u} =\mathbf{0}$
\item $λ\cdot \mathbf{0}=\mathbf{0}$
\item $(λ\cdot \mathbf{u} = \mathbf{0})\limp (λ=0 \lor \mathbf{u}=\mathbf{0})$
\end{enumerate}

  


\begin{exercice}
 Démontrez le  théorème \vref{sev2}: il  nous permettra  la plupart du  temps de
 nous passer  des 8 vérifications habituelles  que seuls les ordinateurs  et les
 algébristes fous apprécient.
\end{exercice}

\end{exercice}

% lien avec instance de classe !!!



\begin{exercice}[R-espaces vectoriels?]
  Déterminez si les ensembles  suivants munis des opérations indiquées
  ont  une  structure de  $\bbr$-espace  vectoriel.  N'hésitez  pas à  voir  ces
  exercices comme des problèmes d'instances de classes.
  \begin{enumerate}
  \item   Soit  $V=\bigl\{\langle   a,b,c,0\rangle  \mid   \langle  a,
    b,c\rangle  \in \bbr^3\bigr\}$  muni de  l'addition canonique  des
    quadruplets et du produit canonique d'un quadruplet par un réel.
  \item Soit  $V=\bigl\{\langle   a,b,c,2\rangle  \mid   \langle  a,
    b,c\rangle  \in \bbr^3\bigr\}$  muni de  l'addition canonique  des
    quadruplets et du produit canonique d'un quadruplet par un réel.
  \item On munit $V=\bbr^\star_+$ de  l'addition définie par $a\oplus b=a\times
    b$ et  $\bbr$ opère  sur le groupe  $\langle V,\oplus\rangle$
    par  le   produit  externe  défini  par   $λ\otimes  \mathbf{x}  =
    \mathbf{x}^λ$.
  \item        $V=\bigl\{\langle       a,b,c\rangle\mid        \langle
    a,b,c\rangle\in\bbr^3 \land  a\cdot b\cdot  c =0\bigr\}$  avec les
    opérations canoniques.
\item $V$ est l'ensemble des fonctions dérivables sur $\bbr$.
\item $V$ est l'ensemble des suites arithmétiques réelles.
  \end{enumerate}
\end{exercice}


\begin{exercice}[K-espaces vectoriels?]
Les exemples suivants permettent-ils de définir des $\bbk$-espaces vectoriels?
  \begin{enumerate}
  \item $\bbk=\bbc$, l'ensemble des  nombres complexes, $V=\bbc$
    muni de l'addition habituelle des complexes, et le produit externe
    est défini par:
$$
 (\star)\ \colon \begin{array}{rll} \bbc\otimes \bbc& \to & \bbc\\
   \langle λ,\mathbf{z}\rangle& \mapsto & λ^2\cdot \mathbf{z}
 \end{array}
 $$

\item Soit $\bbk$ un corps quelconque et $V=\bbk^2$ muni de l'addition
  canonique des couples. On définit le produit externe ainsi:

$$
 (\star)\ \colon \begin{array}{rll} \bbk\otimes \bbk^2& \to & \bbk^2\\
   \big\langle λ,\langle x,y\rangle\big\rangle& \mapsto & \langle λ x,0\rangle
 \end{array}
 $$

\item $\bbk=\bbq$ et $V=\bbr$ munis des opérations canoniques.

  \end{enumerate}
\end{exercice}


\begin{exercice}
Soit $V$ un espace vectoriel muni de tout ce qu'il faut.

Soit  $\langle \mathbf{u_i}\rangle_{0  \leqslant i  \leqslant p}$  une
famille  de  vecteurs  de $V$.  Montrez  que  $\sev{\mathbf{u_0}\cdots
  \mathbf{u_p}}$ a une structure d'espace vectoriel.

Voilà pourquoi on appellera maintenant  $\sev{\mathbf{u_0}\cdots
  \mathbf{u_p}}$  le \textbf{sous-espace  vectoriel  engendré} par  la
famille $\langle \mathbf{u_i}\rangle_{0 \leqslant i \leqslant p}$.

On dit  que $\langle \mathbf{u_i}\rangle_{0 \leqslant  i \leqslant p}$
est une \textbf{famille génératrice} de  $\sev{\mathbf{u_0}\cdots
  \mathbf{u_p}}$.
\end{exercice}












 \begin{exercice}
     On travaille dans l'ev $\mathbb{R}^{2}$ :
\begin{enumerate}
\item $u=\langle  6,-9\rangle  $\ et $v=\langle  -10,15\rangle  .$\ Donner des CL
de la famille $\langle u\rangle ,$\ de la famille $\langle u,v\rangle .$

Pensez  à un  pauvre compilateur:  comment décider  si des  espaces sont  égaux?
Comparer tous les éléments? Avoir une approche plus formelle? Comment?

Il pourrait être utile par exemple, comme pour les rationnels, d'avoir une forme
\textit{normalisée} des vecteurs pour mieux les comparer: des idées?

\item Que représente $\sev{\mathcal{F}} $\ avec $%
\mathcal{F}=\langle  u,v\rangle  $ ?

\item Démontrer que $w=\langle  2,-3\rangle  \in \sev{\mathcal{F}}  .$

\item $u$\ et $v$\ sont-ils colinéaires ?

%\item $\mathcal{F}$\ est-elle libre ou liée ?

\item Démontrer que $\sev{\FR}  =\sev{\langle  w\rangle}  .$

\item Démontrer que $\langle  1,2\rangle  \notin \sev{\mathcal{F}}.$

% \item $t=\langle  1,2\rangle  ,$\ et $\mathcal{F}^{\prime }=\langle  w,t\rangle  $%
% \ ; démontrer que ${\rm Vect}\langle  \mathcal{F}^{\prime }\rangle  =%
% \mathbb{R}^{2}.$
\end{enumerate}

   \end{exercice}



   \begin{exercice}
      On note $H=\left\{ \langle  x,y,z\rangle  \in \mathbb{R}^{3}\mid
x+2y+3z=0\right\} ,$\ démontrer que $H$\ est un sev de $\mathbb{R}^{3}$
en déterminant $u$\ et $v,$\ deux vecteurs de $\mathbb{R}^{3},$\ de
sorte que $H=\sev{\langle  u,v\rangle}  .$


On note $w=(1,2,3)$. Est-ce que $w\in H$?
   \end{exercice}

  \begin{exercice}
    \begin{enumerate}
    \item Démontrer que $H=\left\{ \langle  x,y,z\rangle  \in \mathbb{R}^{3}\mid
        x-z=0\right\} $ est un sev de $\mathbb{R}^{3}$.
    \item Démontrer que $H=\left\{ \langle  x,y,z\rangle  \in \mathbb{R}^{3}\mid
        x=0\right\} $ est un sev de $\mathbb{R}^{3}$.
    \item   $H=\left\{   \langle   x,y,z\rangle    \in   \mathbb{R}^{3}\mid
          ax+by+cz=0\right\} $ o\`{u} $a$, $b$ et $c$ sont des réels
          fixés.  
          Démontrer que $H$ est un sev de $\mathbb{R}^{3}$.  
    \end{enumerate}
  \end{exercice}

% \begin{exercice}[ A bit of game]
  
% \end{exercice}

 \begin{exercice}
    On travaille dans $\mathbb{R}^{3}$ et on note $u=\langle  1,2,2\rangle 
    $ et $v=\langle -2,1,2\rangle $. 


Déterminer des réels $a$, $b$
    et                   $c$                  pour                   que
    $\sev{\langle   u,v\rangle} =\left\{  \langle   x,y,z\rangle   \in
    \mathbb{R}^{3}\mid ax+by+cz=0\right\}$. 
  \end{exercice}

\modenormal

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