Primitivní kořen

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í g^k ≡ a (mod n).

Alternativní definice

Primitivním kořenem modulo n je takové číslo g, pro které neexistuje žádný menší přirozený exponent k než φ(n) takový, že g^k ≡ 1 (mod n)^[1], tzn. g je primitivní kořen modulo n ${\displaystyle \Leftrightarrow \nexists \;k\in \mathbb {N} \,.\,0<k<\varphi (n)\,.\,g^{k}\equiv 1{\pmod {n}}}$.

Příklad

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

${\displaystyle {\begin{array}{rcrcrcrcrcr}3^{1}&=&3^{0}\times 3&\equiv &1\times 3&=&3&\equiv &3{\pmod {7}}\\3^{2}&=&3^{1}\times 3&\equiv &3\times 3&=&9&\equiv &2{\pmod {7}}\\3^{3}&=&3^{2}\times 3&\equiv &2\times 3&=&6&\equiv &6{\pmod {7}}\\3^{4}&=&3^{3}\times 3&\equiv &6\times 3&=&18&\equiv &4{\pmod {7}}\\3^{5}&=&3^{4}\times 3&\equiv &4\times 3&=&12&\equiv &5{\pmod {7}}\\3^{6}&=&3^{5}\times 3&\equiv &5\times 3&=&15&\equiv &1{\pmod {7}}\\\end{array}}}$

Vlastnosti:

• s rostoucím k se zbytek 3^k 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 g^k mod n je konečná a má n − 1 prvků
• žádný zbytek po dělení není nulový
• 3^k 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

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ů

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.

Využití

• pro asymetrické šifrování k definici soukromého a veřejného klíče

Reference