test de Lucas-Lehmer

test de primalité de Lucas-Lehmer
test de primalité de Lucas
test de Lucas

ARITHMETIQUE

Test de primalité dû à Edouard Lucas (1878) et dont une formulation plus efficace est due à Derrick Lehmer (1930).

Soit n un entier impair. N est premier si et seulement s’il existe un entier a tel que a^(n-1) = 1 (modulo n) et, pour tout diviseur premier q de (n-1), a^(n-1)/q ≠ 1 (modulo n).

Le test de primalité de Lucas-Lehmer pour les nombres de Mersenne s’applique de la façon suivante :
Soit Mp = 2^p− 1 le nombre de Mersenne à tester. On définit une suite de la façon suivante :
s0=4; et si = si-1²-2

Le nombre de Mersenne Mp est premier si et seulement si
sp-2 = 0 (modulo Mp).