title: Test de primalité de Lucas-Lehmer
text: # Test de primalité de Lucas-Lehmer
  
  Le test de primalité de Lucas-Lehmer est une méthode pour tester la primalité d'un entier n, connaissant les facteurs premiers de n – 1.
  
  ## Le test
  
  Un entier n > 2 est premier si et seulement si il existe un entier a, strictement compris entre 1 et n, tel que
  
      $a^{n-1}\equiv 1{\pmod {n}}$
  
  et, pour tout facteur premier q de n – 1,
  
      $a^{({n-1})/q}\not \equiv 1{\pmod {n}}.$
  
  ## Exemple
  
  Par exemple, prenons n = 2017, n – 1 = 2016 = $2^5×3^2×7.$
  
  a = 2 ne convient pas car $2^{672}$ ≡ 1 (mod n).
  
  a = 3 non plus car $3^{1008}$ ≡ 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})$ :
  
      $5^{1008}\equiv -1\not \equiv 1{\pmod {n}}{\text{ et }}5^{2016}\equiv (-1)^{2}\equiv 1{\pmod {n}}$
      $5^{672}\equiv 294\not \equiv 1{\pmod {n}}$
      $5^{288}\equiv -138\not \equiv 1{\pmod {n}}$
  
  Donc 2017 est premier.
  
  ## Démonstration
  
  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.
  
  ## Utilisation
  
  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.
  
  