Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel Diskrétní matematika - 4. týden Elementární teorie čísel - Primitivní kořeny Lukáš Vokřínek Masarykova univerzita Fakulta informatiky podzim 2020 Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel Obsah přednášky Q Řád čísla, primitivní kořeny Q Diskrétní logaritmus Q Kvadratické zbytky a nezbytky Q Výpočetní aspekty teorie čísel Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel Doporučené zdroje • Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni.cz/Matematika_drsne_svizne. • Michal Bulant, výukový text k přednášce Elementární teorie čísel, http: //is .muni . cz/el/1431/podzim2012/M6520/ um/main-print.pdf • Jiří Herman, Radan Kučera, Jaromír Šimša, Metody řešení matematických úloh. MU Brno, 2001. o William Stein, Elementary Number Theory: Primes, Congruences, and Secrets, Springer, 2008. Dostupné na http://wstein.org/ent/ent.pdf o Radan Kučera, výukový text k přednášce Algoritmy teorie čísel, http://www.math.muni.cz/~kucera/texty/ATC10.pdf Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel Minule ^^^^^^^^^^^^^^^^^^^^^H Poslední z této řady tvrzení dává do souvislosti řády dvou čísel a řád jejich součinu: Lemma__1 Necht m £ N, a, b £ Z b je řádu s modulo m, modulo m. , (a, m) = kde (r, s) (b, m) = 1. Jestliže a je rádu r a — 1, pak číslo a • b je rádu r • s Důkaz. i Označme S řád čísla a • b. Pak (ab)s = 1 (mod m) a umocněním obou stran kongruence dostaneme arSbrS = 1 (mod m). Protože je r řádem čísla a, je ar = 1 (mod m), tj. brS = 1 (mod m), a proto s | rS. Z nesoudělnosti ras plyne s | S. Analogicky dostaneme i r | ô, a tedy (opět s využitím nesoudělnosti r, s) r • s | S. Obráceně zřejmě platí (ab)rs = 1 (mod m), proto S | rs. Celkem tedy ô = rs. □ Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel Minule ^^^^^^^^^^^^^^^^^^^^^H Důsledek Necht m 6 N a r je nejmenší společný násobek všech řádů modulo m. Pak existuje číslo řádu r modulo m. Důkaz. Stačí pro a řádu s, b řádu t najít prvek řádu [s, t]. Nechť d = (s, t), pak tímto prvkem je ad • b. □ Pak všechna (a, m) = 1 splňují ar = 1 (mod m), tj. jsou to řešení kongruence xr = 1 (mod m) Zejména nás budou zajímat tzv. primitivní kořeny, tj. čísla mající řád přesně (p(m) - to je přesně počet řešení této rovnice. Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel Primitivní kořeny modulo součin Příklad Nechť m = 35 a nechť (a, m) = 1. Pak podle Eulerovy věty a4 = 1 (mod 5), a6 = 1 (mod 7) a12 = 1 (mod 5), a12 = 1 (mod 7) a12 = 1 (mod 35) Je tedy každé číslo řádu 12 (případně menšího, ale to vyloučíme časem). Tedy kongruence x12 = 1 (mod 35) stupně 12 má (p(35) = 4 • 6 = 24 řešení. Pokud je m dělitelné aspoň dvěma lichými prvočísly, primitivní kořen modulo m neexistuje. Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel Polynomiální kongruence modulo prvočíslo Uvažme f{x) = 0 (mod p) a vydělme f{x) se zbytkem kořenovým činitelem (x — a): f(x) = (x - a) • g{x) + r r= f(a) Pokud je a kořenem kongruence, dostaneme f{x) = (x - a) • g{x) (mod p). Protože je p prvočíslo, jsou kořeny ^(x) právě a a kořeny g(x), který je stupně o jedna menšího. Protože konstantní polynomy nemají kořeny, má f(x) maximálně tolik kořenů, kolik je jeho stupeň (bacha na ^(x) = 0). Důsledek x = 1 (mod p) má kořeny právě ±1. Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel Necht p G N je prvočíslo. Pak existuje primitivní kořen modulo p. Důkaz. Nechť r je maximální řád, podle Eulerovy věty r p — 1 nenulových zbytkových tříd jsou kořeny p — 1. Pak všech xr = 1 (mod p) a podle předchozího p — 1 < r. □ Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel Nech^^^^^^prvočí^ Důkaz Platí (f(pk) = pk~x • (p — 1) a tito činitelé jsou nesoudělní. Nechť g (mod p) je primitivní kořen, tj. prvek řádu p — 1. Pak řád g (mod pk) bude násobkem p — 1. Stačí najít prvek řádu pk_1. Ukážeme, že je jím 1 + p; indukcí vzhledem ke k = 1, 2,...; konkrétně ukážeme: >k-2 (l+p)P ^1 + p /c-1 1 (mod pk) (instance pro k + 1 dá (1 + p)p" A = 1 + pk = 1 (mod pk)). C Lemma a = b (mod pfc) ap = bp (mod p^1) Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel Hledání primitivního kořene Sofistikovaná metoda se zatím nezná. Zkoušením po nějaké době uspějeme: Kolik je primitivních kořenů modulo prvočíslo? Jsou to právě ga (mod p), kde (s,(pp) = 1, tedy jich je (p((p(p)). Přitom platí pM^(p)) e O(loglogp), takže pravděpodobnost, že náhodné číslo bude primitivním kořenem je zhruba 1/log log p a počet pokusů potřebných k nalezení primitivního kořene s předem danou pravděpodobností je úměrný log log p, tedy logaritmický vzhledem k délce vstupu (ověření toho, zda se vskutku jedná o primitivní kořen trvá déle, viz příště). Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel Definice Nechť m 6 N. Celé číslo geZ, (g", m) — 1 nazveme primitivním kořenem modulo m, pokud je jeho řád modulo m roven (p(m). Lemma Je-li g primitivní kořen modulo m, pak pro každé číslo a £ Z, (a, m) — 1 existuje jediné x3 G Z, 0 < xa < V9(rn) s vlastnostígXa = a (mod m). Funkce a xa se nazývá diskrétní logaritmus, př/p. /r?c/ex č/s/a x (vzhledem k danému m a zafixovanému primitivnímu kořeni g) a je bijekcí mezi množinami {a G Z; (a, m) = 1, 0 < a < m} a {x G Z; 0 < x < 0 if (exponent mod 2 1): result := (result * base) mod mod u 1 us exponent := exponent » 1 base = (base * base) mod modulus return result Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel Algoritmus modulárního umocňování je založen na myšlence, že např. při počítání 264 (mod 1000) 9 není třeba nejprve počítat 264 a poté jej vydělit se zbytkem číslem 1000, ale lépe je postupně násobit „dvojky" a kdykoliv je výsledek větší než 1000, provést redukci modulo 1000, • ale zejména, že není třeba provádět takové množství násobení (v tomto případě 63 naivních násobení je možné nahradit pouze šesti umocněními na druhou, neboť 264 = (((((22)2)2)2)2)2. Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel Příklad (Ukázka průběhu algoritmu) Vypočtěme 25b0 (mod 561). Protože 560 = (1000110000)2, dostaneme uvedeným algoritmem exponent base result exp's last digit 560 2 1 0 280 4 1 0 140 16 1 0 70 256 1 0 35 460 1 1 17 103 460 1 8 511 256 0 4 256 256 0 2 460 256 0 1 103 256 1 0 511 1 0 A tedy 25b0 = 1 (mod 561). Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel Efektivita modulárního umocňování V průběhu algoritmu se pro každou binární číslici exponentu provede umocnění základu na druhou modulo n (což je operace proveditelná v nejhůře kvadratickém čase), a pro každou „jedničku" v binárním zápisu navíc provede jedno násobení. Celkově jsme tedy schopni provést modulární umocňování nejhůře v kubickém čase.