\documentclass{article}
\usepackage{amsmath,amsfonts,amssymb,a4,epsfig}
\newcommand{\R}{{\mathbb{R}}}
\newcommand{\C}{{\mathbb{C}}}
\newcommand{\Z}{{\mathbb{Z}}}
\newcommand{\N}{{\mathbb{N}}}

\begin{document}
\title{Arithm\'etique et exemples d'applications.}

\maketitle

\section{Arithm\'etique enti\`ere.} \label{sec:entiere}
\begin{itemize}
\item 
La division euclidienne des entiers (comme \`a l'\'ecole primaire): en C 
on utilise \verb|%| (modulo) et \verb|/| (quotient euclidient).
Diviseurs d'un entier: $d$ divise $a$ si le reste de $a$ par $d$ est 0.
\item Les nombres premiers: ce sont des entiers dont les seuls diviseurs sont
1 et lui-m\^eme. Programmation d'un test de primalit\'e trivial.
\item 
PGCD de 2 entiers $a$ et $b$ (plus grand diviseur commun de $a$ et $b$).
On dit que $a$ et $b$ sont premiers entre eux si le PGCD de $a$ et $b$
est \'egal \`a 1.
Propri\'et\'e: le PGCD de $a$ et $b$ est \'egal au PGCD de $b$ et de $r$
le reste de la division euclidienne de $a$ par $b$. L'algorithme
d'Euclide consiste \`a calculer la suite des restes successifs,
le PGCD est le dernier reste non nul.\\
Programmer l'algorithme d'Euclide.
\item 
R\'esolution de l'\'equation de B\'ezout: on cherche $u$ et $v$ entiers
tels que $au+bv=d$ o\`u $d$ est le PGCD de $a$ et $b$. L'algorithme
est une variante de l'algorithme d'Euclide: on \'ecrit $a$, $b$ et les
restes successifs comme combinaison lin\'eaire de $a$ et $b$.\\
Notons $[ D \ U \ V ]$ pour signifier que $D=aU+bV$. On a alors $[a \ 1 \ 0]$
et $[b \ 0 \ 1]$. Si la division euclidienne de $a$ par $b$ est $a=bq+r$ 
alors $a-bq=r$ donc la ligne $[ r \ ? \ ? ]$ s'obtient en retranchant
$q$ fois la ligne $[b \ 0 \ 1]$ \`a la ligne $[a \ 1 \ 0]$. On continue
jusqu'\`a obtenir la ligne $[d \ u \ v ]$.\\
Exemple: le pgcd de 25 et 15 est 5. Les deux premi\`eres lignes sont
ici $[25 \ 0 \ 1]$ et $[15 \ 1 \ 0]$. 
On a $25=15\times 1+10$ donc $q=1$, on retranche
donc \`a a ligne $[25 \ 1 \ 0]$ 1 fois la ligne $[15 \ 0 \ 1]$ ce qui donne 
$[10 \ 1 \ -1]$. Puis on divise 15 par 10: $15=10 \times 1 + 5$ donc $q=1$
\`a nouveau et la ligne obtenue est $[5 \ -1 \ 2]$ donc $u=-1$ et $v=2$.\\
Programmation de l'algorithme de B\'ezout.
\end{itemize}

\section{$\Z/n\Z$} \label{sec:modulaire}
On se fixe un entier $n>1$ et on consid\`ere les entiers de $0$ \`a $n-1$
qui forment l'ensemble des restes de division euclidienne d'entiers par 
l'entier $n$. Cet ensemble est not\'e $\Z/n \Z$.
Sur cet ensemble on d\'efinit les op\'erations $+$ et $*$
en effectuant les op\'erations $+$, $-$, $*$ habituelles puis en
prenant le reste de la division euclidienne du r\'esultat par $n$.

Par exemple prenons $n=5$: $\Z/n\Z=\{ 0, 1, 2, 3, 4 \}$. 
La somme de 2 et 4 est 6, on divise par 5, reste 1, on dit que 
$2+4=1 \pmod 5$.

Ces op\'erations poss\`edent la plupart des propri\'et\'es des op\'erations
sur les nombres entiers (commutativit\'e, associativit\'e, distributivit\'e,
...) et la soustraction est l'op\'eration inverse de l'addition.
De plus on peut d\'efinir l'inverse $u$ d'un \'el\'ement $a$
de $\Z/n\Z$ si $a$ est premier avec $n$: en effet, il s'agit de r\'esoudre
$ a u = 1 \pmod n$. Or cela signifie que le reste de la division de $au$
par $n$ est 1, si on note $q$ le quotient de $au$ par $n$, on a alors:
\[ au=qn+1 \]
qu'on peut mettre sous la forme de l'\'equation de B\'ezout:
\[ a u + n \times (- q) =1 \]
qui admet une solution si le PGCD de $a$ et $n$ est 1.\\
Programmer le calcul de l'inverse d'un entier dans $\Z/n\Z$.

On peut aussi calculer la puissance $k$-i\`eme $a^k \pmod n$
d'un \'el\'ement de $\Z/n\Z$.
Il existe un algorithme rapide pour calculer cette puissance, bas\'e sur 
l'id\'ee suivante:\\
Si $k=0$ on renvoie 1, si $k=1$ on renvoie $a$.
Sinon, soit $k$ est pair, dans ce cas $a^k=(a^{k/2})^2 \pmod n$,
on appelle {\em r\'ecursivement}\/ la fonction puissance pour calculer 
$a^{k/2} \pmod n$, on le multiplie par lui-m\^eme et on le r\'eduit
modulo $n$~; soit $k$ est impair, dans ce cas $a^k=(a^{(k-1)/2})^2*a \pmod n$
etc.\\
Programmer cet algorithme.\\
Notez que si $n$ est premier, tous les nombres inf\'erieurs \`a $n$
sont premiers avec $n$ et donc inversibles dans $\Z/n\Z$ sauf bien
sur 0. Les propri\'et\'es de $\Z/n\Z$ sont alors tr\`es semblables \`a celles
des nombres r\'eels ou complexes: tout \'el\'ement sauf 0 est inversibles.

Petit th\'eor\`eme de Fermat: si $n$ est un nombre premier $a^n=a \pmod n$.
Ce th\'eor\`eme peut se d\'emontrer par r\'ecurrence sur $a$ (c'est vrai pour
$a=1$ puis on passe de $a$ \`a $a+1$ en d\'eveloppant $(a+1)^n$
avec la formule du bin\^ome de Newton, on montre ensuite que tous
les $C^k_n$ sont divisibles par $n$ sauf pour $k=0$ et $k=n$ en utilisant
le fait que $n$ est premier).\\
Tester ce r\'esultat en utilisant le programme de puissance rapide ci-dessus.\\
Lorsque $n$ n'est pas premier, en g\'en\'eral $a^n \neq a \pmod n$. Mais
il existe une g\'en\'eralisation qui fait intervenir 
{\em l'indicatrice d'Euler}\/ de $n$:\\
On appelle indicatrice d'Euler $\varphi (n)$ de $n$ le nombre d'entiers
compris entre 1 et $n$ qui sont premiers avec $n$. \\
Par exemple, si $n$ est premier $\varphi (n)=n-1$.\\
Autre exemple: calculons $\varphi (15)$. Les entiers inf\'erieurs \`a 15
qui sont premiers avec 15 sont: 1, 2, 4, 7, 8, 11, 13, 14, il y en a 8
donc $\varphi (15)=8$.\\
Th\'eor\`eme: si $a$ est premier avec $n$ alors $a^\varphi (n)=1 \pmod n$.\\
Ce th\'eor\`eme est une g\'en\'eralisation du pr\'ec\'edent car si $n$
est un nombre premier, $a^\varphi (n)=a^{n-1} \pmod n$ donc 
$a^n=a^{n-1} \times a=1 \times a=a \pmod n$.\\
Tester ce r\'esultat.\\
On verra plus loin (section \ref{sec:rsa}) que ce th\'eor\`eme 
est \`a l'origine de la m\'ethode de cryptage RSA.

\section{Polynomes} \label{sec:polynomes}
On consid\`ere ici des polyn\^omes \`a coefficients entiers ou \`a
coefficients dans $\Z/n \Z$. Certaines des notions d'arithm\'etique
vues sur les entiers continuent \`a s'appliquer aux polyn\^omes,
en particulier on peut d\'efinir une notion de division euclidienne
selon les puissances d\'ecroissantes.

Soit $A$ un polyn\^ome non nul, $A(X)=a_d X^d + ... + a_0$ avec $a_d\neq 0$.
L'entier $d$ est appel\'e degr\'e de $A$. La division euclidienne de $A$
par $B$ correspond \`a l'\'egalit\'e:
\[ A= B Q + R \]
o\`u le degr\'e de $R$ est strictement inf\'erieur au degr\'e de $B$.
Pour calculer $Q$ et $R$ connaissant $A$ et $B$ on commence par diviser
le terme de plus haut degr\'e de $A$ par celui de plus haut degr\'e de $B$
que l'on met comme coefficient de $X^{d(A)-d(B)}$ dans $Q$. On multiplie
alors ce terme par $Q$ et on le retranche \`a $A$, ce qui diminue le degr\'e
d'un au moins. On recommence tant qu'on peut (tant que le degr\'e est
sup\'erieur ou \'egal \`a celui de $B$), losqu'on s'arr\^ete on
obtient le reste.\\
Programmer la division euclidienne et le PGCD de deux polyn\^omes
dont les coefficients sont dans $\Z/n \Z$.

\section{Cryptographie: exemple de la m\'ethode RSA} \label{sec:rsa}
On se donne 2 nombres premiers $p$ et $q$, on pose $n=pq$,
donc $\varphi (n)=(p-1)(q-1)$. Soit $c$ un entier premier avec $\varphi (n)$
et $d$ son inverse modulo $\varphi (n)$. Alors, pour tout entier
$a$ premier avec $n$, on a:
\[ (a^c)^d = a \mbox{ mod } n \]
Cette \'egalit\'e est le principe de base des codages \`a clefs publiques
(RSA et les logiciels qui l'utilisent comme Pretty Good Privacy,
Gnu Privacy Guard, ssh, etc.). L'entier $n$ est connu de tout le monde
mais $p$ et $q$ ne le sont pas (si $n$ est suffisament grand la
factorisation de $n$ est infaisable en un temps raisonnable), ou
ce qui revient au meme $\varphi (n)$ est inconnu. Il est donc impossible
de d\'eduire $d$ de $c$, $c$ est appel\'e clef publique de Mr X
et $d$ clef secr\`ete de Mr X.
Le codage d'un entier $a$ \`a destination de Mr X uniquement
se fait en envoyant $a^c $ mod $n$. Seul Mr X peut d\'ecoder
$a$ car lui seul connait $d$. Mr X peut s'authentifier (signer
un message par exemple) en
envoyant $a^d$ mod $n$, chacun pourra d\'ecoder la signature
$a$ en utilisant la clef publique $c$. Pour crypter un message complet,
on commence par transformer ce message en suite d'entiers (premiers
avec $n$).\\
Essayez de crypter/d\'ecrypter un message de cette mani\`ere:
prenez 2 nombres premiers, faites en le produit $n$,
calculer $\varphi (n)$, choisissez une clef publique $c$, d\'eduisez
en la clef secr\`ete associ\'ee, etc.

Remarques:
\begin{itemize}
\item L'algorithme RSA est rentr\'e dans le domaine public d\'ebut septembre
2000 aux \'Etats-Unis (contrairement \`a l'Europe pour l'instant,
les \'Etats-Unis autorisent le brevetage de ce type d'algorithmes).
\item  actuellement on est capable de factoriser des nombres jusqu'\`a
environ $n=10^{128}$ (soit environ 400 bits). Les syst\`emes \`a clef
publique permettent donc la confidentialit\'e pour des clefs de 512 bits
ou plus. La l\'egislation fran\c{c}aise autorise les clefs de 40 bits
actuellement, un d\'ecret devrait faire passer cette limite \`a 128 bits
tr\`es bientot avant une lib\'eralisation plus compl\`ete promise par le
premier ministre en janvier 99.
\item le cryptage public avec de grandes clefs peut n\'ecessiter
un temps de calcul trop long, certains logiciels ne l'utilisent que
pour crypter un \'echange de clef de syst\`emes de cryptographie
classique (la cryptographie a clef non publique assurant une
confidentialit\'e avec des clefs de taille plus faible ou des
algorithmes plus rapides, par exemple 128 bits).
\end{itemize}



\section{Correction d'erreurs de transmission: PCE} \label{sec:pce}
On pr\'esente ici un m\'ecanisme de recherche et correction d'erreurs
(utilis\'e par exemple dans les Minitel)
utilisant des propri\'et\'es arithm\'etique des polyn\^omes \`a
coefficients dans $\Z/2\Z$. On travaille pr\'ef\'erentiellement
dans $\Z/ 2 \Z$


\subsection{La parit\'e.} \label{sec:parite}
Les donn\'ees sont souvent \'echang\'ees octet par octet, c'est-\`a-dire
qu'on transf\`ere l'information par paquet de 8 bits \`a la fois.
S'il suffit de 7 bits pour transf\'erer de l'information (ce qui
est le cas pour les caract\`eres non accentu\'ees en utilisant le
codage ASCII), on peut utiliser le 8\`eme bit en y pla\c{c}ant
une valeur calcul\'ee en fonction des 7 premiers et tester en faisant
le m\^eme calcul apr\`es transmission.\\
Une des m\'ethodes de calcul du 8\`eme bit s'appelle le test
de parit\'e, elle consiste \`a fixer la valeur du 8\`eme bit pour
que le nombre de bits de l'octet soit pair.

Si $o$ est un octet, on notera $o=(a_7, ..., a_0)$ o\`u les bits $a_0$, ...,
$a_7 \in \Z/2\Z$. On notera aussi:
\[ P_o(X)=a_7 X^7+...+a_1 X +a_0 \]
On remarque que $o$ est de parit\'e paire si et seulement si $P_o(X)$
est divisble par $X+1$ (dans $\Z/2\Z$).

\subsection{La PCE.} \label{sec:la_pce}
La m\'ethode pr\'ec\'edente permet de savoir avec certitude qu'une
transmission s'est mal pass\'ee si la parit\'e n'est pas respect\'ee,
mais elle ne permet pas de corriger une erreur. La m\'ethode d\'ecrite
dans cette section permet de corriger une erreur (en faisant
l'hypoth\`ese que la transmission a engendr\'e au plus 2 erreurs).

Cette fois-ci on regroupe l'information \`a transmettre par paquets de 15
octets (de parit\'e paire) et on ajoute un 16\`eme octet (dont on
ajuste aussi la parit\'e). On va maintenant expliquer comment on
calcule ce 16\`eme octet en fonction des 15 pr\'ec\'edents.

Soit $Q(X)=X^7+X^3+1$. \'Etant donn\'es 15 octets $o_1$, ..., $o_{15}$ 
de parit\'e paire, on calcule le polyn\^ome:
\[ C(X)= \sum _{j=1}^{15} P_{o_j}(X) X^{8j-1} \]
(le terme de plus bas degr\'e est donc de degr\'e au moins 7:
$X^7$ obtenu pour $j=1$).\\
On calcule ensuite le reste de la division euclidienne de $C(X)$ par $Q(X)$
ce qui donne un polyn\^ome $R$ de degr\'e 6, l'octet $o_{16}$ est alors
l'octet correspondant \`a $R$ (plus pr\'ecis\'ement tel que $P_{o_{16}}$ coinncide avec $R$ sauf pour le terme de degr\'e
7).

A l'autre extr\'emit\'e, le r\'ecepteur re\c{c}oit 16 octets
$\tilde{o}_1, ... \tilde{o}_{16}$ et forme le polyn\^ome
\[ \tilde{C}(X)= \sum _{j=1}^{15} P_{\tilde{o}_j}(X) X^{8j-1}
+ a_6 X^6+...+a_1 X +a_0, \quad \mbox{o\`u } 
\tilde{o}_{16}=(a_7, a_6, ..., a_0) \]
Si la transmission s'est bien pass\'ee, $\tilde{o}_j=o_j$ donc 
$\tilde{C}=C+R$ est divisible par $Q$ (car $R=-R$ dans $\Z/2\Z$).
R\'eciproquement, si tous les octets $\tilde{o}_j$ sont de parit\'e
paire et si $\tilde{C}$ est divisible par $Q$ alors soit la transmission
s'est bien pass\'ee soit le nombre d'erreurs est sup\'erieur ou \'egal \`a 2.

S'il y a une erreur de transmission et une seule, alors il exixste
un entier $i \leq 126$ tel que:
\[ \tilde{C}(X)= C(X)+R(X)+X^i \]
que d\'etermine \`a l'aide du reste de la division euclidienne
de $\tilde{C}$ par $R$ et de la parit\'e des $\tilde{o}_j$.

Programmez un algorithme mettant en oeuvre cette proc\'edure et
testez la en cr\'eant des erreurs de mani\`ere al\'eatoire.


\section{Programmation.} \label{sec:prog}
Sur \verb|pcm2.e.ujf-grenoble.fr|, on peut utiliser la classe 
\verb|entier| pour manipuler des entiers sans contrainte de taille.
Pour les polyn\^omes \`a une variable, on pourra utiliser 
le type \verb|vecteur| de la m\^eme librairie \verb|giac|. Pour
installer cette librairie sur une autre machine, r\'ecup\'erez\\
\verb|ftp://fourier.ujf-grenoble.fr/pub/hp48/giac.tgz|\\
puis~:\\
\verb|tar xvfz giac.tgz|\\
\verb|cd giac-0.2.2|\\
\verb|./configure|\\
\verb|make|\\
\verb|make install| \\
(la derni\`ere \'etape n\'ecessite d'\^etre \verb|root|).

\subsection{La classe entier.} \label{sec:integer}
Mettre en en-t\^ete du programme:\\
\verb|#include <giac/gaussint.h>|\\
\verb|using namespace giac;|\\
Ensuite \verb|entier| s'utilise comme le type de base \verb|int| dans
presque toutes les situations. Attention l'op\'erateur de division \verb|/| 
n'est pas d\'efini, utilisez \verb|iquo| pour le quotient euclidien de deux
entiers.

Pour compiler votre programme, vous devrez rajouter \verb|-lgmp -lgiac|
en fin de ligne de commande.

Pour voir la valeur d'un \verb|entier| avec
le d\'eboggueur, cr\'eez un fichier \verb|.gdbinit|  contenant~:\\
\verb|echo Defining v as print command for giac types\n|\\
\verb|define v|\\
\verb|print $arg0.dbgprint()|\\
\verb|end|\\
L'impression se fait par la m\'ethode \verb|dbgprint()| de \verb|$arg0|.

\subsection{Polynomes.} \label{sec:poly}
On peut utiliser les fonctions de \verb|giac| pour les polynomes 
\`a une variable en mettant en d\'ebut de fichier:\\
\verb|#include <giac/modpoly.h>|\\
Un polyn\^ome \`a une variable est un vecteur d'entiers (\verb|vecteur|),
les \'el\'ements du vecteur sont ces coefficients par ordre d\'ecroissant.

Pour la saisie, on utilisera un \verb|entier| interm\'ediaire
qui permet d'entrer le polynome au clavier sous la forme \verb|[1,2,3]|.
ou sous la forme symbolique \verb|x^2+2*x+3|. On le convertit ensuite
en vecteur comme dans l'exemple suivant~:
\begin{verbatim}
#include <giac/modpoly.h>
using namespace giac;

int main(){
  entier poly1tab(string("[1,2,3]"));
  vecteur poly1(*poly1tab.compptr);

  entier poly2symb(string("x^4-1"));
  vecteur poly2(modularize(sym2r(poly2symb,lvar(poly2symb)),0));

  cout << poly1 << "+" << poly2 << "=" << poly1+poly2 << endl;
}
\end{verbatim}

Principales op\'erations~:
\begin{itemize}
\item Les op\'erateurs arithm\'etiques sont surcharg\'es, par exemple
\verb|+|, \verb|-|, \verb|*| et \verb|%|. 
Utiliser \verb|DivRem| pour la division euclidienne.
\item Pour avoir le polynome nul~:\\
\verb|vecteur zero;|
\item Pour avoir un polyn\^ome constant \'egal \`a 2~:\\
\verb|vecteur two(1,2);|
\item Pour avoir le polyn\^ome \verb|x|~:\\
\verb|vecteur x; x.push_back(1); x.push_back(0);|
\item Consultez \verb|/usr/local/include/giac/modpoly.h| pour connaitre
l'ensemble des op\'erations impl\'ement\'ees sur ce type de polyn\^ome.
\end{itemize}

\end{document}