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. Soit 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 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 (). Condition suffisante : supposons que la congruence soit vérifiée. En élevant au carré, nous obtenons , donc l'ordre multiplicatif de 3 modulo divise , qui est une puissance de deux. D'autre part, l'ordre ne divise pas , et doit donc être égal à . Or, d'après le théorème d'Euler, l'ordre multiplicatif de 3 modulo divise φ() (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 nombres inférieurs à premiers avec , ce qui signifie que est premier. Condition nécessaire : supposons que soit premier. D'après le critère d'Euler, où est le symbole de Legendre. est premier et , d'où , d'après la loi de réciprocité quadratique. Par élévations au carré successives, on trouve donc , et alors : . On obtient donc . 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 qui est composé de . Crible d'Ératosthène Théorème de Proth Théorème de Pocklington