Primitivní kořen: Porovnání verzí
Nová stránka: '''Primitivní kořen''' modulo ''n'' je v modulární aritmetice je takové číslo ''g'', pokud pro každé celé číslo nes… značka: editor wikitextu 2017 |
(Žádný rozdíl)
|
Verze z 8. 5. 2020, 15:15
Primitivní kořen modulo n je v modulární aritmetice je takové číslo g, pokud pro každé celé číslo nesoudělné s n existuje takové celé číslo k, pro které platí gk ≡ a (mod n).
Příklad
Čí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
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.[1][2] Existují pouze optimalizace k nalezení dvojice g a n, které jsou o rychlejší než postupné zkoušení metodou pokus – omyl.
Využití
- pro asymetrické šifrování k definici soukromého a veřejného klíče
