% /solutions/conference-talks/conference-ornate-20min.fr.tex, 22/02/2006 De Sousa

\documentclass{beamer}
\usepackage{url}

% Ce fichier est un exemple d'expose

% - pour des conferences,
% - d'une duree approximative de 20 minutes,
% - avec un style ornemental.


\mode<presentation> {
  \usetheme{Warsaw}
  % ou autre $\ldots$

  \setbeamercovered{transparent}
  % ou autre chose (il est egalement possible de supprimer cette ligne)
}


\usepackage[french]{babel}
% or autre comme par exemple \usepackage[english]{babel}

\usepackage[utf8]{inputenc}
\usepackage{amsmath}

\usepackage{multicol}
\usepackage{multirow}
\usepackage{graphicx}
\usepackage{booktabs}
%\usepackage{tabular}
\providecommand{\tabularnewline}{\\}


\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}

% or autre

\usepackage{times}
\usepackage[T1]{fontenc}


\title{Alg\`ebre et arithm\'etique - mat309}

%\subtitle {ne completer que si l'article possede un sous-titre}

\author{B.~Parisse}
% - Composez les noms dans l'ordre dans lequel ils apparaitrons dans l'article
% - Utilisez la commande \inst{?} uniquement si les auteurs ont des affiliations
%   differentes.

%\institute{UGA}
% - Utilisez la commande \inst uniquement s'il y a plusieurs affectations
% - Faites quelque chose de simple, personne ne s'interesse a votre adresse

%\date[29/11/2007]{Netbook and Xcas}

%\logo{ \includegraphics[width=0.5cm,height=0.5cm,keepaspectratio]{xcas}%}


% Si vous souhaitez recouvrir vos transparents un a un,
% utilisez la commande suivante (pour plus d'info, voir la page 74 du manuel
% d'utilisation de Beamer (version 3.06) par Till Tantau) :

%\beamerdefaultoverlayspecification{<+->}


\begin{document}
\date{Septembre 2021}

\begin{frame}
  \titlepage
URL de ce diaporama  \\
%\url{http://wfourier.u-ga.fr/~parisse/\#mat309}\\
\url{https://www-fourier.univ-grenoble-alpes.fr/~parisse/mat249/m309cours1.pdf}

\end{frame}

\section{Pr\'esentation}

\begin{frame}\frametitle{Contenu}
Ce cours pr\'esente des math\'ematiques avec
une forte composante algorithmique, 
qui sont utilis\'ees dans des domaines comme
la cryptographie ou la d\'etection
et correction d'erreurs de transmission. 
\begin{enumerate}
\item Motivations~: cryptographie, RSA, codes de Hamming binaires
(hors programme cette ann\'ee)
\item Division euclidienne et \'ecriture en base,
 op\'erations + - * sur de grands entiers, liens avec les polyn\^omes
\item Divisibilit\'e, PGCD, algorithme d'Euclide et Euclide \'etendu,
nombres premiers, restes chinois
\item L'anneau $\Z/n\Z$ et le corps $\Z/p\Z$ ($p$ premier)
\item Calcul matriciel sur $\Z/p\Z$ ($p=2$) et applications
\end{enumerate}

\end{frame}

\begin{frame} \frametitle{Organisation}
\begin{itemize}
\item 21 h de cours, 14 s\'eances de 1h30. 
Il y a 2 cr\'eneaux de cours par semaine,
cela permettra de d\'edoubler le cours 
si n\'ecessaire.
\item 36h de TD, 24 s\'eances de 1h30.
%\\ Une partie des TD sera peut-\^etre \`a distance.
\item Site chamilo
\url{https://chamilo.univ-grenoble-alpes.fr/courses/GBX3MT39/index.php}
\end{itemize}
\end{frame}

\begin{frame} \frametitle{\'Evaluation}
\begin{enumerate}
\item CC1: partiel semaine du 8 novembre
\item CC2: interrogations en TD % TP?
\item ET1: janvier 2022
\item ET2: 2\`eme chance juin 2022
\item R\`egle du max si ET est sup\'erieur \`a la moyenne des CC
\end{enumerate}
Un formulaire manuscrit recto-verso est autoris\'e au CC1 et aux ET.
Les calculatrices sont interdites aux interrogations, elles sont
autoris\'ees au CC1 et aux ET. Il est conseill\'e d'avoir une
calculatrice graphique, si possible avec calcul exact sur des entiers
sans limitation de taille.
\end{frame}


\begin{frame} \frametitle{Ressources}
\begin{enumerate}
\item Page web des ressources de l'UE et cours \\
\url{https://www-fourier.univ-grenoble-alpes.fr/~parisse/\#mat309}\\
\url{https://www-fourier.univ-grenoble-alpes.fr/~parisse/mat249/mat309.html}
\item sous-forum UGA-LST du Forum de Xcas\\
\url{https://xcas.univ-grenoble-alpes.fr/forum/}
login g\'en\'erique {\tt etuinf}, password indiqu\'e sur Chamilo
\item outil de calcul en ligne (Xcas ou MicroPython)
\url{https://www-fourier.univ-grenoble-alpes.fr/~parisse/xcasfr.html}
\item Si cours \`a distance n\'ecessaire, site chamilo ou~:
\url{https://meet.univ-grenoble-alpes.fr/b/ber-uph-xdu}
\end{enumerate}
\end{frame}

\section{Deux exemples d'applications}
\begin{frame} \frametitle{Cryptographie monoalphabetique \`a clef secr\`ete.}
\begin{itemize}
\item D\'ecalage circulaire de l'alphabet (C\'esar), exemple. 
\item Variante avec n'importe quelle permutation des lettres de l'alphabet.
\item Cryptographie sym\'etrique: la connaissance de la clef de cryptage
donne la clef de d\'ecryptage.
\item Attaques~? Force brute, fr\'equences des lettres selon la
  langue.
\item M\'ethodes plus robustes~: on n'utilise pas toujours la meme lettre pour une
lettre donn\'ee, mais cela n\'ecessite l'\'echange pr\'ealable de la clef.
Cf. {\em The Key to Rebecca (Le Code Rebecca)} de Ken Follett 
basée sur l’histoire de l’espion nazi Johannes Eppler et l’opération
Salaam.\\
L'attaque d'Enigma par Alan Turing, {\em The Imitation Game}.
\end{itemize}
\end{frame}

\begin{frame} \frametitle{Cryptographie \`a clef publique.}
Ce sont des syst\`emes asym\'etriques ne n\'ecessitant pas d'\'echange pr\'ealable de clefs,
RSA est l'exemple le plus connu.
\begin{itemize}
\item Num\'erisation de l'information \`a transmettre, un entier $a$.
\item Choix des clefs $N=pq$ avec $p,q$ premiers, 
et $c$ et $d$ tels que le reste de $cd$ par 
$(p-1)(q-1)$ soit 1. $N$ et $c$ sont publics, $p,q,d$ sont secrets.
\item codage $b=a^c \pmod N$ est le message crypt\'e, d\'ecodage
on montre (maths!) que $a=b^d  \pmod N$
\item La s\'ecurite repose sur la difficult\'e de factoriser des entiers vs
les multiplier. 
\item L'algorithme de codage/d\'ecodage doit \^etre rapide,
\item Il est essentiel d'\'evaluer l'efficacit\'e des algorithmes.
\end{itemize}

\end{frame}

\begin{frame} \frametitle{Illustration}
\begin{itemize}
\item d\'ecrypter le code de C\'esar
{\tt IZIRSZVEHLZIZIRCVUVIEZVI}
% rira bien qui rira le dernier
\item RSA jouet $p=17, q=19, N=323, c=11, d=131$.
Prendre un entier $a<323$, calculer $b=a^c \pmod N$
puis $b^d \pmod N$, on doit retrouver $a$. 
Attention au d\'epassement de capacit\'e
selon le logiciel utilis\'e! En Xcas\\
{\tt p:=17; q:=19; N:=p*q; }\\
{\tt c:=11; d:=131; irem(c*d,(p-1)*(q-1))}\\
{\tt a:=randint(N); }\\
{\tt b:=pow(a,c,N); pow(b,d,N)}\\
En Python, remplacer {\tt irem} pr\'efix\'e par {\tt \%} infix\'e.
\end{itemize}
\end{frame}

 
\begin{frame} \frametitle{D\'etection et correction d'erreur}
La transmission d'information sur un canal bruit\'e g\'en\`ere
des erreurs, qu'il faut pouvoir d\'etecter et si possible corriger.
\begin{itemize}
\item Bit de parit\'e~: 7 bits d'information, on ajoute 1 bit 
pour avoir un nombre pair de bits \`a 1, d\'etection mais pas de correction
\item Code de r\'ep\'etition~: on r\'ep\`ete 3 fois chaque bit.
On peut alors corriger \`a la majorit\'e. Mais cela coute 3 fois
plus de bande passante.
\item Calcul matriciel modulo 2 permet de faire mieux: codes de
  Hamming binaire.
\end{itemize}
\end{frame}

\begin{frame} \frametitle{Codes de Hamming binaire}
\begin{itemize}
\item on choisit $m>1$, on pose $n=2^m-1$ et $k=n-m$.
Par exemple $m=3, n=7, k=4$.
\item L'information est cod\'ee par un vecteur $v$ ayant $k$
  bits
\item On transmet $w$ un vecteur de $n$ bits~: d'abord les $k$ bits de $v$ 
puis $m$ bits calcul\'e en faisant le produit $C*v$, o\`u $C$ est une matrice fix\'ee 
ayant $k$ colonnes et $m=n-k$ lignes
\item La personne qui recoit $w$ teste si $C*w[0:k]+w[k:n]$ est nul.
Si ce n'est pas le cas il y a erreur.
\item Pour pouvoir corriger une erreur, on choisit $C$ tel que les
  colonnes de la matrice $(C|I_m)$ soient toutes non nulles et distinctes,
en \'ecrivant en base 2 les entiers de 1 \`a $n-1$ et en permutant
les colonnes de $I_m$ \`a la fin.
\end{itemize}
\end{frame}

\begin{frame} \frametitle{Illustration}
\begin{itemize}
\item \'Ecrire les entiers de 1 \`a 7 en base 2 en colonne
\item Permuter les colonnes de la matrice identit\'e $I_3$ \`a la fin
\item Extraire la premi\`ere partie $C$, puis coder 
par exemple $v=[1,0,1,1]$ en $w=(v,C*v)$ modulo 2.
\item V\'erifier que $H*w=0$ (modulo 2) o\`u $H=(C|I_3)$.
\item Bonus~: Simuler une erreur et sa correction.
(On peut remarquer que $H*w$ est l'\'ecriture en base 2
du num\'ero de bit \`a modifier apr\`es permutation).
\end{itemize}
\end{frame}

\begin{frame} \frametitle{Une solution avec Xcas}
{\tt m:=[convert(j+9,base,2) for j in range(7)];}\\
{\tt M:=tran(m)[0..2];}\\
{\tt C:=tran(select(x->sum(x)!=1,tran(M)));}\\
{\tt v:=[1,0,1,1] mod 2;}\\
{\tt w:=concat(v,C*v);}\\
{\tt H:=concat(C,identity(3));}\\
{\tt H*w;}\\
{\tt w[3]:=1-w[3]; H*w;}\\
La premi\`ere ligne utilise une astuce pour forcer la pr\'esence de 0 non
significatifs de l'\'ecriture en base 2 pour $n<4$~: on ajoute 8 qui
cr\'ee un bit 1 en plus, qu'on enl\`eve \`a la ligne suivante. L'extraction de $C$ se
fait en regardant si la somme des coefficients d'une colonne 
(ligne de la transpos\'ee) vaut 1.
\end{frame}

\section{Arithm\'etique des entiers}
\begin{frame} \frametitle{Repr\'esentation des entiers}
\begin{itemize}
\item Les r\'egistres d'un microprocesseur peuvent stocker et
  manipuler des entiers de taille limit\'ee. Les op\'erations
arithm\'etiques sont faites modulo une puissance de 2.
\item Par exemple entier sign\'e dans $[-2^{31},2^{31}-1]$
sur un processeur 32 bits, entier non sign\'e dans $[0,2^{64}-1]$
sur un 64 bits.
\item Pour les entiers plus grands, il est n\'ecessaire d'utiliser
une zone m\'emoire de plusieurs mots, il s'agit d'un cas particulier
d'\'ecriture d'un entier en base $b$. Le fondement math\'ematique est le
\item Th\'eor\`eme~: Soient $a$ et $b$ sont deux entiers naturels, $b
  \neq 0$. Il existe un unique couple $q,r$ tel que $a=bq+r$, $r \in
  [0,b[$, ce sont le quotient et le reste euclidien de $a$ par $b$.
\end{itemize}
\end{frame}

\begin{frame} \frametitle{\'Ecriture en base $b$}
\begin{itemize}
\item Soit $b \geq 2$ fix\'e. 
Tout entier $a>0$ s'\'ecrit de mani\`ere unique
$$a=\sum_{i=0}^n a_i b^i, \quad a_i \in [0,b[, a_n \neq 0$$
\item Algorithme de calcul des $a_i$ en fonction de $a$.\\
Faire la division euclidienne de $a$ par $b$, si le quotient $q$ est nul
alors $n=0$ et $a_0=a$. Sinon d\'eterminer la d\'ecomposition
en base $b$ de $q$, d\'ecaler les indices de 1 et poser $a_0=r$
le reste de la division.
\item Algorithme de calcul de $a$ connaissant les $a_i$.\\
C'est un cas particulier de l'algorithme d'\'evaluation du
polyn\^ome $P(x)=\sum_{i=0}^n a_i x^i$ en $x=b$, qui se
fait de mani\`ere optimale par la m\'ethode de Horner.
\end{itemize}
\end{frame}

\begin{frame} \frametitle{Exemple}
\begin{itemize}
\item \'Ecrire 2020 en base 2, 3, 16.
\item Faire l'op\'eration r\'eciproque.
\item V\'erification avec Xcas\\
{\tt l:=convert(2020,base,3)}\\
{\tt convert(l,base,3)}
\item Dans le monde, il y a 10 catégories de personnes : 
celles qui connaissent le binaire et celles qui ne le connaissent pas.
\end{itemize}
\end{frame}

\begin{frame} \frametitle{Algorithme de Horner}
\begin{itemize}
\item $P(x)=\sum_{i=0}^n a_i x^i$ est donn\'e par
la liste {\tt l}  de ses coefficients $[a_n,...,a_0]$. On veut
calculer $P(b)$. On \'ecrit~:
$$ P(b)=((...((a_nb+a_{n-1})b+a_{n-2})b+...)b+a_0$$
\item Algorithme de Horner en langage naturel\\
Arguments~: la liste {\tt l} et le r\'eel {\tt b}\\
 {\tt n} $\leftarrow $ longueur({\tt l})-1\\
 {\tt r} $\leftarrow $ {\tt l[0]}\\
 Pour {\tt j} de {\tt 1} jusque {\tt n} faire\\
 \quad {\tt r} $\leftarrow $ {\tt r*b+l[j]}\\
 Finpour\\
 Renvoyer {\tt r}
\end{itemize}
\end{frame}

\end{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame} \frametitle{}
\begin{itemize}
\item 
\end{itemize}
\end{frame}
