- Test de primalité de Lucas-Lehmer
-
Le test de primalité de Lucas-Lehmer est une méthode pour tester la primalité d'un nombre entier n pour lequel on suppose connaître les facteurs premiers de n-1.
S'il existe un a inférieur à n et plus grand que 1 tel que
et, pour tous les facteurs premiers q de n-1,
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 :
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 :
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
![a^{n-1}\ \equiv\ 1 \ [n]](5/55510657d834a1834bb0e8fa1829d8c6.png)
![a^{({n-1})/q}\ \not\equiv\ 1 \ [n]](5/c458e26f72f51ae8a7195569f3e45203.png)
![11^{70}\ \equiv\ 1 \ [71]](b/5abb070b3f7a538fa783a0f9c1e61beb.png)
![11^{35}\ \equiv\ 70\ \not\equiv\ 1 \ [71]](9/679df0edbfac4eb9cb0dc3531b093173.png)
![11^{14}\ \equiv\ 54\ \not\equiv\ 1 \ [71]](a/f8a6cb76d302559ae359f6f242f13db6.png)
![11^{10}\ \equiv\ 32\ \not\equiv\ 1 \ [71]](4/854a1fe731061ea28703e596d5544a16.png)
Wikimedia Foundation. 2010.
