Test de Lucas

En teoria de nombres, el test de Lucas és un test de primalitat per a un nombre natural n i requereix que els factors cosins de n - 1 siguin coneguts.

Si hi ha un nombre natural a menor que n i més gran que 1 que verifica les condicions

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

així com

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

per a tots els factors primers q de n - 1, llavors n és primer. Si no pot trobar tal a , llavors n és un nombre compost.

Per exemple, prengui n = 71. Llavors, n - 1 = 70 = (2) (5) (7). Preneu-vos ara a = 11. En primer lloc:

$11^{70}\ \equiv \ 1{\pmod {71}}$

Això no demostra que l'ordre multiplicatiu d'11 mod 71 és 70, perquè algun factor de 70 encara podria funcionar amunt. Verifiquem llavors 70 dividit pels seus factors primers:

$11^{35}\ \equiv \ 70\ \not \equiv \ 1{\pmod {71}}$

$11^{14}\ \equiv \ 54\ \not \equiv \ 1{\pmod {71}}$

$11^{10}\ \equiv \ 32\ \not \equiv \ 1{\pmod {71}}$

Llavors, l'ordre multiplicatiu d'11 mod 71 és 70 i d'aquesta manera, 71 és primer.

Per realitzar aquestes potències modulars hauria d'usar el mètode accelerat de exponenciació binària.

Aquest algorisme és correcte, ja que si a passa el primer pas, podem deduir que a i n són coprimer s. Si a també passa el segon pas, llavors l'ordre de a al grup ( Z / n Z ) * és igual a n - 1, el que significa que l'ordre d'aquest grup és n - 1, implicant que n és primer. Recíprocament, si n és primer, llavors hi ha una arrel primitiva mòdul n i qualsevol arrel primitiva passarà dos passos de l'algorisme.

Vegeu també

• Edouard Lucas
• Test de Lucas-Lehmer
• Nombre primer