Diskrétní matematika - 4. týden Elementární teorie čísel - Primitivní kořeny e čísel Lukáš Vokřínek Masarykova univerzita Fakulta informatiky podzim 2024 Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel ooooooooo oo ooooooooooooo oooooooo 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 □ e Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel ooooooooo oo ooooooooooooo oooooooo 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. □ e Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel ooooooooo oo ooooooooooooo oooooooo 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. William Stein, Elementary Number Theory: Primes, Congruences, and Secrets, Springer, 2008. Dostupné na http://wstein.org/ent/ent.pdf 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 •oooooooo oo ooooooooooooo oooooooo Plán prednášky O Řád čísla, primitivní kořeny Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel O0OOOOOOO oo ooooooooooooo oooooooo Poslední z této řady tvrzení dává do souvislosti řády dvou čísel a řád jejich součinu: Necht m 6 N, a, b e Z, (a, m) = (b, m) = 1. Jestliže a je řac/i/ r a b je řádu s modulo m, kde (r, s) = 1, pak číslo a • b je řádu r • s modulo m. Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel O0OOOOOOO oo ooooooooooooo oooooooo Poslední z této řady tvrzení dává do souvislosti řády dvou čísel a řád jejich součinu: Lemma Necht m 6 N, a, b e Z, (a, m) = (b, m) = 1. Jestliže a je řac/i/ r a b je řádu s modulo m, kde (r, s) = 1, pa/c č/s/o a • b je rádu r • s modulo m. Důkaz. Označme r rád čísla a • b. Zřejmě platí (ab)st = 1 (mod m), proto r | st. Naopak podle definice řádu (ab)r = 1 (mod m) a umocněním obou stran kongruence dostaneme arsbrs = 1 (mod m). Protože je s řádem čísla a, je as = 1 (mod m), tj. brs = 1 (mod m), a proto t | rs. Z nesoudělnosti ras plyne ŕ | r. Analogicky dostaneme i s | r, a tedy (opět s využitím nesoudělnosti s,t) s - t \ r. Celkem tedy r — st. □ Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oo«oooooo oo ooooooooooooo oooooooo 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 čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oo«oooooo oo ooooooooooooo oooooooo 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, ŕ]. Nechť d = (s, ŕ). Definujme k jako součin těch prvočíselných mocnin p( z rozkladu s, které se v ŕ vyskytují ve stejné nebo vyšší mocnině (tj. pa | t) a položme d = k • I. Potom ak je řádu s//c a £/ je řádu t/l a snadno se vidí, že (s//c, ŕ//) = 1 (každé prvočíslo z rozkladu d se vyskytuje pouze v s/k nebo ŕ// ale ne v obou) a také s/k - t/l = [s, ŕ], takže podle předchozího lemmatu ak • £/ má řád [s, ŕ], jak jsme chtěli. □ Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oo«oooooo oo ooooooooooooo oooooooo Nechť 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, ŕ]. Nechť d = (s, ŕ). Definujme k jako součin těch prvočíselných mocnin p( z rozkladu s, které se v ŕ vyskytují ve stejné nebo vyšší mocnině (tj. pa | t) a položme d = k • I. Potom ak je řádu s//c a £/ je řádu t/l a snadno se vidí, že (s//c, ŕ//) = 1 (každé prvočíslo z rozkladu d se vyskytuje pouze v s/k nebo ŕ// ale ne v obou) a také s/k - t/l = [s, ŕ], takže podle předchozího lemmatu ak • £/ má řád [s, ŕ], jak jsme chtěli. □ Necht p G N je prvočíslo. Pak existuje prvek řádu p — 1 modulo p, t zv. primitivní kořen. Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel OOO0OOOOO oo ooooooooooooo oooooooo 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 čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel OOO0OOOOO oo ooooooooooooo oooooooo Důsledek Nechi m 6 N a r je nejmenší společný násobek všech řádů modulo m. Pak existuje číslo řádu r modulo m. 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 oooo»oooo oo ooooooooooooo oooooooo 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). Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooo»oooo oo ooooooooooooo oooooooo 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 x = 1 (mod 35) stupně 12 má 0. Celé číslo geZ, (g", m) = 1 nazveme primitivním kořenem modulo m, pokud je jeho řád modulo m roven (p(m). Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel OOOOOOOOO 09 ooooooooooooo oooooooo Nechť m > 0. 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é a £ Z, 0 < a < (p(m) s vlastností ga = a (mod m). Označujeme a — \ogg a a nazýváme diskrétním logaritmem, příp. indexem čísla a (vzhledem k danému m a zafixovanému primitivnímu kořeni g) a je bijekcí mezi množinami {a e Z] (a, m) = 1, 0 < a < m} a {x G Z; 0 < x < (f(m)}. Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel ooooooooo ooooooooooooo oooooooo Definice Nechť m > 0. 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 G Z, (a, m) — 1 existuje jediné a G Z, 0 < a < (p(m) s vlastností ga = a (mod m). Označujeme a — \ogg a a nazýváme diskrétním logaritmem, příp. indexem čísla a (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 ooooooooo oo ooooooooooooo ooooo»oo Algoritmus modulárního umocňování je založen na myšlence, že např. při počítání 264 (mod 1000) o 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, Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel ooooooooo oo ooooooooooooo ooooo»oo Algoritmus modulárního umocňování je založen na myšlence, že např. při počítání 264 (mod 1000) o 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^ <□► < [fp ► < -E ► < -E ► -E O °n O Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel ooooooooo OO ooooooooooooo OOOOOO0O Příklad (Ukázka průběhu algoritmu) Vypočtěme 2560 (mod 561). Řád čísla, primitivní kořeny ooooooooo Diskrétní logaritmus OO Kvadratické zbytky a nezbytky ooooooooooooo Výpočetní aspekty teorie čísel OOOOOO0O Příklad (Ukázka průběhu algoritmu) Vypočtěme 2560 (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 Řád čísla, primitivní kořeny ooooooooo Diskrétní logaritmus OO Kvadratické zbytky a nezbytky ooooooooooooo Výpočetní aspekty teorie čísel OOOOOO0O Příklad (Ukázka průběhu algoritmu) Vypočtěme 2560 (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 OOOOOOOOO OO OOOOOOOOOOOOO 0000000« 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.