Test de Lucas: diferència entre les revisions
Cap resum de modificació |
Cap resum de modificació |
||
Línia 30: | Línia 30: | ||
[[Categoria: Tests de primalitat|Test de Lucas-Lehmer]] |
[[Categoria: Tests de primalitat|Test de Lucas-Lehmer]] |
||
[[de:Lucas-Test (Mathematik)]] |
[[de:Lucas-Test (Mathematik)]] |
Revisió del 17:00, 18 juny 2011
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
així com
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:
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:
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.