Test de Pépin

En mathématiques, le test de Pépin est un test de primalité, qui est utilisé pour déterminer si un nombre de Fermat est premier ou non. C'est une variante du théorème de Proth. Ce test porte le nom du mathématicien français Théophile Pépin.

Énoncé

Soit ${\displaystyle F_{n}=2^{2^{n}} 1}$ le n-ième nombre de Fermat. Le test de Pépin indique que, pour n > 0: 

${\displaystyle F_{n}}$ est premier si et seulement si ${\displaystyle 3^{(F_{n}-1)/2}\equiv -1{\pmod {F_{n}}}.}$

L'expression ${\displaystyle 3^{(F_{n}-1)/2}}$ peut être évaluée modulo ${\displaystyle F_{n}}$ par exponentiation rapide. Le test a donc une faible complexité en temps. Cependant, les nombres de Fermat croissent si rapidement que seule une poignée d'entre eux peut être testée dans un laps de temps et d'espace raisonnable.

D'autres bases peuvent être utilisées à la place de 3, par exemple 5, 6, 7 ou 10 (suite A129802 de l'OEIS).

Démonstration

Condition suffisante : supposons que la congruence

${\displaystyle 3^{(F_{n}-1)/2}\equiv -1{\pmod {F_{n}}}}$ soit vérifiée.

En élevant au carré, nous obtenons ${\displaystyle 3^{F_{n}-1}\equiv 1{\pmod {F_{n}}}}$, donc l'ordre multiplicatif de 3 modulo ${\displaystyle F_{n}}$ divise ${\displaystyle F_{n}-1=2^{2^{n}}}$, qui est une puissance de deux. D'autre part, l'ordre ne divise pas ${\displaystyle (F_{n}-1)/2}$, et doit donc être égal à ${\displaystyle F_{n}-1}$. Or, d'après le théorème d'Euler, l'ordre multiplicatif de 3 modulo ${\displaystyle F_{n}}$ divise φ(${\displaystyle F_{n}}$) (où φ est l'indicatrice d'Euler), et dans ce cas précis, lui est donc égal (car φ(k) ne peut être supérieure à k - 1).

Il existe donc ${\displaystyle F_{n}-1}$ nombres inférieurs à ${\displaystyle F_{n}}$ premiers avec ${\displaystyle F_{n}}$, ce qui signifie que ${\displaystyle F_{n}}$ est premier.

Condition nécessaire : supposons que ${\displaystyle F_{n}}$ soit premier.

D'après le critère d'Euler,

${\displaystyle 3^{(F_{n}-1)/2}\equiv \left({\frac {3}{F_{n}}}\right){\pmod {F_{n}}}}$, où  ${\displaystyle \left({\frac {3}{F_{n}}}\right)}$ est le symbole de Legendre.

${\displaystyle F_{n}}$ est premier et ${\displaystyle F_{n}\equiv 1{\pmod {4}}}$, d'où ${\displaystyle \left({\frac {3}{F_{n}}}\right)=\left({\frac {F_{n}}{3}}\right)}$, d'après la loi de réciprocité quadratique.

Par élévations au carré successives, on trouve ${\displaystyle 2^{2^{n}}\equiv 1{\pmod {3}}}$, donc ${\displaystyle F_{n}\equiv 2{\pmod {3}}}$, et alors : ${\displaystyle \left({\frac {F_{n}}{3}}\right)=\left({\frac {2}{3}}\right)=-1}$.

On obtient donc ${\displaystyle 3^{(F_{n}-1)/2}\equiv -1{\pmod {F_{n}}}}$.

Tests de Pépin historiques

En raison de la rareté des nombres de Fermat, le test de Pépin n'a été utilisé que huit fois (sur des nombres de Fermat dont les statuts de primalité ne sont pas encore connus)^,,. Mayer, Papadopoulos et Crandall pensent que, en raison de la taille des nombres de Fermat encore indéterminés, il faudra des décennies avant que la technologie permette d'exécuter plus de tests de Pépin. En 2020, le plus petit nombre de Fermat non testé sans facteur premier connu est ${\displaystyle F_{33}}$ qui est composé de 2 585 827 973 chiffres.

Articles connexes

• Crible d'Ératosthène
• Théorème de Proth
• Théorème de Pocklington
• Test de primalité de Miller-Rabin
• Test de primalité de Fermat
• Test de primalité de Solovay-Strassen
• Test de primalité de Lucas-Lehmer
• Test de primalité de Lucas-Lehmer pour les nombres de Mersenne
• Spirale d'Ulam
• Spirale de Sacks

Notes et références

Références

Notes

• Théophile Pépin, « Sur la formule ${\displaystyle 2^{2^{n}} 1}$ », Comptes Rendus Acad. Sci. Paris, vol. 85,‎ 1877, p. 329–333 (lire en ligne, consulté le 16 novembre 2018).

Liens externes

• The Prime Glossary: Pepin's test

• Portail des mathématiques
• Arithmétique et théorie des nombres
• Portail de l'informatique théorique