\documentclass[11pt,a4paper]{article}
\usepackage{t1enc}
\usepackage{amsmath,amssymb,amsthm,amscd,graphicx}
\pagestyle{empty}
\usepackage[frenchb]{babel}
\usepackage[utf8]{inputenc}

\newcommand{\ov}{\overline}
\newcommand{\N}{\mathbb{N}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\ZZ}{\mathbb{Z}}
\def\ds{\displaystyle}
\newcommand{\mathframe}[1]{\fbox{$#1$}}
\def\ima{\mathrm{Im}}

\topmargin-2.8cm
\oddsidemargin-2.4mm
\textwidth17.5cm
\textheight26.7cm
\parskip=3pt
\parindent=0pt

\pagestyle{empty}

\def\soluce#1{} % n'affiche pas les indications de solutions

\begin{document}



\noindent
UGA, mat309  \hfill Feuille de TD 2 \hfill 2020-2021

\vspace{0.5cm}

{\bf Exercice 1}
\begin{enumerate}
\item
Calculer le reste dans la division euclidienne par 7 des nombres 561, 143 et $561\times 143$.

\item
D{\'e}terminer le reste de la division euclidienne de $(8\times 20 +12)\times(5+13\times 52)^2$
par 7.

\item
D{\'e}terminer le reste de la division euclidienne de $(30\times 14 -27\times 18)-5\times(15\times4-13\times 19)^3$
par 13.

\item
D{\'e}terminer le reste de la division euclidienne de $(2^8+1)\times (2^7-1)$ par $2^6$.

\item
D{\'e}terminer le reste de la division euclidienne de $10^{100}$ par 13.

\soluce{On peut faire trois méthodes. Par Lagrange, $10^{12}=1[13]$ donc
$10^{100}=10^{8\times 12+4}=10000[13]$ et $10000=3[13]$. Par exponentielle rapide,
$10^2=9[13]$, $10^4=3[13]$, $10^8=9[13]$, $10^{16}=3[13]$, $10^{32}=9[13]$, $10^{64}=3[13]$
donc $10^{100}=10^{64+32+4}=81=3[13]$. En testant les puissances, on a $10^3=-1[13]$ donc
$10^{100}=10^{3x33+1}=(-1)^{33}\times 10=-10=3[13]$.}

\item
D{\'e}terminer le chiffre des unit{\'e}s de $3^{12}$.

\soluce{$3^2=-1[10]$.}

\item
On veut d{\'e}terminer le chiffre des unit{\'e}s de $7^{7^7}$.
\begin{enumerate}
\item
Montrer que $7^4\equiv 1~[10]$.
\item
D{\'e}terminer le reste de la division euclidienne de $7^7$ par 4.
\item
Conclure.
\end{enumerate}
\end{enumerate}

\vspace{0.2cm}

{\bf Exercice 2~: crit{\`e}res de divisibilit{\'e}.}\\
Soit $x$ un entier positif. On consid{\`e}re l'{\'e}criture d{\'e}cimale $a_ra_{r-1}...a_0$ de $x$,
telle que $$x = a_r.10^r+ a_{r-1}.10^{r-1}+...+a_0$$
\begin{enumerate}
\item
Montrer que $x$ est divisible par 2 si et seulement si $a_0$ est divisible par 2.

\item
Montrer que $x$ est divisible par 3 si et seulement si $a_r+...+a_0$ est divisible par 3.

\item
Montrer que $x$ est divisible par 4 si et seulement si l'entier d'{\'e}criture d{\'e}cimale $a_1a_0$ est divisible par 4.

\item
Montrer que $x$ est divisible par 5 si et seulement si $a_0$ est divisible par 5.

\item
Montrer que $x$ est divisible par 9 si et seulement si $a_r+...+a_0$ est divisible par 9.

\item
Montrer que $x$ est divisible par 11 si et seulement si $a_0-a_1+...+(-1)^ra_r$ est divisible par 11.
\end{enumerate}

\vspace{0.2cm}

{\bf Exercice 3}
\begin{enumerate}
\item
\'Ecrire les tables de multiplication de $\ZZ/7\ZZ$, $\ZZ/9\ZZ$ et $\ZZ/10\ZZ$. % $\ZZ/8\ZZ$

\item
Donner la liste des {\'e}l{\'e}ments inversibles de ces anneaux et expliquer les propri{\'e}t{\'e}s suivantes :
\begin{enumerate}
\item
les lignes et colonnes correspondant aux {\'e}l{\'e}ments inversibles contiennent tous les {\'e}l{\'e}ments
de l'anneau, repr{\'e}sent{\'e} une et une seule fois.

\item
Les lignes et colonnes correspondant aux {\'e}l{\'e}ments non inversibles contiennent une suite p{\'e}riodique.

\item
La derni{\`e}re ligne et la derni{\`e}re colonne, correspondant {\`a} $\overline{n-1}$ dans $\ZZ/n\ZZ$, contient tous les {\'e}l{\'e}ments
de $\ZZ/n\ZZ$ rang{\'e} dans l'ordre inverse de l'ordre usuel.
\end{enumerate}

\item
\'Ecrire la table du groupe $(\ZZ/10\ZZ)^*$.
\end{enumerate}

\vspace{0.2cm}

{\bf Exercice 4}
R{\'e}soudre les {\'e}quations suivantes en $\overline{x}$ :
\begin{enumerate}
\item
$\overline{4}\times \overline{x}=\overline{3}$ dans $\ZZ/6\ZZ$.
\hskip 30pt
\item
$\overline{4}\times \overline{x}=\overline{2}$ dans $\ZZ/6\ZZ$.
\hskip 30pt
\item
$\overline{4}\times \overline{x}=\overline{3}$ dans $\ZZ/7\ZZ$.

\item
$\overline{3}\times \overline{x}=\overline{0}$ dans $\ZZ/9\ZZ$.
\hskip 30pt
\item
$\overline{4}\times \overline{x}=\overline{6}\times \overline{x}$ dans $\ZZ/10\ZZ$.

\item
D{\'e}terminer tous les entiers $x\in \ZZ$ tels que le reste de la division euclidienne
de $4x$ par 7 vaut 3.
\end{enumerate}

{\bf Exercice 5}
Dans le pays A, on ne dispose que de pi\`eces de valeurs 13  et de
pi\`eces de valeur 5.

\begin{enumerate}
\item Quelles sont les solutions de $13x+5y=47$ o\`u $x$ et $y$
appartiennent \`a $\Z$ ?
 \item J'ach\`ete un produit qui a pour valeur 47. Puis-je le payer sans
que l'on me rende la monnaie ?
 \item M\^eme question avec 49.
 \item J'ach\`ete un produit qui a pour valeur 16. Puis-je le payer si
on me rend la monnaie ?
 \item Montrer que pour $n\in\N$, il existe un unique couple $(x,y)$
d'entiers tels que $0\leq x\leq 4$ et $n=13x+5y$.
 \item Montrer que tout achat de produit de valeur plus grande que 48
peut \^etre pay\'e sans rendu de monnaie.
 \item
 Soit $a$ et $b$ deux entiers naturels premiers entre eux.
 
Ecrire un programme en langage naturel donnant le nombre de pi\`eces
de valeur $a$ et de pi\`eces de valeur $b$ permettant si c'est
possible de payer un produit de valeur $n$ sans rendu de monnaie. On
supposera que l'on dispose d'une fonction donnant l'identit\'e de
B\'ezout de $a$ et $b$.
\end{enumerate}


{\bf Exercice 6}
D{\'e}terminer tous les entiers $x$ tels que $x^2=3 \pmod 6$.

{\bf Exercice 7}
\begin{enumerate}
\item
Montrer que si $x$ est un entier impair, alors $x^2=1 \pmod 8$.

\item
Montrer que si $x$ est un entier pair, alors $x^2=0 \pmod 8$ ou $x^2=4
\pmod 8$.

\item
En d{\'e}duire les solutions en $x$ et $y$ entiers de l'{\'e}quation
$x^2+y^2=2 \pmod 8$.

\item
R{\'e}soudre les {\'e}quations suivantes en $x$, $y$ entiers :
\begin{enumerate}
\item
$x^2+y^2=3 \pmod 9$,

\item
$x^2+y^2=5 \pmod 9$.
\end{enumerate}
\end{enumerate}

{\bf Exercice 8}
\`A l'aide de l'algorithme d'exponentiation rapide, d{\'e}terminer :
\begin{enumerate}
\item
$\overline{2}^{65}$ dans $\ZZ/53 \ZZ$.
\item
$\overline{3}^{231}$ dans $\ZZ/53 \ZZ$.
\item
$\overline{7}^{231}$ dans $\ZZ/238 \ZZ$.
\end{enumerate}
Impl\'ementer l'algorithme d'exponentiation rapide (par exemple
la version r\'ecursive) et v\'erifiez
les r\'esultats obtenus .

{\bf Exercice 9}
Les {\'e}l{\'e}ments suivants sont-ils des inversibles ? des diviseurs de z{\'e}ro ?
\begin{enumerate}
\item
$\overline{4}$ dans $\ZZ/22\ZZ$.

\item
$\overline{7}$ dans $\ZZ/16\ZZ$.

\item
$\overline{3}$ dans $\ZZ/10\ZZ$.

\item
$\overline{21}$ dans $\ZZ/30\ZZ$.

\item
$\overline{26}$ dans $\ZZ/45\ZZ$.
\end{enumerate}

{\bf Exercice 10}
Montrer que $\overline 2$, $\overline 3$, $\overline 4$ et $\overline 5$ sont inversibles dans $\ZZ/13\ZZ$ et
d{\'e}terminer les sous-groupes de $(\ZZ/13\ZZ) ^*$ engendr{\'e}s  par $\overline 2$, 
$\overline 3$, $\overline 4$ et $\overline 5$.

{\bf Exercice 11}
Montrer que $\overline{4}$ dans $\ZZ/41\ZZ$  est inversible et donner son inverse. 
D{\'e}terminer l'ordre de $\overline{4}$ dans $(\ZZ/41\ZZ)^*$.
D{\'e}terminer le reste de la division euclidienne de $4^{2017}$ par 41.

{\bf Exercice 12}
\begin{enumerate}
\item Montrer que $\ZZ/89\ZZ$ est un corps.

\item
Que peut-on dire, par le th{\'e}or{\`e}me de Lagrange, sur l'ordre possible des {\'e}l{\'e}ments de $(\ZZ/89\ZZ)^*$ ?

\soluce{Il divise 88, donc vaut 1,2,4,8,11,22,44 ou 88 (on a $2^k.11^l~|~2^3.11$ si et seulement si $k\leq 3$, $l\leq 1$).}

\item
D{\'e}terminer les ordres des {\'e}l{\'e}ments $\overline 2$, $\overline 4$, $\overline 8$ et $\overline 12$ dans $(\ZZ/89\ZZ)^*$.
\end{enumerate}

{\bf Exercice 13}
D{\'e}terminer $\overline{3}^{1025}$ dans $\ZZ/509\ZZ$ par deux m\'ethodes
diff\'erentes~: le
th{\'e}or{\`e}me de Lagrange et l'algorithme d'exponentiation rapide.

{\bf Exercice 14}
On se place dans l'anneau $\ZZ/201\ZZ$.
\begin{enumerate}
\item
Calculer  $\overline{2}^{261}$ sans factoriser 201.

\item
Calculer $\varphi(201)$. 

\item
Montrer que $\overline{2}$ est inversible dans $\ZZ/201\ZZ$,
d{\'e}terminer l'ordre de $\overline{2}$ dans le groupe $(\ZZ/201\ZZ)^*$ et calculer
$\overline{2}^{261}$ en utilisant son ordre.

\item V\'erifiez que 5 est inversible modulo $\varphi(201)$
et d\'eterminez son inverse $s$. Calculer $32^s \pmod 201$
directement et en utilisant le fait que $32=2^5$.

\soluce{$201=3\times 67$, $\varphi(201)=132$. $\overline{2}$ est d'ordre 66. On peut dire $\overline{2}^{261}=2^{-3}$ et par l'algorithme d'Euclide {\'e}tendu
$\overline{8}\inv = \overline{-15}=\overline{156}$.}
\end{enumerate}

{\bf Exercice 15}
On se place dans l'anneau $\ZZ/391\ZZ$.
\begin{enumerate}
\item
Calculer $\overline{2}^{390}$ sans factoriser 391. Qu'en d{\'e}duit-on ?

\soluce{$\overline{2}^{390}=\overline{285}$. Donc 391 n'est pas premier.}

\item
D{\'e}terminer $\varphi(391)$. 

\item
Montrer que $\overline{2}$ est inversible dans $\ZZ/391\ZZ$ et
d{\'e}terminer l'ordre de $\overline{2}$ dans le groupe $(\ZZ/391\ZZ)^*$.

\soluce{$391=17\times 23$, $\varphi(391)=352=32\times 11$. $\overline{2}$ est d'ordre 88.}
\end{enumerate}

{\bf Exercice 16}
On se place dans $\ZZ/49\ZZ$.
\begin{enumerate}
\item
Quel est le cardinal de $(\ZZ/49\ZZ)^*$ ?
\item
Que peut-on en d{\'e}duire sur l'ordre des {\'e}l{\'e}ments de $(\ZZ/49\ZZ)^*$ ?
\item
D{\'e}terminer l'ordre de $\overline{2}$ puis l'ordre de $\overline{3}$ dans $(\ZZ/49\ZZ)^*$.
\item
En d{\'e}duire qu'il existe $n\in \N$ tel que $\overline{3}^n=\overline{2}$.
\end{enumerate}

{\bf Exercice 17}
D\'eteminer un g\'en\'erateur du groupe multiplicatif $(\ZZ/103\ZZ)^*$

{\bf Exercice 18}
Soit $p$ un nombre premier.
\'Ecrire un algorithme permettant de trouver un g\'en\'erateur de $(\ZZ/p\ZZ)^*$.

{\bf Exercice 19}
On prend au hasard un entier $a\in\{1,...,17063\}$. 
Quelle est la probabilit{\'e} que $a$ soit un diviseur de $17063$ ?
un entier non premier {\`a} $17063$ ?

{\bf Exercice 20}
On se place dans $\ZZ/143\ZZ$.
\begin{enumerate}
\item
D{\'e}terminer $\varphi(143)$.

\soluce{$\varphi(11\times 13)=10\times 12=120$.}

\item
Pour quels entiers $x$ a-t-on $x^{142}\equiv 1~[143]$ ?
Indication : {\`a} l'aide du th{\'e}or{\`e}me d'Euler-Fermat, se
ramener {\`a} une {\'e}quation plus simple 
en $x$, et la r{\'e}soudre en factorisant 143 et en appliquant les
restes chinois.

\soluce{Supposons $x^{142}\equiv 1~[143]$. Cette {\'e}quation montre que $x$ est inversible dans $\ZZ/143\ZZ$.
On a donc par Euler-Fermat $x^{\varphi(143)}=x^{120}\equiv 1~[143]$. Donc $x^{pgcd(142,120)}\equiv x^2\equiv 1~[143]$.
Cela {\'e}quivaut {\`a} $143\;|\; (x-1)(x+1)$. Donc $143\;|\; x-1$, ou $143\;|\; x+1$, ou $11\;|\; x-1$ et $13 \;|\; x+1$,
ou $11\;|\; x+1$ et $13 \;|\; x-1$. Les deux premiers cas donnent $x\equiv \pm 1~[143]$. Le troisi{\`e}me cas
est $x\equiv 1~[11]$ et $x\equiv -1~[13]$, le TRC dit que c'est {\'e}quivalent {\`a} $x\equiv 12~[143]$.
Le quatri{\`e}me cas
est $x\equiv -1~[11]$ et $x\equiv 1~[13]$, le TRC dit que c'est {\'e}quivalent {\`a} $x\equiv 131~[143]$.
On peut aussi dire que $(x-1)(x+1)\equiv 0~[143]$ {\'e}quivaut {\`a} $(x-1)(x+1)\equiv 0~[11]$ et $(x-1)(x+1)\equiv 0~[13]$,
puis on raisonne sur les corps $\ZZ/11\ZZ$ et $\ZZ/13\ZZ$.
}

\item
On appelle {\it menteur} de Fermat d'un entier $n$ non premier les entiers $x\in\{0,\dots,n-1\}$
tels que $x^{n-1}\equiv 1~[n]$.
\\
Combien 143 a-t-il de menteurs de Fermat ? de t{\'e}moins de Fermat ? Quels sont les autres {\'e}l{\'e}ments dans $\{0,\dots,142\}$ ?

\soluce{4 menteurs, 116 t{\'e}moins, 23 {\'e}l{\'e}ments non inversibles dans $\ZZ/143\ZZ$.}
\item Facultatif~: m\^eme question en utilisant le test de Miller-Rabin 
\item
On tire 5 fois de suite au hasard un nombre $x\in\{0,\dots,142\}$ et on teste si $x^{142}\equiv 1~[143]$ (test de primalit{\'e} de Fermat).
Quelle est la probabilit{\'e} qu'au moins un nombre parmi eux montre que 143 n'est pas premier ?

\soluce{$1-({4\over 143})^5\simeq 1-1,7.10^{-8}$.}

\end{enumerate}

{\bf Exercice 21} \'Ecrire un algorithme effectuant le test de
primalit\'e de Fermat pour un entier $n$ donn\'e et $N$ entiers
$a$ tir\'es au hasard. On renverra 0 d\`es qu'un test renvoie non
premier, sinon on renverra 1.

{\bf Exercice 22}
\begin{enumerate}
\item
Montrer que pour tout entier impair $x$, on a $x^4\equiv 1~[16]$.
Indication : distinguer les cas $x\equiv 1 ~[4]$ et $x\equiv -1 ~[4]$.

\soluce{C'est plus fort que le th{\'e}or{\`e}me d'Euler-Lagrange car $\varphi(16)=8$.
On {\'e}crit $x=4k\pm 1$, on {\'e}l{\`e}ve {\`a} la puissance 4 et la formule du bin{\^o}me
donne le r{\'e}sultat.
}

\item
En d{\'e}duire que le groupe $(\ZZ/16\ZZ)^*$ n'est pas cyclique.
\soluce{$\card (\ZZ/16\ZZ)^*=8$ mais il n'y a pas d'{\'e}l{\'e}ment d'ordre 8 dans $(\ZZ/16\ZZ)^*$.}

\end{enumerate}

{\bf Exercice 23}
\begin{enumerate}
\item
Montrer que pour tout entier $x$ premier avec 10, on a $x^{4000}\equiv 1~[10000]$.

\soluce{D{\'e}j{\`a} $x\wedge 10^4=1$ {\'e}quivaut {\`a} $x\wedge 10=1$ d'apr{\`e}s les r{\'e}sultats vus en TD sur le pgcd ou la factorisation
en nombres premiers de 10000. Puis $\varphi(10000)=\varphi(2^4\times 5^4)=4000$, donc c'est le th{\'e}or{\`e}me d'Euler-Fermat.}

\item
Pour quels entiers $x$ a-t-on $x^{9999}\equiv 1~[10000]$ ?

\soluce{$4000\wedge 9999=1$ donc $x^{9999}\equiv 1~[10000]$ {\'e}quivaut {\`a} $x\equiv 1~[10000]$.
Donc tous les entiers de 2 {\`a} 9999 sont des t{\'e}moins de Fermat de 10000 !}

\item
Montrer que pour tout entier $x$ premier avec 10, on a $x^{500}\equiv 1~[10000]$.
Indication : utiliser le th{\'e}or{\`e}me des restes chinois. 

\soluce{D{\'e}j{\`a} $x$ premier avec 10 {\'e}quivaut {\`a} $x$ premier avec 2 et 5, donc avec 4 et 125.
Par le TRC, $x^{500}\equiv 1~[10000]$ {\'e}quivaut {\`a} $x^{500}\equiv 1~[2^4]$ et $x^{500}\equiv 1~[5^4]$.
D'apr{\`e}s la premi{\`e}re question, $x^{500}\equiv (x^4)^{125}\equiv 1~[2^4]$ et comme
$\varphi (5^4)=4\times 5^3=500$, la seconde {\'e}galit{\'e} est vraie par Euler-Fermat. 
}
\end{enumerate}

{\bf Exercice 24: nombre de Carmicha{\"e}l.}
On se place dans l'anneau $\ZZ/561\ZZ$.
\begin{enumerate}
\item
Calculer $\overline{2}^{560}$, $\overline{5}^{560}$.

\item
Montrer que 561 n'est pas premier et d{\'e}terminer $\varphi(561)$.

\soluce{$561=3\times 11\times 17$.}

\item
En utilisant l'isomorphisme du th{\'e}or{\`e}me des restes chinois, montrer que pour tout $a\in(\ZZ/561\ZZ)^*$,
on a $a^{80}=\overline{1}$.

\item
En d{\'e}duire que pour tout $a\in(\ZZ/561\ZZ)^*$, on a $a^{560}=\overline{1}$.
\\
Ceci montre qu'il n'y a pas de t{\'e}moin de Fermat pour l'entier 561, qui n'est pourtant pas premier. On dit que
561 est un nombre de Carmicha{\"e}l.

\item
D{\'e}terminer l'ordre de $\overline{2}$ et l'ordre de $\overline{5}$ dans $\ZZ/561\ZZ$.

\soluce{ord(2)=40 et ord(5)=80. Travailler dans $\ZZ/3\ZZ\times \ZZ/11\ZZ\times \ZZ/17\ZZ$.}
\end{enumerate}

{\bf Exercice 25} \'Ecrire un algorithme d\'eterminant la liste des nombres de
Carmichael (i.e. les entiers $n>1$ tels que $n$ n'est pas premier
mais $a^{n-1}=1 \pmod n$ si $a$ et $n$ sont
premiers entre eux) plus petits qu'un entier $N$ fix\'e. 

{\bf Exercice 26} 
En utilisant le test de Miller-Rabin, v\'erifiez que 561 n'est pas
premier. D\'eterminez tous les entiers $a \in [1,560]$ qui passent le test de
Miller-Rabin pour 561, v\'erifiez qu'il y a (nettement) moins d'un
quart de valeurs de $a$ qui renvoient Vrai pour ce test.

{\bf Exercice 27}
Montrer que les relations suivantes dans $\ZZ$ sont des relations d'{\'e}quivalence. Existe-il une loi $+$
sur l'ensemble quotient $\ZZ/\sim$ telle pour tous entiers $a,b$, on a $Cl(a)+Cl(b)=Cl(a+b)$ ?
\begin{enumerate}
\item
$a\sim b$ si et seulement si $a$ et $b$ ont m{\^e}me chiffre des unit{\'e}s dans leurs {\'e}critures d{\'e}cimales.

\item
$a\sim b$ si et seulement si $a$ et $b$ ont m{\^e}me chiffre des
dizaines dans leurs {\'e}critures d{\'e}cimales.
\end{enumerate}

{\bf Exercice 28}
On consid{\`e}re l'application suivante~:
$$ 
\Phi : 
\left\{ \begin{array}{ccc} 
\ZZ/20\ZZ & \rightarrow & \ZZ/4\ZZ \times \ZZ/5\ZZ\\
\overline{x} & \rightarrow & (\overline{x},\overline{x})
\end{array} \right.
$$
o{\`u} $\overline{x}$ d{\'e}signe la classe de l'entier $x$ dans l'anneau consid{\'e}r{\'e}.
\begin{enumerate}
\item Expliquez rapidement pourquoi $\Phi$ est bien d\'efinie
\item
Donner les images par $\Phi$ de tous les {\'e}l{\'e}ments de
$\ZZ/20\ZZ$ et 
v{\'e}rifier que $\Phi$ est bien une bijection.

\soluce{On peut dire que les images sont deux {\`a} deux distinctes, donc $\Phi$ est injective, donc bijective pour raison
de cardinal.}

\item
R{\'e}soudre de deux mani\`eres~:
\begin{enumerate}
\item
$\left\{\begin{array}{cccc}
x&\equiv&2&[4]\\
x&\equiv&4&[5]
\end{array}
\right.$
\hskip 25pt
\item
$\left\{\begin{array}{cccc}
x&\equiv&1&[4]\\
x&\equiv&2&[5]
\end{array}
\right.$
\end{enumerate}
\item
On munit l'ensemble $\ZZ/4\ZZ \times \ZZ/5\ZZ$ des lois $+$ et $\times$ d{\'e}finies par 
$$(x,y)+(x',y')=(x+x',y+y'),~(x,y)\times(x',y')=(x\times x',y\times y').$$
\begin{enumerate}
\item
Montrer que $+$ et $\times$ sur $\ZZ/4\ZZ \times \ZZ/5\ZZ$ poss{\`e}de des {\'e}l{\'e}ments neutres.

\item
On admet (v{\'e}rification facile) que $\ZZ/4\ZZ \times \ZZ/5\ZZ$ est un anneau pour les lois $+$ et $\times$.
Montrer qu'un {\'e}l{\'e}ment $(\overline{x},\overline{y})$ de $\ZZ/4\ZZ \times
\ZZ/5\ZZ$ est inversible si 
et seulement si $\overline{x}$ est inversible dans $\ZZ/4\ZZ$ et $\overline{y}$ est inversible dans $\ZZ/5\ZZ$

\item
D{\'e}terminer les {\'e}l{\'e}ments inversibles de $\ZZ/20\ZZ$ et ceux
de 
$\ZZ/4\ZZ \times \ZZ/5\ZZ$, et montrer
qu'ils sont en relation par $\Phi$.

\item
Trouver l'inverse de $\overline{13}$ dans $\ZZ/20\ZZ$ en utilisant l'image par $\Phi$ de $\overline{13}$ dans $\ZZ/4\ZZ \times \ZZ/5\ZZ$.
Justifier le r{\'e}sultat trouv{\'e} en calculant $\Phi(\overline{13}.\overline{13}^{-1})$.

\soluce{$\Phi(\overline{13})=(\overline{1},\overline{3})$, $(\overline{1},\overline{2})$ est l'inverse de $(\overline{1},\overline{3})$ dans $\ZZ/4\ZZ \times \ZZ/5\ZZ$
et $\Phi\inv (\overline{1},\overline{2}) =\overline{17}$, donc $\overline{17}$ est l'inverse de $\overline{13}$ dans $\ZZ/20\ZZ$ car
$\Phi(\overline{13}.\overline{17})=\dots=(\overline{1},\overline{1})$.}
\end{enumerate}
\end{enumerate}


{\bf Exercice 29~: chiffrement affine}

Soit $n$ un entier, $n\geq 2$.
Pour tous $a,b\in \ZZ/n\ZZ$, on d{\'e}finit l'application $\Phi_{a,b}$
sur $\ZZ/n\ZZ$ par~:
$$ \Phi_{a,b}(x)=ax+b$$
\begin{enumerate}
\item
Trouver une condition n{\'e}cessaire et suffisante pour que $\Phi_{a,b}$ soit bijective.

\soluce{Si $a$ est inversible, $ax+b=y~\Leftrightarrow x=a\inv (y-b)$. Si $\Phi_{a,b}$ est bijective,
l'ant{\'e}c{\'e}dent de $1+b$ donne l'inverse de $a$.}

\item
On prend $n=27$ et on code l'alphabet de la mani{\`e}re suivante :

\smallskip
\centerline{$\llcorner\hskip -2pt\lrcorner$
(espace) $\leftrightarrow~\overline{0}$, $A\leftrightarrow~\overline{1}$, $B\leftrightarrow~\overline{2}$, ..., $Z\leftrightarrow~\overline{26}$.}

\medskip
Lorsque la fonction $\Phi_{a,b}$ est inversible, elle peut {\^e}tre utilis{\'e}e comme application de chiffrement.
C'est le {\it chiffrement affine} sur $\ZZ/27\ZZ$, de clef $(a,b)$ priv{\'e}e (cryptographie sym{\'e}trique).

\begin{enumerate}
\item En utilisant la clef $(\overline{4},\overline{21})$, coder la phrase : {\small LA CLEF EST DANS LE COFFRE}

\soluce{OYUFONRUNPTUJYWPUONUF RRLN}

\item
\`A l'aide d'une analyse de fr{\'e}quence, d{\'e}chiffrer le cryptogramme suivant utilisant un chiffrement affine sur $\ZZ/27\ZZ$ :

\smallskip
\centerline{\small RKCTP ILUAPCHPTCHOGGPPTCGCPTACWKTCEKLKGAUPCWKLC PC MUXXLPZPGA}

\soluce{LA SECURITE DES DONNEES N EST PAS GARANTIE PAR CE CHIFFREMENT}

\item
Combien y a-t-il de clefs possibles pour le chiffrement affine sur $\ZZ/27\ZZ$ ?

\soluce{il y a $\card ((\ZZ/27\ZZ)^*\times \ZZ/27\ZZ)=\varphi(27)\times 27= 486$ clefs possibles.}
\end{enumerate}
\end{enumerate}

{\bf Exercice 30~: Logarithme discret}
On se place dans $\ZZ/11\ZZ$.
\begin{enumerate}
\item
Montrer que $(\ZZ/11\ZZ)^*$ est un groupe cyclique engendr{\'e} par $\ov{2}$.
\item
Dans ce groupe, calculer le logarithme en base $\ov{2}$ de $\ov{3}$.
\end{enumerate}

%%%%%%%%%%%%

{\bf Exercice 31~: Attaque sur le logarithme discret.}\\
On consid{\`e}re le nombre premier 101 et on cherche, s'il existe, un entier $x\in \NN$ tel que $3^x=2~[101]$.
\begin{enumerate}
\item
D{\'e}terminer $\phi(101)$ et le factoriser en nombres premiers.

\item
\`A l'aide de l'algorithme d'exponentiation modulaire, calculer $3^4$, $2^4$, $3^{25}$ et $2^{25}$ modulo 101.

\item
Montrer {\`a} l'aide du th{\'e}or{\`e}me d'Euler-Fermat que $(3^4)^{25}=1~[101]$.

\item
D{\'e}terminer des entiers $a$, $b$ tels que $(3^4)^a=2^4$ et $(3^{25})^b=2^{25}$ modulo 101
(pour d{\'e}terminer $a$, on pourra chercher les puissances successives de $3^4$ modulo 101).

\item
Montrer qu'il existe un entier $x$ tel que $x=a~[25]$ et $x=b~[4]$. Calculer un tel entier $x\geq 0$.

\item
V{\'e}rifier que pour cet $x$, on a $3^x=2~[101]$ (on pourra soit effectuer le calcul {\`a} l'aide de
l'algorithme d'exponentiation modulaire, soit utiliser le calcul de $x$ et les propri{\'e}t{\'e}s de $a$ et $b$).

\end{enumerate}


{\bf Exercice 32}
Bob propose le syst{\`e}me de chiffrement RSA. Il choisit $p=17$ et
$q=13$ donc $n=221$.
\begin{enumerate}
\item
D{\'e}terminer $\varphi(n)$.

\item
V{\'e}rifier qu'il peut utiliser $e=7$ comme exposant de chiffrement.

\item
Calculer l'exposant de d{\'e}chiffrement $d$. 

\item
Quelle est la clef publique~? quelle est la clef priv{\'e}e~?

\item
Chiffrer $M=3$.

\item
Que doit calculer Bob pour d{\'e}chiffrer $C=198$ et quel est le
r{\'e}sultat?
\end{enumerate}

{\bf Exercice/TP RSA}\\
Cf. \verb|www-fourier.ujf-grenoble.fr/~parisse/mat249/rsa231.pdf|


%\section{Cryptographie RSA (12 points)}
{\bf Cryptographie RSA, probl\`eme donn\'e en juin 21}\\
{\bf Premi\`ere partie}, un exemple~:\\
On rappelle que pour crypter un message $a$ \`a un
destinataire dont la clef publique est $(c,n)$, il faut lui envoyer
$b=a^c \pmod n$. Pour pouvoir faire les calculs, on suppose  dans cette question
que $c=17, n=55$. 
\begin{enumerate}
\item Crypter le message $a=3$ en donnant le
d\'etail des calculs par la m\'ethode de la puissance rapide.
\item D\'eterminer $\phi(n)$, le nombre d'\'el\'ements inversibles dans
  $\Z/n\Z$ pour $n=55$.
\item D\'eterminer $d$ l'inverse de 17 modulo $\phi(55)$ en donnant les
  \'etapes interm\'ediaires.
\item D\'eterminer $b^d \pmod n$.
\item Pourquoi ne doit-on pas prendre $n=55$ si on souhaite que le message
cod\'e reste confidentiel~?
\end{enumerate}

{\bf Deuxi\`eme partie}, utiliser 3 comme clef publique.\\
Ici $n$ n'est plus \'egal \`a 55, c'est le produit de deux nombres
premiers quelconques. 
On se propose de prendre $c=3$.
\begin{enumerate}
\item \`A quelle condition sur $\phi(n)$ peut-on prendre $c=3$~?
\item Comparer le nombre d'op\'erations n\'ecessaires au cryptage d'un
message lorsque $c=3$ avec $c=17$.
\item \'Ecrire un algorithme en langage naturel ou en C ou en Python
permettant de connaitre le nombre d'op\'erations n\'ecessaires au
cryptage en fonction de $c$.
\item Un espion envoie le m\^eme message $a$ \`a
trois destinataires diff\'erents, ayant chacun leur 
clef publique $c=3,n_1=187$, $c=3,n_2=46$ et $c=3,n_3=253$
(on a pris des petites valeurs de $n$ pour que les calculs soient
faisables \`a la calculatrice).
Les services de contre-espionnage arrivent
\`a intercepter les trois messages cod\'es~: 
$$ b_1= 98 \pmod{187}, \quad b_2= 15 \pmod{ 46}, \quad b_3= 126 \pmod
{145}$$
Il s'agit de d\'eterminer $a$ {\em sans chercher \`a factoriser les entiers $n_i$}.
\begin{enumerate}
\item Montrer qu'il existe un unique entier $b \in [0,n_1n_2n_3[$ tel que
$$b=b_1 \pmod {n_1}, \quad  b=b_2 \pmod {n_2}, \quad b=b_3 \pmod{ n_3}$$
\item Expliquer comment calculer $b$, et donner le d\'etail des calculs
  si vous avez le temps,
\item On trouve $b=9261$, en d\'eduire $a$ sachant que $a \in [0,n_1[$.
\end{enumerate} 
\end{enumerate}

\end{document}

