Diskrétní matematika - 4. týden Elementární teorie čísel - Primitivní kořeny e čísel 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 oooooooo oo oooo oooooooo Obsah přednášky Rád čísla, primitivní kořeny Q Diskrétní logaritmus Q Kvadratické zbytky a nezbytky Q Výpočetní aspekty teorie čísel □ s Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooooooo oo oooo 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. Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooooooo oo oooo 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. 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 •ooooooo oo oooo oooooooo Plán prednášky Řád čísla, primitivní kořeny Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel O0OOOOOO oo oooo oooooooo Minule 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 řác/u s modulo m, kde (r, s) = 1, pa/c č/s/o 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 O0OOOOOO oo oooo oooooooo Minule 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. □ 1_F Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel OO0OOOOO oo oooo oooooooo Minule 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 OO0OOOOO oo oooo oooooooo Minule 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. □ Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel OOÄOOOOO oo oooo oooooooo Minule 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 OOO0OOOO oo oooo 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 OOOOOOOO oo oooo 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á k-2 (l+p)P ^1 + p k-1 1 (mod pk) k-i (instance pro k + 1 dá (1 + p)p = 1 + p (mod p )) Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel OOOOOO0O OO oooo oooooooo Věta Necht p e N je prvočíslo. Pak existuje primitivní kořen modulo p . 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: (1 + p)pk~2 = 1 + pk~x ž 1 (mod pk) (instance pro k + 1 dá (1 + p)pkl = 1 + pk = 1 (mod p^)). □ Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel OOOOOO0O oo oooo oooooooo 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 k-1 1 (mod pk) k-i (instance pro k + 1 dá (1 + p)p" ± = 1 + pk = 1 (mod p^)) □ Lemma a = £> (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 ooooooo* oo oooo oooooooo 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? Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel ooooooo* oo oooo oooooooo 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 (a,(pp) = 1, tedy jich je (p((p(p)). Přitom platí p/(p((p(p)) G O(loglogp), takže pravděpodobnost, že náhodné číslo bude primitivním kořenem je zhruba 1/log log p Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel ooooooo* oo oooo oooooooo 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 (a,(pp) = 1, tedy jich je (p((p(p)). Přitom platí p/(p((p(p)) G 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 Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel ooooooo* oo oooo oooooooo 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 (a,(pp) = 1, tedy jich je (p((p(p)). Přitom platí p/(p((p(p)) G 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 oooooooo Plán přednás Diskrétní logaritmus •O Kvadratické zbytky a nezbytky oooo Výpočetní aspekty teorie čísel OOOOOOOO Q Diskrétní logaritmus j i □ S1 Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooooooo om oooo oooooooo 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). Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooooooo om oooo oooooooo 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). Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooooooo om oooo oooooooo Definice Nechť m G 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 G 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. /Vie/ex č/s/a x (vzhledem k danému m a zafixovanému primitivnímu koreni g) a je bijekcí mezi množinami {a G Z; (a, m) = 1, 0 < a < m} a {x G Z; 0 < x < ooo Výpočetní aspekty teorie čísel oooooooo 0 Kvadratické zbytky a nezbytky j r □ dš1 Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooooooo oo o«oo oooooooo Kvadratické kongruence modulo prvočíslo Věta_ Necht p je liché prvočíslo a (a, p) = p—i (mod p) má řešení, právě když a 2 1. Kongruence x2 = a = 1 (mod p). Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooooooo oo o«oo oooooooo Kvadratické kongruence modulo prvočíslo Věta Necht p je liché prvočíslo a (a, p) = 1. Kongruence x2 = a (mod p) má řešení, právě když a^~ = 1 (mod p). Důkaz. Použijeme primitivní kořen g a vyjádříme x = a (mod p) pomocí něj: nechť x = g€, a = ga, pak kongruence je ekvivalentní (g^)2 = ga (mod p) 2^ = a (modp-1). Protože je p — 1 sudé, řešení existuje, právě když a je sudé: a = 0 (mod 2) £=± • a = 0 (modp-1). a^ = g^'a = g° = 1 (mod p). □ Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooooooo oo oo»o oooooooo Legendreův symbol Věta Necht p je liché prvočíslo a (a, p) = 1. Kongruence x2 = a (mod p) má řešení, právě když a 2 = 1 (mod p). Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooooooo oo oo»o oooooooo Legendreův symbol Necht p je liché prvočíslo a (a, p) = 1. Kongruence x2 = a p-i (mod p) má řešení, právě když a 2 =1 (mod p) Definice Definujeme (-) = < 1 a kvadratický zbytek modulo p — 1 a kvadratický nezbytek modulo p 0 a soudělné s p Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooooooo oo oo»o oooooooo Legendreův symbol Necht p je liché prvočíslo a (a, p) = 1. Kongruence x2 = a p-i (mod p) má řešení, právě když a 2 =1 (mod p) Definice Definujeme (-) = < 1 a kvadratický zbytek modulo p — 1 a kvadratický nezbytek modulo p 0 a soudělné s p p-i Jednoduchým důsledkem věty dostávame (-) = a 2 (mod p) p-i p-i protože (a 2 )2 = ap 1 = 1, je a 2 rovno ±1 Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooooooo oo ooo« oooooooo Legendreův symbol Důsledek (—^) = +1, resp. — 1, pokud p = 1 (mod 4), resp. p = 3 (mod 4). Tedy kongruence x2 = — 1 (mod p) má řešení, právě když p dává po dělení čtyřmi zbytek 1. Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooooooo oo ooo« oooooooo Legendreův symbol Důsledek (—^) = +1, resp. — 1, pokud p = 1 (mod 4), resp. p = 3 (mod 4). Tedy kongruence x2 = — 1 (mod p) má řešení, právě když p dává po dělení čtyřmi zbytek 1. Počítání Legendreova symbolu je jednoduché s následujícími pravidly: • (?) = (f)(J). • a = b (mod p) (f) = (J), •(f) = (-l)^. • (?) = (f)-(-l)^- Řád čísla, primitivní kořeny oooooooo Diskrétní logaritmus oo Kvadratické zbytky a nezbytky oooo Výpočetní aspekty teorie čísel •ooooooo 0 Výpočetní aspekty teorie číse □ S1 Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooooooo oo oooo o«oooooo Základní úlohy výpočetní teorie čísel V mnoha praktických úlohách využívajících výsledky teorie čísel je zapotřebí umět rychle provést jeden či více z následujících výpočtů: O běžné aritmetické operace (součet, součin, dělení se zbytkem) na celých číslech, Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooooooo oo oooo o«oooooo Základní úlohy výpočetní teorie čísel V mnoha praktických úlohách využívajících výsledky teorie čísel je zapotřebí umět rychle provést jeden či více z následujících výpočtů: O běžné aritmetické operace (součet, součin, dělení se zbytkem) na celých číslech, O zbytek mocniny celého čísla a na přirozené číslo n po dělení daným m. Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooooooo oo oooo o«oooooo Základní úlohy výpočetní teorie čísel V mnoha praktických úlohách využívajících výsledky teorie čísel je zapotřebí umět rychle provést jeden či více z následujících výpočtů: O běžné aritmetické operace (součet, součin, dělení se zbytkem) na celých číslech, O zbytek mocniny celého čísla a na přirozené číslo n po dělení daným m. O inverzi celého čísla a modulo m £ N, Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooooooo oo oooo o«oooooo Základní úlohy výpočetní teorie čísel V mnoha praktických úlohách využívajících výsledky teorie čísel je zapotřebí umět rychle provést jeden či více z následujících výpočtů: O běžné aritmetické operace (součet, součin, dělení se zbytkem) na celých číslech, O zbytek mocniny celého čísla a na přirozené číslo n po dělení daným m. Q inverzi celého čísla a modulo m £ N, O největší společný dělitel dvou celých čísel (a případně koeficienty do Bezoutovy rovnosti), Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooooooo oo oooo o«oooooo Základní úlohy výpočetní teorie čísel V mnoha praktických úlohách využívajících výsledky teorie čísel je zapotřebí umět rychle provést jeden či více z následujících výpočtů: O běžné aritmetické operace (součet, součin, dělení se zbytkem) na celých číslech, O zbytek mocniny celého čísla a na přirozené číslo n po dělení daným m. Q inverzi celého čísla a modulo m £ N, O největší společný dělitel dvou celých čísel (a případně koeficienty do Bezoutovy rovnosti), O rozhodnout o daném čísle, je-li prvočíslo nebo složené, Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooooooo oo oooo o«oooooo Základní úlohy výpočetní teorie čísel V mnoha praktických úlohách využívajících výsledky teorie čísel je zapotřebí umět rychle provést jeden či více z následujících výpočtů: O běžné aritmetické operace (součet, součin, dělení se zbytkem) na celých číslech, O zbytek mocniny celého čísla a na přirozené číslo n po dělení daným m. Q inverzi celého čísla a modulo m £ N, O největší společný dělitel dvou celých čísel (a případně koeficienty do Bezoutovy rovnosti), O rozhodnout o daném čísle, je-li prvočíslo nebo složené, O v případě složenosti rozložit dané číslo na součin prvočísel. Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooooooo oo oooo oo«ooooo Základní aritmetické operace Základní aritmetické operace se i na velkých číslech obvykle provádějí obdobně jako jsme se to učili na základní a střední škol kdy umíme sčítat v lineárním, násobit a dělit se zbytkem v kvadratickém čase. Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooooooo oo oooo oo«ooooo Základní aritmetické operace Základní aritmetické operace se i na velkých číslech obvykle provádějí obdobně jako jsme se to učili na základní a střední škol kdy umíme sčítat v lineárním, násobit a dělit se zbytkem v kvadratickém čase. Pro násobení, které je základem mnoha dalších operací, existují asymptoticky rychlejší algoritmy (typu rozděl a panuj) - např. první takový Karatsubův (1960) časové náročnosti Q(n}o^3) Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooooooo oo oooo oo«ooooo Základní aritmetické operace Základní aritmetické operace se i na velkých číslech obvykle provádějí obdobně jako jsme se to učili na základní a střední škole, kdy umíme sčítat v lineárním, násobit a dělit se zbytkem v kvadratickém čase. Pro násobení, které je základem mnoha dalších operací, existují asymptoticky rychlejší algoritmy (typu rozděl a panuj) - např. první takový Karatsubův (1960) časové náročnosti 0(r?log23) nebo algoritmus Schónhage-Strassenův (1971) časové náročnosti 0(r? log n log log n), který využívá tzv. Fast Fourier Transform. Ten je ale přes svou asymptotickou převahu výhodný až pro násobení čísel majících alespoň desítky tisíc cifer (a používá se tak např. v GIMPS). Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooooooo oo oooo oo«ooooo Základní aritmetické operace Základní aritmetické operace se i na velkých číslech obvykle provádějí obdobně jako jsme se to učili na základní a střední škole, kdy umíme sčítat v lineárním, násobit a dělit se zbytkem v kvadratickém čase. Pro násobení, které je základem mnoha dalších operací, existují asymptoticky rychlejší algoritmy (typu rozděl a panuj) - např. první takový Karatsubův (1960) časové náročnosti 0(r?log23) nebo algoritmus Schónhage-Strassenův (1971) časové náročnosti 0(r? log n log log n), který využívá tzv. Fast Fourier Transform. Ten je ale přes svou asymptotickou převahu výhodný až pro násobení čísel majících alespoň desítky tisíc cifer (a používá se tak např. v GIMPS). Pěkný přehled je např. na http://en.wikipedia.org/wiki/ Computational_complexity_of_mathematical_operations Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooooooo oo oooo ooo«oooo GCD a modulární inverze Jak už jsme ukazovali dříve, výpočet řešení kongruence a • x = 1 (mod m) s neznámou x lze snadno (díky Bezoutově větě) převést na výpočet největšího společného dělitele čísel a a m a na hledání koeficientů /c, / do Bezoutovy rovnosti k • a + / • m = 1 (nalezené k je pak onou hledanou inverzí a modulo m). Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel OOOOOOOO OO OOOO OOO0OOOO GCD a modulární inverze Jak už jsme ukazovali dříve, výpočet řešení kongruence a • x = 1 (mod m) s neznámou x lze snadno (díky Bezoutově větě) převést na výpočet největšího společného dělitele čísel a a m a na hledání koeficientů /c, / do Bezoutovy rovnosti k • a + / • m = 1 (nalezené k je pak onou hledanou inverzí a modulo m). function exte n ded _gcd(a, m) if m — 0 return (1 ■ 0) else (q, r) := divide (a, m) (k, 1) := extended_gcd(m, r) return (1 , k - q * 1 ) Podrobná analýza (viz např. [Knuth] nebo [Wiki]) ukazuje, že tento algoritmus je kvadratické časové složitosti. Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooooooo oo oooo oooo«ooo Modulární umocňování Modulární umocňování je, jak jsme již viděli dříve, velmi využívaná operace mj. při ověřování, zda je dané číslo prvočíslo nebo číslo složené. Jedním z efektivních algoritmů je tzv. modulární umocňování zprava doleva: Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooooooo oo oooo oooo«ooo Modulární umocňování Modulární umocňování je, jak jsme již viděli dříve, velmi využívaná operace mj. při ověřování, zda je dané číslo prvočíslo nebo číslo složené. Jedním z efektivních algoritmů je tzv. modulární umocňování zprava doleva: function mod u la r_pow ( base , exponent , modu lus) result := 1 while exponent > 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 OOOOOOOO oo OOOO OOOOO0OO 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, Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooooooo oo oooo 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) 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 OOOOOOOO OO OOOO OOOOOO0O Příklad (Ukázka průběhu algoritmu) 1 Vypočtěme 2560 (mod 561). Řád čísla, primitivní kořeny OOOOOOOO Diskrétní logaritmus oo Kvadratické zbytky a nezbytky oooo 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 OOOOOOOO Diskrétní logaritmus OO Kvadratické zbytky a nezbytky oooo 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 OOOOOOOO oo oooo ooooooo* 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.