Le test de primalité de Lucas[ 1] [ 2] est une méthode pour tester la primalité d'un entier n facteurs premiers de n-1
Le test
Un entier n > 2premier si et seulement si il existe un entier a 1 et n
a
n
− − -->
1
≡ ≡ -->
1
(
mod
n
)
{\displaystyle a^{n-1}\equiv 1{\pmod {n}}}
et, pour tout facteur premier[ 3] q n – 1
a
(
n
− − -->
1
)
/
q
≢
1
(
mod
n
)
.
{\displaystyle a^{({n-1})/q}\not \equiv 1{\pmod {n}}.}
Exemple
Par exemple, prenons n = 2017, n – 1 = 2016 = 25 ×32 ×7.
a = 2 ne convient pas car 2672 ≡ 1 (mod n ).
a = 3 non plus car 31008 ≡ 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 524 ×3 ) :
5
1008
≡ ≡ -->
− − -->
1
≢
1
(
mod
n
)
et
5
2016
≡ ≡ -->
(
− − -->
1
)
2
≡ ≡ -->
1
(
mod
n
)
{\displaystyle 5^{1008}\equiv -1\not \equiv 1{\pmod {n}}{\text{ et }}5^{2016}\equiv (-1)^{2}\equiv 1{\pmod {n}}}
5
672
≡ ≡ -->
294
≢
1
(
mod
n
)
{\displaystyle 5^{672}\equiv 294\not \equiv 1{\pmod {n}}}
5
288
≡ ≡ -->
− − -->
138
≢
1
(
mod
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.
Utilisation
En théorie de la complexité , ce test donne un certificat de primalité (en) Pratt (en) NP [ 4]
↑ Édouard Lucas , Théorie des nombres , t. 1, 1891 (lire en ligne ) , p. 441↑ (en) D. H. Lehmer , « Tests for primality by the converse of Fermat's theorem », Bull. Amer. Math. Soc. vol. 33, no 3, 1927 , p. 327-340 (lire en ligne ) ↑ Optimisation par Lehmer 1927 de l'énoncé de Lucas 1891 , qui testait sur tous les diviseurs non triviaux q n – 1
↑ (en) Vaughan Pratt, « Every prime has a succinct certificate », Siam J. Comput. vol. 4, no 3, 1975 , p. 214-220 (lire en ligne )
Articles connexes
