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í 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 .
Příklad Číslo 3 je primitivní kořen modulo 7 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
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. 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."Robbins 2006, p. 159: "There is no convenient formula for computing [the least primitive root]." 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