\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, 27 juin 2006}

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

\def\B{\mathcal{B}}
\exo $17$ est-il un carré modulo $209 = 11 \times 19$ ?

\exo Trouver les solutions dans $\ZM^2$ du système d'équations
$$ 
\left\{
\begin{array}{rcl}
2 x + 5 y & \equiv & 1 \pmod{8},\\
3 x + 2 y & \equiv & 0 \pmod{12}.
\end{array}
\right.
$$

\exo La lettre $N$ désigne un entier $ > 1$. On dit que $N$ 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 Montrer que si $N$ vérifie (C), alors il n'a pas de facteur carré autre
que $1$, et que $(p-1) \mid (N-1)$ pour tout $p$ premier divisant $N$.

\Q Réciproquement, montrer que tout $N$ vérifiant les conditions du 1)
vérifie (C).

\Q Montrer que, si $N$ vérifie (C) et n'est pas premier, alors il a au
moins 3 diviseurs premiers.

\Q On suppose que $N$ vérifie (C), et qu'il est impair. On applique le test
de non-primalité de Rabin-Miller à $N$ et on suppose qu'il est positif, i.e.
qu'on dispose de $a\in\ZM/N\ZM$ qui est témoin de non-primalité. Montrer
qu'on peut facilement en déduire un facteur non trivial de $N$. \hint{Combien
de racines carrées de $1$ connaît-on?}

\pb[Racines modulo $p$]
Soit $p$ un nombre premier \emph{impair}. On exprimera les estimations de
complexité en terme d'opérations élémentaires dans $\FM_p$, en utilisant la
notation $\Ot$ pour ne pas avoir à tenir compte des facteurs logarithmiques
ou des constantes. On rappelle qu'une opération ($+,\times$, division
euclidienne ou pgcd) sur deux polynômes de degré $\leq n$ dans $\FM_p[X]$
utilise $\Ot(n)$ opérations dans $\FM_p$.
\smallskip

\noindent Soit $T\in\FM_p[X]$ unitaire de degré $n > 0$, dont on désire
trouver les racines dans~$\FM_p$.

\Q Écrire une procédure \Maple qui détermine les racines de $T$ dans $\FM_p$
en calculant $T(0)$, $T(1)$, \dots Quelle est sa complexité?

\Q Soit $D := \pgcd(T, X^p - X)$.
\qq Montrer que $D$ est produit de facteurs linéaires dans $\FM_p[X]$, que
ses racines sont simples, et qu'il a les mêmes racines que $T$.
\qq Montrer que $D$ se calcule en $\Ot(n\log p)$ opérations dans $\FM_p$.
\hint{Travailler dans $\FM_p[X]/(T)$.} \medskip

\noindent \emph{On suppose dorénavant que $D = T$ avec les notations de la
question précédente, c'est-à-dire que $T$ est scindé à racines simples, de
degré $n > 1$.}

\Q Soit $A$ la $\FM_p$-algèbre $\FM_p[X]/(T)$. On pose $t := (p-1)/2$.
\qq Utiliser le lemme chinois pour montrer que $A\cong(\FM_p)^n$ comme
$\FM_p$-algèbre.

\qq Montrer que tout $a\in A$ vérifie $a^p = a$, et donc $a (a^t-1)(a^t+1) =
0$.

\def\a{\alpha}
\def\b{\beta}
\Q\label{qq} Si $a$, $a^t-1$, $a^t+1$ sont simultanément non-nuls, $a\in A$
est dit \emph{bon}, et \emph{mauvais} sinon.
\qq Soit $u\in\FM_p[X]$ tel que la classe de $u$ dans $A$ soit un diviseur de
zéro\footnote{Si $R$ est un anneau, on dit que $a\in R\setminus\set{0}$ est
\emph{diviseur de $0$} s'il existe $b\in R\setminus\set{0}$ tel que $ab =
0$.}. Montrer que $\pgcd(u, T)$ est un facteur \emph{propre} de $T$,
c'est-à-dire différent de $1$ et de $T$.

\qq Montrer qu'un bon $a$ permet de calculer un diviseur de $0$ dans $A$,
puis d'en déduire un facteur propre de $T$.
\qq Un représentant de degré minimal dans $\FM_p[X]$ de $a\in A$ étant
donné, quelle est la complexité du test «$a$ est-il bon?»
\qq Montrer que $a^t = 1$ et $a^t = -1$ ont tous deux $t^n$ solutions $a\in A$.
\qq En déduire que, si on choisit $a$ uniformément au hasard dans $A$,
la probabilité que $a$ soit mauvais est $(2t^n + 1)/p^n$. Montrer que
cette dernière quantité est toujours inférieure à $1/2$ ($p > 2$, $n > 1$).

\Q Montrer que l'algorithme suivant est correct:

\vskip 0.1cm plus 0.1cm
\hrule
\smallskip
\begin{algorithmic}[1]
\REQUIRE $T\in\FM_p[X]$ unitaire, scindé sur $\FM_p$, $p$ impair.
\ENSURE la liste des racines de $T$.

\STATE Si $\deg T = 1$, retourner $-T(0)$.
\REPEAT
\STATE tirer $a$ uniformément au hasard dans $A = \FM_p[X]/(T)$ 
\UNTIL{$a$ est mauvais.}
\STATE Soit $D$ le facteur propre (unitaire) de $T$ associé au bon $a$.
Effectuer deux appels récursifs avec pour arguments $D$ et $T/D$ et
retourner la concaténation des résultats.
\end{algorithmic}
\smallskip
\hrule
\vskip 0.2cm plus 0.1cm

\Q On modélise le fonctionnement de l'algorithme pour une suite de tirages de
$a$ (supposés uniformes et indépendants) par un arbre dont chaque noeud est
étiqueté par un polynôme $T$, et correspond au tirage d'un $a$. La racine 
est le polynôme d'origine. Si $a$ est mauvais, le noeud a un fils unique
étiqueté par le même $T$. Et deux noeuds étiquetés par $D$ et $T/D$ sinon.
\qq Soit $\a_i$ et $\a_j$ deux racines distinctes de $T$. Montrer que, si on
tire $a$ uniformément au hasard dans $A$, il est bon \emph{et} sépare $\a_i$
et $\a_j$ avec probabilité $1 - (1 + 2t^2)/p^2 \geq 1/2$.
\qq En déduire que la probabilité que $\a_i$ et $\a_j$ ne soient
pas séparées après $k$ tirages est $\leq 2^{-k}$.
\qq* L'algorithme s'arrète une fois que les $n$ racines sont séparées. Montrer
que la probabilité $p_k$ que l'on ne se soit pas arrêté après $k$ tirages
est $O(n^2 2^{-k})$, puis que l'espérance de la hauteur de l'arbre
est $O(\log n)$. 
\hint{Noter qu'il existe des suites infinies de tirages tels que
l'algorithme ne termine pas. On vient de montrer qu'elles sont rares.}
\qq* Montrer que l'algorithme complet utilise en moyenne $\Ot(n\log p)$
opérations pour factoriser $T$.
\end{document}
