Test de Pépin

test de primalité pour les nombres de Fermat

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

Soit Fn=22n+1 le n-ième nombre de Fermat. Le test de Pépin indique que, pour n > 0[1]: 

Fn est premier si et seulement si 3(Fn−1)/2≡−1(modFn).

L'expression 3(Fn−1)/2=32n−1 peut être évaluée modulo Fn 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

modifier

Condition suffisante : supposons que la congruence

3(Fn−1)/2≡−1(modFn) soit vérifiée.

En élevant au carré, nous obtenons 3Fn−1≡1(modFn), donc l'ordre multiplicatif de 3 modulo Fn divise Fn−1=22n, qui est une puissance de deux. D'autre part, l'ordre ne divise pas (Fn−1)/2, et doit donc être égal à Fn−1. Or, d'après le théorème d'Euler, l'ordre multiplicatif de 3 modulo Fn divise φ(Fn) (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 Fn−1 nombres inférieurs à Fn premiers avec Fn, ce qui signifie que Fn est premier.

Condition nécessaire : supposons que Fn soit premier.

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

3(Fn−1)/2≡(3Fn)(modFn), où  (3Fn) est le symbole de Legendre.

Fn est premier et Fn≡1(mod4), d'où (3Fn)=(Fn3), d'après la loi de réciprocité quadratique.

Par élévations au carré successives, on trouve 22n≡1(mod3), donc Fn≡2(mod3), et alors : (Fn3)=(23)=−1.

On obtient donc 3(Fn−1)/2≡−1(modFn).

Tests de Pépin historiques

modifier

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)[2],[3],[4]. 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[5]. En 2020, le plus petit nombre de Fermat non testé sans facteur premier connu est F33[3] 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 F7 composé Oui (1970)
1909 Morehead & Western F8 composé Oui (1980)
1952 Robinson F10 composé Oui (1953)
1960 Paxson F13 composé Oui (1974)
1961 Selfridge & Hurwitz F14 composé Oui (2010)
1987 Buell & Young F20 composé Non
1993 Crandall, Doenias, Norrie & Young F22 composé Oui (2010)
1999 Mayer, Papadopoulos & Crandall F24 composé Non

Articles connexes

modifier

Notes et références

modifier

Références

modifier
  1. ↑ Pascal Boyer, Petit compagnon des nombres et de leurs applications, Paris, Calvage et Mounet, , 648 p. (ISBN 978-2-916352-75-6), II. Nombres premiers, chap. 3.1. (« Nombres de Fermat »), p. 208-210.
  2. ↑ Conjecture 4.
  3. 1 2 (en) Wilfrid Keller, « Fermat factoring status », sur prothsearch.
  4. ↑ R. M. Robinson, Mersenne and Fermat numbers, 1954.
  5. ↑ 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 ).
  • Théophile Pépin, « Sur la formule 22n+1 », Comptes Rendus Acad. Sci. Paris, vol. 85,‎ , p. 329–333 (lire en ligne, consulté le ).

Liens externes

modifier