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

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

\begin{document}
\agregtitle{Test de primalité de Lucas, nombres de Mersenne} 

\section{Introduction}
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. A
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
$\ZM/n\ZM$, où $n$ est un entier, parfois premier. On utilise également un
calcul sur un corps fini quadratique sur $\FM_p$ ($p$ étant un nombre
premier) pour le test de primalité de Lucas.

\section{Tests de non primalité}
Le petit théorème de Fermat fournit un test qui peut permettre de montrer
qu'un nombre $N$ n'est pas premier. Si en effet en calculant $2^{N-1}$ mod
$N$, on trouve un résultat distinct de $1$, on est certain que $N$ n'est pas
premier. Par contre, si on trouve $1$, cela ne veut pas dire que $N$ est
premier. On peut alors prendre d'autres valeurs $a$ que $2$, et calculer
$a^{N-1}$. Si l'on trouve $1$ à chaque fois, cela ne prouvera pas non plus
que $N$ n'est pas premier. Il existe des nombres composés pour lesquels on
n'a que très peu de chances de conclure ainsi: les nombres de Carmichael,
c'est-à-dire les nombres composés $N$ tels que $a^{N-1}\equiv 1$ mod $N$ pour
tout $a$ premier avec $N$. Il a été démontré qu'il existe une infinité de
tels nombres.

Un renforcement de ce test a été donné par Rabin et Miller en 1977. Il se
base sur le théorème 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\{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 à

$$\prod_p\#\{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}}.$$
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=\hbox{min}_pe_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, dû à Lucas. Ce
test suppose connue la factorisation de $N+1$. Il utilise les suites $(U_n)$,
appelées suites de Lucas, définies par récurrence:
$$U_0=0,\quad U_1=1,\quad U_{n+1}=SU_n-PU_{n-1},$$
pour $n\geq2$, où $S$ et $P$ sont des nombres entiers. Soit $D$ le
discriminant du polynôme $Q(x)=x^2-Sx+P$, et soit $p$ un nombre premier
impair ne divisant pas $DP$. On considère la suite $(U_n)$ modulo $p$. On
note $r$ et $r'$ les racines de $Q$ dans une clôture algébrique de $\FM_p$.
Alors $[U_n]_p=(r^n-r'^n)(r-r')^{-1}$. Si $\leg{D}{p}=1$, alors
$r^{p-1}=r'^{p-1}=1$, donc $U_{p-1}\equiv0$ mod $p$. Si $\leg{D}{p}=-1$,
alors $r^p=r'$, donc $U_{p+1}\equiv0$ mod $p$. De plus, si $e$ est le plus
petit entier tel que $U_e\equiv0$ mod $p$, alors $U_n\equiv0$ mod $p$ si et
seulement si $e$ divise $n$. On peut alors montrer le théorème suivant, qui
donne un autre test de primalité.
\begin{theo}\label{Lucas}
Supposons que l'on puisse trouver une suite de Lucas $(U_n)$ telle que
$(N,DP)=1$, et telle que
$$(U_{(N+1)/p},N)=1,\quad \text{pour tout premier $p\mid N+1$}$$
et
$$U_{N+1}\equiv0 \pmod{N}.$$
Alors $N$ est un nombre premier.
\end{theo}
En effet, on peut démontrer que dans les conditions de ce théorème, si $d$
est un diviseur premier de $N$ et $e$ le plus petit entier strictement
positif tel que $U_e=0$, alors $N+1\mid e\mid d+1$. On en déduit alors que
$N=d$.

\section{Nombres de Mersenne}

Si $N$ est de la forme $2^n-1$, la factorisation de $N+1$ est simple et il
est plus facile d'étudier la primalité de $N$. L'entier $N$ ne peut être un
nombre premier que si $n$ est premier. Un nombre de cette forme $M_n=2^n-1$,
où $n$ est un nombre premier, est appelé nombre de Mersenne.

Pour donner un exemple déjà ancien, Euler a démontré que $M_{31}$ est premier
en utilisant le théorème suivant.
\begin{theo}\label{pm1}
Soient $p$ et $q$ deux nombres premiers impairs. Si $p$ divise $M_q$, alors
$p\equiv1 \pmod{q}$ et $p\equiv\pm1 \pmod{8}$.
\end{theo}
Mais revenons aux suites de Lucas. Soit $(V_n)$ définie par récurrence:
$V_{n+1}=SV_n-PV_{n-1}$ pour $n\geq1$, $V_0=2$ et $V_1=S$. Alors
$U_{2n}=U_nV_n$. Si $N$ est un nombre de Mersenne, on a donc
$U_{N+1}=U_{(N+1)/2}V_{(N+1)/2}$. On peut alors remplacer les deux conditions
du théorème \ref{Lucas} par la seule condition:
$V_{(N+1)/2}\equiv0\pmod{N}$. Pour calculer $V_{(N+1)/2}$, on peut remarquer
que $V_{2n}=V_n^2-2P^n$. On pose alors $v_n=V_{2^n}$ et on obtient la
récurrence $v_n=v_{n-1}^2-2P^{2^{n-1}}$. Il est donc intéressant de
s'arranger pour que $P=1$ ou $-1$, c'est-à-dire, si $a$ et $a'$ sont les
racines de $Q$ dans $\CM$, pour que $aa'=1$ ou $-1$. De plus, il est
implicite dans le théorème~\ref{Lucas} que si le test réussit,
$\leg{D}{N}=-1$. On peut prendre pour $D$ un carré multiplié par $3$, et donc
par exemple $a=2+\sqrt3$, ce qui donne pour $Q$: $Q(x)=x^2-4x+1$. 

Malheureusement, le fait que $P=1$, avec $\leg{D}{N}=-1$, implique que
$U_{\frac{N+1}2}\equiv0$ mod $N$, ce qui empêche d'appliquer le
théorème~\ref{Lucas} directement.

On peut alors faire un autre choix pour $a$ et $a'$. Par exemple:
$$ a = \sqrt{2+\sqrt3}=\frac{\sqrt 3+1}{\sqrt2},\quad
\text{et}\quad a' = \frac{\sqrt 3-1}{\sqrt2},$$ ce qui donne le polynôme
$x^2-x\sqrt6+1$. Le raisonnement précédent ne s'applique pas directement,
puisque les coefficients ne sont plus dans $\Z$, mais on peut l'adapter pour
obtenir un résultat similaire.

Pour cela, on peut remarquer qu'il existe un nombre premier $q$ divisant $N$
tel que $(\frac3q)=-1$. De plus, le théorème \ref{pm1} permet d'affirmer que
$2$ est un carré modulo $q$. Soit $\alpha$ une racine carrée de $6$ dans
$\F_{q^2}$, et soient $r$ et $r'$ les racines dans une clôture algébrique de
$\F_q$ de $X^2-\alpha X+1$. On peut démontrer que $r^q=-r'$, $r'^q=-r$ et
$U_{q+1}\equiv0\pmod{q}$.

Soit $(V)$ la suite correspondante, c'est-à-dire: $V_0=2$, $V_1=\sqrt6$,
$V_2=4$, etc. En posant $v_k=V_{2^{k+1}}$, pour $k\geq0$, on peut démontrer
le résultat suivant.

\begin{theo}\label{LucasMersenne}
Soit $n$ un entier impair. Alors $M_n$ est premier si et seulement si
$v_{n-2}\equiv0\pmod{M_n}$, où $v_{k+1}=v_k^2-2$ pour $k\geq0$ et $v_0=4$. 
\end{theo}

\section{Problèmes ouverts}
Signalons au passage une propriété intéressante des nombres de Mersenne: tout
nombre parfait pair est de la forme $2^{n-1}M_n$, où $M_n$ est premier. On
rappelle qu'un nombre parfait est un nombre entier positif égal à la somme de
ses diviseurs propres. Par exemple, $6$ est un nombre parfait. Il n'est pas
connu à ce jour de nombres parfaits impairs, et on ne sait pas s'il en
existe.

Quant aux nombres de Mersenne, on ne sait pas s'il en existe une infinité qui
soient premiers. On ne sait pas non plus s'il en existe une infinité qui
soient composés. Il existe cependant un résultat (théorème~\ref{Euler}
ci-dessous), dû à Euler, qui semble indiquer que la réponse à cette dernière
question devrait être affirmative. On pense en effet qu'il existe une
infinité de couples de nombres premiers $(p,2p+1)$, où $p\equiv3$ mod $4$. 
\begin{theo}\label{Euler}
Si  $k>1$ et  $p=4k+3$ est un nombre premier, alors $2p+1$ est premier si et
seulement si $2^p\equiv1\pmod{2p+1}$.
\end{theo}
 
\section{Suggestions}
\begin{itemize}
\item Plusieurs affirmations sont données sans preuve. Le candidat est invité
à les démontrer. Il est cependant déconseillé d'essayer de démontrer qu'il
existe une infinité de nombres de Carmichael.

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

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

\item On pourra aussi faire une liste de nombres premiers de Mersenne, de
nombres parfaits, de nombres composés de Mersenne.
\end{itemize}
\end{document}
