Primitivní kořen

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání

Primitivní kořen modulo n je v modulární aritmetice je takové číslo g, pokud pro každé celé číslo a nesoudělné s n existuje takové celé číslo k, pro které platí gka (mod n).

Příklad[editovat | editovat zdroj]

Číslo 3 je primitivní kořen modulo 7 protože:

30 = 1 ≡ 1 (mod 7)
31 = 3 ≡ 3 (mod 7)
32 = 9 ≡ 2 (mod 7)
33 = 27 ≡ 6 (mod 7)
34 = 81 ≡ 4 (mod 7)
35 = 243 ≡ 5 (mod 7)
36 = 729 ≡ 1 (mod 7)
37 = 2187 ≡ 3 (mod 7)

Vlastnosti:

  • s rostoucím k se zbytek 3k mod 7 opakuje v konečné množině čísel, v tomto případě {1, 3, 2, 6, 4, 5}.
  • jejich počet je konečný, menší než n, nazývá se perioda gk mod n
  • žádný zbytek po dělení není nulový
  • 3k má k modulo 7 statisticky rovnoměrnou distribuci
  • vlastnost používaná v šifrování – pouze ze znalosti zbytku po dělení nelze zpětně určit g a k.

Historie[editovat | editovat zdroj]

Carl Friedrich Gauss definoval primitivní kořeny v článku č. 57 Disquisitiones Arithmeticae z roku 1801, kde připustil, že tento termín první použil Leonhard Euler. V článku č. 56 téže publikace pronesl, že o primitivních kořenech věděli jak Euler tak Johan Heinrich Lambert, avšak Gauss poprvé přesně ukázal, že primitivní kořeny existují pro prvočísla, a to dokonce ve dvou důkazech.

Určování primitivních kořenů[editovat | editovat zdroj]

K určování primitivních kořenů modulo n zatím neexistuje žádný jednoduchý postup nebo vzoreček.[1][2] Existují pouze optimalizace k nalezení dvojice g a n, které jsou o rychlejší než postupné zkoušení metodou pokus – omyl.

Využití[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

  1. von zur Gathen & Shparlinski 1998, pp. 15–24: "One of the most important unsolved problems in the theory of finite fields is designing a fast algorithm to construct primitive roots."
  2. Robbins 2006, p. 159: "There is no convenient formula for computing [the least primitive root]."