Diskrétní matematika - 4. týden Elementární teorie čísel - Primitivní kořeny e čísel Lukáš Vokřínek Masarykova univerzita Fakulta informatiky podzim 2022 Řád čísla, | ooooooo Obsa 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 oooooooo oo ooooooo 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 ooooooo 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 •ooooooo oo ooooooo oooooooo Plán prednášky O Řád čísla, primitivní kořeny Řád čísla, primitivní kořeny O0OOOOOO Diskrétní oo logaritmus Kvadratické zbytky a nezbytky ooooooo Výpočetní aspekty teorie čísel 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 O0OOOOOO Diskrétní oo logaritmus Kvadratické zbytky a nezbytky ooooooo Výpočetní aspekty teorie čísel 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ůkaz. Označme S řád čísla a • b. Pak (ab)^ = 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 | 5. 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 oo«ooooo Diskrétní OO logaritmus Kvadratické zbytky a nezbytky ooooooo Výpočetní aspekty teorie čísel 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 oo«ooooo oo ooooooo 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 OOOOOOOO oo ooooooo 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 ooooooo 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 OOO0OOOO oo ooooooo 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á (m) je g (mod m). Z vlastností řádu pak x = y (mod íp(m)), tj. x proto je zobrazení injektivní, a tedy i surjektivní. □ Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel OOOOOOOO OO »000000 oooooooo Plán prednášky Q Kvadratické zbytky a nezbytky Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky oooooooo oo o«ooooo Výpočetní aspekty teorie čísel OOOOOOOO Kvadratické kongruence modulo prvočíslo Věta _ Nechť 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«ooooo oooooooo Kvadratické kongruence modulo prvočíslo Nechť 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) Důkaz Použijeme primitivní kořen g a vyjádříme x2 = a (mod p) pomocí něj: nechť x = g^, a = ga, pak kongruence je ekvivalentní (g^)2 = ga (mod p) 2^ = a (modp-1). I Protože je p — 1 sudé, řešení existuje, právě když a je sudé: a = 0 (mod 2) p-i ^, -2 p-i ^ a 2 = g- a = 0 (mod p — 1). V-« = g° = 1 (mod p).D Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooooooo oo oo»oooo 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»oooo 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). r 1 Definice 1 a kvadratický zbytek modulo p Definujeme (|) = < — 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»oooo 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). r 1 Definice 1 a kvadratický zbytek modulo p Definujeme (|) = < — 1 a kvadratický nezbytek modulo p. ^0 a soudělné s p Jednoduchým důsledkem věty dostáváme (-) = a 2 (mod p): p protože (a 2 y = aP~L = 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»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»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) = (f)-(-l)^- Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel OOOOOOOO OO OOOO0OO oooooooo Jacobiho symbol Definice a libovolné, n = pi • • • p^ liché; definujeme Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooooooo oo oooo»oo oooooooo Jacobiho symbol Definice a libovolné, n = pi • • • p^ liché; definujeme n Pi Pk Počítání Jacobiho symbolu je jednoduché s následujícími pravidly: • (f) = (f)(Ž). •(Ž) = (-i)^. * (tt) • (£) = (-1)^^ Pro m, n lichá. Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooooooo oo ooooo»o oooooooo Jacobiho symbol Příklad Spočtěte 383 Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooooooo oo ooooo»o oooooooo Jacobiho symbol Příklad Spočtěte 383 Příklad Spočtěte (|) pro prvočíslo p, tj. rozhodněte, kdy je 3 kvadratický zbytek modulo prvočíslo p. Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel OOOOOOOO oo oooooo* oooooooo Testování prvočíselnosti test Je-li p prvočíslo, pak ap 1 = 1 (mod p) (pro a náhodné nesoudělné s p). Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooooooo oo oooooo* oooooooo Testování prvočíselnosti test Je-li p prvočíslo, pak ap 1 = 1 (mod p) (pro a náhodné nesoudělné s p). složitější test Je-li p prvočíslo, pak a 2 = ±1 (mod p) (pro a náhodné nesoudělné s p). Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel OOOOOOOO oo oooooo* oooooooo Testování prvočíselnosti test Je-li p prvočíslo, pak ap 1 = 1 (mod p) (pro a náhodné nesoudělné s p). složitější test Je-li p prvočíslo, pak a 2 = ±1 (mod p) (pro a náhodné nesoudělné s p). jeste složitější test p-i Je-li p prvočíslo, pak a 2 = (^) (mod p) (pro a náhodné nesoudělné s p). Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel OOOOOOOO OO OOOOOOO »0000000 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 oooooooo oo ooooooo 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 OOOOOOOO oo ooooooo Výpočetní aspekty teorie čísel 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. <□► < rnP ► < -E ► < -E ► -E O °n O Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooooooo oo ooooooo 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 ooooooo 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 ooooooo 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 ooooooo 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. <□► < rnP ► < -E ► < -E ► -E O °n O Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel OOOOOOOO oo ooooooo oooooooo 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 oooooooo oo ooooooo Výpočetní aspekty teorie čísel 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(nlog23) <□► < rnP ► < -E ► < -E ► -E O °n O Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel oooooooo oo ooooooo 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 ooooooo 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 <□► < rnP ► < -E ► < -E ► -E O °n O Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel OOOOOOOO OO OOOOOOO 000*0000 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 OOOOOOO 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 OOOOOOO 0000*000 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 OOOOOOO 0000*000 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 <□► < rnP ► < -E ► < -E ► E O °n O Řád čísla, primitivní kořeny Diskrétní logaritmus Kvadratické zbytky a nezbytky Výpočetní aspekty teorie čísel OOOOOOOO oo ooooooo oooooooo 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 oooooooo oo ooooooo 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 OOOOOOOO OO OOOOOOO OOOOOO0O Příklad (Ukázka průběhu algoritmu) Vypočtěme 2560 (mod 561). Řád čísla, primitivní kořeny OOOOOOOO Diskrétní logaritmus OO Kvadratické zbytky a nezbytky OOOOOOO 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 ooooooo 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 OOOOOOO 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. <□► < rnP ► < -E ► < -E ► E O °n O