58 5. Aplikace teorie čísel 5.1. Výpočetní aspekty 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ů: (1) běžné aritmetické operace (součet, součin, dělení se zbytkem) na celých číslech, (2) zbytek mocniny celého čísla a na přirozené číslo n po dělení daným m. (3) inverzi celého čísla a modulo m G N, (4) největší společný dělitel dvou celých čísel (a případně koeficienty do Bezoutovy rovnosti), (5) rozhodnout o daném čísle, je-li prvočíslo nebo složené, (6) v případě složenosti rozložit dané číslo na součin prvočísel. 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 am/rvuj) - např. první *-takový Karatsubův (1960) časové náročnosti Q(i^E^3^ nebo algoritmus ^ / Schonhage-Strassenův (1971) časové náročnosti 0 (n log n log log n), který využívá tzv. Fast Fourier Transform. Ten je ale pres 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/Computat ional. complexity_of_mathematical_operations 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ů k, l do Bezoutovy rovnosti k-a + l-m = 1 (nalezené A; je pak onou hledanou inverzí a modulo m). function extended_gcd (a , m) i f 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. Modulární umocňování je, jak jsme již viděli dříve, velmi využívaná operace mj. při ověřování, zdaje dané číslo prvočíslo nebo číslo složené. 59 Jedním z efektivních algoritmů je tzv. modulární umocňování zprava doleva: function modular_pow (base , exponent, modulus) result := 1 while exponent > 0 if (exponent mod 2 = 1): result := (result * base) mod modulus exponent := exponent » 1 base = (base * base) mod modulus return result Algoritmus modulárního umocňování je založen na myšlence, že např. při počítání 264 (mod 1000) • 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ť ->64 (((((2 2\2\2\2\2\2 příklad (Ukázka průběhu algoritmu). Vypočtěme 2560 (mod 561). Protože 560 = (1000110000)2, dostaneme uvedeným algoritmem T n 'i exponent base result exp's last digit ,/560 ^280 2 4 1 1 0 0 140 16 1 0 70 256 1 0 35 1 1 17 460 1 8 511 256 0 4 256 256 0 2 460 256 0 1 256 1 0 511 1 0 A tedy 2560 = 1 (mod 561). 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. 60 5.2. Testy # na složenost. Přestože platí základní věta aritmetiky, která nám garantuje, že každé přirozené číslo se dá jednoznačným způsobem rozložit na součin prvočísel, praktické nalezení tohoto rozkladu je obvykle velmi výpočetně náročná operace, obvykle prováděná v několika krocích: (1) nalezení všech dělitelů nepřevyšujících určitou hranici (metodou pokusného dělení všemi prvočísly až do této hranice, typicky je touto hranicí cca 106) (2) otestování zbylého faktoru na složenosti (tzv. test na složenost, testující některou nutnou podmínku prvočíselnosti) Hifi- HrV, li /^/-.y ? a J j.i") a) pokud test složenosti prohlásil, že zkoumané číslo je asi * I / prvočíslo, pak testem na prvočíselnost ověřit, že je to opravdu prvočíslo. cW*T «rMúZn/ _ b) pokud test složenosti prohlásil, že zkoumané číslo je složené,, ^-6 /^-^ fj pak nalézt netriviálního dělitele. £-Takto je posloupnost kroků prováděna z toho důvodu, že jednotlivé ^if^^f^ vy-y algoritmy mají postupně (výrazně) rostoucí časovou složitost. V roce aigunLiiiy maji pusuupiit; ^v^iaznej lusiuuui uasuvuu siuzilusl. v iuuc /i t f\j j^MS> 2002 Agrawal, Kayal a Saxena publikovali algoritmus, který testuje Cr&^vvií/ v prvočíselnost v polynomiálním čase, prakticky je ale zatím stále efek- ^tf^WTwr tivnější používat výše uvedený postup. Takzvané testy na složenost testují některou nutnou podmínku prvočíselnosti. Nej jednodušší takovou podmínkou je Malá Fermatova věta. TVRZENÍ 5.1. [Fermatův test^Existuje-li pro dané N nějaké a ^ 0 (mod N) takové, ze aN~ľ ^ 1 (mod N), pak N není prvočíslo. Bohužel nemusí být pro dané složené N snadné najít takové a, že ^> Fermatův test odhalí složenost N; pro některá výjimečná N dokonce jediná taková a jsou ta soudělná s N; jejich nalezení je tedy ekvivalentní s nalezením dělitele, a tedy i s rozkladem N na prvočísla. Carmichaelova čísla. Skutečně existují taková nehezká (nebo extrémně hezká?) složená čísla N, která splňují, že pro libovolné a nesoudělné s N platí aN~ľ = 1 (mod N). Taková čísla se nazývají Carmichaelova, nejmenší z nich je 561 = 3 • 11 • 17 a teprve v roce 1992 se podařilo dokázat, že jich je dokonce nekonečně mnoho (v OEIS jde o posloupnost A002997: 561,1105,1729, 2465, 2821,...). 61 šok; /vk 6c\£ot^ |/íW»M příklad. Dokážeme, že 561 je Carmichaelovo, tj. že pro každé ^ / a E N, které je nesoudělné s 3 • 11 • 17, platí a560 = 1 (mod 561). Z vlastností kongruencí víme, že stačí dokázat tuto kongruenci mo-dulo 3,11 i 17. To ale dostaneme přímo z Malé Fermatovy věty, protože takové a splňuje a2 = 1 (mod 3), a10 = 1 (mod 11), a16 = 1 (mod 17), přičemž 2,10 i 16 dělí 560 (viz též Korseltovo kritérium). věta 36 (Korseltovo kritérium). Složené číslo n je Carmichae-lovým číslem, právě když je nedělitelné čtvercem (square-free) a pro \7^t fWb\d% """"^ všechna prvočísla p dělící n platí p — 1 | n — 1. tú"A /~7)/ \ příklad. Dokažte, že čísla 2465 a 2821 isou Carmichaelova. (K Eulerův test (též Euler-Jacobi, Solovay-Strassen). Fermatův ^JtÁfi KSíht" test lze zlepšit s využitím kvadratických zbytků na Eulerův test, ale (v>? LuJdW vfše zniíněný problém se ani tak zcela neodstraní. a^ = {a/N) (modiV). tyj^ 3*?^ příklad. Uvažme3 a = 5: Pak 5280 = 1 (mod 3), 5280 = 1 (mod 11), ^ ^7 n&O^fb./ ^(Qjj) přitom 5280 = — 1 (mod 17), proto určitě 5280 ^ ±1 (mod 561). Zde J-^O-^ / došlo k tomu, že neplatilo a~^~ = ±1 (mod N), proto ani nebylo třeba _ testovat hodnotu Jacobiho symbolu, často ale právě Eulerův test může —fó^ . / HFl/>. odhalit složené číslo i v případě, kdy tato mocnina je rovna ±1. ' ' ÚL*- A (fr^W) příklad. Test, zda = ±1 (mod N), neodhalí například N = Jjľ^~ ^ 1729 = 7-13-19, neboť ^ = 864 = 25 • 33 je dělitelné 6, 12 i 18 a i^'f]r tedy z Fermatovy věty plyne, že pro všechna celá čísla a nesoudělná 'OL^J f 1^)4jí) tvrzení 5.2 (Eulerův test). Je-li N prvočíslo a a E Z, N \ a, pak r SI ^, 2 - ~ j~ . ů£k A f JMl tedy z Fermatovy věty plyne, že pro všechna cel s N platí = 1 (mod N). H^lfMi) í3- U /i^l (to ^(^ Přitom ale pro a = 11 dostaneme (p^g) = — 1 a Eulerův test tedy složenost čísla 1729 odhalí. --' . Poznamenejme, že hodnotu Legendreova nebo Jacobiho symbolu . (£) lze díky zákonu kvadratické reciprocity spočítat v lepším než ku-. /---I ss s l\ bickém čase. Definice (Pseudoprvočísla). Složené číslo n se nazývá pseudo-prvočíslo, pokud projde testem na složenost a není jím odhaleno jako složené. Máme tak Ař-^f (1) Fermatova pseudoprvočískVo základu a (K> ^^(^-^Oih^) (2) Eulerova pseudoprvočísla l\J i Oi!^~ ~ /-£/J A^VJ (3) silná (strong) pseudoprvočísla o základu a, pokud projdou následujícím testem na složenost. 3Testování by selhalo už pro a = 3, ale to je dělitel, my chceme ukázat, že test může uspět i bez nalezení dělitele. 62 tvrzení 5.3 (Test na složenost - zesílení Malé Fermatovy věty). Nechť p je liché prvočíslo. Píšme p — 1 = 2* • q, kde t je přirozené číslo a q je liché. Pak pro každé celé číslo a nedělitelné p buď platí ^ **£LÚ\ sčfl = 1 jjmod p)) nebo existuje e g {0,1,..., t — 1} splňující a2'°q = — 1 (mocTp)). "~—---------- Ukazuje se, že tento snadný test výrazně zesiluje schopnost rozpoznávat složená čísla. Nej menší silné pseudoprvočíslo o základu 2 je 2047 (přitom nej menší Fermatovo o základu 2 bylo již 341) a při otestování základů 2, 3 a 5 dostaneme nejmenší pseudoprvočíslo 25326001. Jinými slovy pokud nám stačí testovat pouze čísla do 2 • 107, pak stačí tento test na složenost provést pouze pro základy 2, 3 a 5. Pokud číslo není odhaleno jako složené, pak je určitě prvočíslem. Na druhou stranu, bylo dokázáno, že žádná konečná báze není dostatečná. Test Millera a Rabina je praktickou aplikací předchozího testu, kdy jsme navíc schopni omezit pravděpodobnost neúspěchu. VĚTA 37. Nechť N > 10 je liché složené číslo. Pišme N—l =2t -q, kde t je přirozené číslo a q je liché. Pak nejvýše čtvrtina z čísel množiny {a g Z; 1 < a < N, (a,N) = 1} splňuje následující podmínku: aq = 1 (mod N) nebo existuje e g {0,1,..., t — 1} splňující a2eq = -l (modiV). V praktických implementacích se obvykle testuje cca 20 náhodných základů (příp. nejmenších prvočíselných základů). V takovém případě dostáváme z předchozí věty, že pravděpodobnost neodhalení složeného čísla je menší než 2~40. Časová náročnost algoritmu je asymptoticky stejná jako složitost modulárního umocňování, tedy nejhůře kubická. Je ale třeba si uvědomit, že test je nedeterministický a spolehlivost jeho deterministické verze závisí na tzv. zobecněné Riemannově hypotéze (GRH). 63 5.3. Testy na prvočíselnost. Testy na prvočíselnost přicházejí na řadu obvykle ve chvíli, kdy testy na složenost prohlásí, že jde pravdepodobne o prvočíslo, případně se provádějí rovnou u speciálních typů čísel. Uveďme nejprve přehled nejznámějších testů. (1) AKS (2002) - obecný polynomiální test na prvočísla (2) Pocklington-Lehmerův test - test na prvočíselnost subexpo- nenciální složitosti P A e. i/l (3) Lucas-Lehmerův test - test prvočíselnosti pro Mersenneho čísla *~ ' p (4) Pépinův test (1877) - test prvočíselnosti pro Fermatova čísla <^ (5) ECPP - test prvočíselnosti založený na tzv. eliptických křivkách 2- ^ i & Speciální testy — Mersenneho čísla. tvrzení 5.4 (Lucas-Lehmerův test). Definujme posloupnost (sn)^Lo rekurzívně předpisem s$ = 4, sn+i = — 2. Pak je číslo Mp = 2P — 1 prvočíslo, právě tehdy, když Mp dělí sp_2- // Determine i f Mp = 2P — 1 is prime Lucas—Lehmer (p) var s = 4 var M = 2p - 1 repeat p — 2 times : s = s2 - 2 (mod M) if s = 0 return PRIME else return COMPOSITE Časová složitost testuje asymptoticky stejná jako v případě Miller-Rabinova testu, v konkrétních případech je ale efektivnější. Speciální testy — Fermatova čísla. Fermatova čísla jsou čísla tvaru Fn = 22" + 1. Pierre de Fermat v 17. století vyslovil hypotézu, že všechna čísla tohoto tvaru jsou prvočísly (zřejmě veden snahou zobecnit pozorování pro F0 = 3,F1 = 5, F2 = 17, F3 = 257 a FA = 65537. V 18. století ale Leonhard Euler zjistil, že F^ = 641 x 6700417 a dodnes se nepodařilo nalézt žádné další Fermatovo prvočíslo. Vzhledem k rychle rostoucí velikosti těchto čísel je počítání s nimi velmi časově náročné (a ani následující test tak není příliš používán). V současné době nej menší netestované Fermatovo číslo je F33, které má 2 585 827973 číslic, a je tak výrazně větší než největší dosud nalezené prvočíslo. tvrzení 5.5 (Pépinův test). Označme Fn = 22" + 1 tzv. n-té Fermatovo číslo. Pak Fn je prvočíslo, právě když 3^ = -1 (mod Fn). Vidíme, že jde o velmi jednoduchý test, který je vlastně pouze malou částí Eulerova testu na složenost. 64 11 1. Nechť p je prvočíslo dělicí N — 1. Předpokládejme dále, že existuje ap g Z íaA;, ie / — \ a*-1 = 1 (modiV) a a/ -l,iVl=i. Nechť pap je nejvyšší mocnina p dělící N — 1. PaA: pro každý kladný dělitel d čísla N platí d=l (mod důkaz věty pocklingtona a Lehmera. Každý kladný dělitel d čísla N je součinem prvočíselných dělitelů čísla N, větu dokažme pouze pro d prvočíslo. Podle Fermatovy věty platí ap~ľ = 1 (mod d), N-l N-l neboť (ap,N) = 1. Protože {app — l,iV) = 1, platí app ^ 1 (mod d). Označme e řád ap modulo d. Pak platí e\ d — l,e|iV — 1 a e 1 N~ľ Kdyby pap \ e, z e | N — 1 by plynulo e | spor. Je tedy pap \ e p p a tedy i pap \ d — 1. □ Užití věty Pocklingtona a Lehmera. tvrzení 5.6. Nechť N g n, N > 1. Předpokládejme, že můžeme psát N — 1 = F - U, kde (F, U) = 1 a F > y/Ň, přičemž známe rozklad čísla F na prvočinitele. Pak platí: • jestliže pro každé prvočíslo p | F můžeme najít ap £ 1* z předchozí věty, pak je N prvočíslo; • je-li N prvočíslo, pak pro libovolné prvočíslo p | N — 1 existuje ap g Z s požadovanými vlastnostmi. důkaz, ad 1. Podle Věty je d = 1 (mod pro všechny prvočíselné faktory F, proto je d = 1 (mod F), a tedy d > \/iV- ad 2. Stačí za ap zvolit primitivní kořen modulo prvočíslo N (nezávisle nap). □ 65 poznámka. Předchozí test v sobě zahrnuje Pépinův test (totiž pro N = Fn máme p = 2, kterému vyhovuje svědek prvočíselnosti ap = 3). 5.4. Hledání dělitele. Máme-li testem na složenost potvrzeno, že jde o číslo složené, obvykle chceme najít netriviálního dělitele. Jde ale o výrazně obtížnější úkol (což je na druhé straně výhodné pro RSA a podobné protokoly), proto si k tématu uvedeme jen stručný přehled používaných metod. (1) Pokusné dělení - v krajním případě je možné testovat potenciální (prvočíselné) dělitele až do y/n, tedy v nej horším případě vykonáme až 0(y/n) dělení. (2) Pollardova p-metoda (3) Pollardova p — 1 metoda (4) faktorizace pomocí eliptických křivek (5) Metoda kvadratického síta (QS) (6) Metoda síta v číselném tělesa (NFS) Podrobnosti viz předmět M8190 Algoritmy teorie čísel. 5.5. Kryptografie s veřejným klíčem. Dva hlavní úkoly pro kryptografie s veřejným klíčem (PKC - public key cryptography) jsou zajistit • šifrování, kdy zprávu zašifrovanou veřejným klíčem příjemce není schopen rozšifrovat nikdo kromě něj (resp. držitele jeho soukromého klíče) • podepisování, kdy integrita zprávy podepsané soukromým klíčem odesílatele může být ověřena kýmkoliv s přístupem k veřejnému klíči odesílatele Nejčastěji používané systémy PKC: • RSA (šifrování) a odvozený systém pro podepisování zpráv • Digital signatuře algorithm (DSA) a varianta založená na eliptických křivkách (ECDSA) • Rabínův kryptosystém (a podepisování) • ElGamal kryptosystém (a podepisování) • Kryptografie eliptických křivek (ECC) • Diffie-Hellmanův protokol na výměnu klíčů (DH) Princip digitálního podpisu. Proces podepisování a ověření podpisu zprávy M probíhá obvykle v následujících krocích. Podepisování (1) Vygeneruje se otisk (hash) H m zprávy pevně stanovené délky (např. 160 nebo 256 bitů). (2) Podpis zprávy Sa(Hm) Je vytvořen (pomocí dešifrování) z tohoto hashe s nutností znalosti soukromého klíče podepisujícího. (3) Zpráva M (případně zašifrovaná veřejným klíčem příjemce) je spolu s podpisem odeslána. 66 Ověření podpisu (1) K přijaté zprávě M se (po jejím případném dešifrování) vygeneruje otisk H'M (2) S pomocí veřejného klíče (deklarovaného) odesílatele zprávy se rekonstruuje původní otisk zprávy Va{Sa{Hm)) = Hm- ^____ (3) Oba otisky se porovnají H m = H'M1. RSA Ron Rívest, Adi Shamir, Leonard Adleman (1977; C. Cocks, We2**íLkCf GCHQ- 1973) . • každý účastník A potřebuje dvojici klíčů - veřejný V a a sou- ffil^J /V) JAhřie^i^ kromýS^ • generování klíčů: zvolí dvě velká prvočísla p, q, vypočte n = pq, f(n) = (p — l)(g — 1) [n je veřejné, ale íp(ri) nelze snadno spočítat ] • zvolí veřejný klíč e a ověří, že (e, f(n)) = 1 • např. pomocí Euklidova algoritmu spočítá tajný klíč d tak, aby e • d = 1 (mod f (n)) • zašifrování numerického kódu zprávy M: C = Ce(M) = Me (mod n) • dešifrování šifry C: OT = D^C) = Cd (mod n) Rabínův kryptosystém je prvním veřejným kryptosystémem, k jehož prolomení je prokazatelně potřeba faktorizovat modul. Uvedeme si jej ve zjednodušené verzi: • každý účastník A potřebuje dvojici klíčů - veřejný V a a soukromý S a • generování klíčů: A zvolí dvě podobně velká prvočísla p, q = 3 (mod 4), vypočte n = pq. • V a = n, SA = (p, q) Z n fkftfti na,") * zašifrování numerického kódu zprávy M: X ~ C ' M H C = Ce(M) = M2 (mod n) -2 . \ • dešifrování šifry C: vypočtou se (čtyři) odmocniny z C modulo j£ ^ C(j>J & — C(^fJ n a snadno se otestuje, která z nich byla původní zprávou. Výpočet druhé odmocniny z C modulo n = pq, (hj kde p = q = 3 (mod 4) . ' K-kf^íj) • vypočti r = C(p+1)/4 (mod p) a s = C^/4 (mod q) • vypočti a, b tak, že ap + bq = 1 • polož4 x = (aps + bqr) (mod n), y = (aps — bqr) (mod n) • druhými odmocninami z C modulo n jsou ±x, ±y. I^V^^cJ C-£rT příklad. V Rabínově kryptosystému Alice zvolila za svůj sou- kromý klíč p = 23, q = 31, veřejným klíčem je pak n = pq = 713. Zašifrujte zprávu m = 327 pro Alici a ukažte, jak bude Alice tuto zprávu dešifrovat. \ 4Uvědomte si, že jde vlastně o aplikaci Čínské zbytkové věty! 67 Řešení, c = 692, kandidáti původní zprávy jsou ±4-23-14±3-31-18 (mod 713). Diffie-Hellman key exchange. Whítfield Diffie, Martin Hellman (1976; M. Williamson, GCHQ - 1974) Výměna klíčů pro symetrickou kryptografii bez předchozího kontaktu (tj. náhrada jednorázových klíčů, kurýrů s kufříky, ...). fáoLfáífa • Dohoda stran na prvočísle p a primitivním kořenu g modulo i i] iň / \L > V (veřejné) ^ *~q, Zlí)0' jfo$kl)h*j fn& ' • Alice vybere náhodné a a pošle ga (mod p) £ ' ^ ^ /> ojlxáltj • Bob vybere náhodné b a pošle g£g(mod p) ^j. «o k . ^1 ~ j._£ • Společným klíčem pro komunikaci je gab (mod p). y J " Kryptosystém ElGamal. Z protokolu DH na výměnu klíčů je odvozen šifrovací algoritmus ElGamal: • Alice zvolí prvočíslo p spolu s primitivním kořenem g • Alice zvolí tajný klíč^ípspočítá h = gx (mod p) a zveřejní veřejný klíč (p, g, h) *^ý*ť/ (Ias/Ía - in*Al*\ & * šifrování zprávy A£i_Bob zvolí náhodné y a vypočte C\ = gy ^vwe\ • ifiw* s? ^mod ^ a ^ ^~/^(mod p) a pošle Ca) ^ poznámka. Analogicky jako v případě RSA lze odvodit podepisování. Eliptické křivky jsou rovinné křivky o rovnici tvaru y2 = x3 + ax + b a zajímavé jsou tím, že na jejich bodech lze definovat operace tak, že výslednou strukturou bude komutativní grupa. Přitom uvedené operace lze efektivně provádět a navíc se ukazuje, že mají (nejen) pro kryprografii zajímavé vlastnosti - srovnatelné bezpečnosti jako RSA lze dosáhnout již s podstatně kratšími klíči. Výhodou je rovněž velké množství použitelných eliptických křivek (a tedy grup různé struktury) podle volby parametru a, b . Některé protokoly: • ECDH - přímá varianta DH na eliptické křivce (jen místo generátoru se vybere vhodný bod na křivce) • ECDSA - digitální podpis pomocí eliptických křivek. poznámka. Problém diskrétního logaritmu (ECDLP). Navíc se ukazuje, že eliptické křivky jsou velmi dobře použitelné při faktorizaci prvočísel. 6. Diofantické rovnice Už ve třetím století našeho letopočtu se řecký matematik Diofan-tos zabýval řešením rovnic, ve kterých za řešení připouštěl jen celá