Diskrétní matematika do c. Lukáš Vokřínek, PhD. 22. září 2024 Obsah Úvod iii Sylabus přednášky iii 1. Problémy teorie čísel 1 2. Dělitelnost 1 3. Společní dělitelé a společné násobky 3 4. Prvočísla 5 5. Kongruence 6 6. Soustavy lineárních kongruencí o jedné neznámé 9 7. Prvočísla 12 8. Aritmetické funkce 15 9. Malá Fermatova věta, Eulerova věta 16 10. Primitivní kořeny 18 11. Kvadratické zbytky a nezbytky 20 12. Výpočetní aspekty teorie čísel 23 13. Diofantické rovnice 25 14. Kryptografie s veřejným klíčem 25 15. (n, fc)-kódy 27 16. Lineární kódy 28 17. Polynomiální kódy 29 18. Kombinatorika - motivace 19. Elementární kombinatorické metody 20. Vytvořující funkce 21. (Formální) mocninné řady 22. Operace s vytvořujícími funkcemi 23. Řešení rekurencí 24. Binární stromy a Catalanova čísla 25. Caleyho vztah pro počet stromů 26. Rekurzivně propojené posloupnosti Uvod Tady bude úvod. Lukáš Vokřínek Sylabus přednášky Tady bude sylabus. iii 1. Problémy teorie čísel 1 Problémy teorie čísel Přirozená a celá čísla jsou nejjednodušší matematickou strukturou, zkoumání jejich vlastností však postavilo před generace matematiků celou řadu velice obtížných problémů. Často jsou to problémy, které je možno snadno formulovat, přesto však dodnes neznáme jejich řešení. V několika přednáškách se teď budeme zabývat úlohami o celých číslech. Převážně v nich půjde o dělitelnost celých čísel, popřípadě o řešení rovnic v oboru celých nebo přirozených čísel. God made integers, all else is the work of man. (L. Kronecker) Příklady problémů teorie čísel • problém prvočíselných dvojčat - rozhodnout, zda existuje nekonečně mnoho prvočísel p takových, že i p + 2 je prvočíslo; • problém existence lichého dokonalého čísla - tj. čísla jehož součet dělitelů je roven dvojnásobku tohoto čísla; • Goldbachova hypotéza (rozhodnout, zda každé sudé číslo větší než 2 je možno psát jako součet dvou prvočísel); • velká Fermatova věta (Fermaťs Last Theorem) - rozhodnout, zda existují kladná celá čísla n, x, y, z tak, že n > 2 a platí xn + yn = zn; Pierre de Fermat jej formuloval cca 1637, vyřešil Andrew Wiles v roce 1995. Diofantické rovnice V kouzelném měšci máme neomezené množství dvoukorun a pětikorun. Jaké částky můžeme zaplatit tak, aby nebylo potřeba vracet? Ptáme se tedy, pro která přirozená čísla n existují přirozená k, £ tak, aby 2k + U = n. Asi se dá vcelku snadno uvěřit, že libovolnou vyšší částku takto zaplatíme, po pravdě jakoukoliv částku s výjimkou 1 Kč a 3 Kč. S vracením pak zvládneme zaplatit libovolnou částku, tj. každé n lze vyjádřit jako 2k + U = n pro nějaká celá k, í. Umíme to pro jakékoliv hodnoty mincí? Jak by to dopadlo třeba pro 7k + 11 í = n? A jak pro Ak + U = n? 2 Dělitelnost Základní motivací pro nás bude důkaz věty o rozkladu čísla na součin prvočísel a zejména jednoznačnost tohoto rozkladu, která nám například umožní snadno vypsat všechny dělitele daného čísla (vybereme z rozkladu libovolnou kolekci činitelů). Vysvětlíme nyní krátce, jak jednoznačnost rozkladu souvisí s dělitelností: Pro konkrétnost ukážeme, proč nemůže nastat rovnost 2-7 = 3-5; pravá strana je totiž součinem lichých čísel a je tedy lichá, zatímco levá strana obsahuje činitel 2 a je tedy sudá. Podobný argument bude fungovat i pro prvočísla různá od 2, pokud dokážeme následující: Součin čísel, která nejsou dělitelná prvočíslem p nemůže být dělitelný p (případně obměnou, pokud je součin čísel dělitelný prvočíslem p, pak musí být dělitelný p některý z činitelů). 1 2. Dělitelnost Poznamenejme, že v některých číselných oborech jednoznačnost rozkladu neplatí, např. 2 • 3 = (1 — \J—5) • (1 + \J—5) jsou dva různé rozklady čísla 6 v číselném oboru všech těch komplexních čísel, která lze vyjádřit ve tvaru a + b\/—5 (a opravdu se tam jedná o „prvočísla"). Budeme tedy muset využít nějaké netriviální vlastnosti celých čísel. Definice. Řekneme, že celé číslo a dělí celé číslo b (neboli číslo b je dělitelné číslem a, též a je dělitel a neboli b je násobek a), právě když existuje celé číslo c tak, že platí a ■ c = b. Píšeme pak a | b. Snadno se vidí, že dělitelnost je uspořádání na přirozených (tedy nezáporných celých) číslech, tj. splňuje reflexivitu a \ a, tranzitivitu a \ b \ c =>• a \ c a antisymetrii a \ b \ a =>• a = b. Je vcelku užitečné mít představu o Hasseho diagramu tohoto uspořádání: / / / i l i 2 • 2 2 V oboru všech celých čísel už dělitelnost antisymetrická není, neboť —a | a. Pokud v Hasseho diagramu nahradíme každé nenulové číslo a dvojicí ±a, dostaneme velice dobrou představu o dělitelnosti na všech celých číslech. (Obecně relace < splňující pouze reflexivitu a tranzitivitu se nazývá předuspořádání & a^b<^a ac | bc (c =/= 0) Příklad. Zjistěte, pro která přirozená čísla n je číslo n2 + 1 dělitelné číslem 3. Řešení. Uvidí se, že záleží pouze na zbytku n po dělení třemi. Příklad. Zjistěte, pro která přirozená čísla n je číslo n2 + 1 dělitelné číslem n + 1. Dělení se zbytkem Věta 1 (o dělení celých čísel se zbytkem). Pro libovolně zvolená celá čísla a, m > 0 existují jednoznačně určená čísla q G Z, r G {0,1, ... , m — 1} tak, že a = qm + r. Důkaz. Prvně dokážeme pro a > 0 indukcí: pro a < m zřejmé, pro a > m pak rekurzivně s využitím výsledku pro a — m (podíl je potřeba zvětšit o 1, zbytek zůstane stejný). Případ a < 0 lze snadno převést na(—a — 1)>0. □ Číslo q, resp. r z věty se nazývá (neúplný) podíl, resp. zbytek při dělení čísla a číslem m se zbytkem. Vhodnost obou názvů je zřejmá, přepíšeme-li rovnost a = mq + r do tvaru ar, r — = q H--, přitom 0 < — < 1. mm m Příklad. Dokažte, že jsou-li zbytky po dělení čísel a, b G Z číslem m G N jedna, je jedna i zbytek po dělení čísla ab číslem m. 2 3. Společní dělitelé a společné násobky 3 Společní dělitelé a společné násobky Největší společný dělitel (gcd) Jedním z nejdůležitějších nástrojů výpočetní teorie čísel je výpočet největšího společného dělitele. Protože jde, jak si ukážeme, o relativně rychlou proceduru, je i v moderních algoritmech velmi často využívána. Definice. Mějme přirozená čísla a, b. Libovolné přirozené číslo m takové, že m | a, m \ b se nazývá společný dělitel čísel a, b. Společný dělitel čísel a, b, který je dělitelný libovolným společným dělitelem těchto čísel, se nazývá největší společný dělitel čísel a, b a značí se (a,b). (Jedná se o infimum vzhledem k dělitelnosti.) Například (12,16) = 4: společní dělitelé jsou 4, 2, 1, největší z nich (vzhledem k dělitelnosti) je 4. 16 12 8 Poznámka. Přímo z definice plyne, že pro libovolné a, b G N platí (a, b) = (b, a), (a, 1) = 1, (a, 0) = a. Definici lze snadno rozšířit i na libovolná celá čísla a, b. Budeme požadovat, aby nevjětší společný dělitel byl největší mezi nezápornými společnými děliteli, tím bude jednoznačně určený. Definice. Mějme přirozená čísla a, b. Libovolné přirozené číslo m takové, že a \ m, b \ m se nazývá společný násobek čísel a, b. Společný násobek čísel a, b, který dělí libovolný společný násobek těchto čísel, se nazývá nejmenší společný násobek čísel a, b & značí se [a,b]. Poznámka. Analogicky se definuje i největší společný dělitel a nejmenší společný násobek více než dvou celých čísel a snadno se následně dokáže, že platí (»1, ■ ■ ■ , an) = ((al; ■ ■ ■ ; an-l), O-n), [<2i, ... ,an} = [[<2i, . . . , Čin — l] > an] ■ Eukleidův algoritmus Dosud jsme nijak nezdůvodnili, zda pro každou dvojici a, b G Z čísla (a, b) a [a, b] vůbec existují. To si lze hezky představit přes rozklad na prvočinitele, ale ten je výpočetně velmi náročný (RSA) a navíc k jeho odvození budeme existenci největšího společného dělitele využívat. Pokud však existují, jsou určena jednoznačně: Pro každá dvě čísla m\,m,2 G No totiž podle definice platí, že pokud m\ \ a zároveň \ m\, je nutně m\ = m^. Důkaz existence čísla (a, b) podáme (spolu s algoritmem jeho nalezení) v následující větě. Věta 2 (Euklidův algoritmus). Nechi a\ > jsou přirozená čísla. Pro každé n > 3, pro které an—i =/= 0, označme an zbytek po dělení čísla a„_2 číslem an-\. Pak po konečném počtu kroků dostaneme ar = 0 a platí ar_i = (a\,a,2). Důkaz. Jelikož platí a% = a\ — qa^, dostáváme (&i,&2) = (^3,^2) = (^2,^3) a největší společný dělitel tedy zůstává stále stejný, přičemž (&r-i, ar) = (&r-i, 0) = ar_i. □ Algoritmus a důkaz jeho korektnosti demonstrujeme na příkladu: Příklad. Určete největšího společného dělitele čísel 10175 a 2277. 3 3. Společní dělitelé a společné násobky Vlastnosti gcd Poznámka. Z definice, z předchozího tvrzení a z toho, že pro libovolná a, b G Z platí (a, 6) = (a, — b) = (—a,b) = (—a,—6), plyne, že existuje největší společný dělitel libovolných dvou celých čísel. Věta 3 (Bezoutova). Pro libovolná celá čísla a1; a2 existuje jejich největší společný dělitel (a1; a2), přitom existují celá čísla k\, k2 tak, že (ai, a2) = k\a\ + ^2^2- Důkaz. Při první z metod se největší společný dělitel (ai, 02) rekurzivně počítá jako (02, »3) a je vyjádřen jako celočíselná kombinace a2, &3 přičemž se následně nahradí a% = a\ — qa2 celočíselnou kombinací a\, a2. Druhá metoda funguje z druhé strany a při počítání a\, a2, &3, .. ., &r-i, ar = 0 zároveň počítá i vyjádření každého an jako celočíselné kombinace a1; a2, viz příklad. □ Důsledek. Pro libovolná celá čísla a1; a2 fee jako celočíselné kombinace n = kiai + k2ci2 vyjádřit právě násobky největšího společného dělitele (0,1,0,2). Příklad. Výpočet největšího společného dělitele pomocí Euklidova algoritmu je s využitím výpočetní techniky i pro relativně velká čísla poměrně rychlý. V našem příkladu to vyzkoušíme na 2 číslech A, B, z nichž každé je součinem dvou 101-ciferných prvočísel. Všimněme si, že výpočet největšího společného dělitele i takto velkých čísel trval zanedbatelný čas. p = next_prime (5* 10 " 300) q = next_prime (3* 10 " 300) r = next_prime (2* 10 " 300) A=p * q; B=p * r gcd(A, B)_ Příklad v systému SAGE lze vyzkoušet na https: //cocalc. com/. Poznámka. Euklidův algoritmus a Bezoutova věta jsou základními výsledky elementární teorie čísel a tvoří jeden z pilířů algoritmů algebry a teorie čísel. Nesoudělnost Definice. Čísla a, b G Z se nazývají nesoudělná, jestliže platí (a, b) = 1. Čísla 01,02,... ,an G Z se nazývají po dvou nesoudělná, jestliže pro každé i =/= j platí (oí, Oj) = 1. Věta 4. Pro libovolná přirozená čísla a, b a jejich největšího společného dělitele (a, b) = d jsou čísla a/d, b/d nesoudělná. Důkaz. Dokážeme obecněji pro libovolné d \ (a,b) vztah (a/d, b/d) = (a,b)/d, tvrzení je pak speciálním případem. Číslo k je společný dělitel čísel a/d, b/d, právě když k I a/d, k I b/d •<=> kd \ a, kd \ b <ř=> kd \ (a, b) <ř=> k \ (a, b)/d a největší takové k je tedy (a, b)/d. □ Poznámka. Diagramaticky lze předchozí důkaz znázornit takto: a b a/d b/d kd 4 4. Prvočísla Věta 5. Pro libovolná přirozená čísla a, b, c platí: jestliže c \ ab, (c, a) = í, pak c \ b. Důkaz. Zjevně c | cb a podle předpokladu také c | ab, musí tedy c dělit i jakoukoliv jejich celočíselnou kombinaci; přitom podle Bezoutova lemmatu kc + la = 1, takže c \ (k ■ cb + l ■ ab) = (kc+ la)b = b. □ Nejmenší společný násobek Věta 6. Pro libovolná přirozená čísla a\,a2 existuje jejich nejmenší společný násobek [&i,&2] a platí (a\ ,0,2) • [ai, a2~\ = a\a2. Důkaz. Nejlépe se vidí přes rozklad na součin prvočísel. Jinak se vše prvně převede na případ (a1;a2) = 1 a pak a2 | x implikuje a^a2 \ a±x, symetricky ai \ x implikuje a^a2 \ a2x a jejich celočíselnou kombinací pak dostaneme a\a2 \ (ka\ + la2)x = x. Jinými slovy každý společný násobek a\, a2 je násobkem a\a2 a tento je tedy nejmenší společný násobek. □ 4 Prvočísla Prvočíslo je jeden z nej důležitějších pojmů elementární teorie čísel. Jeho důležitost je dána především větou o jednoznačném rozkladu libovolného přirozeného čísla na součin prvočísel, která je silným a účinným nástrojem při řešení celé řady úloh z teorie čísel. Definice. Každé přirozené číslo n > 2 má aspoň dva kladné dělitele: lan. Pokud kromě těchto dvou jiné kladné dělitele nemá, nazývá se prvočíslo. V opačném případě hovoříme o složeném čísle. V dalším textu budeme zpravidla prvočíslo značit písmenem p. Nejmenší prvočísla jsou 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, ... (zejména číslo 1 za prvočíslo ani za číslo složené nepovažujeme, je totiž invertibilní, neboli tzv. jednotkou okruhu celých čísel). Prvočísel je, jak brzy dokážeme, nekonečně mnoho, máme ovšem poměrně limitované výpočetní prostředky na zjištění, zda je dané číslo prvočíslem (největší známé prvočíslo 282589933 — 1 má pouze 24 862 048 cifer). Základní věta aritmetiky Uveďme nyní větu, která udává ekvivalentní podmínku prvočíselnosti a je základní ingrediencí při důkazu jednoznačnosti rozkladu na prvočísla. Věta 7 (Euklidova o prvočíslech). Přirozené číslo p > 2 je prvočíslo, právě když platí: pro každá celá čísla a, b z p \ ab plyne p \ a nebo p \ b. Důkaz. Jedná se o reformulaci Věty 5 pro c = p prvočíslo s tím, že podmínka (p, a) = 1 je ekvivalentní tomu, že p \ a (to lze vidět naopak tak, že (p, a) = p je ekvivalentní p \ a). □ Věta 8. Libovolné přirozené číslo n > 2 je možné vyjádřit jako součin prvočísel, přičemž je toto vyjádření jediné, nebereme-li v úvahu pořadí činitelů. (Je-li n prvočíslo, pak jde o „součin" jednoho prvočísla.) Důkaz. Existence se dokáže jednoduše metodou rozděl a panuj: Pokud n je prvočíslo, máme hotovo, jinak jej rozdělíme na součin dvou menších čísel, na obě aplikujeme indukci a součiny dáme dohromady. Jednoznačnost je složitější v tom, že využívá Eukleidovu větu. Předpokládejme pi ■ ■ ■ Pk = n = qi ■ ■ ■ qi. Protože pic dělí součin vlevo, musí dělit i součin vpravo a podle Eukleidovy věty některý z činitelů qj] protože se jedná o prvočísla, pic = qj. Vydělením tímto prvočíslem dostaneme číslo menší než n a jeho dva rozklady, na něž můžeme použít indukci. □ 5 5. Kongruence 5 Kongruence Pojem kongruence byl zaveden Gaussem. Ačkoliv je to pojem velice jednoduchý, jeho důležitost a užitečnost v teorii čísel je nedocenitelná; projevuje se zejména ve stručných a přehledných zápisech některých i velmi komplikovaných úvah. Definice. Jestliže dvě celá čísla a, b mají při dělení přirozeným číslem to týž zbytek, nazývají se a, b kongruentní modulo m (též kongruentní podle modulu m), což zapisujeme takto: a = b (mod to). V opačném případě řekneme, že a, b nejsou kongruentní modulo to, a píšeme a ^ b (mod to). Lemma. Pro libovolná a, b G Z, to G N jsou následující podmínky ekvivalentní: 1. a = b (mod to), 2. a = b + mt pro vhodné í £ Z, 3. to | a — b. Důkaz. Protože se zbytky po dělení to periodicky opakují s periodou to, dvě čísla dávají stejný zbytek po dělení to, právě když se liší o násobek to. □ Základní vlastnosti kongruencí Kongruence modulo to je relace ekvivalence, jejíž třídy budeme nazývat zbytkové třídy modulo to; jedná se o řádky v následující tabulce: —to 0 TO —to + 1 1 to + 1 — 1 to — 1 2to — 1 Konkrétně tedy kongruence modulo to splňuje následujcí vlastnosti: • a = a (mod to), tj. kongruence podle modulu to je reflexivní, • a = b (mod to) => b = a (mod to), tj. kongruence podle modulu to je symetrická, • a = b (mod to), b = c (mod to) => a = c (mod to), tj. kongruence podle modulu to je tranzitivní. Následující triviální vlastnost se hodí při počítání s konkrétními čísly (zejména zápornými, kde zbytek po dělení to není tolik používaný a proto svádí k numerickým chybám, např. 120 = —10 = 3 (mod 13) prvně odečtením 130 a poté přičtením 13): • K libovolné straně můžeme přičíst libovolný násobek modulu: a = b (mod to) => a = b + k ■ to (mod to). Nyní následují algebraické vlastnosti, které dohromady říkají, že v kongruenci můžeme v libovolném polynomiálním výrazu všechna vystupující čísla nahradit čísly s nimi kongruentními (zejména menšími, aby se výraz zjednodušil); to se ovšem netýká exponentů, kterými se budeme zabývat později. 6 5. Kongruence • Kongruence podle téhož modulu můžeme sčítat, tedy i vynásobit týmž číslem: a>i = b\ (mod to), , , , . , , ; , ; =>• a1+a2 — b1+b2 (mod to). a2 = b2 (mod to) y ' a = b (mod to) => k ■ a = k ■ b (mod to). • Kongruence podle téhož modulu můžeme násobit, tedy i umocnit na totéž číslo. ai = h (mod to), , , , . , ; . ; =>• ai • a2 = Oi • b2 mod to . a2 = b2 (mod to) 1 ^ 1 1 y ' a = b (mod to) => ak = bk (mod to). • Obě strany kongruence můžeme vydělit číslem k, jestliže je nesoudělné s modulem. k ■ a = k ■ b (mod to), (k, to) = 1 => a = b (mod to). Poslední sada vlastností se týká vztahů mezi kongruencemi vzhledem k různým modulům, využijeme je až později, takže se na první čtení dají přeskočit. • Jestliže n | to, pak a = b (mod to) => a = b (mod n). Naopak pokud a = b (mod n), dostáváme m/n = k možných řešení a = b, a = b + n, . .., nebo a = b + (k — l)n (mod to). • Jestliže to = [mi,m2] je nejmenší společný násobek, pak a = b (mod toi), a = b (mod m2) •<=> a = b (mod to). • Obě strany kongruence a modul lze vynásobit nebo vydělit libovolným číslem a = b (mod to) <ř=> k ■ a = k ■ b (mod k ■ to) . Poznámka. Některé vlastnosti kongruencí jsme již používali, aniž bychom si toho povšimli -například příklad z minulého týdne lze přeformulovat do tvaru a = 1 (mod to), b = 1 (mod to) => ab = 1 (mod to), což je speciální případ z předhozího tvrzení. Nejde o náhodu. Libovolné tvrzení používající kongruence můžeme snadno přepsat pomocí dělitelnosti. Užitečnost kongruencí tedy netkví v tom, že bychom pomocí nich mohli řešit úlohy, které bez nich řešit nejsme schopni, ale v tom, že jde o velmi vhodný způsob zápisu. Osvojíme-li si ho, výrazně tím zjednodušíme jak vyjadřování, tak i některé úvahy. Je to typický jev: v matematice hraje vhodná symbolika velmi závažnou úlohu. Příklad. Nalezněte zbytek po dělení čísla 520 číslem 26. Příklad. Dokažte, že pro libovolné prvočíslo p a libovolná a, b G Z platí ap + bp = (a + b)p (mod p). Příklad. Najděte "inverzi" k číslu 39 modulo 47, tj. najděte x takové, že 39 • x = 1 (mod 47). 7 5. Kongruence Inverze modulo m Věta 9. Je-li a nesoudělné s modulem m, tj. (a, to) = í, pak existuje řešení a ■ x = 1 (mod to) . Toto řešení značíme x = a-1 a nazýváme inverzí k a modulo to. Jakožto zbytková třída je toto řešení jediné. Důkaz. Zobrazení x (mod to) h-> a ■ x (mod to) na zbytkových třídách je injektivní (to přesně říká vlastnost dělení: ax = ay => x = y); protože je zbytkových tříd na obou stranách stejně, totiž to, jedná se o bijekci a jednička 1 (mod to) má jediný vzor. □ Věta 10. Necht to G N, a, b G Z. Pokud (a, to) = 1, má kongruence a ■ x = b (mod to) právě jedno řešení x (mod to). V obecném případě označme d = (a, to). Pak má tato kongruence řešení právě tehdy, když d \ b; řešením je pak právě d zbytkových tříd x (mod to). Důkaz. Podle předchozí věty inverze a-1 (mod to) existuje a vynásobením rovnice a ■ x = b (mod to) touto inverzí dostaneme (jediné) řešení x = a^1 ■ b (mod to). V obecném případě d | to | (b — ax); protože také d \ a, dostáváme opravdu d \ b. Naopak, pokud d | b, vydělíme obě strany i modul největším společným dělitelem d a dostaneme při označení a' = a/d, b' = b/d, m! = m/d ekvivalentní rovnici a' ■ x = b' (mod to') kde již (a', to') = 1 podle Věty 4. Podle první části dostaneme jediné řešení x (mod to'), kterému odpovídá právě d řešení x (mod to). □ Algoritmus Začneme s ekvivalentní soustavou dvou kongruencí to • x = 0 (mod to) a ■ x = b (mod to) a vždy první rovnici systému nahradíme rovnicí vzniklou odečtením vhodného násobku druhé rovnice (tak abychom koeficient to nahradili jeho zbytkem po dělení číslem a), dokud nedostaneme koeficienty d a 0: d ■ x = c (mod to) 0 • x = k (mod to) Máme dvě možnosti: • k = 0 a soustava, a tedy i původní rovnice, má řešení vzniklé z první rovnice vydělením d, totiž: x = c/d (mod m/d);1 1Zde tvrdíme, že v případě k = 0 už bude automaticky d \ c, což je sice pravda, ale dokazovat to nebudeme; v každém příkladu to tak vyjde a není potřeba to tedy v rámci výpočtu používat. 8 6. Soustavy lineárních kongruencí o jedné neznámé • k ^ O a soustava, a tedy i původní rovnice, nemá řešení. Příklad. Řešte 39x = 41 (mod 47) Poznámka. Teoretický, i když ne příliš praktický postup, pro jednoduchost v případě (a, to) = 1: z Bezoutovy věty dostaneme ka + Z to = 1, použijeme a ■ x = b = (ka + lm)b = fcaĎ (mod to) a vydělíme a, takže x = kb (mod to). (Zbytečně počítáme koeficient l.) Wilsonova věta Pomocí věty o řešitelnosti lineárních kongruencí lze dokázat mj. významnou Wilsonovu větu udávající nutnou (i postačující) podmínku prvočíselnosti. Takové podmínky jsou velmi významné ve výpočetní teorii čísel, kdy je třeba efektivně poznat, je-li dané velké číslo prvočíslem. Bohužel dosud není známo, jak rychle vypočítat modulární faktoriál velkého čísla, proto není v praxi Wilsonova věta k tomuto účelu používána. Věta 11 (Wilsonova). Přirozené číslo n> 1 je prvočíslo, právě když (n — 1)! = —1 (mod n) Důkaz. Pokud n není prvočíslo, je některé z čísel 1, .. ., n — 1 v součinu (n — 1)! soudělné s n, proto také celý součin, a nemůže tedy být kongruentní s —1. Naopak, pokud např. n = 7, pak 6! = 1 ■ (2 ■ 4) ■ (3 ■ 5) ■ 6 = 1 ■ 1 ■ 1 ■ (-1) = -1 (mod 7), kde do závorek jsme vždy spárovali číslo se svou inverzí (naopak je pak původní číslo inverzí k tomu spárovanému), takže součin každé závorky je 1. Jediná čísla, která nejsou spárována s žádným dalším jsou ta, co jsou spárována sama se sebou, tj. x^1 = x neboli x2 = 1. Věta 24, kterou bychom mohli dokázat bez problému nyní, říká, že to jsou právě 1 a —1, proto součin vždy vyjde = 1 ■ 1---1 ■ (-1) =-1. □ 6 Soustavy lineárních kongruencí o jedné neznámé Soustavy lineárních kongruencí Máme-li soustavu lineárních kongruencí o téže neznámé, můžeme podle předchozí věty rozhodnout o řešitelnosti každé z nich. V případě, kdy aspoň jedna z kongruencí nemá řešení, nemá řešení ani celá soustava. Naopak, jestliže každá z kongruencí řešení má, upravíme ji do tvaru x = cí (mod mi). Dostaneme tak soustavu kongruencí x = ci (mod toi) x = cfe (mod TOfe) Zřejmě stačí vyřešit případ k = 2, řešení soustavy více kongruencí snadno obdržíme opakovaným řešením soustav dvou kongruencí. Čínská zbytková věta (CRT) Ve čtvrtém století se čínský matematik Sun Ze (Sun Tsu) ptal na číslo, které při dělení třemi dává zbytek 2, při dělení pěti zbytek 3 a při dělení sedmi je zbytek opět 2. 9 6. Soustavy lineárních kongruencí o jedné neznámé Věta 12 (Čínská zbytková věta). Nechi m\, ... , m^ G N jsou po dvou nesoudělná, c\,. .. , c^ G Z. Pak platí: soustava x = ci (mod mi) x = cfe (mod mfe) má jediné řešení modulo iiíj • m2 • • • m^. Uvědomme si, že jde o docela silné tvrzení (které ve skutečnosti platí v podstatně obecnějších algebraických strukturách), umožňující nám při předepsání libovolných zbytků podle zvolených (po dvou nesoudělných) modulů garantovat, že existuje číslo s těmito předpsanými zbytky. Důkaz. Budeme se zabývat pouze soustavou dvou kongruencí. Uvažujme zobrazení x (mod miTO2) 1—> (x (mod mi), x (mod 7772)), které zbytkové třídě modulo m\m^ přiřadí dvojici odpovídajících zbytkových tříd modulo m\ a modulo m^. Toto zobrazení je injektivní (viz vlastnosti kongruencí: x = y (mod m{), x = y (mod 7712) => x = y (mod 77717772)). Na obou stranách přitom máme stejný počet prvků m\m^, jedná se tedy o bijekci a dvojice (c\,C2) má jediný vzor - tím je zbytková třída c (mod 77717772) taková, že c = Ci (mod mi), c = c2 (mod m2), tedy řešení soustavy. □ Obecný případ Věta 13. Necht c\,c^ jsou celá ěísla, m\,m^ přirozená. Označme d= (7711,7712) am= [m\, 777,2]. Soustava dvou kongruencí x = ci (mod mi) x = C2 (mod 777,2) v případě ci ^ C2 (mod d) nemá řešení. Jestliže naopak c\ = C2 (mod d), pak existuje celé číslo c tak, že x G Z vyhovuje soustavě, právě když vyhovuje kongruencí x = c (mod 771). Důkaz. Má-li soustava nějaké řešení x G Z, platí nutně x = c\ (mod d), x = c^ (mod d), a tedy i ci = C2 (mod d). Odtud plyne, že v případě ci ^ C2 (mod d) soustava nemůže mít řešení. Uvažujme opět zobrazení c (mod 777) 1—> (c (mod 777,1), c (mod 7772)), které zbytkové třídě modulo 777 přiřadí dvojici odpovídajících zbytkových tříd modulo m\, m^. Toto zobrazení je opět injektivní. Počítejme dvojice tříd ze zadání, tj. takové, že ci = C2 (mod d). Libovolné ci (mod toi) určuje C2 (mod d) a to odpovídá právě m^ld třídám C2 (mod 7772). Dohromady tak je těchto dvojic toi • (7772/d) = [7771,7772] = 777 a zobrazení je opět bijekce (jen jsme potřebovali zmenšit množinu napravo ze všech dvojic na ty "kompatibilní"). Zbytek důkazu je stejný. □ Algoritmus Prvně obměna na algoritmus pro jednu rovnici: soustavu x = ci (mod 777l) x = C2 (mod 7772) 10 6. Soustavy lineárních kongruencí o jedné neznámé přepíšeme na ekvivalentní to2 • x = m2 • Ci (mod TOiTO2) ui\ ■ x = mi • c2 (mod mim2) a vyřešíme podobně jako předtím postupným odčítáním. O něco lepší bývá převedení první rovnice na "parametrický" tvar x = ui\ ■ t + c\, dosazení do druhé rovnice mi • t + ci = c2 (mod m2), vyřešení vzhledem k t, dosazení doi = mi • ŕ + c\ a převedení na "implicitní" tvar. Příklad. Řešte systém kongruencí x = 1 (mod 10) x = 5 (mod 18) x = —4 (mod 25). Řešení. Výsledkem je x = 221 (mod 450). Čínskou zbytkovou větu můžeme použít také „v opačném směru". Příklad. Řešte kongruencí 23 941x = 915 (mod 3564). Řešení. Víme, že x G Z je řešením dané kongruence, právě když je řešením soustavy 23941x = 915 (mod 22) 23941x = 915 (mod 34) 23941x = 915 (modli). Vyřešíme-li postupně každou z kongruencí soustavy (což lze paralelně, viz níže), dostaneme ekvivalentní soustavu x = 3 (mod 4) x = -3 (mod 81) x = —4 (mod 11), odkud snadno postupem pro řešení soustav kongruencí dostaneme x = —1137 (mod 3564), což je také řešení zadané kongruence. Modulární reprezentace čísel Při počítání s velkými čísly je někdy výhodnější než s dekadickým či binárním zápisem čísel pracovat s tzv. modulární reprezentací (též residue number systém), která umožňuje snadnou pa-ralelizaci některých výpočtů s velkými čísly (algebraických, nefunguje např. porovnávání čísel; navíc je potřeba hlídat přetečení). Takový systém je určen fc-ticí modulů (obvykle po dvou nesoudělných) a každé číslo menší než jejich součin je pak jednoznačně reprezentováno fc-ticí zbytků (jejichž hodnoty nepřevyšují příslušné moduly) - viz např. http://goo.gl/oM25m. Příklad. Pětice modulů 3, 5, 7,11,13 nám umožní jednoznačně reprezentovat čísla menší než 15015 a efektivně provádět (v případě potřeby distribuovane) běžné aritmetické operace. Vypočtěme např. součin čísel 1234 a 5678, v této modulární soustavě reprezentovaných pěticemi [1, 4, 2, 2,12] a [2,3,1,2,10]. Součin provedeme po složkách a dostaneme [2, 2, 2,4, 3], což na závěr pomocí CRT převedeme zpět na 9662, což je modulo 15015 totéž jako 1234 • 5678. 11 7. Prvočísla 7 Prvočísla PRIMES is in P Poznámka. Již jsme se zmínili, že je složité o velkých číslech s jistotou rozhodnout, jde-li o prvočíslo (na druhou stranu je o naprosté většině složených čísel snadné prokázat, že jsou skutečně složená). Přesto se v roce 2002 podařilo indickým matematikům (Agrawal, Saxena, Kayal: http: //www. cse. iitk. ac. in/users/manindra/algebra/primality_v6. pdf) dokázat, že problém prvočíselnosti je možné rozhodnout algoritmem s časovou složitostí polynomiálně závislou na počtu cifer vstupního čísla. Nic podobného se zatím nepodařilo v otázce rozkladu čísla na prvočísla (třebaže se obecně nevěří, že je to možné, exaktní důkaz zatím nebyl podán). Is FACTOR in P? Nic podobného se zatím nepodařilo v otázce rozkladu čísla na prvočísla (třebaže se obecně nevěří, že je to možné, exaktní důkaz zatím nebyl podán). Nejrychlejší obecně použitelný faktorizační algoritmus, tzv. sito v číselném tělese2, je sub-exponenciální časové složitosti 0(e1-9^l°eN^ 1 'logloĚ,v' 1 ). Poznámka. Peter Shor v roce 1994 vymyslel algoritmus, který faktorizuje v kubickém čase (tj. 0((log]V)3)) na kvantovém počítači. Je k tomu nicméně třeba sestrojit počítače s dostatečným počtem qubits - jak je to obtížné, lze vysledovat z toho, ze v roce 2001 se IBM podařilo pomocí kvantového počítače rozložit číslo 15 a v roce 2012 byl dosažen další faktorizační rekord rozkladem čísla 21. RSA Challenge Poznámka. Ze je problém rozkladu přirozeného čísla na prvočísla výpočetně složitý, o tom svědčí i (již neplatná) výzva učiněná v roce 1991 firmou RSA Security (viz http://www.rsasecurity. com/rsalabs/node. asp?id=2093). Pokud se komukoliv podařilo rozložit čísla označená podle počtu cifer jako RSA-100, ..., RSA-704, RSA-768, ..., RSA-2048, mohl obdržet 1 000,..., 30 000, 50 000, ..., resp. 200 000 dolarů (číslo RSA-100 rozložil v temže roce Arjen Lenstra, číslo RSA-704 bylo rozloženo v roce 2012, některá dosud rozložena nebyla). Dělitelé znovu Díky jednoznačnosti rozkladu na prvočísla jsme schopni (se znalostí tohoto rozkladu) snadno odpovědět i na otázky ohledně počtu či součtu dělitelů konkrétního čísla. Stejně snadno dostaneme i (z dřívějška intuitivně známý) postup na výpočet největšího společného dělitele dvou čísel ze znalosti jejich rozkladu na prvočísla. Důsledek. • Každý kladný dělitel čísla a = p"1.....p^k je tvaru p™1.....p™fc, kde iiíj , .. ., mk G N0 a m1 < n1, m2 2 a l je liché. Pak 2p ■ l = 2a = a (a) = (2P - 1) • a(l) (poslední rovnost je speciálním případem multiplikativity funkce a, viz níže). Protože 2P — 1 dělí levou stranu a je nesoudělné s 2P, musí 2P — 1 | l, řekněme l = (2p-l)-ma rovnici znovu přepíšeme: 2p ■ (2p - 1) • to = 2a = a (a) = (2P - 1) • cr((2p - 1) • to), tedy 2P • to = (j((2p — 1) • to). Protože (2P — 1) • to má zjevně následující dva dělitele to < (2P — 1) • to, jejichž součet už je 2P ■ to, musí to být právě všichni dělitelé a tedy to = 1 a 2P — 1 musí být prvočíslo. □ Na druhou stranu popsat lichá dokonalá čísla se dodnes nepodařilo, resp. dodnes se neví, jestli vůbec nějaké liché dokonalé číslo existuje. Hledání velkých prvočísel Mersenneho prvočísla jsou právě prvočísla tvaru 2P — 1. Bez zajímavosti není ani to, že právě Mersenneho prvočísla jsou mezi všemi prvočísly nejlépe „vidět" - pro Mersenneho čísla existuje poměrně jednoduchý a rychlý postup, jak ověřit, že jde o prvočísla. Test (Lucas-Lehmerův test). Definujme posloupnost (s„)^°=0 rekurzívně předpisem s0 = 4, s„+1 = 4-2. Pak je číslo Mp = 2P — 1 prvočíslo, právě tehdy, když Mp dělí sp_2. Proto není náhodou, že největší známá prvočísla jsou obvykle tvaru 2P — 1 (viz např. http: //www.utm.edu/research/primes/largest.html). Jakkoliv může být hledání největšího známého prvočísla chápáno jako pochybná zábava bez valného praktického užitku3, jednak posunuje hranice matematického poznání a zdokonaluje použité metody (a často i hardware), jednak může přinést beneŕit i samotným objevitelům (Electronic Frontier Foundation vypsala odměny EFF Cooperative Computing Awards za nalezení prvočísla majícího alespoň 106,107,108 a 109 číslic - odměny 50, resp. 100 tisíc $ za první dvě kategorie byly vyplaceny v letech 2000, resp. 2009 - v obou případech projektu GIMPS - na další odměny si ještě zřejmě nějaký čas počkáme). Rozložení prvočísel Nyní se budeme snažit zodpovědět následující otázky: 1. Je prvočísel nekonečně mnoho? 2. Je prvočísel nekonečně mnoho v každé (nebo aspoň některé) aritmetické posloupnosti? 3. Jak jsou prvočísla rozložena mezi přirozenými čísly? 3Viz např. titulek iDnes z 6.února 2013: Největší známé prvočíslo na světě má 17 milionů číslic a je k ničemu 13 7. Prvočísla There are two facts about the distribution of prime numbers. The first is that, [they are] the most arbitrary and ornery objects studied by mathematicians: they grow like weeds among the natural numbers, seeming to obey no other law than that of chance, and nobody can predict where the next one will sprout. The second fact is even more astonishing, for it states just the opposite: that the prime numbers exhibit stunning regularity, that there are laws governing their behavior, and that they obey these laws with almost military precision. Don Zagier Prvočísel je nekonečně mnoho Věta 14 (Eukleidés). Mezi přirozenými čísly existuje nekonečně mnoho prvočísel. Důkaz. Předpokládejme, že prvočísel je konečně mnoho a označme je p±,P2, ■ ■ ■ ,Pn- Položme N = Pi • P2 ■ ■ ■ Pn + 1- Toto číslo je buď samo prvočíslem nebo je dělitelné nějakým prvočíslem různým od pi,... ,pn (čísla pi,... ,pn totiž dělí číslo N — 1), což je spor. □ Poznámka. Existuje mnoho variant důkazů nekonečnosti prvočísel z různých oblastí matematiky, uveďme ještě alespoň některá tvrzení, z nichž zároveň získáme alespoň částečnou informaci o rozložení prvočísel mezi přirozenými čísly. Prvočísel je vcelku hodně Příklad. Pro celé n > 2 existuje mezi čísly nan! alespoň jedno prvočíslo. Řešení. Označme p libovolné prvočíslo dělící číslo n! — 1 (takové existuje podle Základní věty aritmetiky, protože n! — 1 > 1). Kdyby p < n, muselo by p dělit číslo n! a nedělilo by n! — 1. Je tedy n < p. Protože p | (n! — 1), platí p < n! — 1, tedy p < n!. Prvočíslo p splňuje podmínky úlohy. □ Z této věty rovněž vyplývá nekonečnost prvočísel, její tvrzení je ale velice slabé. Následující tvrzení, uvedené bez důkazu, je podstatně silnější. Věta 15 (Cebyševova, Bertrandův postulát). Pro libovolné číslo n > 1 existuje alespoň jedno prvočíslo p splňující n < p < 2n. Prvočísel je vcelku málo Příklad. Dokažte, že pro libovolné přirozené číslo n existuje n po sobě jdoucích přirozených čísel, z nichž žádné není prvočíslo. Řešení. Zkoumejme čísla (n + 1)! + 2, (n + 1)! + 3,..., (n + 1)! + (n + 1). Mezi těmito n po sobě jdoucími čísly není žádné prvočíslo, protože pro libovolné k G {2, 3,.. ., n + 1} platí k | (n + 1)!, a tedy k | (n + 1)! + k, a proto (n + 1)! + k nemůže být prvočíslo. □ Prvočísla jsou relativně rovnoměrně rozložena v tom smyslu, že v libovolné „rozumné" aritmetické posloupnosti je jich nekonečně mnoho. Například zbytek 1 po dělení čtyřmi, stejně jako zbytek 3 po dělení čtyřmi dá vždy nekonečně mnoho prvočísel (zbytek 0 nedá samozřejmě žádné a zbytek 2 pouze jediné). Obdobná situace je pak při uvažování zbytků po dělení libovolným jiným přirozeným číslem, jak uvádí následující věta, jejíž důkaz je ovšem velmi obtížný. Věta 16 (Dirichletova o prvočíslech v aritmetické posloupnosti). Jsou-li a, m nesoudělná přirozená čísla, existuje nekonečně mnoho přirozených čísel k tak, že mk + a je prvočíslo. Jinými slovy, mezi čísly 1 ■ m + a, 2 ■ m + a, 3-m + a, ... existuje nekonečně mnoho prvočísel. Uveďme proto alespoň důkaz ve speciálním případě. 14 8. Aritmetické funkce Prvočísel tvaru 3A; + 2 je nekonečně mnoho Příklad. Dokažte, že existuje nekonečně mnoho prvočísel tvaru 3k + 2, kde í; e FJ0. Řešení. Předpokládejme naopak, že existuje pouze konečně mnoho prvočísel tohoto tvaru a označme je pi = 2, p2 = 5, P3 = 11, ..., pn. Položme N = 3p2 ■ Pz.....pn + 2. Rozložíme-li N na součin prvočísel, musí v tomto rozkladu vystupovat aspoň jedno prvočíslo p tvaru 3k+2, neboť v opačném případě by bylo N součinem prvočísel tvaru 3k + l (uvažte, že N není dělitelné třemi), a tedy podle dřívějšího příkladu by bylo i N tvaru 3k + 1, což není pravda. Prvočíslo p ovšem nemůže být žádné z prvočísel p\,p2, ■ ■ ■ ,Pn, jak plyne z tvaru čísla N, a to je spor. Asymptotické chování prvočísel Z tvrzení uvedených v této kapitole je možné si udělat hrubou představu o tom, jak „hustě" se mezi přirozenými čísla prvočísla vyskytují. Přesněji (i když „pouze" asymptoticky) to popisuje velmi důležitá tzv. „Prime Number Theorem": Věta 17 (Prime Number Theorem, věta o hustotě prvočísel). Nechi tt(x) udává počet prvočísel menších nebo rovných číslu i£l. Pak tj. podíl funkcí 7r(x) a x/lnx se pro x —> oo limitně blíží k 1. Příklad. O tom, jak odpovídá asymptotický odhad tt(x) ~ x/ln(x), v některých konkrétních příkladech vypovídá následující tabulka: x tt(x) x/ ln(x) relativní chyba 100 25 21.71 0.13 1000 168 144.76 0.13 10000 1229 1085.73 0.11 100000 9592 8685.88 0.09 1000000 78498 72382.41 0.08 8 Aritmetické funkce Aritmetické funkce Aritmetickou funkcí zde rozumíme funkci, jejímž definičním oborem je množina kladných celých čísel. Definice. Multiplikativní funkcí přirozených čísel rozumíme takovou aritmetickou funkci, která splňuje, že pro všechny dvojice nesoudělných čísel a, b e N platí f(a-b) = f(a)-f(b). Příklad. Multiplikativními funkcemi jsou např. funkce f(n) = cr(n), f(n) = r(n) nebo, jak brzy dokážeme i tzv. Eulerova funkce f(n) = 4>(n). V podstatě přímo z definice plyne, že multiplikativní funkce je jednoznačně určena svými hodnotami na mocninách prvočísel: f(n) = /(p"1 ■■■Ptk) = fiPi1) ■ ■ ■ /(Pfe*). 15 9. Malá Fermatova věta, Eulerova věta Eulerova funkce Definice. Nechť n G N. Definujme Eulerovu funkci 0 předpisem 0(n) = \{a G N i 0 < a < n, (a, n) = 1}| (lépe počet zbytkových tříd nesoudělných s n nebo také těch, které mají modulo n inverzi). Příklad. 0(1) = 1, 0(5) = 4, 0(6) = 2, je-li p prvočíslo, je zřejmě 4>{p) = p — 1. Nyní dokážeme několik důležitých tvrzení o funkci 0: Lemma. Platí(pa) = pa — pa~x = pa^1(p — 1) = pa(í — i). Důkaz. Mezi čísly {1,.. . ,pa} jsou soudělná s pa právě násobky p, tedy 1 -p, 2-p, ...,pa^ -p a těch je pa~x. Nesoudělných je proto pa — pa~x. □ Věta 18. Eulerova funkce 0 je multiplikativní. Nechi n G N, jehož rozklad je tvaru n = p"1 • • • p^k . Pak 4>{n) = (p*1 -Pi1^1) ■ ■ ■ {plk -Pfefc_1) = 71 ■ [ 1 - —) ■ ■ ■ [ 1 - — v Pij v Pk Důkaz. Nechť a, b jsou nesoudělná. Připomeňme bijekci x (mod a ■ b) i—> (x (mod a), x (mod b)) Stačí proto ukázat, že x (mod a ■ b) má inverzi, právě když obě složky obrazu mají inverzi -takových dvojic je totiž přesně 4>{a) ■ 4>{b). To plyne z Čínské zbytkové věty - inverze modulo a ■ b je inverzí modulo a i modulo b, naopak k inverzím modulo a a modulo b lze najít jedinou reprezentující zbytkovou třídu modulo a ■ b; ta je pak inverzí modulo a i modulo b, tedy modulo a ■ b. □ Příklad. Vypočtěte 0(72). Řešení. 72 = 23 • 32 ^> 0(72) = 72 • (1 - \) ■ (1 - \) = 24, alternativně 0(72) = 0(8) • 0(9) = 4 • 6 = 24. □ Příklad. Dokažte, že Vn G N : 0(4n + 2) = 0(2n + 1). Řešení. (4n + 2) = 0(2 • (2n + 1)) = 0(2) • 0(2n + 1) = 0(2n +1). □ 9 Malá Fermatova věta, Eulerova věta Úplná a redukovaná soustava zbytků Definice. Úplná soustava zbytků modulo m je libovolná m-tice čísel po dvou nekongruentních modulo m (nejčastěji 0,1, ... , m — 1). Redukovaná soustava zbytků modulo m je libovolná 0(m)-tice čísel nesoudělných s m a po dvou nekongruentních modulo m. Lemma. Nechi Xi, x2, ■ ■ ■, x^m^ tvoří redukovanou soustavu zbytků modulo m. Je-li a G Z, (a, m) = 1 pak i čísla a ■ x\,. .. , a ■ x^m^ tvoří redukovanou soustavu zbytků modulo m. Důkaz. Protože (a, m) = 1 a (xi,m) = 1, platí (a • Xi,m) = 1 (buď přes rozklad na prvočísla nebo přes invertibilnost modulo m - platí (a ■ Xi)~x = xfx ■ a-1). Kdyby pro nějaká i, j platilo (mod to), po vydělení obou stran kongruence číslem a nesoudělným s to dostaneme Xi = Xj (mod to). □ 16 9. Malá Fermatova věta, Eulerova věta Eulerova věta Věta 19 (Eulerova). Nechi a G Z, to G N, (a, m) = 1. PaÄ; a^™) = 1 (mod to). Důkaz. Buď xi, x2, .. ., x^m^ libovolná redukovaná soustava zbytků modulo to. Podle předchozího lemmatu je i a ■ x\, .. ., a ■ X0(m) redukovaná soustava zbytků modulo to. Platí tedy, že pro každé i existuje j {1, 2,. .. , (to)}) tak, že a ■ Xj = Xj (mod m). Vynásobením dostáváme (a • xi) ■ (a • x2) ■ ■ ■ (a ■ X0(m)) = Xi • 2ľ2 • • • X0(m) (mod m). Po úprave a0(m) . xi ■ x2 ■ ■ ■ X0(m) = xi ■ x2 ■ ■ ■ X0(m) (mod m) vydělení číslem x\ ■ x2 • • • X0(m) dostaneme požadované. □ Speciálním případem pro prvočíselný modul je pak tzv. Fermatova věta. Věta 20 (Fermatova, Malá Fermatova). Nechi a G Z, p prvočíslo, p \ a. Pak ap_1 = 1 (mod p). V tomto případě se dá věta přeformulovat bez předpokladu p \ a: Důsledek. Necht a G Z, p prvočíslo. Pak ap = a (mod p). Rád čísla S Eulerovou funkcí a Eulerovou větou úzce souvisí důležitý pojem řád čísla modulo m: Definice. Nechť a G Z, m G N (a, m) = 1. Řádem čísla a modulo m rozumíme nejmenší kladné celé číslo n splňující an = 1 (mod to). Poznámka. To, že je řád definován, plyne z Eulerovy věty - pro každé číslo nesoudělné s modulem je totiž jistě jeho řád nejvýše roven (to). Jak později uvidíme, velmi důležitá jsou právě ta čísla, jejichž řád je roven právě 4>(m) - tato čísla nazýváme primitivními kořeny modulo to. Příklad. Pro libovolné to G N má číslo 1 modulo to řád 1. Číslo —1 má řád • 1 pro to = 1 nebo to = 2 • 2 pro to > 2 Příklad. Určete řád čísla 2 modulo 7. Řešení. 21 = 2 ^ 1 (mod 7) 22 = 4 ^ 1 (mod 7) 23 = 8 = 1 (mod 7) Rád čísla 2 modulo 7 je tedy roven 3. Věta 21. Nechi to G N, a G Z, (a, to) = 1. Označme r řád čísla a modulo to t, s G N platí a* = as (mod to) <í=> t = s (mod r). □ . Pak pro libovolná 17 10. Primitivní kořeny Důkaz. Díky tomu, že as = as ■ ar = as+r (mod to), opakují se hodnoty mocnin as s periodou r, což dává implikaci "<í=". Zbývá ukázat, že zbytkové třídy a° (mod to), .. ., ar~1 (mod to) jsou všechny různé. Přitom pokud pro 0 a12 = 1 (mod 35). Je tedy každé číslo řádu 12 (případně menšího). Tedy kongruence x12 = 1 (mod 35) stupně 12 má 0(35) = 4 • 6 = 24 řešení. Věta 23. Pokud je m dělitelné aspoň dvěma lichými prvočísly, primitivní kořen modulo m neexistuje. Důkaz. Hlavní myšlenka je stejná jako výše. Rozložme m = k ■ l na součin dvou nesoudělných čísel větších než 2, např. k může být nej vyšší možná mocnina jednoho z lichých prvočísel z předpokladu. Označíme-li n = [(p(k), (p(l)] nejmenší společný násobek, platí a0(fe) = 1 (mod k) an = í (mod k) a podobně an = 1 (mod l); protože m = k ■ l a činitelé jsou nesoudělní, dostaneme dohromady an = 1 (mod to) a každý prvek má řád maximálně n = [(p(k), 4>{V)\ < (p(k)(p(l) = (p(m), protože hodnoty (k), (l) jsou obě sudé a tudíž soudělné. □ Podobně, pokud je to dělitelné čtyřmi a aspoň jedním lichým prvočíslem, primitivní kořen modulo to neexistuje. Polynomiální kongruence modulo prvočíslo Vydělme polynom 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 f(x) = 0 (mod p), dostaneme f(x) = (x — a) ■ g{x) (mod p). Protože je p prvočíslo, jsou kořeny f(x) právě kořen a lineárního činitele x — 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 f(x) = 0). Věta 24. x2 = 1 (mod p) má kořeny právě ±1. Primitivní kořen modulo prvočíslo Věta 25. Nechi p e 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. Pak všech p — 1 nenulových zbytkových tříd jsou kořeny xr = 1 (mod p) a podle předchozího p — 1 < r. □ Věta 26. Nechi p E N je prvočíslo. Pak existuje primitivní kořen modulo pk. Důkaz. Platí (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~x. Ukážeme, že je jím 1 + p; konkrétně níže ukážeme: (1 + p)p"~2 = 1 + pfe_1 ^ 1 (mod /) instance pro k+1 dá (l+p)pk = l+pk (mod pk+1) a po redukci modulo pk pak vyjde (l+p)pk ľ = 1 + pk = 1 (mod pk). □ 19 11. Kvadratické zbytky a nezbytky Lemma. a = b (mod pk) =>• ď = bp (modpfe+1). Důkaz. Platí ap — bp = (a — Ď)(ap_1 + • • • + akbl + • • • + kde první člen je dělitelný pk podle předpokladu, zatímco druhý člen je modulo p kongruentní aP-1 + ■■■ + akbl + ■■■ + bP-1 = gP-1 + ■■■ + ap-\ = p ■ aP-1 = 0 (mod p), p členu tedy je dělitelný p a součin je dělitelný pk+1. □ Důsledek. (1 + p)pk2 = 1 + pfe_1 (mod Důkaz. Indukční krok (v druhé kongruenci aplikujeme předchozí lemma na indukční předpoklad): (1 +Pf-1 EE ((l+pf-y EE (1 +Pk-y EE 1 + Qp*"1 + Qp2^ + ■ ■ ■ = í+pk (mod/+1). □ 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, 4>(p)) = 1, tedy jich je (p((p(p)). Přitom platí p/((p)) e O (log log p), 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 logp, tedy logaritmický vzhledem k délce vstupu (ověření toho, zda se vskutku jedná o primitivní kořen trvá déle, viz příště). Diskrétní logaritmus Definice. Nechť m > 0. Celé číslo g G Z, (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 < 4>(m) s vlastností ga = a (mod to). Označujeme a = logs a a nazýváme diskrétním logaritmem, příp. indexem čísla a (vzhledem k danému to a zafixovanému primitivnímu kořeni g) a je bijekcí mezi množinami {a G Z; (a, to) = 1, 0 < a < to} a {x G Z; 0 < x < (to)}. Důkaz. Zobrazení a (mod 4>(m)) <—> ga (mod to) je dobře definované a injektivní podle valstností řádu. Protože mají množiny stejný počet prvků (vpravo bereme pouze invertibilní zbytkové třídy), jedná se o bijekci. □ 11 Kvadratické zbytky a nezbytky Kvadratické kongruence modulo prvočíslo Věta 27. Nechí p je liché prvočíslo a (a,p) = 1. Kongruence x2 = a (mod p) má řešení, právě když a^š- = 1 (mod p). 20 11. Kvadratické zbytky a nezbytky 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) 45 2£ = a (modp-1). Protože je p — 1 sudé, řešení existuje, právě když a je sudé: a = 0 (mod 2) 45 ■ a = 0 (modp-1). 45 a 2 = g 2 a = g = í (mod p). O Legendreův symbol a kvadratický zbytek modulo p Definice. Definujeme (^) = ^ — 1 a kvadratický nezbytek modulo p. a soudělné s p Jednoduchým důsledkem věty dostáváme (^) = aRi~ (mod p): protože (a^í-)2 = ap_1 = 1, je a 2 rovno ±1. Důsledek. (-^) = +1, resp. — í, 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) = (*)(*)> . a^b (modp) =5 (£) = (*), • (P = (^)-(-l)^^- p—i Důkaz. První dvě položky plynou velice snadno z vyjádření (^) = a-^- (mod p). Druhé dva poznatky jsou značně hlubší, ukážeme hlavní ideu jejich důkazu, která spočívá v „geometrické" interpretaci Legendreova symbolu (^) = a^š- (mod p). Při interpretaci Legendreova symbolu vyjdeme z důkazu Eulerovy věty, ilustrujeme na příkladu (^-) = 75 (mod 11). Pišme tentokrát zbytky jako ±1,.. ., ±5 a uvažme opět násobení sedmi: 7 ■ 1 = -4 (mod 11) 1 ■ 7 • 2 = +3 (mod 11) 2 ■ 7 • 3 = -1 (mod 11) 3 ■ 7-4 =-5 (modli) 4- 7 • 5 = +2 (mod 11) 5 ■ a vynásobením dostaneme 75 • 5! = ±5! (mod 11), takže výsledné znaménko je přesně Legendreův symbol 75 (mod 11). Uvážíme-li namísto zbytků po dělení jedenácti příslušné zlomky se jmenovatelem 11 jako v prostředním sloupci, budou kladné zbytky odpovídat „oznaménkové desetinné části" menší než 1/2, zatímco záporné zbytky oznaménkové desetinné části větší než 1/2. Ještě jinak, po vynásobení zlomků dvěma jako v pravém sloupci budou kladné zbytky odpovídat sudé 7 4 7 3 = i - - 2 • = i -i 11 11 TT " TT 7 3 7 6 = i + 4- = 2^ 11 TT TT " TT 7 i 7 9 = 2 - 6 • = 3^ 11 TT TT " TT 7 5 7 i = 3- 8 • = 5^ -- TT TT TT n 7 2 7 4 = 3 + 10 • = 6^ TT TT TT " TT 21 11. Kvadratické zbytky a nezbytky celé části (standardní - desetinná část bez znamének), zatímco záporné zbytky liché celé části. Dostáváme tak (jSj = (_l)[2-Ä] + [4-Ä] + [6-Ä] + [8-Ä] + [10-ňl. Podstatná je tedy parita exponentu, přičemž exponent je „zjevně" počet černě zvýrazněných mřížových bodů v následujícím obrázku (sudé sloupce, pod diagonálou): ■ • ■ ■ o o § ■ • ■ ■ o ■ • ■ ■ a/ • • ■ • ■ • • • ■ • o • • • o • o • • • Protože je v každém sloupečku dohromady sudý počet (šest) mřížových bodů, je parita černě zvýrazněných bodů v pravé polovině stejná jako počet šedě zvýrazněných bodů (komplement v každém sloupečku) a díky středové symetrii je pak tento počet stejný jako počet bíle zvýrazněných bodů. Dohromady dostáváme, že (jt) je rovno —1 na počet mřížových bodů pod diagonálou v levé části. Symetricky dostaneme, že (—) je rovno —1 na počet mřížových bodů vlevo od diagonály ve spodní části. Vynásobením pak (^-) • (^) je rovno —1 na počet mřížových bodů v levé spodní části; těch je zjevně 5 • 3. Obecně pak = (-l)J V důkazu jsme nepoužili, že 7 je prvočíslo, ale jen, že je liché (protože jsme potřebovali v každém sloupečku sudý počet mřížových bodů). Proto můžeme počítat (směrnice této diagonály je přibližně 1 a počty mřížových bodů v jednotlivých sloupečcích budou narůstat o jedna přesně do poloviny): (-1) 1+2+- + Í (-D1 □ Ukážeme nyní, jak spočítat druhé odmocniny z kvadratického zbytku a (mod p) modulo prvočíslo splňující p = 3 (mod 4). V takovém případě a = a 2 ■ a = a 2 a odmocninu lze snadno spočítat jako ±aP4 . V případě, že a není kvadratický zbytek, tj. (^) = —1, dostaneme takto druhé odmocniny z —a, jak lze snadno z postupu vidět. Jacobiho symbol Definice, a libovolné, n = p\ ■ ■ -p^ liché číslo vyjádřené jako součin ne nutně různých prvočísel; definujeme ' a \ ( a \ ( a Pi Pk 22 12. Výpočetní aspekty teorie čísel Počítání Jacobiho symbolu je jednoduché s následujícími pravidly: • (£) = (£)(£)> . flE^modn) => (f) = (£), • (^ = (-1)^, • (-^) = (^) • (—l)22^^1 pro to, n lichá. Důkaz. Toto plyne z vlastností Legendreova symbolu poměrně přímočarým překladem (využívající identity typu (to2 — 1) + (n2 — 1) = (mn)2 — 1 (mod 16) pro to, n lichá). □ Příklad. Spočtěte (§§§). Příklad. Spočtěte (|) pro prvočíslo p, tj. rozhodněte, kdy je 3 kvadratický zbytek modulo prvočíslo p. Testování prvočíselnosti Test (test). Je-li p prvočíslo, pak aP^1 = 1 (mod p) (pro a náhodné nesoudělné s p). Test (složitější test). Je-li p prvočíslo, pak = ±1 (mod p) (pro a náhodné nesoudělné s p). Test (ještě složitější test). Je-li p prvočíslo, pak = (^) (mod p) (pro a náhodné nesoudělné s p). 12 Výpočetní aspekty teorie čísel 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ů: 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 to. 3. inverzi celého čísla a modulo to G N, 4. nej vě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 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 O(nlog2 3) nebo algoritmus Schonhage-Strassenův (1971) časové náročnosti O (n 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 23 12. Výpočetní aspekty teorie čísel GCD a modulární inverze Jak už jsme ukazovali dříve, výpočet řešení kongruence a-x = 1 (mod to) 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 to a na hledání koeficientů k, l do Bezoutovy rovnosti k ■ a + l ■ to = 1 (nalezené k je pak onou hledanou inverzí a modulo to). function extended_gcd(a, m) i f m = 0 return (1, 0) e ls e (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í 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 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ť 264 = (((((22)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 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 24 13. Diofantické rovnice A tedy 2560 = 1 (mod 561). 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. 13 Diofantické rovnice Příklad. Vyřešte diofantickou rovnici 72x + ÍOOy = 16. Příklad. Vyřešte diofantickou rovnici 72x + ÍOOy + 45z = 1. 14 Kryptografie s veřejným klíčem Kryptografie s veřejným klíčem (PKC) Dva hlavní úkoly pro PKC 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) RSA Ron Rivest, Adi Shamir, Leonard Adleman (1977; C. Cocks, GCHQ - 1973) • každý účastník A potřebuje dvojici klíčů - veřejný V a a soukromý S a • generování klíčů: zvolí se dvě velká prvočísla p, q, vypočte se n = pq, (p(n) = (p — í)(q — 1), dále se zvolí e a ověří, že (e, (p(n)) = 1, např. pomocí Euklidova algoritmu se spočítá d tak, aby e • d = 1 (mod (p(n)) • VA = (n, e), SA = d • zašifrování numerického kódu zprávy M: C = Va(M) = Me (mod n) • dešifrování šifry C: M = Sa(C) = Cd (mod n) 25 14. Kryptografíe s veřejným klíčem Rabínův kryptosystém Prvním veřejným kryptosystémem, k jehož prolomení je prokazatelně potřeba faktorizovat modul, je Rabínův kryptosystém, který si uvedeme 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, S a = (p, q) • zašifrování numerického kódu zprávy M: C = Va(M) = M2 (mod n) • dešifrování šifry C: vypočtou se (čtyři) odmocniny z C modulo n a snadno se otestuje, která z nich byla původní zprávou. Poznámka. Výpočet druhé odmocniny z C modulo n = pq, kde p = q = 3 (mod 4) • vypočti odmocniny modulo p a modulo q, konkrétně r = ±C*(p+1)/4 (mod p) a s = ±C*(9+1)/4 (mod q) • pomocí Čínské zbytkové věty spočti pro každou kombinaci odmocnin modulo p a modulo q odpovídající odmocninu modulo n = pq Příklad. V Rabínově kryptosystému Alice zvolila za svůj soukromý 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. Řešení. C = 692, kandidáti původní zprávy jsou ±138 ± 248 (mod 713). Princip digitálního podpisu Poznámka. 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. Poznámka. 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í Hm = H'M1. Diffie-Hellman key exchange Whitfield Diffie, Martm Hellman (1976; M. Williamson, CCHQ - 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, . ..). • Dohoda stran na prvočísle p a primitivním kořenu g modulo p (veřejné) • Alice vybere náhodné a a pošle ga (mod p) • Bob vybere náhodné b a pošle gb (mod p) • Společným klíčem pro komunikaci je gab (mod p). Poznámka. • Problém diskrétního logaritmu (DLP) • Nezbytná autentizace (man in the middle attack) 26 15. (n, k)-kódy Kryptosystém ElGamal Z protokolu DH na výmenu klíčů odvozen šifrovací algoritmus ElGamal: • Alice zvolí prvočíslo p spolu s primitivním kořenem g • Alice zvolí a a spočítá h = ga (mod p) • VA = (p, g, h), SA = a • šifrování zprávy M: Bob zvolí náhodné b a vypočte C\ = gb (mod p) a C2 = M ■ hb (mod p) a pošle C = (Ci, C2) • dešifrování zprávy: M = C2/C" (mod p) Poznámka. Analogicky jako v případě RSA lze odvodit podepisování. Eliptické křivky 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 kry-prografii 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 . 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. 15 (n, A;)—kódy Při přenosu informace zpravidla dochází k její deformaci. Budeme pro jednoduchost pracovat s modelem, kdy jednotlivé částečky informace jsou buď nuly nebo jedničky a budeme je interpretovat jako prvky Z2, tj. jako zbytkové třídy modulo 2, přičemž podstatné pro nás bude, že s nimi můžeme provádět algebraické manipulace: sčítat a násobit. Prvky Z2 budeme pro jednoduchost značit pomocí reprezentatů, tj. 0 a 1 namísto přesnějšího [0] a [1]. Protože operace splňují axiomy „tělesa", můžeme uvažovat vektorové prostory se skaláry v Z2, budeme však využívat pouze dva příklady: standardní (sloupcové) vektory jsou prvky kartézské mocniny (Z2)fe a polynomy jsou prvky Z2[x]. Sloupcové vektory sčítáme po složkách, přičemž je dobré mít na paměti, že v Z2 platí 1 + 1 = 0. To stejné platí pro polynomy - při jejich sčítání sčítáme odpovídající si koeficienty a opět využíváme 1 + 1 = 0. Ještě jedna ekvivalentní interpretace tohoto pravidla se nám bude hodit: — v = v. (Násobení skaláry není moc zajímavé, protože násobení 0 i násobení 1 je vynucené axiomy vektorového prostoru.) Přenášíme slova o k bitech. Protože přenosové chyby chceme rozpoznávat a ideálně i opravovat, přidáváme za tím účelem dodatečných n — k bitů informace pro pevně zvolené n > k. Mluvíme pak o (n, k)-kódu. Všech slov o k bitech je 2fe a každé z nich má jednoznačně určovat jedno kódové slovo z 2™ možných. Máme tedy ještě 2™ - 2fe = 2fe(2"~fe - 1) slov, které jsou chybové. Lze tedy tušit, že pro veliké k nám i malý počet přidaných bitů dává hodně redundantní informace. 27 16. Lineární kódy Úplně jednoduchým příkladem je kód kontrolující paritu. Kódové slovo o k + 1 bitech je určené tak, aby přidáním prvního bitu byl zaručen sudý počet jedniček ve slově. Pokud při přenosu dojde k lichému počtu chyb, přijdeme na to. Dvě různá kódová slova se při tomto kódu vždy liší alespoň ve dvou pozicích, chybové slovo se ale od dvou různých kódových slov liší pouze v pozici jedné. Nemůžeme proto umět chyby opravovat ani kdybychom věděli, že došlo k právě jedné. Navíc neumíme detekovat tak obvyklé chyby, jako je záměna dvou sousedních hodnot ve slově. Definice. Hammingova vzdálenost dvou slov je rovna počtu bitů, ve kterých se liší. Věta 28. 1. Kód odhaluje r a méně chyb právě, když je minimální Hammingova vzdálenost kódových slov právě r + 1. 2. Kód opravuje r a méně chyb právě, když je minimální Hammingova vzdálenost kódových slov právě 2r + 1. 16 Lineární kódy Definice. Lineární kód je injektivní lineární zobrazení g : (Z2)fe —> (Z2)™. Matice G typu n/k reprezentující toto zobrazení v standardních bazích se nazývá generující matice kódu. Pro každé slovo u je v = G ■ u příslušné kódové slovo. Pro jednoduchost budeme předpokládat, že kód přidává dodatečnou informaci a pro konkrétnost tedy, že v má blokový tvar v = {p^), kde Pu je ona dodatečná informace a m je původní vektor. Proto matice G bude mít blokový tvar Věta 29. Je-li g : (Z2)fe —> (Z2)™ lineární kód s maticí jako výše, potom zobrazení h : (Z2)™ —> (Zy™~fe s maticí H = (i„_fe P) má následující vlastnost: slovo v je kódové, právě když H ■ v = 0. Důkaz. Slovo v = (y) je kódové, právě když v = Gy = (Fyy), protože v takovém případě jsme schopni původní slovo y dekódovat z informačních bitů. Slovo f je tedy kódové, právě když x = Py, což je přesně podmínka H(y) = 0. □ Matici H z věty se říká matice kontroly parity přílušného (n, Ä;)-kódu, součinu Hv říkáme syndrom slova v. Nyní vysvětlíme význam syndromu i v případě, že je nenulový. Pokud neplatí Hv = 0, chceme přičtením co nejmenšího chybového vektoru k v dosáhnout toho, aby podmínka Hv = 0 platila. Přitom přičtení jedničky na z-tém místě způsobí změnu hodnoty přesně o i-tý sloupec kontrolní matice H. Chceme tedy hodnotu Hv vynulovat co nejmenším počtem sloupců matice H, přičemž v levé submatici máme právě sloupce s jednou jedničkou a v pravé právě kontrolní bity sloupců matice kódu. Kdybychom využívali pouze levou submatici (opravovali pouze kontrolní bity), potřebujeme opravit přesně tolik bitů, kolik obsahuje Hv jedniček (navíc přesně na stejných pozicích), syndrom tedy udává přesně tu jedinou možnou chybu, ke které mohlo dojít čistě na kontrolních bitech. Při použití informačních bitů můžeme počet chyb snížit, je tedy sice Hv jistá míra chybovosti, ale ne minimální. Naopak, nechť h je lineární zobrazení, jehož matice H je tvaru jako ve větě. Pak můžeme sestrojit lineární kód s maticí G jako před zněním věty a podle věty pak H bude matice kontroly parity. Jsme tedy schopni lineární kód zadat jeho (lineární) kontrolou parity. Jednoduše to lze ilustrovat na klasické kontrole parity, kde Ii(xq, . .., x^) = xq + • • • + x^ je zjevně lineární s maticí H=(í 1 ••• 1), 28 17. Polynomiální kódy kýženého tvaru. Nemusíme tedy specifikovat matici kódu, tu lze z matice kontroly parity odvodit. V další části uvedeme konstrukci polynomiálních kódů skrze jejich matici kontroly parity. Poznámka. Jak jsme viděli, přenos zprávy Gu s chybou e dává výsledek v = Gu + e, kde ale neznáme u, e a hledáme takový "rozklad", kde e obsahuje co nejméně jedniček (oprava chyby za předpokladu co nejmenšího počtu chyb). Je-li v = (y ), pak jednou z možností na odeslanou zprávu je Gy = (Fyy) (ne nutně optimální), tedy ::)=(?)+e+»^ kde s = x + Py = (in-t p)(y) = Hv je právě syndrom slova v a jedná se tedy o chybu za předpokladu, že k ní došlo pouze na kontrolních bitech (z informačních bitů lze proto přečíst původní slovo). Protože kódová slova jsou právě součty sloupců matice G, lze všechny další možnosti obdržet přičítáním sloupců ke kódovému slovu i chybě, buď přičítáním jednoho sloupce: x\ ff Py\ \ ((x + Py .vJ'KKvJ '9lJ + {{ o 1+91 případně dvou sloupců, atd. Přitom přičtení každého sloupce vyrobí jednu jedničku v informačních bitech chyby, snažíme se jejich počet kompenzovat snížením počtu jedniček v kontrolních bitech. Toto budeme zkoušet pouze pro malý počet chyb, viz cvičení. 17 Polynomiální kódy Jak konstruovat kódová slova, abychom je snadno rozpoznali? Kontrolu parity jsme už viděli, další triviální možnost je prosté opakování bitů - např. (3, l)-kód bere jednotlivé bity a posílá je třikrát po sobě. Docela systematickou cestou je využití dělitelnosti polynomů. Zpráva bgbi... bk—i je reprezentována jako polynom m(x) = bo + b\x + • • • + bk-ixk~1 G 7L2\x\. Definice. Nechť p(x) = ao + - ■ • + art_/c2ľrt~fe G Z2[x] je polynom s ao = 1, an-fe = 1- Polynomiální kód generovaný polynomem p(x) je lineární (n, Ä;)-kód, jehož slova jsou polynomy stupně menšího než n dělitelné p(x) a jehož kontrola parity je lineární zobrazení h posílající polynom na jeho zbytek po dělení p(x). Zobrazení h je opravdu lineární (zbytek součtu je součet zbytků). Polynomy stupně menšího než n — k jsou automaticky zbytkem po dělení p(x), takže je na nich h identita a matice H je tedy tvaru H = (I„_fe P) , jak je potřeba. Nastíníme nyní, jak matici P sestavit. Její první sloupec je zbytek xn~k a sestává se tedy z koeficientů p(x) stupně menšího než n—k. Další sloupec je zbytkem xn~k+1 = x-xn~k a získáme jej tedy z předchozího sloupce vynásobením x, přičemž případný výskyt xn~k nahradíme jeho zbytkem, tedy prvním sloupcem P. Konkrétně tedy sloupec posuneme dolů a případná jednička se při přetečení nahradí přičtením prvního sloupce. Takto postupujeme i pro další sloupce - posouváme předchozí, při přetečení přičítáme první! Příklad. 1. Polynom p(x) = 1 + x generuje (n, n — l)-kód kontroly parity pro všechna n > 3. 2. Polynom p(x) = 1 + x + x2 generuje (3, l)-kód opakování bitů. První tvrzení plyne z toho, že 1 + x dělí polynom v(x) tehdy a jen tehdy, když f (1) = 0 a to nastane tehdy, když je ve v(x) sudý počet nenulových koeficientů. Druhé je zřejmé. 29 18. Kombinatorika - motivace Matice příslušná k polynomu p(x) = 1 + x + x3 a jím určenému (7, 4)-kódu je G = /l 0 1 1\ 1 1 1 0 0 1 1 1 1 0 0 0 0 1 0 0 0 0 1 0 \o 0 0 1/ Přenos slova v G ^[x] dopadne příjmem polynomu u (x) = v (x) + e(x) kde e(x) je tzv. chybový polynom reprezentující vektor chyby přenosu. Chyba je rozpoznatelná pouze, když generátor kódu p (x) nedelí e(x). Máme proto zájem o polynomy, které nevystupují jako dělitelé zbytečně často. Připomeňme, že matice kontroly parity obsahuje ve sloupcích zbytky po dělení xl polynomem p(x). Pokud chceme, aby kód rozpoznal jednoduché chyby, nesmí matice kontroly parity obsahovat žádný nulový sloupec - to totiž odpovídá p(x) | xl. Pokud chceme, aby kód rozpoznal dvojité chyby, nesmí matice kontroly parity obsahovat žádný sloupec dvakrát - to totiž odpovídá p(x) \ x% + xJ. Při počtu řádků m = n — k, tak může P obsahovat maximálně 2m — 1 sloupců. Definice. Ireducibilní polynom p(x) G 7L2\x\ stupně m se nazývá primitivní, jestliže p(x) \ (l + x^) pro l < 2m - 1, a teprve p(x) | (1 + xe) pro £ = 2m - 1. Věta 30. Je-li p(x) primitivní polynom stupněm, pak pro všechna n < 2m — l rozpoznává příslušný (n,k)-kód všechny jednoduché a dvojité chyby. □ Důsledek. Je-li q(x) primitivní polynom stupně m, pak pro všechna n < 2m — 1 rozpoznává (n,k)-kód generovaný polynomem p(x) = q(x)(í + x) všechny dvojité chyby a všechna slova s lichým poetem chyb. □ Tabulka dává informace o výsledcích předchozích dvou vět pro několik polynomů: primitivní polynom kontrolní bity délka slova 1 + x- f x2 2 3 1 + x- f x3 3 7 1 + x- f x4 4 15 H -x2- f x5 5 31 1 + x- f x6 6 63 H - x3 - f x7 7 127 i + x2 + x3 ^ -x4- f xs 8 255 H -x4- f x9 9 511 1 + X3 -+ x10 10 1023 Nástroje pro konstrukci primitivních polynomů dává teorie konečných polí. Souvisí s tzv. primitivními prvky v Galoisových polích G(2m). Ze stejné teorie lze také dovodit příjemnou realizaci dělení se zbytkem, tj. ověřování, zda je přijaté slovo kódové, pomocí zpožďovacích registrů. Jde o jednoduchý obvod s tolika prvky, kolik je stupeň polynomu. 18 Kombinatorika — motivace Kombinatorika = umění počítat Často potřebujeme umět spočítat, kolika možnými způsoby se něco může stát! 30 18. Kombinatorika - motivace Nebývá to jednoduché a naším cílem nyní bude vybudovat základní prostředky pro řešení úloh obdobných těmto: Analýza algoritmů: Např. chceme zjistit očekávaný počet porovnání během algoritmu Quicksort. Odvození Cayleyho formule: Chceme znát počet různých stromů na daných n vrcholech. Quicksort — analýza průměrného případu Ukázka implementace (divide and conquer): i f L = [ ] : return [] return qsort([x for x in L 1:] if x < L[0]]) + L[0:1] + qsort([x for x in L 1:] if x >= L[0]]) 1. Počet porovnání při rozdělení (divide): n — 1. 2. (Předpoklad náhodnosti): Pravděpodobnost toho, že prvek L[0] je k-tý nej větší, je i. 3. Velikost tříděných polí ve fázi conquer: k — 1 a n — k. Pro střední hodnotu počtu porovnání tak dostáváme rekurentní vztah: n 1 Cn = n - 1 + V - (Cfe_i + Cn_fe). z—' n k=l Zjednodušení rekurence n Cn = n - 1 + V - (Cfe_! + C„_fe), Co = 0. '-^ n k=l symetrie obou sum vynásob n tentýž výraz pro Cn-\ odečteno a upraveno Vyřešení rekurence nCn = (n+ l)C„_i + 2(n - 1) Přestože jsme již rekurenci výrazně zjednodušili, takže je možné jednoduše iterativně hodnoty Cn dopočítat, je často žádoucí tyto hodnoty konkrétně (nebo alespoň přibližně) vyjádřit explicitně jako funkci n. Nejprve si pomůžeme drobným trikem, kdy vydělíme obě strany výrazem n(n + 1) : Cn = Cn-i | 2(n - 1) n + 1 n n(n + 1) Cn = n - 1 + - V C*fe_i n '-^ k=l n nCn = n(n - 1) + 2 ^ C*fe_i fe=i n-l (n - l)Cn_i = (n-í)(n-2) + 2j2 Ck-i k=l iCn = (n+ l)C„_i + 2(n - 1) 31 19. Elementární kombinatorické metody Nyní tento vztah „rozbalíme" (telescope, příp. si pomůžeme substitucí Bn = Cn/n+ 1): Cn = 2(n - 1) 2(n - 2) 2 ■ 1 Ci n+1 n(n+l) (n - l)n "' 2-3 2 Odkud n+ 1 ~~ ^ fe=i 0 + 1)0 + 2)' Výraz sečteme např. pomocí rozkladu na parciální zlomky /fc+1vfc+2) = ~~ ITT a dostaneme 2 ( ií„+i — 2 n+1 \ n+1 odkud C„ = 2(n + l)iřn+1 - 4(n + 1) + 2 (Hn = 5^fe=i i Je součet prvních n členů harmonické řady). Přitom je možné odhadnout Hn > J™ ^ + 7 = ln n + 7, odkud Cn ~ 2(n + l)(ln(n + 1) + 7 - 2) + 2. 19 Elementární kombinatorické metody Pravidlo součtu a součinu Vylučující se možnosti sčítáme, vzájemně nezávislé a současně se vyskytující případy se násobí. Na dané konečné množině S s n prvky je právě n! různých pořadí. Počet kombinací k-tého stupně z n prvků je (k < n) /n\ n(n — 1) ■ ■ ■ (n — k + 1) c(n, k j = ' 1 — Kk) k(k-í)...í (n-k)\kV Pro počet variací platí v (n, k) = n(n — 1) • • • (n — k + 1) pro všechny 0 < k < n (a nula jinak). Příklad. Určete, kolika způsoby lze z 15 poslanců vybrat čtyřčlennou komisi, není-li možné, aby jistí 2 poslanci pracovali spolu. Řešení. Výsledek je (^) - (If) = 1287. Kombinace a variace s opakováním Nechť je mezi n danými prvky p\ prvků prvního druhu, p2 prvků druhého druhu, ... , pk prvků k-tého druhu, pi+p2+- ■ -+Pk = n, potom pro počet pořadí těchto prvků s opakováním, P(p\, .. ., Pk), platí „\ P(pi, ■ ■ -,Pk) Pro variace k-tého stupně s opakováním z n prvků platí V(n, k) = nk. Pro kombinace s opakováním, C(n,k), platí Věta 31. Poěet kombinací s opakováním k-té třídy z n prvků je pro všechna 0 < k a 0 < n ni m ín + k-ť C(n, k) = 32 20. Vytvořující funkce Princip inkluze a exkluze Poznámka. Uvažujme obecnou konečnou množinu M a její podmnožiny A\,. .. , A^. Budeme psát \M\ pro počet prvků množiny M, tj. pro mohutnost množiny M. \m \ (utiA)l = |M| + J2(V1)* E l^i n ■ ■ ■ n . j = l ^ l • ELo(-i)feG)=o. Podíváme se teď na obě strany v binomické větě „spojitýma očima" a s využitím vlastností derivací odvodíme další vztah mezi kombinačními čísly. Důsledek. Platí po— Důkaz. Na obě strany binomické věty se podíváme jako na polynomiální funkce. Derivací pravé strany dostaneme n(l+x)rt_1, derivací levé strany (člen po členu) pak Efe=i ^(fe)a;fe_1- Dosazením x = 1 dostaneme tvrzení. □ 34 21. (Formální) mocninné řady 21 (Formální) mocninné řady (Formální) mocninné řady Definice. Buď dána nekonečná posloupnost a = (ao, &i, &2, ■ ■ ■)■ Její vytvořující funkcírozumíme (formální) mocninnou řadu tvaru Poznámka. O formální mocninné řadě hovoříme proto, že se zatím na tuto řadu díváme čistě formálně jako na jiný zápis dané posloupnosti a nezajímáme se o konvergenci. Na druhou stranu to ale znamená, že formální mocninná řada není funkce a nemůžeme do ní dosazovat. To ovšem vzápětí napravíme, když s využitím znalostí z analýzy nekonečných řad přejdeme od formálních mocninnných řad k příslušným funkcím. Příklad. Posloupnosti samých jedniček odpovídá formální mocninná řada 1 + x + x2 + x3 + • • •. Z analýzy víme, že stejně zapsaná mocninná řada konverguje pro x G (—1,1) a její součet je roven funkci 1/(1 — x). Stejně tak obráceně, rozvineme-li tuto funkci do Taylorovy řady v bodě 0, dostaneme zřejmě původní řadu. Takovéto „zakódování" posloupnosti čísel do funkce a zpět je klíčovým obratem v teorii vytvořujících funkcí. Jak jsme již zmínili, tento obrat lze ale použít pouze tehdy, pokud víme, že řada alespoň v nějakém okolí 0 konverguje. Často ale „diskrétní" matematici používají následující „podvod": • pomocí formálních mocninných řad odvodí nějaký vztah (formuli, rekurenci,. ..) bez toho, aby se zajímali o konvergenci • jinými prostředky (často matematickou indukcí) tento vztah dokážou Vytvořující funkce v praxi využíváme: • k nalezení explicitní formule pro k-tý člen posloupnosti; • často vytvořující funkce vycházejí z rekurentních vztahů, občas ale díky nim odvodíme rekurentní vztahy nové; • výpočet průměrů či jiných statistických závislostí (např. průměrná složitost algoritmu); • důkaz různých identit; • často je nalezení přesného vztahu příliš obtížné, ale mnohdy stačí vztah přibližný nebo alespoň asymptotické chování. Součet formální mocninné řady Následující větu znáte z matematické analýzy z loňského semestru: Věta 33. Bud (ao, &i, &2, ■ ■ ■) posloupnost reálných čísel. Platí-li pro nějaké R G R, že pro všechna k 3> 0 je |afe| < Rk, pak řada konverguje pro každé x E (—j^, -^). Součet této řady tedy definuje funkci na uvedeném intervalu, tuto funkci označujeme rovněž a(x). Hodnotami funkce a(x) na libovolném okolí 0 je jednoznačně určena původní posloupnost, neboí má a(x) v 0 derivace všech řádů a platí oo fe=0 fe>0 w(o) k\ 35 22. Operace s vytvořujícími funkcemi Přehled mocninných řad 1 E .k x 1 — x k>0 ln l-x 1 x .k Poznámka. • Poslední vzorec x' .k je tzv. zobecněná binomická věta, kde pro r e M je binomický koeficient definován vztahem /r\ r (r — 1) (r — 2) • • • (r — k + 1) \k) ~ k\ ' Speciálně klademe = 1. • Pro n G N z uvedeného vztahu snadno dostaneme který odvodíte na cvičení. • Ještě o něco obecněji můžeme substitucí ax za x obdržet obecnější vzorec, vhodný pro počítání konkrétních příkladů 22 Operace s vytvořujícími funkcemi Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (a.j + 6j) posloupností člen po členu odpovídá součet a(x) + b(x) příslušných vytvořujících funkcí. • Vynásobení (a-ai) všech členů posloupnosti stejným skalárem a odpovídá vynásobení a-a(x) příslušné vytvořující funkce. • Vynásobení vytvořující funkce a(x) monomem xk odpovídá posunutí posloupnosti doprava o k míst a její doplnění nulami. To plyne ze vztahu 36 22. Operace s vytvořujícími funkcemi • Pro posunutí posloupnosti doleva o k míst (tj. vynechání prvních k míst posloupnosti) nejprve od a(x) odečteme polynom bk(x) odpovídají posloupnosti (ao, .. ., &fc-i, 0,. ..) a poté podělíme vytvořující funkci xk. Dalšími důležitými operacemi, které se při práci s vytvořujícími funkcemi často objevují, jsou: • Derivování podle x: funkce a'(x) je vytvořující fukcí posloupnosti (a\, 2a2, 3a^, .. .), člen s indexem A; je (k + \)ak+\ (tj. mocninnou řadu derivujeme člen po členu). • Integrování: funkce Q a(t) dt je vytvořující fukcí posloupnosti (0, ao, \d\, \a2, \cl^, ■ ■ ■), pro k > 1 je člen s indexem k roven ^ftfc-i (zřejmě je derivací příslušné mocninné řady člen po členu původní funkce a(x)). • Násobení řad: součin a(x)b(x) je vytvořující funkcí posloupnosti (cq, c\, c2, .. .), kde Cfe = a0bk + <2i&fe_i H-----h akb0 = ^ azbj, i+j=k tj. členy v součinu až po ck jsou stejné jako v součinu (ao + aix + a2x2 + ■ ■ - + akxk)(bo + bix + b2x2 + • • • bkxk). Posloupnost (ck) bývá také nazývána konvolucí posloupností (&&), (bk). V dalším bude výhodné položit a_i = 0, a_2 = 0, atd. (pak můžeme sčítat přes všechna k), jenom bacha na konkrétní součty typu ^2k>0xk = j^, pro ty je potřeba sčítat pouze přes nezáporná k. Operace s vytvořujícími funkcemi přepíšeme: • £ akxk + £ bkxk = £(afc + bk)xk. • ol-Yj akXk = Y,(aak)xk. • xn ■ Y akxk = Y ak-nxk. • (E«fe^) ' (EMfe) = Ev', kde Cfe = ^ azbj. i+j=k Ukažme si důležitý příklad využívající konvoluci posloupností: Příklad, j^a(x) je v.f.p. (ao, &o + &i, ao + ai + a2, ■ ■ ■)■ Odtud např. dostáváme, že -In- je v.f.p. harmonických čísel Hk. 1 — x 1 — x Příklad. Protože = Yk>o xk > dostáváme konvolucí posloupnosti (1, 1, .. .) se sebou vztahy což máme dokázáno z dřívějška jako důsledek zobecněné binomické věty. Příklad. V krabici je 30 červených, 40 modrých a 50 bílých míčků, míčky stejné barvy přitom nelze rozeznat. Kolika způsoby je možné vybrat soubor 70 míčků? Řešení. Hledaný počet je roven koeficientu u x70 v součinu (í + x + x2 + ■■■+ x30)(í + x + x2 + ■■■+ x40)(í +x + x2 + ■■■ + x50). Tento součin upravíme na tvar (1 — x)~3(l — x31)(í — x41)(í — x51), odkud pomocí zobecněné binomické věty dostaneme ( (2) + (2) X + (2) ^ + ''' ) (1 " " - + ^2 + ■ ■ ■) a tedy koeficientem u x70 je zřejmě (70+2) - (70+^31) - (70+^41) - (70+22~51) = 1061. 37 22. Operace s vytvořujícími funkcemi Přiklad. Zkusme pomocí vytvořujících funkcí najít explicitní vzoreček pro 1 + 2 + • • • + 2k. Protože je 1^2x vytvořující funkce posloupnosti (2fe), je vytvořující funkcí pro posloupnost (1 + 2+ • • - + 2k) funkce i i _ n __í___i_ 1-x ' l-2x ' l-2x 1-x' Proto je zpětně tato posloupnost rovna (2 • 2fe — 1). Rozklad na parciální zlomky! Rozklad na parciální zlomky — připomenutí Rozklad na parciální zlomky jsme již viděli dříve při integraci racionálních lomených funkcí, přesto připomeneme: • Předpokládáme, že P(x)/Q(x) je podíl polynomů, kde degP < degQ (jinak vydělíme se zbytkem) a P(x),Q(x) nemají společné kořeny. • Polynom Q(x) rozložíme na kořenové činitele. • Jsou-li všechny kořeny a\, .. ., ag jednoduché, pak P(x) Á! | Ae Q(x) x — cii x — ai • Má-li kořen násobnost ki, pak se příslušný parciální zlomek nahradí součtem parciálních zlomků tvaru Au Ai2 Aiki (x — Cli) [x — Cli)2 [x — OLi)ki • V případě dvojice komplexně sdružených kořenů nahrazujeme sčítanec A/{x — a) sčítancem (Ax + B)/(x2 + px + q) včetně příslušných mocnin jmenovatele. • Neznámé dopočítáme roznásobením a buď porovnáním koeficientů u jednotlivých mocnin x nebo dosazením jednotlivých kořenů. • Výrazy A/(x — a)k převedeme na výrazy tvaru 5/(1— f3x)k vydělením čitatele i jmenovatele výrazem (—a)k. Tento výraz již umíme rozvinout do mocninné řady. Rozklad na parciální zlomky — vychytávka Protože preferujeme 1 — j3x, bude lepší jmenovatel rozložit rovnou na součin takovýchto činitelů, např. 1 - 5x + 6x2 = (1 - 2x)(í - 3x), který obecně získáme "otočením" polynomu - provedeme substituci x — cl vynásobme t . l-5i+6£ = (l-2i)(l-3i) í2-5í + 6= (ŕ-2)(ŕ-3) Přitom poslední tvar je již klasický rozklad na kořenové činitele, ve kterém můžeme použít např. známé vzorečky pro kořeny kvadratického polynomu. 38 23. Řešení rekurencí 23 Řešení rekurencí Fibonacciho čísla a zlatý řez Připomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem F0 = 0, Fi = 1, Fk = Ffe_! + Ffe_2 pro k > 2. Již dříve jste si uváděli všemožné výskyty této posloupnosti v přírodě, v matematice nebo v teoretické informatice (podrobně viz http://is.muni.cz/th/41281/prif_d/disertace.pdf). Našim cílem bude (opět) najít formuli pro výpočet n-tého členu posloupnosti. Poznámka. (Nejen) pro manipulace se sumami používají autoři Concrete mathematics velmi vhodné označení [logický predikát] - výraz je roven 1 v případě splnění predikátu, jinak 0., např. [k = 1], [2\k] apod. Pro vyjádření koeficientu u xk ve vytvořující funkci F(x) se pak často používá zápis [xk]F(x). Uvažme vytvořující funkci F(x) Fibonacciho posloupnosti. Při podmínkách Fq = 0, íi = 1 je to F(x) — xF(x) — x2F(x) = x, a tedy F(x) = 1 — x — x2 Našim cílem je tedy odvodit vztah pro k-tý člen posloupnosti. Využijeme k tomu rozklad na parciální zlomky a dostaneme x A B 1 — x — x2 1 — Xx 1— fix kde A, fi jsou kořeny t2 — í — 1 a A, B vhodné konstanty odvozené z počátečních podmínek. Odtud už vcelku snadno vyjde Fk = A ■ Xk + B ■ /j,k, jak to známe z dřívějška. S využitím počátečních podmínek dostáváme Fk~7E 1 + VŠ\ M - -v/5 Jistě je zajímavé, že tento výraz plný iracionálních čísel je vždy celočíselný. Uvážíme-li navíc, že (l--v/5)/2 « -0.618, vidíme, že pro všechna přirozená čísla lze Fk snadno spočítat zaokrouhlením čísla 1+2v^)fc. Navíc je vidět, že lim^^oo -Ffc+i/'-ffe = A ~ 1.618, což je poměr známý jako zlatý řez - objevuje se již od antiky v architektuře, výtvarném umění i hudbě. Řešení rekurencí Mocninné řady jsou velmi silným nástrojem pro řešení rekurencí (a to nejen lineárních!). Tím je míněno vyjádření členu jako funkci k. Často se s pomocí řad podaří vyřešit na první pohled velmi složité rekurence. Obvyklý (takřka mechanický) postup pro řešení rekurencí se skládá ze 4 kroků: 1. Zapíšeme jedinou rovnicí závislost na ostatních členech posloupnosti. Tento vztah musí platit pro všechna k e No (předpokládajíce a_i = a_2 = • • • = 0). 2. Obě strany rovnice vynásobíme xk a sečteme přes všechna k E No. Na jedné straně tak dostaneme 5^fc>oafea;fe' co^ Je vytvořující funkce A(x). Pravou stranu vztahu je pak třeba upravit na výraz rovněž obsahující A(x). 3. Zjištěná rovnice se vyřeší vzhledem k A(x). 39 23. Řešení rekurencí 4. Výsledné A(x) se rozvine do mocninné řady, přičemž koeficient u xk udává ak, tj. ak = [xk]A{x) . Příklad. Řešte rekurenci ao = 0, ai = 1 «fe = 5afe_! - 6afe_2 Řešení. • Krok 1: = 5afc_i — 6afc_2 + [A; = 1]. • Krok 2: = 5xA(a;) - 6x2A(x) + x. • Krok 3: m \ x 1 1 1 — bx + 6x2 1 — 3x l — 2x • Krok 4: ak = 3fe - 2fe. Quicksort — analýza průměrného případu Ukázka implementace (divide and conquer, rozmyslete, proč není optimální): i f L = [ ] : return return qsort([x for x in L 1:] if x=L[0]]) 1. Počet porovnaní při rozdělení (divide): k — 1. 2. (Předpoklad náhodnosti): Pravděpodobnost toho, že prvek L[0] je i-tý největší, je -g. 3. Velikost tříděných polí ve fázi conquer: i — 1 a k — i. Pro střední hodnotu počtu porovnání tak dostáváme rekurentní vztah: k k k Ck = k-Í + J2v (Ci-i + Cfe-i). Analýza Quicksortu pomocí vytvořujících funkcí Vyřešme nyní rekurenci k kCk = k(k-l) + 2j2 Ci-!,C0 = Ci = 0 i=i pomocí uvedeného postupu. . xC>(x) = T^ + 2^ • Vyřešíme tuto lineární diferenciální rovnici prvního řádu ((1 — x)2C(x))' = j^r, a tedy odkud konečně Ck = 2(k + í)(Hk+1 - 1) - 2fc. 40 24. Binární stromy a Catalanova čísla 24 Binární stromy a Catalanova čísla S využitím standardních vytvořujících funkcí určíme formuli pro počet bn tzv. pěstovaných binárních stromů na n vrcholech, které je pro naše účely možné definovat jako kořen s uspořádanou dvojicí [levý binární podstrom, pravý binární podstrom]. Prozkoumáním případů pro malá n vidíme, že 6o = l,6i = l,62 = 2,63 = 5. Dělením problému na levý a pravý strom dostaneme pro n > 1 bn = 606„_i + 6i6„_2 H-----h bn-ib0. Vidíme, že jde vlastně o konvoluci posloupností. Vztah upravíme, aby platil pro všechna n G Nq: K = E bkbn-k-i + [n = 0]. 0> = o]*" n n,k n,k = J2bkxk ( E&n-fc-l*"-*M + 1 = k \ n J = bkxk{xB{x)) + 1 = B (x) ■ xB(x) + 1. k Pravá strana rekurence na prvním řádku je koeficientem u xn~x v součinu B(x) ■ B(x), tj. členem u xn v xB(x)2. Je tedy xB{x)2 vytvořující po tutéž posloupnost jako B(x) s výjimkou prvního členu u x°. V kroku 3 řešíme kvadratickou rovnici B(x) = xB(x)2 + 1 pro B(x) : i±VT~4Í B{x) =-Yx-' Znaménko + ale nepřichází v úvahu, protože pak by pro x —> 0+ B (x) měla limitu 00, zatímco vytvořující funkce pro naši posloupnost musí mít v 0 hodnotu 60 = 1. Naopak pro znaménko — to tak dostaneme. Pro vytvořující funkci B(x) tedy platí 1-VT~4Í B{X) =-2x-' Zbývá už pouze krok 4, tedy rozvinout B(x) do mocninné řady. Rozvoj získáme pomocí zobecněné binomické věty fe>0 ^ " / k>l a po vydělení 1 — y/1 — 4x výrazem 2x dostaneme fe>i ^ /-l/2\ (-4x)" _ ^ (2n\ x- -ŕ l n / « -I- 1 -ŕ „ .. , n + 1 ^-^ \ n ) n + 1 41 25. Caleyho vztah pro počet stromů Catalanova čísla Dokázali jsme, že počet binárních pěstovaných stromů na n vrcholech je roven bn = ^q-j- (2^). Tato významná posloupnost se nazývá posloupnost Catalanových čísel. Kromě toho, že Catalanova čísla vyjadřují počet binárních pěstovaných stromů, vystupují rovněž jako: • počet monotónních cest z [0, 0] do [n, n] podél stran jednotkových čtverců, které nepřekročí diagonálu • počet slov délky 2n obsahujících n znaků X a Y takových, že žádný prefix slova neobsahuje více Y než X • podobně takové fronty u pokladny (n lidí má 5korunu a m lOkorunu, lístek stojí 5 Kč.), že nezásobená pokladna může vždy vrátit • počet korektně ozávorkovaných výrazů složených z levých a pravých závorek • počet různých triangulací konvexního (n + 2)-úhelníku. 25 Caleyho vztah pro počet stromů Cayleyho formule Cayleyho formule je vztah z kombinatorické teorie grafů, který udává, že počet stromů (tj. grafů, v nichž jsou libovolné dva vrcholy spojené právě jednou cestou) na n vrcholech je K(Kn) = nn~2. Dokážeme tento výsledek pomocí exponenciálních vytvořujících funkcí. Označme pro jednoduchost tn = n{Kn). Lze snadno spočítat, že íi = Í2 = 1, Í3 = 3, Í4 = 16. (Např. víme, že v případě stromů na 4 vrcholech musíme z (g) = 20 potenciálních grafů s právě 3 hranami odebrat ty možnosti, kde tyto hrany tvoří trojúhelník. Těch je ale právě (4) = 4). Rekurentní vztah získáme tak, že zafixujeme jeden vrchol v0 a možné případy rozdělíme podle počtu komponent v grafu, který dostaneme z koster Kn tak, že odstraníme vrchol v a hrany s ním incidentní. Kvůli jednoduchosti argumentu budeme rekurzivně vyjadřovat počet tzv. kořenových stromů, tj. stromů s vybraným vrcholem, kterému říkáme kořen. Jejich počet je zjevně un = ntn. Uvažme kořenový strom na n vrcholech s kořenem v0. Odstraněním tohoto vrcholu dostaneme disjunktní sjednocení několika stromů (tzv. les), přičemž každý strom, tj. každá z komponent, má vybraný kořen Ví, konkrétně soused vq v původním stromu. Naopak, pokud zvolíme vrchol f o, rozložíme množinu zbylých vrcholů na několik neprázdných disjunktních částí - označme jejich počet -a na každé vybereme strukturu kořenového stromu s kořenem Ví, dostaneme přidáním hran vqVi, ..., v0vm kořenový strom. Proto pro n > 1 platí El x ^ n\ m>0 1+feiH-----hkm=n (množinu všech vrcholů obarvíme barvami následovně: jeden vrchol vq barvou 0, dále ki vrcholů barvou i, pro každé i; faktor zaručí, že nezáleží na pořadí barev 1,... ,m, takže se vskutku jedná o rozklad; v komponentě každé barvy zvolíme kořenový strom). Vydělením n\ pak rekurenci výrazně zjednodušíme, zejména při substituci un = ^j: Un _ \p J_ \ - Ukj_ Ukm n\ ^ m\ ^ kx\ km\ m>0 /ciH-----\-km— n — 1 a je vidět, že vnitřní sumu dostaneme jako koeficient u xn 1 v m-té mocnině řady U(x) = Proto je Un r1] E -fiw Un m>0 42 25. Caleyho vztah pro počet stromů a tedy Ú(x) = xeG{x). Věta 34. Pokud vytvořující funkce g{x) = 5^n>i 9nXn splňuje vztah x = f(g(x)), kde /(o) = o,/'(o) ^ O, pak ff„ = -K-1] , , n \f(u), Důkaz. Nebudeme se pokoušet o rigorózní důkaz, uvedeme jen, proč by vůbec nějaký vztah mezi koeficienty f a, g měl existovat a jak lze pro malá n odvodit: Označíme-li f(u) = ^2k>1 akuk a g(x) = 5^;>i bix1, pak dosazením do sebe dostaneme vztah x = f(d(x)) = ai(bix + b2x2 + b3x3 + . ..) + a2{bix + b2x2 + . .. )2 + a^{bxx + .. . )3 + . .. = a\b\x + (aib2 + a2b\)x2 + (ai&3 + a2(bib2 + b2bi) + a3bl)x3 + ... ze kterého lze induktivně počítat (první koeficient a\b\ = 1, další jsou nulové): 1 -a2 2a| - aia3 h = —, b2 = —3-, 63 = -5-□ a\ a^ a^ Řešíme U(x) = xeu(x\ tj. U(x) splňuje vztah x = f (U (x)), kde f (u) = j^. Odtud z Lagran-geovy formule [xn]Ú(x) = -[u™-1 n \u/eu 1 1 t?" -kí™-1! e™ n (n — 1)! n! Protože = [x"]t/(x), dostáváme odtud tn = ^=nn-2. Další aplikace Lagrangeovy inverzní formule Vraťme se ještě krátce ke Catalanovým číslům. Chtěli jsme vyřešit rovnici B{x) = xB{x)2 + 1 a výslednou funkci B{x) pak rozvést do mocninné řady. Substitucí B{x) = C(x) + 1 rovnici převedeme na C(x) = x(C(x) + l)2 neboli C(x) _ (C(x) + Í)2 Označíme-li nyní f(u) = ^pj2, je hledaná funkce C{x) k této funkci inverzní a podle Lagrangeovy formule její koeficienty jsou n ]( , n2)" = -K"1]((" + i)T w/(it + l)z n = l-[u^]{l+u)2"=l-( 2n n n \n — 1 což lze vskutku ekvivalentně přepsat jako ^j(2)f)- Ukážeme ještě jeden způsob důkazu využívající exponenciální vytvořující funkce. 43 26. Rekurzivně propojené posloupnosti Exponenciální vytvořující funkce Kromě výše zmíněných vytvořujících funkcí se v praxi rovněž často objevují jejich tzv. exponenciální varianty4. n>0 Poznámka. Jméno vychází z toho, že exponenciální funkce ex je (exponenciální) vytvořující funkcí pro základní posloupnost (1,1,1,1,...). V zápětí v důkazu Cayleyho věty uvidíme, že je použití exponenciálních vytvořujících funkcí výhodné. Opět standardním operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami (coby exponenciálními vytvořujícími funkcemi): • Sčítání (čij + bi) posloupností člen po členu odpovídá součet a(x) + b(x) příslušných vytvořujících funkcí. • Vynásobení (a-ai) všech členů posloupnosti stejným skalárem a odpovídá vynásobení a-a(x) příslušné vytvořující funkce. • Derivování podle x: funkce a'(x) vytvořuje posloupnost (a\, &3, .. .), tj. derivování odpovídá posuvu doleva o jedno místo . • Integrování a(ť)dt vytvořuje posloupnost (0, a0, a1; a2, &3, .. .), tj. odpovídá posuvu doprava o jedno místo. • Součin vytvořujících funkcí vytvořuje posloupnost se členy i-\-j—n ' Alternativní závěr výpočtu Pro dokončení výpočtu budeme potřebovat tvrzení, které uvedeme bez důkazu. Definice. Zobecněnou exponenciální mocninnou řadou £t(x) nazýváme řadu ck £t(x) = J2(tk+l)k-1* k>0 Snadno je vidět, že £q = ex, dále označujeme £(x) = £\(x). Fakt: ]n£t(x) = x ■ £t(x), tj. spec. £(x) = ex£^ . Srovnáním tohoto vztahu s výše uvedeným U(x) = le17'1' vidíme, že U(x) = x£(x). Proto tn = — = -[xn]Ú(x) = {n- l)!^"-1]^(a;) = n n 26 Rekurzivně propojené posloupnosti Někdy dokážeme snadno vyjádřit hledaný počet jen pomocí více vzájemně provázaných posloupností. Příklad. Kolika způsoby můžeme pokrýt (nerozlíšenými) kostkami domina obdélník 3 x n? 4Používají se i další typy vytvořujících funkcí (např. v teorii čísel se používají Diricliletovy vytvořující funkce, kde roli faktoru i" hraje nTx), ale těmi se zde zabývat nebudeme. 44 26. Rekurzivně propojené posloupnosti Řešení Snadno zjistíme, že c\ = 0, C2 = 3, C3 = 0, dále klademe cq = 1 (nejde jen o konvenci, má to svou logiku). Najdeme rekurzívní vztah - diskusí chování „na kraji" zjistíme, že c„ = 2r„_i + c„_! + r„_2; ro = 0,ri = 1, kde rn je počet pokrytí obdélníku 3 x n, ze kterého jsme odstranili levý horní roh. Hodnoty c„ a rn pro několik malých n jsou: n 0 1 2 3 4 5 6 7 1 0 3 0 11 0 41 0 rn 0 1 0 4 0 15 0 56 • Krok 1: c„ = 2rn_1 + c„_2 + [n = 0], T n -1 + rn-2- Krok 2: C(x) = 2xiž(x) + x2C(x) + 1, i?(x) = xC(x) + x2R(x). • Krok 3: C(x) = í-x2 l-Ax2 R(x) = l-Ax2 • Krok 4: Vidíme, že funkce C(x) je funkce x2, ušetříme si práci tím, že uvážíme funkci D (z) = 1/(1-4z + z2), pak totiž C(x) = (l-x2)D(x2), tj. [x2n]C{x) = [x2n]{\-x2)D(x2) = [xn](í - x)D(x), a tedy c2„ = dn - dn-X- Kořeny 1 — 4x + x2 jsou 2 + -\/3 a 2 — \/3 a již standardním způsobem obdržíme (2 + VŠ)n (2 - VŠ)n C2n 3-VŽ 3 + VŠ Podobně jako u Fibonacciho posloupnosti je druhý sčítanec pro velká n zanedbatelný a pro všechna n leží mezi 0 a 1, proto ' (2 + y/3)n C2n 3- Např. c20 = 4 1 34 03. Ještě jeden příklad Příklad. Vyřešte rekurenci ao = ai = 1 an = an-i + 2a„_2 + (-1)™ Řešení. Tato rekurence je opět jiného typu než dosud studované. Jako vždy neuškodí vypsání prvních několika členů posloupnosti (teď ale ani moc nepomůže, snad jen pro kontrolu správnosti výsledku).5 • Krok 1: an = a„_i + 2a„_2 + (-l)"[n > 0] + [n = 1]. • Krok 2: A(x) = xA(x) + 2x2A(x) + + x. • Krok 3: 1 + x + x2 {X) ~ (í-2x)(í + x)2' • Krok 4: an = \2n + (|n + |) (-1)™. 5Narozdíl od tvrzení v Concrete mathematics je již možné tuto posloupnost nalézt v The On-Line Encyclopedia of Integer Sequences. 45