Obsah
Výpočet primitívnych koreňov je užitočná zručnosť v kryptografii a teórii čísel. Číslo "g" je primitívny koreň pre dané prvočíslo "p", ak g mod p má modul p-1 poradia. To znamená, že zoznam "g1 mod p", "g2 mod p" až "g (p-1) mod p" obsahuje všetky celé čísla od 1 do (p-1). Neexistuje žiadny známy algoritmus na efektívne vypočítanie primitívnych koreňov. Najjednoduchšou metódou je vyskúšať každé možné číslo od 2 do (p-1).
inštrukcia
-
Vyberte prvočíslo, "p", ako päť. Primárne číslo nemá deliteľov nad seba a jedného. Napríklad štyri nie je prvočíslo, pretože "4/2 = 2", má 2 ako jeden z jeho deliteľov.
-
Vypočítajte "2 ^ n mod p" pre každé celé číslo "n" od 1 do (p-1). Pomocou príkladu "p" je 5, potom vypočítajte "2 ^ n mod 5" pre "n" od 1 do 4. Toto vytvorí zoznam:
2 ^ 1 = 2 mod 5 = 2 2 ^ 2 = 4 mod 5 = 4 2 ^ 3 = 8 mod 5 = 3 2 ^ 4 = 16 mod 5 = 1
-
Uistite sa, že zoznam čísel obsahuje všetky možné stopy po piatich. Zoznam 2, 4, 3 a 1 sa kvalifikuje, takže 2 je primitívny koreň so zvyškom 5. Ak namiesto toho bol zoznam 2,1,4 a 1, čo je zoznam pre 4, potom 4 by nebolo primitívny koreň, pretože číslo 3 chýba v zozname.
-
Opakujte predchádzajúci krok pre všetky celé čísla menšie ako päť. Číslo tri je tiež primitívny koreň odpočinku päť, ale štyri nie; potom dva a päť sú primitívne korene pre päť.