Test de primalite de Lucas-Lehmer

Test de primalité de Lucas-Lehmer

Le test de primalité de Lucas-Lehmer est une méthode pour tester la primalité de certains nombres n ; il requiert que les facteurs premiers de n-1 soient connus.

S'il existe un a inférieur à n et plus grand que 1 tel que

$a^{n-1}\ \equiv\ 1 \ [n]$

et, pour tous les facteurs premiers q de n-1,

$a^{({n-1})/q}\ \not\equiv\ 1 \ [n]$

alors n est premier.

Si un tel nombre a ne peut pas être trouvé, alors n est un nombre composé.

Par exemple, prenons n=71, n-1=70=(2)(5)(7). Choisissons a=11 :

$11^{70}\ \equiv\ 1 \ [71]$

Ceci ne montre pas que l'ordre multiplicatif de 11 mod 71 est 70 parce qu'un certain facteur de 70 pourrait aussi convenir. Donc vérifions 70 divisé par ses facteurs premiers :

$11^{35}\ \equiv\ 70\ \not\equiv\ 1 \ [71]$

$11^{14}\ \equiv\ 54\ \not\equiv\ 1 \ [71]$

$11^{10}\ \equiv\ 32\ \not\equiv\ 1 \ [71]$

Donc, l'ordre multiplicatif de 11 mod 71 est bien 70, et ainsi 71 est premier.

Pour calculer rapidement ces exponentiations, on utilise la méthode de l'exponentiation par carrés.

La raison pour laquelle cet algorithme fonctionne est la suivante : si a survit à la première étape de l'algorithme, nous pouvons déduire que a et n sont premiers entre eux. Si a survit aussi à la deuxième étape, alors l'ordre de a dans le groupe (Z/nZ)* est égal à n-1, ce qui veut dire que l'ordre de ce groupe est n-1, impliquant le fait que n est premier. Réciproquement, si n est premier, alors il existe une racine primitive modulo n, et n'importe quelle racine primitive de ce genre survivra aux deux étapes de l'algorithme.

Voir aussi

• Édouard Lucas
• Nombres premiers
• Tests de primalité
• Test de primalité de Lucas-Lehmer pour les nombres de Mersenne

Ce document provient de « Test de primalit%C3%A9 de Lucas-Lehmer ».