\documentclass[10pt]{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, 29 avril 2009}

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

\def\B{\mathcal{B}}

\noindent 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 le corps $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».

\exo 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 utilisant l'identité
$a^{p-1}\equiv 1\pmod 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 $\FM_p$), puis 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, puis comparer les complexités binaires des deux
procédés.

\exo Soit $N > 1$ un entier dont on désire montrer qu'il est \emph{premier}.

\Q Soit $p \mid N-1$ un nombre premier et $e = v_p(N-1)$ la plus grande
puissance de $p$ divisant $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}
On va montrer que tout diviseur $d$ de $N$ vérifie $d \equiv 1 \pmod{p^e}$.
\qq Montrer qu'il suffit de démontrer l'assertion pour tout diviseur $d$
\emph{premier}.

\qq On suppose donc $d\mid N$ premier et on note $o$ l'ordre de $a$ dans
$(\ZM/d\ZM)^*$. Montrer que $o\mid N-1$, mais que $o\nmid (N-1)/p$.
\qq En déduire que $p^e\mid o$ et conclure.

\Q On suppose que $N - 1 = FU$, où $F\geq \sqrt{N}$ est un facteur
dont tous les diviseurs premiers sont connus tel que $(F,U) = 1$, 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}$. \hint{Utiliser le 1) et penser au Lemme
Chinois.}
\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)$
vérifiant la propriété ci-dessus?

\pb
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$. Sous cette hypothèse, 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'hypothèse $n=2^k$ est inoffensive: on peut toujours se ramener
à cette situation.

\qq Pour $0 \leq i \leq k$ et $0 \leq j < 2^{k-i}$, on pose
$\displaystyle M_{i,j} = \prod_{0 \leq \ell < 2^i} \L[j 2^i + \ell]$.

\noindent 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
\footnote{On n'explicitera pas l'implantation de cet arbre; la représentation
standard d'un arbre binaire parfait par un tableau unidimensionnel convient.}
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 considère l'algorithme suivant

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

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

\STATE Si $n = 1$, retourner $N \bmod \L[0]$.
\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 \emph{admet} les deux faits suivants:
\begin{itemize}
\item Le crible d'Ératosthène calcule $\L := \set{p \leq x \colon \text{$p$
premier}}$ en temps $\Ot(x)$,

\item On a $\log \L = \sum_{p \leq x} \log p \sim x$ quand $x\to
\infty$ (théorème des nombres premiers).
\end{itemize}

\qq Comment 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$.
\qq 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, que l'on explicitera) ?

\end{document}
