\chapterimage{asterix1}
\chaptertext{}

\chapter{Un peu d'arithmétique}



\section{Ave Cesar}

Pour les problèmes  de codage-décodage (cf X 2008),  on a souvent besoin
de manipuler des listes de caractères.

On   peut  utiliser  la   bibliothèque  \lstinline+StringTools+   et  en
particulier:

\begin{itemize}
\item   \lstinline+Ord("car")+   qui    renvoie   le   code   ASCII   de
  \texttt{car}. Par exemple \lstinline+Ord("a")+ renvoie \lstinline+97+;
\item \lstinline+Char(code)+  effectue l'opération inverse.  Par exemple
  \lstinline+Char(97)+ renvoie \texttt{"a"};
\item \lstinline+Explode("abc")+ renvoie \lstinline+["a","b","c"]+;
\item \lstinline+Implode(["a","b","c"])+ renvoie \lstinline+"abc"+;  
\end{itemize}

Créez  une fonction \lstinline+cesar:=proc(message,cle)+  qui code  un message
rentré sous forme d'une chaîne selon la méthode bien connue de César, en
se  donnant la possibilité  de choisir  sa clé.  On travaillera  avec un
alphabet de 95 lettres:


\begin{center}
\begin{table}[h!]
{\footnotesize
\begin{tabularx}{\linewidth}{Il*{19}{|X}I}
\whline
Caractère&  & ! & " & \# & \$ & \% & \& & ' & (  & ) & * & + & , & - & . & / & 0 & 1 & 2 \\
\hline
Code & 32 & 33 & 34 & 35 & 36 & 37 & 38 & 39 & 40 & 41 & 42 & 43 & 44 & 45 & 46 & 47 & 48 & 49 & 50 \\
\hline
\end{tabularx}


\begin{tabularx}{\linewidth}{Il*{19}{|X}I}
\hline
Caractère&3 & 4 & 5 & 6 & 7 & 8 & 9 & : & ; & < & = & > & ? & @ & A & B & C & D & E \\
\hline
Code &51 & 52 & 53 & 54 & 55 & 56 & 57 & 58 & 59 & 60 & 61 & 62 & 63 & 64 & 65 & 66 & 67 & 68 & 69\\
\hline
\end{tabularx}



\begin{tabularx}{\linewidth}{Il*{19}{|X}I}
\hline
Caractère&F & G & H & I & J & K & L & M & N & O & P & Q & R & S & T & U & V & W & X \\
\hline
Code &70 & 71 & 72 & 73 & 74 & 75 & 76 & 77 & 78 & 79 & 80 & 81 & 82 & 83 & 84 & 85 & 86 & 87 & 88\\
\hline
\end{tabularx}





\begin{tabularx}{\linewidth}{Il*{19}{|X}I}
\hline
Caractère& Y & Z & [ & \verb+ \ + & ] & \verb+ ^ + & \verb+ _ + & \verb+ ` + & a & b & c & d & e & f & g & h & i & j & k \\
\hline
Code & 89 & 90 & 91 & 92 & 93 & 94 & 95 & 96 & 97 & 98 & 99 & 100 & 101 & 102 & 103 & 104 & 105 & 106 & 107 \\
\hline
\end{tabularx}



\begin{tabularx}{\linewidth}{Il*{19}{|X}I}

\hline
Caractère& l & m & n & o & p & q & r & s & t & u & v & w & x & y & z & \{ & | & \} & \verb+~+ \\
\hline
Code & 108 & 109 & 110 & 111 & 112 & 113 & 114 & 115 & 116 & 117 & 118 & 119 & 120 & 121 & 122 & 123 & 124 & 125 & 126\\
\whline
\end{tabularx}
}
\caption{Table des caractères ASCII affichables}
\end{table}

\end{center}





\section{Éléments inversibles de Z$_{\mathbf{n}}$}

Dans la suite, nous noterons $\bbz_n$ l'ensemble $\bbz / n\bbz$.

Dressez  la   table  de   Pythagore  de  $(\bbz_n,\times)$   pour  $n\in
\bigl\{9,11,12\bigr\}$.

Vous créerez une procédure \lstinline+pyth:=proc(n)+ qui dresse la table
de $(\bbz_n,\times)$ en commençant par exemple par:

\begin{lstlisting}
pyth:=proc(n)
 local T,i,j;
 T:=array(1..n-1,1..n-1);
 ........................
   ......................
      T[i,j]:=...........
   ...
 ...
 print(T)
 end:
\end{lstlisting}



On observe par exemple que $
4\times2\equiv4\times5[12]$ mais on n'a pas pour autant $2\equiv5[12]$.

Autre problème : on a $4\times 3\equiv0[12]$, alors que ni 4 ni 3
n'est nul.




Donnez  une condition  nécessaire et  suffisante pour  qu'un  élément de
$(\bbz_n,\times)$ soit inversible.

Créez  une  procédure \lstinline+invm(a,n)+  qui  calcule, s'il  existe,
l'inverse de \lstinline+a+ dans $(\bbz_n,\times)$.

On  pourra  utiliser  la  commande  \lstinline+igcdex(a,b,'u','v')+  qui
renvoie $a\wedge  b$ et qui stocke  des coefficients de  Bézout dans les
variables \lstinline+u+ et \lstinline+v+.

\begin{lstlisting}[caption={}]
> igcdex(7,9,'u','v');
                                  1
> u,v;
                                4, -3
\end{lstlisting}



Comparez \lstinline+invm(a,n)+ avec \lstinline+1/a mod n+... 

\section{Chiffrement affine}


On utilise  encore notre alphabet  de 95 caractères  et on va  coder les
nombres associés par une fonction du style:
$$f~:~x\mapsto ax+b\ [95]$$
où $a$ et $b$ sont des entiers.

En utilisant certaines procédures utilisées précédemment avec le code de César, créez
une  procédure \lstinline+code_affine:=proc(message,a,b)+  qui  code une
message à l'aide de la fonction précédente.




Comment décoder un message?   Créez
une  procédure \lstinline+decode_affine:=proc(crypte,a,b)+  qui  décode un
message crypté à l'aide de la fonction $f~:~x\mapsto ax+b\ [95]$.



\section{Chiffrement de \bsc{Vigenère}}




Blaise de \textsc{Vigenère} naquit  en 1523 à Saint-Pourçain sur Sioule,
célèbre  pour  ses   vins  d'Auvergne.  Il  fit  paraître   en  1586  le
\textit{Traicté      des     chiffres      ou      secrètes     manières
  d'escrire}\footnote{Le  manuscrit est  disponible sur  Gallica}.%  Voici
% une des tables de chiffrement disponible:


% \begin{figure}[h!]
% \begin{center}
%   \includegraphics[width=0.5\linewidth]{table_vigenere}
% \end{center}\caption{Table de chiffrement - \textit{Traicté      des     chiffres      ou      secrètes     manières
%   d'escrire} (1586)}
% \end{figure}


Nous allons  étudier un  cas particulier. Choisissons  une clé  qui peut
être un  mot, une phrase, un  ensemble de phrase, un  livre entier. Pour
nous   simplifier   la   vie,   prenons   par   exemple   la   clé   \og
VENTRILOQUIST\fg{}\footnote{En  plus  d'un  mot  anglais  désignant  une
  personne 
  parlant sans ouvrir la bouche, ce terme était également le nom d'un réseau
  de résistance dirigé par  Philippe de \textsc{Vomécourt} en Sologne et
  qui 
  sabota les  voies de chemin de  fer menant vers la  Normandie à partir
  du 5 juin 44 suite à la réception d'un fameux message codé...}.

On veut chiffrer le message \og LES SANGLOTS LONGS DES VIOLONS DE L'AUTOMNE\fg{}


On a besoin d'un tableau de  chiffrement où on affiche les 26 lettres de
notre alphabet  actuel sur  chaque ligne, en  décalant les  lettres d'un
cran d'une ligne à l'autre.


On peut  le faire à la  main...ou demander à \textsf{Maple}  de le faire
grâce à la commande \verb+Char+ et en travaillant modulo 26.





Retirons les espaces de notre message et disposons les lettres ainsi:

\begin{Verbatim}
LESSANGLOTSLONGSDESVIOLONSDELAUTOMNE
VENTRILOQUISTVENTRILOQUISTVENTRILOQU
\end{Verbatim}

Pour chiffrer le  L, il suffit de regarder dans  notre tableau la lettre
se trouvant sur la ligne du L et la colonne du V: c'est G.

On fait pareil pour le E qui est chiffré en I, le S en F, le S suivant
en L, etc.

Comme c'est assez répétitif, on va utiliser \textsf{Maple} pour faire le sale
boulot. Il  suffit de mathématiser un  peu le travail et  tout sera plus
simple.

Vous devez obtenir par exemple:


\begin{lstlisting}
> code_vige('LESSANGLOTSLONGSDESVIOLONSDELAUTOMNE','VENTRILOQUIST')
            'GIFLRVRZENADHIKFWVAGWEFWFLYIYTLBZADY'
> decode_vige('GIFLRVRZENADHIKFWVAGWEFWFLYIYTLBZADY','VENTRILOQUIST')
              'LESSANGLOTSLONGSDESVIOLONSDELAUTOMNE'
\end{lstlisting}


Plus  la clé est  longue, plus  grande est  la sécurité.  D'ailleurs, le
principe de la machine ENIGMA  était semblable, avec une clé de longueur
$26^n$ où $n$ est le nombre de rotors utilisés.

Auparavant, les  messages étaient cryptés  à l'aide de  clés représentés
par des livres entiers.

Cependant,  si  la  clé  est  trop  courte,  une  étude  statistique  et
arithmétique  permet  de  casser  le  code  comme  le  démontra  Charles
\textsc{Babbage} en  1846, près  de trois siècles  après la  parution du
traité de \textsc{Vigenère}.






\section{Fonction indicatrice d'Euler}

\subsection{Rappel}

Il existe plusieurs définitions  équivalentes de la fonction indicatrice
d'\bsc{Euler} $\f$. Pour être en lien avec ce qui a été vu précédemment,
nous dirons que $\f(n)$ est l'ordre du groupe des inversibles de $\bbz_n$.



Ainsi,  on  obtient  le  théorème  d'\bsc{Euler}: si  $a$  et  $n$  sont
premiers entre eux, $a^{\f(n)}\equiv 1\ [n]$.
\subsection{Théorème chinois}

Notons $\dot{a}[n]$  la classe d'un entier  $a$ modulo $n$.  Soit $n$ et
$k$ deux entiers  premiers entre eux. Voici une  version simplifiée mais
suffisante pour la suite de nos aventures du fameux théorème:

L'application $f$ définie par:


$$ f\colon \begin{array}{rll} \bbz_{nk} & \to & \bbz_n\times\bbz_k\\
  \dot{x}[nk] & \mapsto & \left(\dot{x}[n],\dot{x}[k]\right)
\end{array}
$$

est bien définie et c'est un isomorphisme d'anneaux.

\subsection{Propriétés de $\mathbf{\f}$}


Pouvez-vous le  démonter puis  en déduire que  pour tout  couple $(n,k)$
d'entiers naturels premiers entre eux: $$\f(n\times k)=\f(n)\times \f(k)$$




Soit $p$  un nombre premier  et $n$ un  entier naturel. Prouvez  que $\f
\left(p^n\right)=p^n-p^{n-1}$ puis que, pour tout entier naturel non nul
$k$, $\f(k)=k
\displaystyle\prod_{p\mid k}\left(1-\frac{1}{p}\right)$.

\subsection{Calcul de $\mathbf{\f}$(n)}

Déterminez une procédure \lstinline+eul:=proc(n)+ qui calcule $\f(n)$.


Vous pourrez utiliser la fonction \textsf{Maple} \lstinline+ifactors(n)+
qui renvoie, pour  des entiers positifs non nuls,  une liste contenant 1
et la liste des diviseurs premiers de $n$ et de leur valuation.


Par exemple:

\begin{lstlisting}[caption={}]
> ifactors(60);
                    [1, [[2, 2], [3, 1], [5, 1]]]
\end{lstlisting}


\subsection{Une première application}

Calculez $\f(100)$.


Trouvez, DE TÊTE, les trois derniers chiffres de:

$$7895875463786378378378345453646538978977^{208582714591458551455135135135147454098258258001}$$

Vérifiez directement avec \textsf{Maple}...


Qu'en concluez-vous  sur le calcul de  $x^m[n]$ lorsque $x$  et $n$ sont
premiers entre eux?


\subsection{Résolution de x\up{m}$\ \mathbf{\equiv}$ a \ [n]}

Par  exemple, on  cherche  un entier  $x$  tel que  $x^{130355971}\equiv
3208718\ [9108163]$.



% > m:=130355971:
% > 
% > n:=9108163;
% > 

%                              n := 9108163

% > eul(n);

%                                8628768

% > 1/m mod eul(n);

%                                7274731

% > 

% > k:=1/m mod eul(n);

%                              k := 7274731

% > x:=3208718&^k mod n;

%                              x := 5369492

% > x&^m mod n;

%                                3208718





\section{Deux exercices d'oral de Centrale}

\subsection{Exercice}


Soit    $p$    un   nombre    premier.    Pour    tout   entier    $k\in
\bigl\{1,...,p-1\bigr\}$, on pose:

$$p_k=\frac{(p-1)!}{k(p-k)}$$


\begin{enumerate}
\item  Cette question est  à traiter  à l'aide  d'un logiciel  de calcul
  formel. Les instructions  \lstinline+ithprime+ et \lstinline+numer+ de
  \textsf{Maple} pourront être utiles.

  \begin{enumerate}
  \item       Étudier       la       divisibilité      de       l'entier
    $\displaystyle\sum_{k=1}^{p-1}p_k$  par  $p$  pour  les  20  nombres
    premiers $p$.
  \item On note  $\frac{a_p}{b_p}$ la fraction irréductible représentant
    le rationnel $  \displaystyle\sum_{k=1}^{p-1} \frac{1}{k} $. Étudiez
    la  divisibilité de  $a_p$ par  $p^2$ pour  les 20  premiers nombres
    premiers.


  \end{enumerate}

\item On suppose que le nombre premier  $p$ est supérieur ou égal à 5 et
  on se place  dans le corps $\bbz_p$. On  note $\overline{k}$ la classe
  d'un entier $k\in\bbz$ dans $\bbz_p$.

  \begin{enumerate}
  \item Montrer que $ \overline{(p-1)!}=-1$.
\item  Montrer  que  pour  tout $k\in  \bigl\{1,...,p-1\bigr\}$,  on  a:
  $\overline{p_k}=\left(\overline{k^2}\right)^{-1}$.
\item                   Montrer                   que                  $
  \displaystyle\sum_{k=1}^{p-1}\left(\overline{k^{-1}}\right)^2=\displaystyle\sum_{k=1}^{p-1}\overline{k}^2$. Conclure
  quant à la divisibilité de $ \displaystyle\sum_{k=1}^{p-1}p_k$ par $p$.
  \end{enumerate}

\item Exprimer  $p b_p \displaystyle\sum_{k=1}^{p-1}p_k$  en fonction de
  $a_p$. Qu'en conclut-on?

\end{enumerate}



\subsection{Exercice sur la fonction de \bsc{Möbius}}


La fonction  $ \mu: \bbn^\star\to  \bigl\{-1,0,1\bigr\}$ de \bsc{Möbius}
est  définie   suivant  $\mu(1)=1$  et,  pour  tout   $n  \geqslant  2$,
$\mu(n)=(-1)^r$ si  $n$ est  un produit de  $r$ nombres premiers  deux à
deux  distincts, $  \mu(n)=0$ si  $n$ est  divisible par  le  carré d'un
nombre premier.


\begin{enumerate}
\item  Montrer  que $  \mu$  est  une fonction  \textit{multiplicative},
  c'est-à-dire: $ \mu(1)=1$ et, si $a$ et $b$ sont premiers entre eux, $
  \mu(ab)=\mu(a)\mu(b)$.

\item On note  $ d \mid n$  pour signifier que l'entier naturel  $ d \in
  \bbn^\star$ divise $ n\in \bbn^\star$. Montrer que:
$$\forall n \geqslant 2,\quad \displaystyle\sum_{d \mid n}^{ }\mu(d)=0$$
\item  Calculer  les $  \mu(n)$  pour  $n\in \bigl\{1,2,...,20\bigr\}$  à
  l'aide   de   \textsf{Maple}   \textit{sans  utiliser}   de   commande
  \textsf{Maple}    détectant   les    nombres    premiers   (de    type
  \lstinline+isprime+    par exemple)
\end{enumerate}


\includepdf[pages={1-3}]{X2008}




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