Test de Lucas: diferència entre les revisions
espais |
|||
Línia 19: | Línia 19: | ||
Per realitzar aquestes [[Potenciació modular|potències modulars]] hauria d'usar el mètode accelerat de [[exponenciació binària]]. |
Per realitzar aquestes [[Potenciació modular|potències modulars]] hauria d'usar el mètode accelerat de [[exponenciació binària]]. |
||
Aquest [[algorisme]] és correcte, ja que si '' |
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|arrel primitiva mòdul ''n'']] i qualsevol arrel primitiva passarà dos passos de l'algorisme. |
||
== Vegeu també == |
== Vegeu també == |
Revisió del 00:12, 24 feb 2018
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 coprimers. Si a també passa el segon pas, llavors l'ordre de a al grup (Z/nZ)* é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.