Test de primalite de Lucas-Lehmer

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

  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Test de primalit%C3%A9 de Lucas-Lehmer ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Test de primalite de Lucas-Lehmer de Wikipédia en français (auteurs)

Игры ⚽ Нужна курсовая?

Regardez d'autres dictionnaires:

  • 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 et, pour tous les… …   Wikipédia en Français

  • Test de primalité de Lucas-Lehmer — Pour les articles homonymes, voir Lucas et 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 …   Wikipédia en Français

  • Test de primalite de Lucas-Lehmer pour les nombres de Mersenne — Test de primalité de Lucas Lehmer pour les nombres de Mersenne En mathématiques, le test de Lucas Lehmer est un test de primalité pour les nombres de Mersenne. Le test fut originellement développé par Édouard Lucas en 1878 et amélioré de façon… …   Wikipédia en Français

  • Test de primalité de lucas-lehmer pour les nombres de mersenne — En mathématiques, le test de Lucas Lehmer est un test de primalité pour les nombres de Mersenne. Le test fut originellement développé par Édouard Lucas en 1878 et amélioré de façon notable par Derrick Henry Lehmer dans les années 1930. Le test Le …   Wikipédia en Français

  • Test de primalité de Lucas-Lehmer pour les nombres de Mersenne — Pour les articles homonymes, voir Lucas et Lehmer. En mathématiques, le test de Lucas Lehmer est un test de primalité pour les nombres de Mersenne. Le test fut originellement développé par Édouard Lucas en 1878 et amélioré de façon notable par… …   Wikipédia en Français

  • Test de primalite AKS — Test de primalité AKS Le test de primalité AKS (aussi connu comme le test de primalité Agrawal Kayal Saxena et le test cyclotomique AKS) est un algorithme déterministe de preuve de primalité découvert et publié le 6 août 2002 par trois… …   Wikipédia en Français

  • Test de primalité aks — Le test de primalité AKS (aussi connu comme le test de primalité Agrawal Kayal Saxena et le test cyclotomique AKS) est un algorithme déterministe de preuve de primalité découvert et publié le 6 août 2002 par trois scientifiques indiens nommés… …   Wikipédia en Français

  • Test de primalité AKS — Le test de primalité AKS (aussi connu comme le test de primalité Agrawal Kayal Saxena et le test cyclotomique AKS) est un algorithme déterministe de preuve de primalité découvert et publié le 6 août 2002 par trois scientifiques indiens nommés… …   Wikipédia en Français

  • Test de primalite — Test de primalité Un test de primalité est un algorithme permettant de savoir si un nombre entier est premier. Sommaire 1 Méthode naïve 2 Tests probabilistes 3 Tests déterministes rapides …   Wikipédia en Français

  • Test de primalité — Un test de primalité est un algorithme permettant de savoir si un nombre entier est premier. Sommaire 1 Méthode naïve 2 Tests probabilistes 3 Tests déterministes rapides …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”