\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{Examen, 05 mai 2006}

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

\def\B{\mathcal{B}}
\exo Soit $N = 143$ et $\B = \set{2,3,5}$. On remarque que dans $\ZM/N\ZM$,
on a $17^2 = 3$, $19^2 = 3 \times 5^2$ et $21^2 = 2^2 \times 3$. En
\emph{déduire} une identité $x^2 = y^2$ exhibant un facteur non trivial
de $N$.

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

\exo Soit $N > 1$ un entier.

\Q Soit $p \mid N-1$ un nombre premier et $e := v_p(N-1)$. On suppose
qu'il existe $a\in \ZM$ vérifiant
\begin{itemize}
\item $a^{N-1}\equiv 1\pmod{N}$,
\item $\pgcd\paren{a^{(N-1)/p} - 1, N} = 1$.
\end{itemize}
Montrer que tout diviseur $d$ de $N$ vérifie $d \equiv 1 \pmod{p^e}$.
\hint{On peut supposer $d$ premier; introduire l'ordre de $a$ dans
$(\ZM/d\ZM)^*$.}

\Q On suppose que $N - 1 = FU$, où $F\geq \sqrt{N}$ est un facteur
dont tous les diviseurs premiers sont connus, et que pour chaque $p\mid
F$, on connaît $a(p)$ vérifiant les propriétés du 1). Soit $d > 1$ un
diviseur de $N$.
\qq Montrer que $d \equiv 1\pmod{F}$.
\qq En déduire que $d > \sqrt{N}$, puis que $N$ est premier.

\Q On suppose $N$ premier, et on fixe $p\mid N-1$. Tirant $a$ uniformément
au hasard dans $[1,N]$, quelle est la probabilité de trouver un $a(p)$
convenable?

\pb[Multi-évaluation] Dans les estimations de complexité, on utilisera 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 $K[X]$ utilise $\Ot(n)$ opérations élémentaires dans $K$.
Une opération sur deux entiers de valeur absolue $\leq 2^n$ utilise
$\Ot(n)$ opérations élémentaires sur des chiffres. Dans les deux cas, on
dira «en temps $\Ot(n)$» au lieu de «en utilisant $\Ot(n)$ opérations
élémentaires». On note $a \Rem b$ le reste de la division euclidienne de
$a$ par $b$.

\Q Soit $P\in K[X]$ non constant, et $\L = [x_0, \dots, x_{n-1}]\in K^n$
une liste d'éléments de $K$.
\qq Écrire une procédure \Maple qui teste si $P(x_i)\neq 0$ pour tout
$0\leq i < n$.
\qq Majorer la complexité de cette procédure, en fonction de $\deg P$ et
$n$.

\Q Soit $N>0$ un entier et $\L = [x_0, \dots, x_{n-1}] \in \ZM^n$ une liste
de $n$ entiers $> 1$.

\qq Écrire une procédure \Maple qui teste si $N$ n'est divisible par
aucun $x\in \L$.

\qq Expliquer pourquoi on peut supposer que les éléments de $\L$ sont
inférieurs à $N$. Majorer la complexité de cette procédure, en fonction de
$\log N$ et $n$.

\Q Expliquer en quoi les deux questions précédentes résolvent
essentiellement le même problème.

\Q On se concentre désormais sur le cas $N\in \ZM$, $\L\in\ZM^n$, plus
facile à décrire, et on s'intéresse plus généralement à l'ensemble des $N
\Rem \L[i]$. On suppose dans toute la suite que $\#\L = n = 2^k$ est une
puissance de $2$.

\qq Montrer que l'on peut toujours se ramener à $n = 2^k$.

\qq Pour $0 \leq i \leq k$ et $0 \leq j < 2^{k-i}$, on pose
$$ M_{i,j} = \prod_{0 \leq \ell < 2^i} \L[j 2^i + \ell].$$
Si $k = 3$, dessiner l'arbre binaire naturel dont les noeuds sont les
$M_{i,j}$ et tel que chaque noeud contienne le produit de ses deux fils.

\qq Montrer que l'ensemble des $M_{i,j}$ se calculent en temps $\Ot(\log
\L)$, où la taille totale $\log \L$ de la liste $\L$ est définie par
$\log \L := \sum_{i \leq n} \log \L[i]$.

\qq Écrire une procédure \Maple calculant tous les $M_{i,j}$.

\Q On suppose que les $M_{i,j}$ sont précalculés, stockés sur un arbre
organisé de telle sorte que l'on puisse détacher le sous-arbre gauche ou
droit de la racine, respectivement associés à la première ou deuxième
moitié de $\L$, en temps négligeable. On ne s'intéressera pas à
l'implantation de l'arbre\footnote{La représentation standard de la
structure de tas par un tableau unidimensionnel convient.}. On considère
l'algorithme suivant

\vskip 3pt\hrule\vskip 3pt
\begin{algorithmic}[1]
\REQUIRE $N\in \ZM_{>0}$, un arbre des $M_{i,j}$ associé à une liste $\L\in
\ZM^n$. On suppose que $\log N < \log \L$ et $n = 2^k$.

\ENSURE La liste des $N \Rem \L[i]$, $0\leq i < n$.

\STATE Si $n = 1$, retourner $N$.
\STATE Soit $r_0 \leftarrow N \Rem M_{k-1,0}$. Calculer récursivement
les $r_0 \Rem \L[i]$, $0\leq i < n/2$.
\STATE Soit $r_1 \leftarrow N \Rem M_{k-1,1}$. Calculer récursivement
les $r_1 \Rem \L[i]$, $n/2\leq i < n$.
\STATE Renvoyer la concaténation des résultats.
\end{algorithmic}
\vskip 3pt\hrule\vskip 3pt

\qq Détailler le passage «Calculer récursivement\dots». Avec quelles entrées
rappelle-t-on la fonction ?

\qq Montrer que l'algorithme est correct et calcule les $N\Rem \L[i]$
en temps $\Ot(\log \L)$.

\Q On rappelle que le crible d'Ératosthène calcule $\L := \set{p \leq x \colon
\text{$p$ premier}}$ en temps $\Ot(x)$, et que $\log \L = \sum_{p \leq x}
\log p \sim x$ quand $x\to \infty$.

\qq Montrer que l'on peut trouver tous les facteurs premiers de $N$
inférieurs à $\log N$ en temps $\Ot(\log N)$.

\qq Comparer avec la méthode naïve de division successive par les éléments
de~$\L$. Utilisant la méthode récursive, à quel coût détecte-t-on \emph{tous}
les facteurs premiers de $N$ (dans le cas le pire) ?

\end{document}
