\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, 04 mai 2007, 8h30 -- 11h30}

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

\noindent Les trois exercices d'application et le problème sont indépendants.
\emph{On demande que les questions 1.a) et 1.b) du Problème soient abordées.}

\def\B{\mathcal{B}}
\exo Soit $N = 187$ et $\B = \set{2,3,5}$. On remarque que dans $\ZM/N\ZM$,
on a 
\begin{eqnarray*}
37^2  & = & 2^2\times 3 \times 5,\\
149^2 & = & 3^3 \times 5,\\
163^2 & = & 3 \times 5.
\end{eqnarray*}
En \emph{déduire} une identité $x^2 = y^2$ exhibant un facteur non trivial de
$N$.

\exo On désire trouver tous les polynômes $A, B, C\in\FM_2[x]$ tels que
\begin{equation}\tag{$*$}\label{eq}
(x+1)A + x^2 B + C = 1
\end{equation}
\Q Trouver une matrice $U\in \Gl_3(\FM_2[x])$, c'est-à-dire $3\times 3$
et inversible, telle que
$$ \begin{pmatrix} (x+1) & x^2 & 1\end{pmatrix} U
 = \begin{pmatrix} 1 & 0 & 0\end{pmatrix}.
$$
\Q On pose 
$$
 \begin{pmatrix} a \\ b \\ c\end{pmatrix} :=
 U^{-1}\begin{pmatrix} A \\ B \\ C\end{pmatrix}.
$$
Décrire l'ensemble des $a,b,c\in \FM_2[x]$ et en déduire l'ensemble des 
$(A,B,C)$ solutions de l'équation \eqref{eq}.

\exo Soit $I$ l'idéal de $\CM[x,y,z]$ engendré par $x+y+z$, $y^2 + yz + z^2$
et $z^3$.
\Q On choisit l'ordre lexicographique sur les monômes de $\CM[x,y,z]$,
avec $x > y >\nobreak z$. Calculer un reste de la division de $x^2 + xy^2$
par les 3 polynômes ci-dessus. On rappellera la condition que doit vérifier le
reste.
\Q Étant donné $f\in \CM[x,y,z]$, on cherche à décider si $f\in I$ par
division euclidienne par les polynômes de la base. Que peut-on dire dans les
trois situations suivantes:
\qq le reste obtenu est $0$.
\qq le reste obtenu est $1$. \hint{Montrer par l'absurde que $1\not\in I$.}
\qq le reste obtenu est $x$. \hint{Attention au piège!}

\pb[Preuve de primalité] Soit $N > 1$ un entier. Soit $p \mid N-1$ un nombre
premier et $e := v_p(N-1)$, c'est-à-dire que $p^e$ divise exactement $N-1$.
On suppose qu'il existe $a\in \ZM$ vérifiant
\begin{equation}\tag{$S_p$} \label{eq2}
\begin{cases}
a^{N-1}\equiv 1\pmod{N}, \\
\pgcd\paren{a^{(N-1)/p} - 1, N} = 1.
\end{cases}
\end{equation}
\fbox{Sous ces conditions, tout diviseur $d$ de $N$ vérifie $d \equiv
1 \pmod{p^e}$.} \hint{On ne demande pas de reproduire cette démonstration.}

\Q On fixe $N$ et $p$ et on se donne un entier $0 < a < N$.
\qq Proposer un code Maple testant si $a$ vérifie bien les conditions
\eqref{eq2}.

\qq Borner le nombre d'opérations élémentaires utilisées par votre
algorithme, en fonction de $n := \log N$. \hint{On pourra supposer
qu'addition et multiplication dans $\ZM/N\ZM$ utilisent $\Ot(n)$
opérations élémentaires, ainsi que le calcul de $\pgcd(u,v)$ quand $\abs{u},
\abs{v} < N$.}

\Q Dans toute cette question, on suppose que $N$ est premier, et on fixe 
un nombre premier $p$ divisant $N-1$.
\qq Comment se simplifient les deux propriétés \eqref{eq2}?
\qq En déduire la probabilité qu'un entier $a$ tiré uniformément au hasard dans
$[1,N]$ vérifie~\eqref{eq2}. S'attend-on à trouver rapidement de tels $a$?
\medskip

\noindent\fbox{\vbox{\noindent On suppose dans toute la suite que $N - 1 =
FU$, où tous les facteurs premiers de $F$ sont connus, et que pour chaque
$p\mid F$, on connaît $a = a(p)$ vérifiant les propriétés \eqref{eq2}.}}

\Q On suppose dans cette question que $F\geq N^{1/2}$. Soit $d > 1$ un
diviseur de $N$.
\qq Montrer que $d \equiv 1\pmod{F}$.
\qq En déduire que $d > N^{1/2}$, puis que $N$ est premier.

\Q On suppose maintenant que $N^{1/3}\leq F < N^{1/2}$.
\qq Démontrer que la décomposition en base $F$ de $N$ est de la forme
$c_2 F^2 + c_1 F + 1$.
\qq On suppose que $N$ n'est pas premier. Montrer qu'il a exactement 
deux diviseurs premiers de la forme $p = aF + 1$, $q = bF +1$, pour
des entiers $0 < a \leq b$. Montrer que $ab \leq F-1$ et en déduire que
$a + b \leq F-1$ \hint{montrer que le cas $a = 1$, $b = F-1$ est
impossible}, puis que $c_1 = a+b$, $c_2 = ab$. Conclure que $c_1^2 - 4c_2$
est un carré dans $\ZM$.
\qq Avec les notations du a), montrer que $N$ est premier si et seulement si
$c_1^2 - 4c_2$ n'est pas un carré dans $\ZM$.

\Q Écrire une procédure Maple complète qui prend en entrée un entier $N$
et une liste $L_F$ de nombres premiers divisant $N-1$, et prouve la primalité
de $N$ grâce aux méthodes du 3) et du 4), si l'entier $F$ correspondant est
suffisamment grand. Il est interdit d'utiliser les fonctions de type
\texttt{factor}.
\end{document}
