\documentclass[a4paper,11pt]{amsart}
\usepackage{kbexo}
\pagestyle{empty}
\course{MHT812 -- Master}
\def\ANNEE{2007--2008}
\begin{document}
\pbtitle{Devoir Surveillé, 5 mars 2008}
\smallskip

\begin{center}
Durée 1h30. Documents interdits.
\end{center}
\thispagestyle{empty}

\noindent
On rappelle que si $a$ et $b$ sont deux entiers de longueurs $\leq l$ (c'est-à-dire vérifiant $\vert a\vert,\,\vert b \vert<2^l$), la complexité binaire des opérations suivantes est en $\tilde{O}(l)$ : $a\pm b$, $a\times b$, division euclidienne de $a$ par $b$, algorithme d'Euclide (étendu ou non) appliqué à $a$ et $b$. 

\exo[Inversion modulaire via Fermat]
Soient $p$ un nombre premier et $a$ un entier vérifiant $0<a<p$.
\Q Montrer comment calculer l'inverse de $a$ modulo $p$ en se servant du petit théorème de Fermat. On rappelle que ce dernier 
s'énonce : $a^{p-1}\equiv 1\mod p$.  
\Q Rédiger l'algorithme correspondant. On fera bien sûr appel à l'exponentiation binaire.
\Q Estimer, en fonction de $p$, la complexité algébrique (nombre d'opérations dans $\mathbb Z$) et la complexité binaire de cet algorithme.
\Q Rappeler comment se servir de l'algorithme d'Euclide étendu pour résoudre le même problème d'inversion.
\Q Comparer les complexités binaires des deux procédés d'inversion.
\medskip

\exo[Newton linéaire]
Soient $\phi\in {\mathbb Z}[X]$ et $p$ un nombre premier. Soient également $s$ et $g\in{\mathbb Z}$ vérifiant 
\begin{enumerate}
\item[(i)]{$\phi(g)\equiv 0 \mod p^k$, pour un entier $k\geq 1$ donné}
\item[(ii)]{$s\phi'(g)\equiv 1\mod p$.} 
\end{enumerate}
\smallskip
On définit $h$ par $h\equiv g-s\phi(g)\mod p^{k+1}$.
\smallskip
\Q Montrer que $\phi(h)\equiv 0\mod p^{k+1}$, $h\equiv g\mod p^k$ et $s\phi'(h)\equiv 1 \mod p$.
\Q En déduire un algorithme qui, à partir de $s$ et $g\in\mathbb Z$ vérifiant 
\begin{enumerate}
\item[(a)]{$\phi(g)\equiv 0 \mod p$}
\item[(b)]{$s\phi'(g)\equiv 1 \mod p$,} 
\end{enumerate}
permet de trouver $h\in \mathbb Z$ vérifiant 
\begin{enumerate}
\item[(1)]{$\phi(h)\equiv 0 \mod p^l$}
\item[(2)]{$h\equiv g\mod p$,}
\end{enumerate}
où $l\geq 1$ est un entier donné. 
\Q Soient $P$ un polynôme de $\mathbb Z[X]$ de degré $m$ et $a\in\mathbb Z$. 
Estimer la complexité algébrique (nombre d'opérations dans $\mathbb Z$) de l'évaluation de $P$ en $a$ en fonction de $m$. 
\Q Soit $n$ le degré de $\phi$. Estimer la complexité algébrique (nombre d'opérations dans $\mathbb Z$) 
de l'algorithme décrit en {\bf 2)} en fonction de $l$ et $n$.
\medskip

\exo[Lemme chinois]
On cherche $f\in {\mathbb F}_5[X]$ vérifiant
$$(S)\;\left\{\begin{array}{rlll}
f & \equiv & 1 &\mod x+1\\
xf &\equiv & x+1&\mod x^2+1\\
(x^2-1)f & \equiv & x+1 &\mod x^3+1.
\end{array}
\right.$$
\Q Transformer $(S)$ en un système équivalent ne comportant que des congruences de la forme $f\equiv \nu\mod \mu$ avec $\nu,\mu\in {\mathbb F}_5[X]$.
\Q Montrer que les $\mu$ précédemment obtenus sont premiers entre eux deux à deux.
\Q Montrer que $(S)$ admet une unique solution $g$ de degré $<5$ et décrire l'ensemble de toutes les solutions $f$ de $(S)$.
\Q Calculer $g$.
\end{document}
