Test de Pépin

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

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é[modifier | modifier le code]

Soit   qui est le n-ième nombre de Fermat. Le test de Pépin indique que, pour n > 0 : 

 est premier si et seulement si 

L'expression  peut être évaluée modulo  par exponentiation rapide. Le test a donc une faible complexité en temps. Cependant, les nombres de Fermat se développent si rapidement que seule une poignée de nombres de Fermat 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 (séquence A129802 dans l'OEIS).

Démonstration[modifier | modifier le code]

Condition suffisante : supposons que la congruence

tient.

Ensuite, , donc l'ordre multiplicatif de 3 modulo  divise , qui est une puissance de deux. D'autre part, l'ordre ne divise pas , et doit être donc égal à . En particulier, il y a bien  nombre derrière qui coprime , et peut se produire seulement si  est premier.

Condition nécessaire : supposons que  est premier.

Par le critère d'Euler,

, où   est le symbole de Legendre.

est premier et , d'où .

, donc , et alors: .

.

Ainsi, , ce qui implique .

Tests de Pépin historiques[modifier | modifier le code]

En raison de la rareté des nombres de Fermat, le test Pépin n'a été utilisé que huit fois (sur des nombres de Fermat dont les statuts de primalité ne sont pas encore connus)[1],[2],[3]. Mayer, Papadopoulos et Crandall pensent que, en fait, en raison de la taille des nombres de Fermat encore indéterminées, il faudra des décennies avant que la technologie permette d'exécuter plus de tests de Pépin[4]. En 2016, le plus petit nombre de Fermat non testé sans facteur premier connu est qui est composé de 2,585,827,973 chiffres.

Année Chercheurs nombre

de Fermat

Résultat

du test de Pépin 

Facteur trouvé plus tard?
1905 Morehead & Western composé Oui (1970)
1909 Morehead & Western composé Oui (1980)
1952 Robinson composé Oui (1953)
1960 Paxson composé Oui (1974)
1961 Selfridge & Hurwitz composé Oui (2010)
1987 Buell & Young composé Non
1993 Crandall, Doenias, Norrie & Young composé Oui (2010)
1999 Mayer, Papadopoulos & Crandall composé Non

Articles connexes[modifier | modifier le code]

Notes et références[modifier | modifier le code]

Références[modifier | modifier le code]

  1. Conjecture 4.
  2. Wilfrid Keller, Fermat factoring status
  3. R. M. Robinson, Mersenne and Fermat numbers, 1954.
  4. Richard Crandall, Ernst W. Meyer et Jason Papadopoulos, « The twenty-fourth Fermat Number is composite », Mathematics of Computation, vol. 72, no 243,‎ , p. 1555-1572 (DOI 10.1090/S0025-5718-02-01479-5, lire en ligne, consulté le 16 novembre 2018).

Notes[modifier | modifier le code]

  • Théophile Pépin, « Sur la formule  », Comptes Rendus Acad. Sci. Paris, vol. 85,‎ , p. 329–333 (lire en ligne, consulté le 16 novembre 2018).

Liens externes[modifier | modifier le code]