Obsah
Výpočet primitivních kořenů je užitečnou dovedností v kryptografii a teorii čísel. Číslo "g" je primitivní kořen pro dané prvočíslo "p", pokud g mod p má modul p-1 řádu. To znamená, že seznam "g1 mod p", "g2 mod p" až "g (p-1) mod p" obsahuje všechna celá čísla od 1 do (p-1). Neexistuje žádný známý algoritmus pro efektivní výpočet primitivních kořenů. Nejjednodušší metodou je vyzkoušet každé možné číslo od 2 do (p-1).
Pokyny
-
Vyberte si hlavní číslo, "p", jako pět. Primární číslo nemá dělitele mimo sebe a jednoho. Například, čtyři není prvočíslo protože “4/2 = 2”, to má 2 jako jeden z jeho dělitelů.
-
Vypočítejte "2 ^ n mod p" pro každé celé číslo "n" od 1 do (p-1). Pomocí příkladu, "p" je 5, pak spočítat "2 ^ n mod 5" pro "n" od 1 do 4. Tím se vytvoří seznam:
2 ^ 1 = 2 mod 5 = 2 2 ^ 2 = 4 mod 5 = 4 2 ^ 3 = 8 mod 5 = 3 2 ^ 4 = 16 mod 5 = 1
-
Ujistěte se, že seznam čísel obsahuje všechny možné stopy po pěti. Seznam 2, 4, 3 a 1 se kvalifikuje, takže 2 je primitivní kořen se zbytkem 5. Pokud místo toho byl seznam 2,1,4 a 1, což je seznam pro 4, pak 4 by nebylo primitivní kořen, protože číslo 3 chybí v seznamu.
-
Opakujte předchozí krok pro všechna celá čísla menší než pět. Číslo tři je také primitivní kořen odpočinku pět, ale čtyři ne; pak dva a pět jsou primitivní kořeny pro pět.