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í gk ≡ 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 gk ≡ 1 (mod n), tzn. g je primitivní kořen modulo n \Leftrightarrow \nexists \; k \in \mathbb{N} \, . +more \, 0 .

Příklad

Číslo 3 je primitivní kořen modulo 7 protože: :: \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 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

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. +more 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

Reference

Kategorie:Modulární aritmetika