théorème de Pocklington

ARITHMETIQUE

Le théorème de Pocklington est un test de primalité qui généralise le théorème de Proth et le test de primalité de Lucas-Lehmer .
Enoncé :
Toutes les lettres désignent des entiers naturels.
Si N – 1 = qⁿ R avec q premier et n ≥ 1
et s’il existe a>0 tel que :
1) a^N-1 ≡ 1 mod N
2) PGCD ( a^(N-1)/q – 1 , N) = 1
alors : tout facteur premiier p de N est de la forme k qⁿ + 1
(voir Bulletin de l’APMEP n°503)

Il permet d’obtenir de très grands nombres premiers, ce qui est utilisé en cryptographie.