\documentclass[11pt]{amsart}
\usepackage{kbexo}
\course{MAT823 -- Calcul Formel}
\DeclareMathOperator{\Rem}{mod}
\def\Maple{{\sc Maple}\xspace}
\def\L{\mathcal{L}}
\def\thepb{}
\def\exoskip{0pt plus 1pt}
\def\Qskip{0pt plus 1pt}

\begin{document}
\pbtitle{Deuxième session, 15 juin 2007}

\smallskip
\centerline{\bf  Durée 3 heures. Documents interdits, calculettes autorisées.}

\def\B{\mathcal{B}}
\exo $17$ est-il un carré modulo $77$ ?

\exo On choisit l'ordre lexicographique sur les monômes de $\CM[x,y,z]$,
avec $x > y >\nobreak z$.
\qq Calculer un reste de la division de $x^2+xy+yz$ par $(x+y+z,
y^2+yz+z^2,z^3)$.
\qq Parmi les éléments suivants lesquels sont des restes possibles d'une
division de $f\in\CM[x,y,z]$ par les trois polynômes ci-dessus: $2yz+3$,\;
$yz^2+yz+z^2+1$,\; $xyz$?

\exo On dit que l'entier $N > 1$ vérifie la
condition (C) de Carmichael si
\begin{equation}
\tag{C} a^N \equiv a \pmod{N}\quad\text{pour tout $a\in \ZM$}.
\end{equation}
\Q On suppose que $N$ vérifie $(C)$ et que $p$ est un diviseur premier de $N$.
\qq Montrer par l'absurde que $p^2\nmid N$.
\qq Montrer que $p-1 \mid N-1$.

\Q Réciproquement, montrer que tout $N$ vérifiant les deux conditions du 1)
pour tout diviseur premier $p$ de $N$ vérifie (C).

\Q Montrer par l'absurde que, si $N$ vérifie (C), il n'est pas de la forme
$N = pq$, où $p$ et $q$ sont premiers. \hint{On peut supposer
$p < q$; montrer que $p \equiv 1 \pmod{q - 1}$.}

\Q On suppose que $N$ vérifie (C), et qu'il est impair. On écrit $N - 1 = 2^e
q$, $q$ impair, et on applique avec succès le test de non-primalité de
Rabin-Miller à $N$ : on dispose donc de $a\in\ZM/N\ZM$ qui est témoin de
non-primalité. 
\qq Montrer que $a^{N-1} = 1$ ou bien $\pgcd(a,N) > 1$.
\qq Montrer qu'on peut facilement en déduire un facteur non trivial de $N$.
\hint{Dans le cas intéressant, combien de racines carrées de $1$ connaît-on?}

\pb 
Soit $N = pq$ produit de deux nombres premiers impairs distincts; on pose
$T := \log N$. On pourra supposer qu'addition et multiplication dans
$\ZM/N\ZM$ utilisent $\Ot(T)$ opérations élémentaires, ainsi que le calcul du
symbole de Jacobi $\leg{a}{N}$ quand $\abs{a} < N$.

\Q Soit $a\in(\ZM/N\ZM)^*$. Montrer que $a$ est un carré si et seulement
si $\leg{a}{p} = \leg{a}{q} = 1$.

\Q Dans cette question, on veut décider si $a\in(\ZM/N\ZM)^*$ est un carré.
\qq Montrer que si $\leg{a}{N} = -1$, alors $a$ n'est pas un carré.
\qq Montrer que si $\leg{a}{N} = 1$, on ne peut rien dire.
\qq Montrer que, connaissant $a$, $p$ et $q$, on peut répondre à la question
en temps $\Ot(T)$.
\qq Écrire une fonction Maple complète qui prend en argument $a$, $p$,
$q$ comme ci-dessus et répond \kbd{true} ou \kbd{false}.

\Q Dans cette question, on suppose connus $p$ et $q$.
\qq Donner un algorithme probabiliste pour trouver un
$d$ qui ne soit pas un carré dans $\ZM/N\ZM$, \emph{mais} satisfaisant
$\leg{d}{N} = 1$.
\qq Calculer l'espérance du nombre d'essais avant d'obenir $d$.

\Q Le procédé cryptographique RSA fonctionne de la façon suivante:
Alice choisit $N = pq$, ainsi que $d,e$ dans $]2,N[$ tels que $d e\equiv 1
\pmod{\phi(N)}$ et publie $d$ et $N$ (clé publique). Tout un chacun peut
alors chiffrer un message $M\in\ZM/N\ZM$ à destination d'Alice en calculant
$C = M^d$; munie de sa clé privée $e$, Alice déchiffre $C$ en calculant $C^e
= M$. \smallskip

\qq Montrer que $C$ et $M$ sont de taille $O(T)$ puis que chiffrage et
déchiffrage utilisent $\Ot(T^2)$ opérations élémentaires.
\qq On suppose $N$ et $\phi(N) = (p-1)(q-1)$ connus. Écrire un programme
Maple en déduisant $p$ et $q$, sans utiliser de commande de factorisation.

\Q Détailler et commenter le protocole cryptographique suivant:
\begin{quote}
Alice choisit $N = pq$ et $d$ comme au \textbf{3)}: $(d, N)$ est
sa clé publique, et $(p,q)$ sa clé secrète. Pour chiffrer un message,
constitué d'une suite finie $(\e_n)\in \{0,1\}^k$ de $0$ et de $1$, on
construit une suite $(x_n)\in (\ZM/N\ZM)^k$ de la façon suivante: pour $u_n
\in (\ZM/N\ZM)^*$ choisi uniformément au hasard, il pose
$$ x_n := u_n^2 d^{\e_n} $$
et expédie le message chiffré $(x_n)$. Alice, munie de sa clé secrète, peut
facilement décider si $x_n$ est un carré modulo $N$ ou non, et ainsi
déterminer $\e_n$ pour tout $n$.
\end{quote}

\Q Modifier le protocole précédent pour permettre à Alice de donner une
«preuve probabiliste» qu'elle connaît la factorisation de $N = pq$, sans
dévoiler aucune information sur ladite factorisation. Plus précisément, décrire
une épreuve en $k$ étapes qu'Alice n'aurait qu'une chance sur $2^k$ de
réussir si elle répondait au hasard.
\end{document}
