%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt]{article}
\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{times}
% A tribute to the worthy AMS:
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
%
\usepackage{mathrsfs}
\usepackage{wasysym}
\usepackage{url}
%
\theoremstyle{definition}
\newtheorem{comcnt}{Tout}
\newcommand\exercice{%
\refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}}
\newcommand{\limp}{\mathrel{\Rightarrow}}
\newcommand{\liff}{\mathrel{\Longleftrightarrow}}
\newcommand{\pgcd}{\operatorname{pgcd}}
\newcommand{\ppcm}{\operatorname{ppcm}}
\newcommand{\signe}{\operatorname{signe}}
\newcommand{\tee}{\mathbin{\top}}
\newcommand{\Frob}{\operatorname{Fr}}
\DeclareUnicodeCharacter{00A0}{~}
%
\newif\ifcorrige
\corrigetrue
\newenvironment{corrige}%
{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
{{\hbox{}\nobreak\hfill\checkmark}%
\ifcorrige\relax\else\egroup\fi\par}
%
%
%
\begin{document}
\ifcorrige
\title{INFMDI720\\Exercices --- Corrigé\\{\normalsize Rappels mathématiques pour la cryptographie}}
\else
\title{INFMDI720\\Exercices\\{\normalsize Rappels mathématiques pour la cryptographie}}
\fi
\author{}
\date{}
\maketitle
\pretolerance=10000
\tolerance=8000

%
%
%

\exercice

(A) Quel entier entre $0$ et $100$ est congru à $19$ modulo $13$ et à
$13$ modulo $19$ ?

\begin{corrige}
(A) Commençons par trouver un entier qui convient.  On pourrait se
  rendre compte que $19+13 = 32$ convient pour des raisons de
  symétrie.  Pour procéder de façon plus systématique, cherchons une
  relation de Bézout entre $19$ et $13$, qui sont visiblement premiers
  entre eux (et ceci va de toute façon le confirmer) : on a $19 = 1\times 13 +
  6$ puis $13 = 2\times 6 + 1$ donc le pgcd est bien $1$, et on a $1 =
  13 - 2\times 6 = 3\times 13 - 2\times 19$.  Ainsi, d'après un
  résultat du cours (version « effective » du théorème chinois), un
  nombre congru à $19$ (soit $6$) modulo $13$ et à $13$ modulo $19$
  est donné par $3 \times 13 \times 13 - 2 \times 19 \times 6$ : ceci
  vaut $279$, mais pour simplifier les calculs on pouvait calculer
  $3\times 13 \equiv 1 \pmod{19}$ et $-2 \times 6 \equiv 1 \pmod{13}$,
  donc il reste $13 + 19 = 32$.  En tout état de cause, comme $13$ et
  $19$ sont premiers entre eux, les nombres congrus à $x$ modulo $13$
  et à $y$ modulo $19$, quels que soient $x$ et $y$ entiers, forment
  une unique classe de congruence modulo $13 \times 19 = 247$ (qu'il
  n'était pas vraiment nécessaire de calculer, seul importe que ce
  soit $>100$, ce qui est évident), donc dès qu'on a trouvé un nombre
  vérifiant les congruences demandées (en l'occurrence $32$), on sait
  que les autres sont les nombres qui lui sont congrus modulo $13
  \times 19$, et en particulier il n'y en a pas d'autre entre $0$
  et $100$.
\end{corrige}

\ifcorrige\medbreak\else\relax\fi

(B) Quel entier à trois chiffres en base $10$ se termine par $23$ et
est multiple de $19$ ?

\begin{corrige}
(B) Se terminer par $23$ en base $10$ signifie être congru à $23$
  modulo $100$.  Cherchons une relation de Bézout entre $100$ et $19$
  qui sont premiers entre eux : on a $100 = 5\times 19 + 5$ et $19 =
  3\times 5 + 4$ et $5 = 1\times 4 + 1$ donc $1 = 5 - 4 = 4 \times 5 - 19 = 4
  \times 100 - 21 \times 19$.  Ainsi, d'après un résultat du cours
  (version « effective » du théorème chinois), un nombre congru à $23$
  modulo $100$ et à $0$ modulo $19$ (i.e., divisible par $19$) est
  donné par $- 21 \times 19 \times 23$ : ceci vaut $-9177$, mais pour
  simplifier les calculs on pouvait calculer $-21\times 23 \equiv -83
  \equiv 17 \pmod{100}$ et ainsi $- 21 \times 19 \times 23 \equiv 17
  \times 19 = 323 \pmod{1900}$.  Le nombre $323$ répond aux conditions
  demandées, et comme tout les entiers congrus à $23$ modulo $100$ et
  à $0$ modulo $19$ forment une unique classe de congruence
  modulo $1900$, on a trouvé le seul nombre à trois chiffres.
\end{corrige}

\ifcorrige\medbreak\else\relax\fi

(C) Quel entier entre $0$ et $100$ est congru respectivement à
$1,2,3,4$ modulo $2,3,5,7$ ?  (C'est-à-dire : congru à $1$ modulo $2$,
et à $2$ modulo $3$, et à $3$ modulo $5$, et à $4$ modulo $7$.)

\begin{corrige}
(C) Les nombres $2,3,5,7$ sont premiers entre eux deux à deux.
  Commençons par trouver des solutions à deux congruences
  simultanées : comme les nombres sont assez petits, il est plus
  simple de le faire par tâtonnement : par exemple, $5$ est congru à
  $1$ modulo $2$ et à $2$ modulo $3$, cela se trouve immédiatement en
  parcourant les entiers de $0$ à $5$ ou plus astucieusement ceux qui
  vérifient une des deux congruences pour chercher ceux qui vérifient
  l'autre.  Comme on va vouloir mettre ensuite ensemble deux
  congruences de ce genre, il vaut mieux les trouver de même taille
  et, si possible, vérifiant une relation de Bézout simple : le plus
  économique est donc de mettre $2$ avec $7$ et $3$ avec $5$, ce qui a
  le bon goût que $1\times 15 - 1\times 14 = 1$ est une relation de Bézout évidente
  entre $3\times 5$ et $2\times 7$.  Par tâtonnement, on trouve que
  $11$ (et exactement les nombres de sa classe modulo $14$) est congru
  à $1$ modulo $2$ et à $4$ modulo $7$, et que $8$ (et exactement les
  nombres de sa classe modulo $15$) est congru à $2$ modulo $3$ et à
  $3$ modulo $5$.  Avec la relation de Bézout $1\times 15 - 1\times 14
  = 1$, toujours en appliquant la même version « effective » du
  théorème chinois, on voit que les entiers vérifiant les quatre
  congruences demandées sont exactement la classe de $1\times 15\times
  11 - 1\times 14\times 8 = 53$ modulo $15 \times 14 = 210$, donc le
  seul entre $0$ et $100$ est $53$.
\end{corrige}

\ifcorrige\medbreak\else\relax\fi

(D) Déterminer tous les entiers entre $0$ et $2009$ congrus à $1$
modulo chacun des nombres $7$, $11$ et $13$.  (C'est-à-dire : congrus
à $1$ modulo $7$, et à $1$ modulo $11$, et à $1$ modulo $13$.)
(Indication : y-t-il un nombre évident qui répond à cette condition ?)

\begin{corrige}
(D) Comme le suggère l'indication, il y a un nombre évident congru à
  $1$ modulo $7$ et $11$ et $13$ à la fois, c'est $1$ lui-même.  Le
  théorème chinois assure que, comme $7$ et $11$ et $13$ sont premiers
  entre eux deux à deux, les entiers congrus à $1$ modulo chacun d'eux
  forment une classe de congruence modulo $7 \times 11 \times 13 =
  1001$.  Les nombres entre $0$ et $2009$ vérifiant les congruences
  demandées sont donc : $1$, $1002$ et $2003$.
\end{corrige}

\ifcorrige\medbreak\else\relax\fi

(E) Déterminer tous les entiers entre $0$ et $100\,000$ congrus à
$192$ modulo $300$ et à $169$ modulo $305$.

\begin{corrige}
(E) Un entier congru à $192$ modulo $300$ est (comme $5|300$) congru à
  $192 \equiv 2$ modulo $5$, et un entier congru à $169$ modulo $305$
  est (comme $5|305$) congru à $169 \equiv 4$ modulo $5$.  Comme $2
  \not\equiv 4 \pmod{5}$, il n'existe \emph{aucun} entier vérifiant
  les deux congruences demandées.
\end{corrige}

%
%
%

\exercice

(A) Pour chaque élément de $\mathbb{Z}/18\mathbb{Z}$, calculer son
ordre additif et, si cela a un sens, son ordre multiplicatif.  Quels
sont les entiers primitifs modulo $18$ ?

(B) Dresser la table d'un isomorphisme entre le groupe additif
$\mathbb{Z}/n\mathbb{Z}$ (pour un $n$ à déterminer) et le groupe
multiplicatif $(\mathbb{Z}/18\mathbb{Z})^\times$.

(C) Que vaut $7^{333\,333}$ modulo $18$ ?  Que vaut $5^{6\,000\,004}$
modulo $18$ ?

\begin{corrige}
(A)\strut\par{\footnotesize
\begin{tabular}{r|c|c}
&add.&mult.\\\hline
$\bar 0$&$1$&---\\
$\bar 1$&$18$&$1$\\
$\bar 2$&$9$&---\\
$\bar 3$&$6$&---\\
$\bar 4$&$9$&---\\
$\bar 5$&$18$&$6$\\
$\bar 6$&$3$&---\\
$\bar 7$&$18$&$3$\\
$\bar 8$&$9$&---\\
$\bar 9$&$2$&---\\
$\bar{10}$&$9$&---\\
$\bar{11}$&$18$&$6$\\
$\bar{12}$&$3$&---\\
$\bar{13}$&$18$&$3$\\
$\bar{14}$&$9$&---\\
$\bar{15}$&$6$&---\\
$\bar{16}$&$9$&---\\
$\bar{17}$&$18$&$2$\\
\end{tabular}
\par}

Il existe donc des éléments primitifs, il en existe
$\varphi(\varphi(18)) = \varphi(6) = 2$, à savoir $\bar 5$ et
$\bar{11}$.  (Les entiers primitifs modulo $18$ sont donc ceux congrus
à $5$ ou $11$ modulo $18$.)

(B) Une fois choisi un élément primitif, disons $g = \bar 5$,
l'isomorphisme $\mathbb{Z}/6\mathbb{Z} \to
(\mathbb{Z}/18\mathbb{Z})^\times$ est donné par $\bar k \mapsto g^k$,
soit ici :

\begin{tabular}{c|cccccc}
$\bar k \in \mathbb{Z}/6\mathbb{Z}$&$\bar 0$&$\bar 1$&$\bar 2$&$\bar 3$&$\bar 4$&$\bar 5$\\\hline
$g^k \in (\mathbb{Z}/18\mathbb{Z})^\times$&$\bar 1$&$\bar 5$&$\bar 7$&$\bar{17}$&$\bar{13}$&$\bar{11}$\\
\end{tabular}

(C) On vient de voir que l'ordre de $\bar 7$ dans
$(\mathbb{Z}/18\mathbb{Z})^\times$ vaut $3$, donc $7^{3k} \equiv 1
\pmod{18}$ pour tout $k$ et en particulier pour $k = 111\,111$, de
sorte que $7^{333\,333} \equiv 1 \pmod{18}$.  Pour ce qui est de
$5^{6\,000\,004}$, il suffit de chercher la valeur en regard de
$6\,000\,004$ modulo $6$ dans le tableau ci-dessus : on a $5^6 \equiv
1 \pmod{18}$ donc $5^{6\,000\,000} \equiv 1$ donc $5^{6\,000\,004}
\equiv 5^4 \equiv 13 \pmod{18}$.
\end{corrige}

%
%
%

\exercice

(A) Calculer $\varphi(3\,125)$.  Que vaut $2^{5\,000\,000}$
modulo $3\,125$ ?

(B) Que vaut $2^{5\,000\,000}$ modulo $32$ ?

(C) Sachant que $293\times 32 - 3\times 3\,125 = 1$, quels sont les
cinq derniers chiffres en base $10$ de $2^{5\,000\,000}$ ?

\begin{corrige}
(A) On a $3\,125 = 5^5$ donc $\varphi(3\,125) = 4\times 5^4 = 2\,500$.
  Comme $2$ est premier avec $3\,125$, le théorème d'Euler entraîne
  que $2^{2\,500} \equiv 1 \pmod{3\,125}$, donc $2^{5\,000\,000}
  \equiv 1 \pmod{3\,125}$ (puisque $2\,500\,|\,5\,000\,000$).

(B) (Attention à ne pas chercher à appliquer le théorème d'Euler !
  $2$ n'est pas du tout premier avec $32$...)  On a $32 = 2^5$ donc
  $32 | 2^{5\,000\,000}$, c'est-à-dire que $2^{5\,000\,000} \equiv 0
  \pmod{32}$.

(C) Trouver les cinq derniers chiffres de $2^{5\,000\,000}$ en
  base $10$ revient à calculer ce nombre modulo $100\,000 = 10^5 = 2^5
  \times 5^5 = 32 \times 3\,125$.  On vient de le calculer modulo $32$
  (il vaut $0$) et modulo $3\,125$ (il vaut $1$).  Le théorème chinois
  assure donc que $2^{5\,000\,000}$ est, modulo $100\,000$, l'unique
  classe de congruence possible qui vaut $0$ modulo $32$ et $1$
  modulo $3\,125$.  C'est donc $293\times 32 = 1 + 3\times 3\,125 =
  9\,376$.  Les cinq derniers chiffres de $2^{5\,000\,000}$ en
  base $10$ sont donc : $09376$.
\end{corrige}

%
%
%

\exercice

Les nombres $593$ et $1\,187$ sont premiers.

(A) Expliquer brièvement pourquoi, si $b^2 = \bar 1$ avec $b \in
\mathbb{Z}/1187\mathbb{Z}$ alors $b = \bar 1$ ou $b = -\bar 1$
(indication : factoriser $b^2 - \bar 1$).

(B) Quelles sont les valeurs possibles de $a^{593}$ modulo $1\,187$
(pour $a$ un entier quelconque) ?

(C) Montrer que $a^{593} \equiv -1 \pmod{1\,187}$ si et seulement si
$a$ est primitif modulo $1\,187$ \emph{ou} $a \equiv -1
\pmod{1\,187}$.

\begin{corrige}
(A) Si $b^2 = \bar 1$ avec $b \in \mathbb{Z}/1187\mathbb{Z}$, alors
  $(b-\bar 1)(b+\bar 1) = b^2 - \bar 1 = \bar 0$.  Comme
  $\mathbb{Z}/1187\mathbb{Z}$ est un corps (et en particulier, un
  anneau intègre), un produit ne peut être nul que si un des deux
  facteurs est nul, donc soit $b - \bar 1 = \bar 0$, soit $b + \bar 1
  = \bar 0$, c'est-à-dire soit $b = \bar 1$ soit $b = -\bar 1$.

(B) On a $1\,186 = 2\times 593$.  Le théorème d'Euler ou de Fermat
  assure que $a^{1\,186} \equiv 1 \pmod{1\,187}$ pour tout $a$ non
  multiple de $1\,187$, c'est-à-dire $(a^{593})^2 \equiv 1
  \pmod{1\,187}$ : d'après ce qu'on vient de voir, ceci signifie que
  $a^{593}\equiv 1$ ou $a^{593}\equiv -1$.  (Et ces deux cas se
  produisent effectivement, comme le montrent les exemples de $a=1$ et
  $a=-1$.)  Enfin, si $a$ est multiple de $1\,187$, on a évidemment
  $a^{593} \equiv 0^{593} = 0 \pmod{1\,187}$.  Les trois valeurs
  possibles sont donc : $+1, -1, 0$.

(Remarquons que les deux sous-questions ci-dessus n'ont pas utilisé le
  fait que $593$ était premier, et fonctionnaient également en
  remplaçant $1\,187$ par n'importe quel nombre premier $p$ impair et
  $593$ par $(p-1)/2$.)

(C) Tout d'abord, si $a^{593} \not\equiv 0 \pmod{1\,187}$ alors $a$
  n'est pas multiple de $1\,187$, c'est-à-dire qu'il est premier avec
  $1\,187$.  Lorsque c'est le cas, l'ordre multiplicatif de $a$ doit
  diviser $\varphi(1\,187) = 2\times 593$ : les diviseurs de ce nombre
  sont $1$, $2$, $593$ et $1\,186$.  Le seul élément (de n'importe
  quel groupe, noté multiplicativement) dont l'ordre est $1$ est $1$
  (le neutre) ; la première question montre que le seul élément de
  $(\mathbb{Z}/1187\mathbb{Z})^\times$ dont l'ordre est $2$ est $-1$ ;
  si l'ordre de $a$ est $593$ (en particulier, $a$ n'est pas
  primitif), alors $a^{593} \equiv 1 \pmod{1\,187}$.  Enfin, si
  l'ordre de $a$ est $1\,186$, c'est-à-dire si $a$ est primitif, alors
  $a^{593}$ ne peut pas valoir $1$, et doit donc valoir $-1$.  Tout
  ceci mis ensemble, on a bien : $a^{593} \equiv -1 \pmod{1\,187}$ si
  et seulement si $a \equiv -1 \pmod{1\,187}$ ou bien $a$ est primitif
  modulo $1\,187$.
\end{corrige}

%
%
%
\end{document}