Přeskočit na obsah

Primitivní kořen

Z Wikipedie, otevřené encyklopedie

Primitivní kořen modulo n je v modulární aritmetice 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).

Alternativní definice

[editovat | editovat zdroj]

Primitivním kořenem modulo n je takové číslo g, pro které neexistuje žádný menší přirozený exponent k než φ(n) takový, že gk ≡ 1 (mod n)[1], tzn. g je primitivní kořen modulo n .

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

Vlastnosti:

  • s rostoucím k se zbytek 3k mod 7 opakuje v konečné množině čísel, v tomto případě {3, 2, 6, 4, 5, 1}
  • pokud n je prvočíslo, tak perioda gk mod n je konečná a má n − 1 prvků
  • žá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

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.[3][4] Existují pouze optimalizace k nalezení dvojice g a n, které jsou rychlejší než postupné zkoušení metodou pokus – omyl.

  1. RŮŽIČKA, Jiří. Teorie čísel, sbírka příkladů. Brno, 2006 [cit. 2023-06-18].  69 s. Diplomová práce. Masarykova univerzita, Fakulta informatiky. Vedoucí práce Michal Bulant. s. 58. Dostupné online.
  2. STROMQUIST, Walter. What are primitive roots? [online]. Bryn Mawr College [cit. 2017-07-03]. Dostupné v archivu pořízeném z originálu dne 2017-07-03. 
  3. 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."
  4. Robbins 2006, p. 159: "There is no convenient formula for computing [the least primitive root]."