Conţinut
Calculul rădăcinilor primitive este o abilitate utilă în criptografie și teoria numerelor. Un număr "g" este o rădăcină primitivă pentru un prim număr dat "p" dacă g mod p are modulul p-1. Aceasta înseamnă că lista "g1 mod p", "g2 mod p" și "g (p-1) mod p" conține toate numerele întregi de la 1 la (p-1). Nu există un algoritm cunoscut pentru a calcula eficient rădăcinile primitive. Metoda cea mai simplă este încercarea fiecărui număr posibil de la 2 la (p-1).
instrucțiuni de ghidare
-
Alegeți un număr prime, "p", cum ar fi cinci. Un număr prime nu are divizori dincolo de el însuși și unul. De exemplu, patru nu este un număr prime deoarece "4/2 = 2", are 2 ca unul dintre divizori.
-
Calculați "2 ^ n mod p" pentru fiecare număr întreg "n" de la 1 la (p-1). Folosind exemplul, "p" este 5, apoi calculează "2 ^ n mod 5" pentru "n" de la 1 la 4. Aceasta produce lista:
2 ^ 1 = 2 mod 5 = 2 2 ^ 2 = 4 mod 5 = 4 2 ^ 3 = 8 mod 5 = 3 2 ^ 4 = 16 mod 5 = 1
-
Asigurați-vă că lista numerelor conține toate urmele posibile de cinci. Lista 2, 4, 3 și 1 se califică, deci 2 este o rădăcină primitivă cu restul 5. Dacă, în schimb, lista ar fi 2,1,4 și 1, care este lista pentru 4, atunci 4 nu ar fi o rădăcină primitivă deoarece numărul 3 lipsește din listă.
-
Repetați pasul anterior pentru toate numerele întregi mai mici de cinci. Numărul trei este, de asemenea, o rădăcină primitivă de odihnă cinci, dar patru nu este; apoi două și cinci sunt rădăcinile primitive pentru cinci.