Exercice 23 Nombres de Poulet

1. Raisonnons par contraposée. Supposons $n$ premier. Comme $n$ est impair, on a $n\neq 2$, donc $n$ ne divise pas $2$. Le petit théorème de Fermat s'applique alors : $$2^{\,n-1}\equiv 1\;[n]$$ ce qui contredit l'hypothèse $2^{\,n-1}\not\equiv 1\;[n]$. $$\boxed{n \text{ n'est pas premier.}}$$ C'est un test de non-primalité : il permet d'affirmer qu'un nombre est composé sans en connaître le moindre diviseur, ce qui est remarquable.

2. Remarquons que $$2^{10}=1\,024=3\times 341+1 \qquad\text{donc}\qquad 2^{10}\equiv 1\;[341]$$ Comme $340=10\times 34$ : $$2^{340}=\left(2^{10}\right)^{34}\equiv 1^{34}=1\;[341] \qquad\Longrightarrow\qquad \boxed{\text{le reste est } 1.}$$

Ce que cela signifie. Le nombre $341$ vérifie donc la conclusion du petit théorème de Fermat, $2^{\,341-1}\equiv 1\;[341]$. Pourtant : $$341=11\times 31$$ n'est pas premier. Autrement dit, la réciproque du petit théorème de Fermat est fausse : la congruence $2^{\,n-1}\equiv 1\;[n]$ ne garantit pas la primalité de $n$. Le test de la question 1 ne fonctionne que dans un sens.

3. (a) Examinons quand le verdict est erroné.

• Si $n$ est premier, alors $2^{\,n-1}\equiv 1\;[n]$ et l'on annonce « premier » : le verdict est correct.

• Si $n$ n'est pas premier, deux cas se présentent. Ou bien $2^{\,n-1}\not\equiv 1\;[n]$ et l'on annonce « pas premier » : correct. Ou bien $2^{\,n-1}\equiv 1\;[n]$, c'est-à-dire $n$ est un nombre de Poulet, et l'on annonce à tort « premier ».

Les seuls cas d'erreur sont donc les $21\,853$ nombres de Poulet, sur les $25$ milliards d'entiers considérés : $$P(\text{erreur})=\frac{21\,853}{25\times 10^{9}}\approx 8{,}74\times 10^{-7}$$

(b) On annonce « premier » lorsque $2^{\,n-1}\equiv 1\;[n]$, ce qui se produit pour les $1\,091\,987\,405$ nombres premiers et pour les $21\,853$ nombres de Poulet. En notant $A$ l'événement « $n$ est premier » et $B$ l'événement « $n$ est annoncé premier » : $$P_{B}(A)=\frac{1\,091\,987\,405}{1\,091\,987\,405+21\,853} =\frac{1\,091\,987\,405}{1\,092\,009\,258}$$

$$\boxed{P_{B}(A)\approx 0{,}999\,98}$$ Interprétation. Le test se trompe environ deux fois sur cent mille annonces de primalité. C'est cette fiabilité — combinée à sa rapidité, puisque le calcul de $2^{\,n-1}$ modulo $n$ est très rapide — qui rend ce type de test précieux en cryptographie, où l'on a besoin de fabriquer de très grands nombres premiers.