Test de primalité de Lucas-Lehmer

Infos
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^\ \equiv\ 1 \ et, pour tous les facteurs premiers q de n-1, :a^\ \not\equiv\ 1 \ alors n est premier. Si un tel nombre a ne peut pas être trouvé, alors n est un nombre composé. Par exempl
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^\ \equiv\ 1 \ et, pour tous les facteurs premiers q de n-1, :a^\ \not\equiv\ 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 : :11^\ \equiv\ 1 \ 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^\ \equiv\ 70\ \not\equiv\ 1 \ :11^\ \equiv\ 54\ \not\equiv\ 1 \ :11^\ \equiv\ 32\ \not\equiv\ 1 \ 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 Lucas-Lehmer de:Lucas-Test (Mathematik) en:Lucas–Lehmer test es:Test de Lucas-Lehmer fi:Lucasin ja Lehmerin alkulukutesti he:מבחן לוקאס-להמר nl:Algemene Lucas-Lehmertest sv:Lucas-Lehmers test vi:Kiểm tra Lucas-Lehmer
Sujets connexes
Algorithmique   Exponentiation par carrés   Nombre composé   Nombre premier   Ordre multiplicatif   Racine primitive modulo n   Réciproque   Test de primalité   Test de primalité de Lucas-Lehmer pour les nombres de Mersenne  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^