\documentclass[12pt]{article}
\usepackage{kbexo}
\course{MHT633 -- Arithmétique et Cryptologie}
\num{3}

\begin{document}
\exotitle[Compléments d'arithmétique]
\medskip

\exo[Théorème Chinois]
\noindent Dans le livre de Sun Zi, le Sunzi Suanjing datant du IIIe siècle,
on trouve le problème suivant :
\begin{quote}
Combien l'armée de Han Xing comporte-t-elle de soldats si, rangés par 3
colonnes, il reste 2 soldats, rangés par 5 colonnes, il reste 3 soldats et,
rangés par 7 colonnes, il reste 2 soldats ?
\end{quote}
La résolution proposée par Sun Zi pour le problème des soldats est la suivante :
\begin{quote}
Multiplie le reste de la division par 3, c'est-à-dire 2, par 70, ajoute lui
le produit du reste de la division par 5, c'est-à-dire 3, par 21 puis ajoute
le produit du reste de la division par 7, c'est-à-dire 2, par 15. Tant que le
nombre est plus grand que 105, retire 105.
\end{quote}
La solution n'explique pas très clairement la méthode utilisée. Nous allons
formaliser les choses:

\Q Soient $a$ et $b\in\ZM$ deux entiers non nuls premiers entre eux.
Si $n\neq 0$, on note $x_n$ la classe de $x$ dans $\ZM/n\ZM$. Montrer que
l'application
$$
\begin{array}{llll}
\Phi \colon & \ZM/ab\ZM & \longrightarrow & \ZM/a\ZM\times \ZM/b\ZM\\
 & x_{ab} & \longmapsto & (x_a,x_b)
\end{array}
$$
est bien définie.
\Q Montrer qu'il s'agit d'un isomorphisme d'anneaux et déterminer sa réciproque.

\Q Généraliser à $r$ entiers non nuls $a_1$, $a_2$, \ldots, $a_r$ premiers
entre eux deux à deux.

\Q Résoudre le problème de Sun Zi et retrouver la solution proposée. 

\Q Résoudre le problème suivant :
\begin{quote}
Une bande de 17 pirates possède un trésor constitué de pièces d'or d'égale
valeur. Ils projettent de se les partager également, et de donner le reste au
cuisinier chinois. Celui-ci recevrait alors 3 pièces. Mais les pirates se
querellent, et 6 d'entre eux sont tués. Un nouveau partage donnerait au
cuisinier 4 pièces. Dans un naufrage ultérieur, seuls le trésor, 6 pirates et
le cuisinier sont sauvés, et le partage donnerait alors 5 pièces d'or à ce
dernier. Quelle est la fortune minimale que peut espérer le cuisinier s'il
décide d'empoisonner le reste des pirates ?
\end{quote}

\exo[Indicatrice d'Euler] 
\noindent Soit $\phi$ la fonction indicatrice d'Euler définie sur $\ZM_{>0}$
par
$$\phi(n) = \abs{
  \set{
    k\in\ZM_{>0}\colon 1\leq k \leq n\text{ et }\pgcd(k,n)=1
  }
}.$$
\Q Montrer que $\phi(n)$ est le cardinal de $(\ZM/n\ZM)^*$.
\Q Soit $p$ un nombre premier et $k\in\ZM_{>0}$. Calculer $\phi(p)$ et
$\phi(p^k)$.
\Q Se servir du théorème chinois pour établir que si 
$$ n = \prod_{i=1}^r p_i^{e_i}$$
est la décomposition en produit de facteurs premiers de $n$ on a
$$\phi(n)
  = \prod_{i=1}^r(p_i-1)p_i^{e_i-1}
  = n\prod_{i=1}^r\paren{ 1-\frac{1}{p_i} }.$$
\Q Soit $n$, $a\in \ZM_{>0}$ tels que $\pgcd(a,n)=1$. Montrer que 
$$ a^{\phi(n)}\equiv 1 \pmod{n}.$$
Ce résultat généralise le petit théorème de Fermat. 

\Q En déduire une façon de calculer l'inverse de $x_n$ dans $(\ZM/n\ZM)^*$
(même notation que dans l'exercice 1), qui ne fasse pas appel à l'algorithme
d'Euclide étendu. Application : calcul de l'inverse de $7_{15}$ dans
$(\ZM/15\ZM)^{*}$. 

\exo[Exponentiation binaire]
\Q Montrer que $35$ est inversible modulo $129$.
\Q Calculer l'inverse de $35$ modulo $129$ à l'aide de l'algorithme d'Euclide.
\Q Calculer le maintenant par la méthode de l'exercice précédent.
\Q Écrire un algorithme récursif permettant de calculer $a^k\pmod{n}$ de
façon économique, en distinguant les cas $k$ pair / impair, puis en se
ramenant à un problème du même type après une mise au carré.

\exo[Ordre d'un élément dans un groupe abélien fini]

Soit $G$ un groupe abélien fini. On note multiplicativement sa loi de
composition interne et $e$ son élément neutre. On rappelle que l'ordre d'un
élément $g$ de $G$ est le plus petit entier $k\geq 1$ tel que $a^k=e$. On
pourra poser $\abs{G} = n$.

\Q Dans cette question (et uniquement dans celle-ci) on suppose $G$ cyclique de générateur $g$. Quel est l'ordre d'un élément quelconque $g^r$ ?  

\Q Montrer que si les ordres de $a$ et $b\in G$ sont premiers entre eux, $ab$ a pour ordre leur produit.

\Q Soit $H = \gen{a, b}$ le sous-groupe de $G$ engendré par deux
éléments $a$ et $b$. Montrer qu'il existe $g\in H$ d'ordre le ppcm
des ordres de $a$ et $b$.

\hint{Indication: noter $\prod p_i^{e_i}$ la décomposition en produit de
facteur premiers du ppcm en question; pour chaque $i$, déterminer un
$g_i\in H$ d'ordre $p_i^{e_i}$.}

\Q Soit $\omega$ le ppcm des ordres des éléments de $G$. Déduire de la
question précédente qu'il existe $g\in G$ d'ordre $\omega$ et
que $\omega$ divise $\abs{G}$.

\Q En déduire que tout sous-groupe multiplicatif fini $G$ d'un corps
commutatif $K$ est cyclique.

\noindent\hint{Indication: remarquer que tout $x\in G$ est racine de 
$X^\omega-1$ et en déduire que $\omega=\abs{G}$.}

\exo{Travail dans $\FM_{16}$} 
\Q Trouver dans $\FM_2[X]$ tous les polynômes irréductibles de degrés 1, 2, 3
et 4. 

\def\e{\varepsilon}
\def\w{\omega}
\Q On considère le polynôme $P(X)=X^4+X+1$ qui est irréductible dans
$\FM_2[X]$ et l'on pose $$\FM_{16}=\FM_2[X]/(P(X)),$$ 
qui est un corps à 16 éléments. Vérifier que $\w=X\bmod P(X)$ engendre
$\FM_{16}^*$. On dressera la liste des puissances de $\w$ sous la forme
de $4$-uplets $[\e_3,\e_2,\e_1,\e_0]$, où
$\e_i\in \FM_2$, représentant l'élément $\sum_{i=0}^3\e_i\w^i$.
Par exemple
$$\w^5 = \w^2+\w = [0,1,1,0].$$

\Q À l'aide de ce codage, coder $\w^{57}\cdot \w^{18}$ puis
$\w^{13}+\w^{11}+\w^8+\w^2+1$ et calculer les comme
puissances de $\w$. 

\Q En déduire des règles de calcul simples et commencer à dresser les tables
d'addition et de multiplication de $\FM_{16}$.

\Q Identifier un corps à 4 éléments dans $\FM_{16}$. 

\Q À chaque indice $i$ ($1\leq i\leq 14$) on associe $j$ ($1\leq j\leq 14$) tel que $$\w^j=1+\w^i.$$ 
Montrer qu'un tel $j$ est bien défini et qu'alors on a $\w^i=\w^j+1$.

\Q On écrira alors $i\longleftrightarrow j$ et on parlera de correspondance
de Zech. Dresser la liste des correspondances de Zech de $\FM_{16}$.

\Q Montrer que le recours à ces correspondances peut ramener le calcul de
sommes de puissances de $\w$ à celui beaucoup plus simple de produits de
puissances de $\w$.
\end{document}
