\documentclass[11pt]{amsart}
\usepackage[theo]{kbexo}

\def\Q{{\mathbb Q}}
\def\C{{\mathbb C}}
\def\R{{\mathbb R}}
\def\Z{{\mathbb Z}}
\def\F{{\mathbb F}}

\begin{document}
\agregtitle{Tests de non primalité, tests de primalité} 

\section{Introduction}
\noindent On peut se poser trois questions distinctes sur
la nature arithmétique de~$N\in\NM$:
\begin{itemize}
\item $N$ est-il  composé? 
\item $N$ est-il premier?
\item Factoriser $N$.
\end{itemize}
Si les trois questions semblent équivalentes, elles sont en fait de
difficulté largement différente. On s'intéresse ici aux deux premières. À
savoir, comment montrer qu'un nombre est composé, puis, si la réponse est
«apparemment pas», comment montrer qu'il est premier. Les tests proposés
utilisent les notions nécessaires aux calculs et raisonnements dans $\Z/N\Z$,
où $N$ est un entier, parfois premier.
suivant.
\begin{theo}
Soit $N$ un nombre premier impair, et $a$ un entier premier à $N$. Si
$N-1=2^eq$, où $q$ est un entier impair, alors:
\begin{enumerate}
\item Soit $a^q\equiv1$ mod $N$.
\item Soit il existe $i$ tel que $0\leq i\leq e-1$ tel que
$a^{2^iq}\equiv-1$ mod $N$.
\end{enumerate}
\end{theo}
Là encore, la réciproque est fausse, comme le montre l'exemple où $N=3277$ et
$a=2$. Si un entier $a\in\set{1,\dots N-1}$ vérifie l'une des propriétés (1)
ou (2) du théorème de Rabin-Miller, on dit que $N$ est pseudo-premier (de
Miller-Rabin) pour la base $a$.

Toutefois, la situation est meilleure que pour le test venant directement du
petit théorème de Fermat. Le théorème suivant montre en effet que si un
nombre $N$ n'est pas premier, et si l'on essaie un nombre suffisant de
valeurs de $a$, on a une très forte probabilité de trouver une base $a$ pour
laquelle $N$ n'est pas pseudo-premier.
\begin{theo}
Si $N$ est composé, alors il est pseudo-premier dans au plus $1/4$ des bases
$a$.
\end{theo}
Pour démontrer ce théorème, on peut procéder de la manière suivante. On écrit
la décomposition de $N$ en produit de facteurs premiers $N=\prod_pp^{f_p}$.
En utilisant le théorème chinois, on voit que le nombre $A$ d'éléments $a$
qui satisfont le test est égal à
\begin{multline*}
\prod_p
  \#\set{x\colon qx\equiv0\mod (p-1)p^{f_p-1}}\\
+\sum_{i=0}^{e-1}\prod_p\#\set{x \colon q2^ix\equiv
(p-1)p^{f_p-1}/2\mod (p-1)p^{f_p-1}}.
\end{multline*}
On trouve alors que
$$A=\left(1+\frac{2^{\omega E}-1}{2^{\omega}-1}\right)\prod_p(q,p-1),$$
où $\omega$ est le nombre de facteurs premiers de $N$, et où
$E=\min_p e_p$, l'entier $e_p$ étant défini pour tout $p$
par: $e_p=v_2(p-1)$. La probabilité $P$ cherchée est égale à
$A/(N-1)$. Si $\omega=1$, on trouve $P=1$ si $f_p=1$, et
$P\leq (p-1)/(p^{f_p}-1)\leq1/(p+1)\leq1/4$ si $f_p>1$. Si $\omega>1$, les
inégalités
$(q,p-1)\leq (p-1)/2^{e_p}$ et $\prod_p(p-1)\leq N-1$ montrent
que
$$P\leq\left(1+\frac{2^{\omega E}-1}{2^{\omega}-1}\right)/2^{\omega
  E}.$$
On obtient alors la majoration voulue, sauf dans le cas où
$\omega=2$, où on obtient seulement $P\leq 1/2$. Dans ce cas,
on peut affiner les inégalités précédentes pour obtenir
le bon résultat, sauf si $p-1$ divise $N-1$ pour tout $p$ et
si $N$ est sans facteurs carrés. On montre alors
que ce cas est impossible.

\section{Tests de primalité}

Supposons que $N$ ait passé le test de Rabin-Miller. Nous sommes alors
à peu près certains que $N$ est premier. Le démontrer
rigoureusement est un problème plus difficile. Nous donnons
ici un exemple de test, trouvé par Pocklington et amélioré
par Lehmer, basé sur le théorème suivant.
\begin{theo}\label{PockLehmer}
Soit $N>1$ un entier. Alors $N$ est un nombre premier si et seulement
si pour tout diviseur premier $p$ de $N-1$ on peut trouver un entier
$a_p$ tel que
$$a_p^{N-1}\equiv1\pmod{N}\quad et\quad (a_p^{(N-1)/p}-1, N) = 1.$$
\end{theo}

En effet, si $N$ est premier, et si $g$ est
une racine primitive modulo $N$, alors il suffit de poser $a_p=g$ pour
tout $p$. Réciproquement, soit $d$ un diviseur premier de $N$,
on montre que pour tout $p$ divisant $N-1$, $p^{v_p(N-1)}$ divise
$d-1$, ce qui permet ensuite de conclure que $N=d$. 

\medskip

Ce théorème fournit un test de primalité rapide, dès que l'on
connaît la factorisation de $N-1$. La factorisation d'un entier est
un problème difficile et peut être un obstacle à l'utilisation
de ce test. Il arrive toutefois qu'il ne soit pas trop difficile de
factoriser $N-1$. De plus, on n'a pas vraiment besoin
de la factorisation complète de $N-1$, comme le montrent
les théorèmes~\ref{raf1} et \ref{raf2}
ci-dessous, auxquels la démonstration du
théorème~\ref{PockLehmer}
s'applique, avec quelques modifications.
\begin{theo}\label{raf1}
Soit $N>1$ un entier. On suppose qu'on sait écrire $N-1=FU$, où
$(F,U)=1$, $F=\prod_{i=1}^gp_i^{f_i}$ est complètement factorisé,
et où $U<F$.
Alors $N$ est premier si et seulement si pour
tout élément $x=p_i$, $i\in\{1,\dots,r\}$, on peut
trouver un entier $a_x$ tel que
$$a_x^{N-1}\equiv1\pmod{N}\quad\text{et} (a_x^{(N-1)/x}-1,N) = 1.$$
\end{theo}
\begin{theo}\label{raf2}
Soit $N>1$ un entier. On suppose qu'on sait écrire $N-1=FU$, où
$(F,U)=1$, $F=\prod_{i=1}^gp_i^{f_i}$ est complètement factorisé,
 où tous les diviseurs premiers de $U$ sont plus grand qu'un entier $B$,
et où $BF\geq\sqrt N$. Alors $N$ est premier si et seulement si pour
tout élément $x=p_i$, $i\in\{1,\dots,r\}$ et $x=U$, on peut
trouver un entier $a_x$ tel que
$$a_x^{N-1}\equiv1\pmod{N}\quad \text{et}\quad (a_x^{(N-1)/x}-1,N)=1.$$
\end{theo}


\bigskip
 
\section{Suggestions}
Plusieurs affirmations sont données sans preuve. Le candidat est invité à les
démontrer. Il est déconseillé d'essayer de démontrer qu'il existe une
infinité de nombres de Carmichael.

Par ailleurs, la preuve de certains théorèmes n'est qu'ébauchée. On pourra en
fournir plus de détails.

Plusieurs tests sont proposés. On pourra en implémenter certains et les
commenter.

On peut aussi chercher à illustrer expérimentalement la proportion des bases
pour lesquelles un nombre composé est pseudo-premier.
\end{document}

