%\makeindex
\documentclass{article}
\usepackage[T1]{fontenc}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage{xspace}
\newcommand{\R}{{\mathbb{R}}}
\newcommand{\C}{{\mathbb{C}}}
\newcommand{\Z}{{\mathbb{Z}}}
\newcommand{\N}{{\mathbb{N}}}
\newcommand{\Q}{{\mathbb{Q}}}

\begin{document}
\noindent
Master 2 Crypto 2-d\hfill Arithmétique de base \hfill 2005/6

\vspace{0.5cm}

But du TP~: programmer les algorithmes fondementaux d'arithmétique
et une application de codage \`a clef publique. Vous devrez rendre
le(s) fichier(s) source(s) de ce TP en fin de s\'eance.

\section{Prérequis} 
Choisir un langage et un type de donnée, éventuellement
installer des librairies ou logiciels complémentaires.

Le langage C/C++ a l'avantage d'être un langage standardisé, compilé
(donc efficace), et dispose de nombreux outils, en particulier pour la mise 
au point (gdb) ou l'optimisation (gprof). Par contre, il n'y a pas 
d'arithmétique
en standard (mais il existe de nombreuses librairies pour ces
fonctionnalités, par exemple GMP, PARI-GP, NTL, LiDIA, giac/xcas, etc.).
Les systèmes de calcul formel possèdent par contre une librairie
mathématique importante et sont interactifs (pas de cycle édition/ 
compilation/exécution), par contre le langage est interprété donc moins
efficace, n'est pas standardisé (il y a autant de langages que de systèmes), 
et les outils de mise au point sont souvent moins évolués 
voire quasi-inexistants.

\subsection{Langage C ou C++.}
\subsubsection{Arithmétique des entiers}
Commencez par travailler avec le type \verb|int| qui est le
plus efficace, mais les entiers doivent être de taille inférieure à $2^{31/2}$
sur une machine 32 bits
(ce qui n'est pas toujours une limitation grâce au théorème des
restes chinois). 

En C++, définir au début\\
\verb|typedef int Int;|\\
et utiliser \verb|Int| partout, ainsi en remplaçant \verb|int|
par \verb|mpz_class|, on peut travailler avec des entiers en précision
arbitraire (notez aussi qu'une bonne partie des algorithmes présentés ici
sont déjà programmés dans GMP, faire Ctrl-H I dans emacs puis Ctrl-S gmp
pour avoir l'aide de GMP). Alternative à typedef: utiliser des templates.

\subsubsection{Arithmétique des polynômes à une variable}
A faire uniquement si vous avez le temps.
Vous pouvez aussi programmer ces algorithmes avec des polynômes
denses en une variable par exemple à coefficient dans $\Z/n\Z$
(avec $n$ un entier premier inférieur à $2^{31}$) en utilisant le type C++
\verb|std::vector<int>|, ou à coefficient dans $\Q$ avec 
\verb|std::vector<mpq_class>|.
En redéfinissant les {\tt operator + - * / \%}, le code pour les entiers
devrait s'appliquer aux polynômes sauf pour les tests où on utilise le degré.
En C, il faut gérer soi-même l'allocation mémoire du tableau de coefficients
et rajouter un champ pour le degré et \'ecrire les op\'erations avec
la notation fonctionnelle (par exemple \verb|poly_add(x,y)|)

Comme la programmation de l'arithmétique
des polynômes est un peu longue, vous pouvez r\'ecup\'erer un patron
de classe sur\\
\verb|www-fourier.ujf-grenoble.fr/~parisse|\\
ou utiliser un logiciel de calcul formel.

\subsubsection{Mise au point}
Pour mettre au point votre programme, 
vous pouvez compiler avec l'option \verb|-g| puis
utiliser le débuggueur \verb|gdb| (appel depuis \verb|emacs| par 
\verb|Esc x gdb|, valider, puis \verb|a.out|, valider).

Attention, les variables de type structur\'e ou les classes
s'affichent comme des structurs C, m\^eme si vous avez red\'efini
l'op\'erateur \verb|<<|. Pour afficher une variable d'un type
classe, on peut la d\'eriver et lui ajouter une m\'ethode:\\
\verb|void dbgprint() const { cout << *this << endl; }|\\
On peut alors visualiser une variable \verb|x| du type consid\'er\'e
en tapant\\ 
\verb|p x.dbgprint()|\\
Pour automatiser tout cela,
cr\'eez un fichier nomm\'e \verb|.gdbinit| et contenant\\
\verb|echo Defining v as print command for class types\n|\\
\verb|define v|\\
\verb|print ($arg0).dbgprint()|\\
\verb|end|\\
Dans la session \verb|gdb|, vous pouvez alors
taper \verb|v x| pour visualiser le contenu
de la variable \verb|x|.

\subsubsection{GMP}
Pour utiliser \verb|mpz_class|, vous devez auparavant
installer la librairie GMP, avec \verb|apt-get| ou
par depuis le source \verb|gmp-4.1.tar.gz|, désarchivez le~:\\
\verb|tar xvfz gmp-4.1.tar.gz|\\
puis déplacez-vous dans le répertoire \verb|gmp-4.1| et compilez
puis installez \verb|gmp|~:
\verb|./configure --enable-cxx|\\
\verb|make| \\
\verb|su|\\
\verb|make install|

Pour que la librairie GMP soit reconnue, il peut être nécessaire d'ajouter
le chemin \verb|/usr/local/lib| dans les chemins par défaut du linker 
\verb|ld|. Ouvrez le fichier \verb|/etc/ld.so.conf|, ajouter le chemin
si nécessaire puis exécutez la commande~:\\
\verb|ldconfig|

N'oubliez pas de mettre \verb|-lgmpxx -lgmp| à la fin de la ligne 
de commande de compilation. En C \verb|-lgmp| suffit, la programmation
est plus fastidieuse (en compensation le programme résultant devrait
être un peu plus rapide).

\section{Avec un logiciel de calcul formel}
Vous pouvez installer \verb|xcas| (logiciel libre disponible sous
forme de paquet debian \`a t\'el\'echarger sur 
\verb|www-fourier.ujf-grenoble.fr/~parisse| et
installer avec \verb|dpkg -i|)
qui est proche de \verb|maple| pour ceux qui connaissent
ou l'utiliser en ligne (URL \verb|www.exo-maths.org| puis
cliquer sur Xcas en ligne).
Tous les algorithmes à programmer sont bien entendu dejà
présents dans ces systèmes (recherchez-les dans l'aide ou pour xcas dans
les menus Math->Integer et Alg),
vous pouvez donc simplement
les utiliser pour vérifier les programmes écrits en C++ (ou en C)
(vous pouvez aussi utiliser une calculatrice!).

La mise au point en \verb|xcas| se fait avec l'instruction
\verb|debug|, par exemple~:\\
\verb|pgcd(a,b):={ if (b==0) return a; else return pgcd(b,irem(a,b)); }|\\
\verb|debug(pgcd(25,15))|

\section{Algorithmes à programmer}
On donne le prototype d'une fonction C++ à réaliser pour des
\verb|int|. A programmer ensuite avec des \verb|mpz_class|.
\begin{enumerate}
\item \verb|int gcd(int a,int b)|: calcul du PGCD par une 
méthode itérative ou/et méthode récursive.
(Pour les polyn\^omes, si vous \^etes tr\`es en avance, 
vous pouvez programmer l'algorithme ``polynomial
subresultant'' qui est plus efficace que l'algorithme naif, il consiste
\`a utiliser la pseudo-division des polyn\^omes au lieu de la
division euclidienne, et \`a diviser le reste par un facteur entier
calcul\'e \`a priori).
\item \verb|int gcdext(int a,int b,int & u,int & v)|: identité de Bézout
méthode itérative ou/et récursive. Renvoie le pgcd $d$ de $a$ et $b$ et 
calcule $u$ et $v$ tels que $au+bv=d$.
Pour la méthode itérative, on part de
\begin{eqnarray*}
1 \times a + 0 \times b &= &a \\
0 \times a + 1 \times b &= &b 
\end{eqnarray*}
on ajoute des lignes, en calculant le quotient $q$ de 2 membres de droite
successifs et en effectuant la manipulation $L_{n+2}=L_n-qL_{n+1}$,
par exemple la ligne 3 s'écrit
\[ (1-q . 0) \times a + (0 -q.1) \times b = a-q.b=r \]
La dernière ligne avec second membre non nul donne $d$ comme
combinaison linéaire de $a$ et $b$.
Notez que la ligne suivante (avec second membre nul) donne le PPCM
de $a$ et $b$.
La méthode récursive est calquée sur le pgcd récursif (cf. exemple
de code en xcas ci-dessus), mais
il faut remonter les coefficients $u$ et $v$ d'un étape sur l'autre
à partir de la dernière étape $d=r_n=1\times r_n+0\times r_{n-1}$
en remplaçant~: $r_n=r_{n-2}-q_n r_{n-1}$ ce qui donne $d$ en
fonction de $r_{n-1}$ et $r_{n-2}$, etc.
\item \verb|int invmod(int a,int n)|~: en appliquant l'identité
de Bézout pour $a$ et $n$.
Renvoyer 0 si $a$ n'est pas inversible modulo $n$. Notez qu'on peut
écrire une version un peu plus efficace que \verb|gcdext|, 
car les coefficients de $n$ ne nous intéressent pas.
\item \verb|int ichinrem(int a,int n,int b,int m)|: calcule
$c$ s'il existe tel que $c=a \pmod m$ et $c=b \pmod n$. On pourra
supposer que $m$ et $n$ sont premiers entre eux (dans ce cas
$c$ existe, on renverra $c$ compris entre 0 et $m\* n$)\\
Variante à plusieurs arguments, les 4 arguments sont remplacée (en C++)
par deux \verb|vector<int>|.
\item \verb|int powmod(int a,int b,int n)|: méthode récursive, selon
la parité de $b$, on a~:
\[ a^b=(a^{b/2})^2 \mbox{ ou } =a \times (a^{(b-1)/2})^2\]
Attention \`a bien effectuer le calcul du reste modulo $n$ apr\`es chaque
op\'eration.
Si $b<0$, commencer par inverser $a$ modulo $n$. Pour les polynômes,
$b$ reste bien sur un entier.
La méthode itérative est plus difficile à programmer et n'apporte pas
de gain appréciable d'efficacité (donc passez à la question
suivante!).
\item Codage et d\'ecodage d'un message par RSA en utilisant les
fonctions pr\'ec\'edentes. Le codage se fait par 
$a\rightarrow a^c \pmod n $ o\`u $n$ est le produit de 2 nombres
premiers $p$ et $q$ et $c$ une clef de codage inversible modulo
$\phi(n)=(p-1)(q-1)$. Si vous avez le temps, vous pouvez lire un
fichier, grouper les codes ASCII des caract\`eres par exemple par 32
pour obtenir des nombres $a$ entre 0 et $2^{32\times 8}$. GMP a une
fonction de test de pseudo-primalit\'e et de g\'en\'eration
de nombres al\'eatoires.
\item Test de pseudo-primalité (pour les entiers uniquements).
Si $p$ est premier, alors $a^p=a \pmod p$. On prend quelques
valeurs de $a$ et on vérifie l'égalité (attention utilisez
\verb|powmod| pour calculer la puissance).\\ 
Trouvez la première valeur de $p$ non premier pour lequel le test renvoie
$p$ pseudo-premier (et ce pour toute valeur de $a$ entre 2 et $p-1$, 
pour savoir si $p$ est premier, on utilisera un test de primalit\'e 
par divisibilit\'e).\\
Si vous avez le temps, programmez un test de pseudo-primalit\'e
plus \'evolu\'e (par exemple Miller-Rabin)
\end{enumerate}

\section{Quelques r\'ef\'erences}
\begin{itemize}
\item H. Cohen, A Course in Computational Algebraic Number Theory
\item D. Knuth, The Art of Computer Programming, Semi-numerical algorithms
\item J. Von zur Gathen et J. Gerhard, Modern Computer Algebra
\item rechercher sur google...
\end{itemize}

\end{document}