Literatura Řešení kongruencí a jejich si 3 u stav Polynomiální kongruence Kvadratické kongruence Šifry oooo oooooo ooooooooooooo ooo Diskrétní matematika B - 4. týden Elementární teorie čísel - Řešení kongruencí Michal Bulant Masarykova univerzita Fakulta informatiky jaro 2014 Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry oooo oooooo ooooooooooooo ooo Q Řešení kongruencí a jejich soustav • Binomické kongruence Ql Obecné polynomiální kongruence Q Kvadratické kongruence a Legendreův symbol Ql Dalších pár slov o šifrách Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry oooo oooooo ooooooooooooo ooo • Jan Slovák, Martin Panák, Michal Bulant, Matematika drsně a svižně, MU Brno, 2013, 774 s. (též jako e-text). • Předmětové záložky v IS MU • Michal Bulant, výukový text k přednášce Elementární teorie čísel, http://is.muni.cz/el/1431/podzim2012/M6520/ um/main-print.pdf • William Stein, Elementary Number Theory: Primes, Congruences, and Secrets, Springer, 2008. Dostupné na http://wstein.org/ent/ent.pdf a http://wstein.org/edu/2007/spring/ent/ Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry oooo oooooo ooooooooooooo ooo • Radan Kučera, výukový text k přednášce Algoritmy teorie čísel, http://www.math.muni.cz/~kucera/texty/ATC10.pdf • Donald E. Knuth, The Art Of Computer Programming. • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, MIT Press, 2009. • Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone, Handbook of Applied Cryptography, CRC Press, 2001. (též jako e-text). Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry •ooo oooooo ooooooooooooo ooo Binomické kongruence V této části se zaměříme na řešení speciálních typů polynomiálních kongruencí vyššího stupně, tzv. binomických kongruencí. Jde o analogii binomických rovnic, kdy polynomem f(x) je dvojčlen x" — a. Snadno se ukáže, že se můžeme omezit na případ, kdy je a nesoudělné s modulem kongruence - v opačném případě totiž vždy můžeme pomocí ekvivalentních úprav kongruencí na tento případ převést nebo rozhodnout, že kongruence není řešitelná. ' Příklad Řešte kongruencí x3 = 3 (mod 18). Řešení Protože je (3,18) = 3, nutně 3 | x. Užijeme-li substituci x = 3 • x\, dostáváme kongruencí 27x3 = 3 (mod 18), která zřejmě nemá řešení, protože (27,18) \ 3. Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry o»oo oooooo ooooooooooooo ooo Mocr inné zbytky Definice Nechť m G N, a G Z, (a, m) = 1. Číslo a nazveme n-tým mocninným zbytkem modulo m, pokud je kongruence x" = a (mod m) řešitelná. V opačném případě nazveme a n-tým mocninným nezbytkem modulo m. Pro n = 2,3,4 používáme termíny kvadratický, kubický a bikvadratický zbytek, resp. nezbytek modulo m. Ukážeme, jakým způsobem řešit binomické kongruence modulo m, pokud modulo m existují primitivní kořeny (tedy zejména, je-li modul liché prvočíslo nebo jeho mocnina). Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry 00*0 OOOOOO OOOOOOOOOOOOO OOO Řešení binomických kongruencí Věta Bud m £ N takové, že modulo m existují primitivní kořeny. Dále nechi a £ Z, (3, m) = 1. Pak kongruence x" = a (mod m) je řešitelná (tj. a je n-tý mocninný zbytek modulo m), právě když a 1, můžeme nahradit tuto kongruenci soustavou kongruencí která má stejnou množinu řešení, a řešit každou kongruenci této soustavy zvlášť. Tím získáme obecně několik soustav lineárních kongruencí, které už umíme řešit. Výhoda této metody spočívá v tom, že moduly kongruencí soustavy jsou menší než modul původní kongruence (a navíc je možné, jak brzy ukážeme, tyto kongruence ještě zjednodušit). f(x) 0 (mod p"1) f(x) 0 (mod p"kk), Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry oooo o#oooo ooooooooooooo ooo Příklad Řešte kongruenci x5 + 1 = 0 (mod 11). Příklad Řešte kongruenci x3 — 3x + 5 = 0 (mod 105). Řešení Kdybychom postupovali obdobně jako dříve pro m = 105, museli bychom spočítat pro f(x) = x3 — 3x + 5 sto pět hodnot ^(0), f(l), ..., f(104). Proto raději rozložíme 105 = 3 • 5 • 7 a budeme řešit kongruence f(x) = 0 postupně pro moduly 3, 5, 7 a z řešení soustavy těchto kongruencí zrekonstruujeme řešení kongruence původní. Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry oooo oo»ooo ooooooooooooo ooo Kongruence modulo mocnina prvočísla Postup pro řešení kongruencí modulo mocnina prvočísla udává důkaz následující věty. Věta (Henselovo lemma) Necht p je prvočíslo, f(x) G Z [x], a G Z je takové, že p | f (a), p \ f '(a). Pak platí: pro každé n G N má soustava x = a (mod p) f{x) = 0 (mod p") právě jedno řešení modulo p". Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry oooo ooo»oo ooooooooooooo ooo Důkaz. Indukcí vzhledem k n: pro n = 1 platí díky předpokladu věty. Nechť dále n > 1 a věta platí pro n — 1. Bud' x řešení soustavy pro n, tedy i pro n — 1. Označme jedno z řešení soustavy pro n — 1 jako c„_i a hledejme řešení pro n ve tvaru x = c„_i + /c • p"-1. Je třeba zjistit, pro která k platí f (c„-i + /c • p"-1) = 0 (mod p"). Víme, že p"_1 | f (c„-i + /c • p"-1) a užijme binomickou větu pro f{x) = amxm H-----h aix + a0. Odtud f (c„_i + /c • p""1) = 0 (mod p") ^ ^ 0 = f~^T- + * • f'(c"-i) (mod P)- Přitom f'(cn-i) = f'{a) ^ 0 (mod p) a odtud vidíme, že existuje právě jedno řešení k této kongruence, a je tedy číslo Q7-1 + ^ " p" 1 jediným řešením dané soustavy modulo p". □ Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry oooo oooo»o ooooooooooooo ooo Příklad Řešte kongruenci x4 + 7x + 4 = 0 (mod 27). Řešení Řešme nejprve tuto kongruenci modulo 3 (např. dosazením) -snadno zjistíme, že řešení je x = 1 (mod 3). Zapišme řešení ve tvaru x = 1 + 3ŕ, kde ŕ G Z a řešme kongruenci modulo 9. x4 + 7x + 4 = 0 (mod 9) (1 + 3ř)4 + 7(1 + 3t) + 4 = 0 (mod 9) l + 4-3ř + 7 + 7-3ř + 4 = 0 (mod 9) 33ř = -12 (mod 9) lir = -4 (mod 3) t = 1 (mod 3) Zapsáním t = 1 + 3s, kde s G Z dostaneme x = 4 + 9s. Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry oooo ooooo* ooooooooooooo ooo Řešení Po dosazení (4 + 9s)4 + 7(4 + 9s) + 4 = 0 (mod 27) 44 + 4 . 43 . 9S + 28 + 63s + 4 = 0 (mod 27) 256 • 9s + 63s = -288 (mod 27) 256s + 7s = -32 (mod 3) 2s = 1 (mod 3) s = 2 (mod 3) Celkem dostáváme řešení x = 4 + 9s = 4 + 9(2 + 3r) = 22 + 27r, kde r G Z, neboli x = 22 (mod 27). □ Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry OOOO OOOOOO »000000000000 ooo Naším úkolem bude najít jednodušší podmínku, jak zjistit, jestli je řešitelná (a případně, kolik má řešení) kvadratická kongruence ax2 + bx + c = O (mod m). Z teorie, uvedené dříve, je snadné vidět, že k rozhodnutí, je-li tato kongruence řešitelná, stačí určit, je-li řešitelná (binomická) kongruence x2 = a (mod p), kde p je liché prvočíslo a a číslo s ním nesoudělné. Pro určení řešitelnosti kongruence můžeme samozřejmě využít Větu o řešitelnosti binomické kongruence, její využití ale často naráží na výpočetní složitost, proto se (nejen) v kvadratickém případě snažíme najít kritérium jednodušší na výpočet. Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry oooo oooooo o»ooooooooooo ooo Příklad Určete počet řešení kongruence x2 = 219 (mod 383). Řešení Protože 383 je prvočíslo a (2,■ $ = (£). Důkaz. ad 1. Pro p | a je tvrzení zřejmé; pokud je a kvadratický zbytek modulo p, pak tvrzení plyne z Věty o řešitelnosti binomických kongruencí. Z téže věty plyne, že v případě kvadratického nezbytku je a^~ ^ 1 (mod p). Pak ale, protože p | ap_1 - 1 = (aV - l)(aV + 1) nutně p | aV + 1, tj. a^T~ = — 1 (mod p). ad 2. Plyne z 1. ad 3. Zřejmé z definice. □ Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry oooo oooooo oooo»oooooooo ooo Důsledek O V libovolné redukované soustavě zbytků modulo p je stejný počet kvadratických zbytků a nezbytků. O Součin dvou kvadratických zbytků je zbytek, součin dvou nezbytků je zbytek, součin zbytku a nezbytku je nezbytek. 0 (—1/p) = (—1)^, tj. kongruence x2 = — 1 (mod p) je řešitelná právě tehdy, když p = 1 (mod 4). Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry oooo oooooo ooooo»ooooooo ooo Již s využitím těchto základních tvrzení o hodnotách Legendreova symbolu jsme schopni dokázat větu o nekonečnosti počtu prvočísel tvaru 4/c + 1. Tvrzení Prvočísel tvaru 4/c + 1 je nekonečně mnoho. Důkaz. Sporem. Předpokládejme, že pi,p2, ■ ■ ■, Pe jsou všechna prvočísla tvaru 4/c + 1 a uvažme číslo N = (2pi • • • pi)2 + 1. Toto číslo je opět tvaru 4/c + 1. Pokud je N prvočíslo, jsme hotovi (protože je jistě větší než kterékoli z pi,p2, • • • ,Pi), pokud je složené, musí existovat prvočíslo p, dělící N. Zřejmě přitom žádné z prvočísel 2, pi, P2, • • •, Pí není dělitelem N, proto stačí dokázat, že p je rovněž tvaru 4/c + 1. Protože ale (2pi • • • pi)2 = — 1 (mod p), dostáváme, že (—1/p) = 1, a to platí právě tehdy, je-li p = 1 (mod 4). □ Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry OOOO OOOOOO 000000*000000 ooo Nejdůležitější tvrzení, umožňující efektivně určit hodnotu Legendreova symbolu (a tak rozhodnout o řešitelnosti kvadratické kongruence), je tzv. Zákon kvadratické reciprocity. ' Věta Necht p, q jsou lichá prvočísla. Pak o (f) = (-1)^ o ® = (-1)^ o © = ©-(-i)^ Důkaz. Viz literatura, důkazů je celá řada (v roce 2010 uváděl F. Lemmermeyer 233 důkazů), obvykle ovšem využívajících (zejména u těch stručnějších z nich) hlubších znalostí z algebraické teorie čísel. □ Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry oooo oooooo ooooooo»ooooo ooo Věta se v tomto tvaru uvádí zejména proto, že pomocí těchto tří vztahů a základních pravidel pro úpravy Legendreova symbolu jsme schopni vypočítat hodnotu (a/p) Pro libovolné celé číslo a. Důsledek O — 1 je kvadratický zbytek pro prvočísla p splňující p = 1 (mod 4) a nezbytek pro prvočísla splňující p = 3 (mod 4). O 2 je kvadratický zbytek pro prvočísla p splňující p = ±1 (mod 8) a nezbytek pro prvočísla splňující p = ±3 (mod 8). 0 Je-li p = 1 (mod 4) nebo q = 1 (mod 4), je (p/q) = {q/p), pro ostatní lichá p, q je (p/q) = —(q/p). Řešení kongruencí a jejich soustav oooo Polynomiální kongruence oooooo Kvadratické kongruence oooooooo^oooo Příklad Určete ($). 79 101 101 79 22 79 2 79 11 79 (-D n 101 c/aVa po dělení 4 zbytek 1 79 dává pod dělení 8 zbytek -1 11 i 79 dávají pod dělení 4 zbytek 3 11 dává pod dělení 8 zbytek 3 Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry oooo oooooo ooooooooo»ooo ooo Vyčíslení Legendreova symbolu (jak jsme viděli i v předchozím příkladu) umožňuje používat zákon kvadratické reciprocity jen na prvočísla a nutí nás tak provádět faktorizaci čísel na prvočísla, což je výpočetně velmi náročná operace. Toto lze obejít rozšířením definice Legendreova symbolu na tzv. Jacobiho symbol s podobnými vlastnostmi. Definice Nechť a G Z, b G N, 2 \ b. Nechť b = pxp2 ■ ■ ■ Pk je rozklad b na (lichá) prvočísla (výjimečně neseskupujeme stejná prvočísla do mocniny, ale vypisujeme každé zvlášť, např. 135 = 3 • 3 • 3 • 5). Symbol se nazývá Jacobiho symbol. Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry oooo oooooo oooooooooosoo ooo Dále ukážeme, že Jacobiho symbol má podobné vlastnosti jako Legendreův symbol (s jednou podstatnou odchylkou). Neplatí totiž obecně, že z (a/b) = 1 plyne řešitelnost kongruence x2 = a (mod b). Příklad = (-1) •(-!) = ! a přitom kongruence x2 = 2 (mod 15) není řešitelná (není totiž řešitelná kongruence x2 = 2 (mod 3) a není ani řešitelná kongruence x2 = 2 (mod 5)). Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry OOOO OOOOOO OOOOOOOOOOO0O ooo Věta (Kvadratická reciprocita pro Jacobiho symbol) Necht a, b G N jsou lichá. Pak o (^) = (-i)^1 © (i) = (-i)^ © (f)(1) = (-i)" Rozhodněte o řešitelnosti kongruence x2 = 219 (mod 383). Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry OOOO OOOOOO OOOOOOOOOOOO* ooo 383 je prvočíslo, proto bude kongruence řešitelná, bude-li Legendreův symbol (219/383) = 1. ) = — ( ^j-^ ) (Jacobi) 383 i 219 dávají po dělení 4 zbytek 3 164 = 22 -41 383 219 164 219 219 1T 14 41 7_ 41 41 Y -1 T v219/ (Jacobi) 41 dává po dělení 4 zbytek 1 v41/ V41/ 41 dává po dělení 8 zbytek 1 41 dává po dělení 4 zbytek 1 = 1 7 dává po dělení 4 zbytek 3. Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry oooo oooooo ooooooooooooo #oo Prvním veřejným kryptosystémem, k jehož prolomení je prokazatelně potřeba faktorizovat modul, je Rabinův kryptosystém, který si uvedeme ve zjednodušené verzi: • každý účastník A potřebuje dvojici klíčů - veřejný Va a soukromý Sa • generování klíčů: A zvolí dvě podobně velká prvočísla p,q = 3 (mod 4), vypočte n = pq. • VA = n, SA = (p, q) • zašifrování numerického kódu zprávy M: C = Ce(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. Literatura Řešení kongruenci a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry oooo oooooo ooooooooooooo o»o Výpočet druhé odmocniny z C modulo n = pq, kde p = q = 3 (mod 4) • vypočti r = C(p+1)/4 (mod p) a s = C^1)/4 (mod q) • vypočti a, fa tak, že ap + bq = 1 • položa x = (aps + faqr) (mod n), y = (aps — faqr) (mod n) 9 druhými odmocninami z C modulo n jsou ±x, ±y. aUvědomte si, že jde vlastně o aplikaci Čínské zbytkové věty! Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry oooo oooooo ooooooooooooo oo» 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 ±4 • 23 • 14 ± 3 • 31 • 18 (mod 713).