Diferència entre revisions de la pàgina «Test de Lucas»

1 octet eliminats ,  fa 5 anys
m
Corregit: - coprimer s. + coprimers.
m (Corregit: correcte -> correcte, ja que si)
m (Corregit: - coprimer s. + coprimers.)
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 '' 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é ==
1.154.876

modificacions