Primitivní kořen

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í 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), tzn. g je primitivní kořen modulo n $\iff \nexists k\in \mathbb{N}.0<k<\phi (n).g^k\equiv 1(\mathrm{mod}n)$.

Příklad

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

$\begin{array}{ccccccccc}{3}^1& =& 3^0\times 3& \equiv & 1\times 3& =& 3& \equiv & 3(\mathrm{mod}7)\\ 3^2& =& 3^1\times 3& \equiv & 3\times 3& =& 9& \equiv & 2(\mathrm{mod}7)\\ 3^3& =& 3^2\times 3& \equiv & 2\times 3& =& 6& \equiv & 6(\mathrm{mod}7)\\ 3^4& =& 3^3\times 3& \equiv & 6\times 3& =& 18& \equiv & 4(\mathrm{mod}7)\\ 3^5& =& 3^4\times 3& \equiv & 4\times 3& =& 12& \equiv & 5(\mathrm{mod}7)\\ 3^6& =& 3^5\times 3& \equiv & 5\times 3& =& 15& \equiv & 1(\mathrm{mod}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. 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