Test de primalité de Lucas-Lehmer

Un entier n > 2 est premier si et seulement si il existe un entier a, strictement compris entre 1 et n, tel que

${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$

et, pour tout facteur premier^[3] q de n – 1,

${\displaystyle a^{({n-1})/q}\not \equiv 1{\pmod {n}}.}$

Par exemple, prenons n = 2017, n – 1 = 2016 = 2⁵×3²×7.

a = 2 ne convient pas car 2⁶⁷² ≡ 1 (mod n).

a = 3 non plus car 3¹⁰⁰⁸ ≡ 1 (mod n)

Essayons a = 5 (pour calculer rapidement mod n les puissances voulues, on peut utiliser la méthode d'exponentiation rapide et de plus, calculer d'abord 5^24×3) :

${\displaystyle 5^{1008}\equiv -1\not \equiv 1{\pmod {n}}{\text{ et }}5^{2016}\equiv (-1)^{2}\equiv 1{\pmod {n}}}$

${\displaystyle 5^{672}\equiv 294\not \equiv 1{\pmod {n}}}$

${\displaystyle 5^{288}\equiv -138\not \equiv 1{\pmod {n}}}$

Donc 2017 est premier.

La première condition signifie que a est inversible modulo n et que son ordre multiplicatif est un diviseur de n – 1. La seconde signifie que cet ordre est exactement n – 1 (et non un diviseur strict). Par conséquent, l'ordre du groupe des inversibles de l'anneau ℤ/nℤ — qui est a priori inférieur ou égal à n – 1 — est divisible par n – 1 donc égal à n – 1, ce qui signifie que n est premier.

Réciproquement, si n est premier, alors il existe φ(n – 1) racines primitives modulo n, et n'importe laquelle satisfera toutes les conditions du test.

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