test de Pocklington

test de Pocklington-Lehmer
test de primalité de Pocklington

ARITHMETIQUE

Test de primalité dû au mathématicien anglais Henry Cabourn Pocklington (1870 – 1952).

Il découle du théorème de Pocklington dont un énoncé est : soit n un entier >1. On écrit n sous la forme n-1= q^r m , avec q premier et r≥1.
S’il existe un entier a avec (a^qr)≡ 1 (modulo n) et pgcd(a^qr-1, n) = 1.
Alors tout facteur premier de n est congru à 1 modulo q^r .