\documentclass[12pt]{report}
\usepackage{kbexo}
\course{Arithmétique -- M1MA7W01}
\formation{Master 1 CSI}
\num{3}
%\def\exoskip{5pt plus 15pt minus 1pt}

\begin{document}
\exotitle
\exo Donner une construction d'un corps fini de cardinal $2^5 = 32$.

\exo Soit $A$ un anneau commutatif et $a,b$ deux entiers $>0$. Donner la
caractéristique des anneaux suivants:
$$\QM,\quad \RM,\quad \ZM/a\ZM,\quad \ZM/a\ZM\times \ZM/b\ZM,\quad A[X].$$

%\exo La caractéristique d'un corps est $0$ ou un nombre premier.
%Trouver un contre-exemple à la réciproque, c'est-à-dire un anneau commutatif
%de caractéristique~$0$ ou~$p$ premier qui n'est pas un corps.

\exo On considère $P = X^3+X+1$ et $Q = X^3+X^2+1$ dans $\FM_2[X]$.
\Q Montrer $P$ et $Q$ sont irréductibles.
\Q Soit $K = \FM_2[X]/\gen{P}$. Trouver les racines de $Q$ dans le corps $K$.
\Q En déduire un isomorphisme explicite $\FM_2[X]/\gen{Q} \to \FM_2[X]/\gen{P}$.

\exo Soit $L/K$ une extension de corps, et $a,b\in L$ algébriques sur $K$.
On note $K' = K(a)$ .
\Q Montrer que les extensions $K'/K$ et $K'(b)/K'$ sont de degré fini.
\Q En déduire que $a+b$ et $ab$ sont algébriques sur $K$, puis que l'ensemble
$\set{x\in L\colon \text{$x$ algébrique sur $K$}}$ est un corps.

\exo Soit $\FM_q$ un corps fini de caractéristique impaire.
\Q Quelles sont les solutions de l'équation $x^2 = 1$ dans $\FM_q$?
\Q En déduire le nombre de \emph{carrés} dans $\FM_q^*$, puis que
les carrés de $\FM_q^*$ sont exactement les racines de l'équation
$x^{(q-1)/2} = 1$.
\Q Quels sont les carrés de $\FM_{2^k}$ ?

\exo Soit $q \equiv 3 \pmod{4}$ une puissance d'un nombre premier. Montrer
que si $a\in \FM_q^*$ est un carré, alors $a^{(q+1)/4}$ est une racine carrée
de $a$. \hint{Utiliser l'exercice~5.}

\exo Soit $q$ une puissance d'un nombre premier et $d$ un diviseur de $q - 1$. 
\Q On rappelle que le groupe multiplicatif $\FM_q^*$ est cyclique. Montrer
que l'équation $x^d = 1$ a exactement $d$ solutions dans $\FM_q$.
\Q Montrer que les puissances $d$-ièmes dans $\FM_q$ sont exactement les
$(q-1)/d$ solutions de l'équation $x^{(q-1)/d} = 1$.

\exo[Chiffrement de Pohlig-Hellman] Soit $K = \FM_q$ un corps fini et $m\in
K^*$ un message clair. On choisit une clé secrète $k \in \ZM/(q-1)\ZM$, qui
définit l'opération de chiffrement $f:m \mapsto m^k$. 
\Q Quelle hypothèse faire sur $k$ pour que le déchiffrement soit possible ?
(Pour tout $y\in K^*$, il existe $m\in K^*$ unique tel que $y = f(m)$.)
\Q* Connaissant $k$, comment déchiffrer efficacement $f(m)$ ? Estimer la
complexité du déchiffrage.
\quad\hint{Introduire $d$ tel que $k d \equiv 1\pmod{q-1}$.}

\exo[Logarithme discret] Soit $K$ le corps fini à $q$ éléments et $g\in K^*$
un élément d'ordre $N$, engendrant un sous-groupe cyclique $G\subset K^*$.
\Qqq Expliquer pourquoi l'application
\begin{align*}\exp_g \colon (\ZM/N\ZM, +) & \to (G,\times)\\
 x &\mapsto g^x
\end{align*}
est bien définie, et pourquoi elle réalise un isomorphisme.
\qq Montrer que pour $x\in \ZM/N\ZM$, on peut calculer $g^x$ en utilisant
$O(\log N)$ multiplications. \hint{Écrire $x$ en base $2$.}

\Q On note $\log_g \colon (G,\times)\to (\ZM/N\ZM,+)$ son inverse,
qui à $g^x$ associe $\bar{x}$. Montrer que $\log_g (ab) = \log_g(a) +
\log_g(b)$ pour tout $a,b\in G$.

\Q Les deux systèmes suivants reposent sur l'asymétrie  entre le calcul
de $\exp_g$ (facile) et de $\log_g$ (pas d'algorithme en temps polynomial
connu).
\qq [\,Diffie-Hellman\,] Alice et Bob choisissent chacun de leur côté un
exposant secret, respectivement $a$ et $b$. Ils se communiquent $g^a$ et
$g^b$, via un canal dont la sécurité n'est pas garantie. Expliquer comment
ils peuvent chacun reconstituer la «clé partagée» $g^{ab}$, à partir des
informations dont ils disposent respectivement. Détailler le problème que
doit résoudre un attaquant qui veut reconstituer la clé.

\qq [\,Elgamal\,] Alice choisit une clé secrète $c\in \ZM/N\ZM$ et publie $h
= g^c$. Bob souhaite lui envoyer le «message» $m\in K^*$; il tire $k$ au
hasard dans $\ZM/N\ZM$ et transmet le couple $(g^k, m h^k)$. Expliquer
comment Alice peut en déduire $m$.

\Q*[Algorithme de Pohlig-Hellman] Pour calculer $\log_g h$, où $h\in G$, il
faut résoudre l'équation $g^x = h$, où $0 \leq x < \text{ord}(g) = N$. Soit $d$ un diviseur
de $N$ et $e = N/d$.
\qq Montrer qu'il existe $0 \leq x_0 < e$ et $0 \leq x_1 < d$ tels que
$x = x_1 e + x_0$.
\qq Montrer que $x_0 = \log_{g^d} (h^d)$ et $x_1 = \log_{g^e} (hg^{-x_0})$.
\qq Expliquer en quoi cette décomposition aide à calculer $\log_g h$.
\end{document}
