Test de Lucas

De Viquipèdia
Dreceres ràpides: navegació, cerca

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é[modifica | modifica el codi]

Nota[modifica | modifica el codi]