Test de primalité de Lucas-Lehmer

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Lucas, Lehmer et Test de Lucas.

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.

Le test[modifier | modifier le code]

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é.

Exemple[modifier | modifier le code]

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 rapide.

Démonstration[modifier | modifier le code]

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.

Utilisation[modifier | modifier le code]

En théorie de la complexité, ce test donne un certificat de primalité, appelé certificat de Pratt, qui montre que le test de primalité est dans NP[1].

Voir aussi[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. Vaughan Pratt. Every prime has a succinct certificate. SIAM Journal on Computing, vol.4, pp.214–220. 1975. Citations, Full-text