Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry ooooooooooooooooooooooo ooooo ooooooooooooo ooo Diskrétní matematika B - 4. týden Elementární teorie čísel - Řešení kongruencí Michal Bulant Masarykova univerzita Fakulta informatiky jaro 2013 Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry ooooooooooooooooooooooo ooooo ooooooooooooo ooo řednášky Řešení kongruencí a jejich soustav • Lineární kongruence • Lineární kongruence o jedné neznámé • Soustavy lineárních kongruencí o jedné neznámé • Binomické kongruence Obecné polynomiální kongruence Kvadratické kongruence a Legendreův symbol Dalších pár slov o šifrách Literatura Řešení kongruencí a jejich soustav Polynomiá ní kongruence Kvadratické kongruence Šifry ooooooooooooooooooooooo ooooo ooooooooooooo ooo Dopo ručené zdroje • Martin Panák, Jan Slovák, Drsná matematika, průběžně připravovaný e-text. • Předmětové záložky v IS MU 9 Michal Bulant, výukový text k přednášce Elementární teorie čísel, http: //is .muni. cz/el/1431/podzim2012/M6520/ um/main-print.pdf • Jiří Herman, Radan Kučera, Jaromír Šimša, Metody řešení matematických úloh. MU Brno, 2001. • William Stein, Elementary N um ber Theory: Primes, Congruences, and Secrets, Springer, 2008. Dostupné na http://wstein.org/ent/ent.pdf a http://wstein.org/edu/2007/spring/ent/ • Radan Kučera, výukový text k přednášce Algoritmy teorie čísel, http://www.math.muni.cz/~kucera/texty/ATC10.pdf Nechť m G N, f (x), g (x) G Z [x]. Zápis f(x) = g(x) (mod m) nazývame kongruencí o jedné neznámé x a rozumíme jím úkol nalézt množinu řešení, tj. množinu všech takových čísel c G Z, pro která f (c) = g(c) (mod m). Dvě kongruence o jedné neznámé nazveme ekvivalentní, m a j í-1 i stejnou množinu řešení. Uvedená kongruenceje ekvivalentní s kongruencí f (x) — g(x) = 0 (mod m). ez[x] Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry o^ooooooooooooooooooooo ooooo ooooooooooooo ooo Necht m G N, ŕ (x) G Z [x]. Pro libovolná a, b G Z platí Nechť je f (x) = c„x" + cn_ix"_1 + • • • + c\x + cq, kde Co, ci,..., c„ G Z. Protože a = fa (mod m), pro každé / = 1, 2,..., n platí cf-a' = c/b' (mod m), a tedy sečtením těchto kongruencí pro / = 1, 2,..., n a kongruence co = cq (mod m) dostaneme (mod m). cnan H-----h cia + c0 tj. f(a) = (mod m). = cnbn + • • • + c\b + co (mod m), □ Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry OO0OOOOOOOOOOOOOOOOOOOO ooooo ooooooooooooo ooo Počel : řešení kongruence Důsledek Množina řešení libovolné kongruence modulo m je sjednocením některých zbytkových tříd modulo m. Definice Počtem řešení kongruence o jedné neznámé modulo m rozumíme počet zbytkových tříd modulo m obsahujících řešení této kongruence. Příklad Q Kongruence 2x = 3 (mod 3) má jedno řešení (modulo 3). O Kongruence lOx = 15 (mod 15) má pět řešení (modulo 15). 0 Kongruence z příkladu (1) a (2) jsou ekvivalentní. -■ Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry ooosooooooooooooooooooo ooooo ooooooooooooo ooo ' Věta ^ Necht m e N, a, b e Z. Označme d = (a, m). Pak kongruence ax = b (mod m) (o jedné neznámé x) má řešení právě tehdy, když d b. Pokud platí d b, má tato kongruence právě d řešení (modulo m). Důkaz. Dokážeme nejprve, že uvedená podmínka je nutná Je-li celé číslo c řešením této kongruence, pak nutně m a ■ c — b. Pokud přitom d = (a, m), pak protože d\m\d\a-c — ba d a ■ c — (a • c — b) = b. Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry OOOO0OOOOOOOOOOOOOOOOOO ooooo ooooooooooooo ooo Dokončení důkazu. Obráceně dokážeme, že pokud d \ b, pak má daná kongruence právě d řešení modulo m. Označme a\, b\ G Z a m\ G N tak, že a = d • a\, b = d-b\2,m = d- m\. Řešená kongruence je tedy ekvivalentní s kongruencí a\ • x = b\ (mod mi), kde (ai, m\) = 1. Tuto kongruencí můžeme vynásobit číslem a^(mi) 1 a Eulerově větě obdržíme x = b\ • a^mi^ 1 (mod mi). Tato kongruence má jediné řešení modulo m\ a tedy d = m/mi řešení modulo m. □ Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry ooooo«ooooooooooooooooo ooooo ooooooooooooo ooo Následující příklad ukáže, že postup uvedený v důkazu věty obvykle není tím nejefektivnějším - s výhodou lze použít jak Bezoutovu větu, tak ekvivalentní úpravy řešené kongruence. Příklad Řešte 39x = 41 (mod 47) O Nejprve využijeme Eulerovu větu, stejně jako v důkazu předchozí věty. Q Další možností je využít Bezoutovu větu. O Obvykle nejrychlejším, ale nejhůře algoritmizovatelným způsobem řešení je metoda takových úprav kongruence, které zachovávají množinu řešení. 39x = 41 (mod 47) 4x = 3 (mod 47) x = -11 (mod 47) Literatura Řešení kongruencí a jejich soustav Polynomiá ní kongruence Kvadratické kongruence Šifry OOOOOO0OOOOOOOOOOOOOOOO ooooo ooooooooooooo ooo Wilso nova 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 (Wilsonova) Přirozené číslo n > 1 je prvočíslo, právě když (n-l)! = -l (mod /?) Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry ooooooo»ooooooooooooooo ooooo ooooooooooooo ooo Důkaz. Dokážeme nejprve, že pro libovolné složené číslo n > 4 platí n\ (n - 1)!, tj. (n - 1)! = 0 (mod n). Nechť 1 < d < n je netriviální dělitel n. Je-li d ^ n/d, pak protože 1 < d, n/d < n — 1, je n = d ■ n/d | (n — 1)!. Pokud d = n/d, tj. n = d2, pak protože je n > 4, je i d > 2 a n | (c/ • 2c/) | (n - 1)!. Pro n = 4 snadno dostáváme (4 - 1)! = 2 ^ -1 (mod 4). Nechť je nyní p prvočíslo. Čísla z množiny {2, 3,..., p — 2} seskupíme do dvojic vzájemně inverzních čísel modulo p, resp. dvojic čísel, jejichž součin dává zbytek 1 po dělení p. Pro dané číslo a z této množiny existuje podle předchozí věty jediné řešení kongruence a ■ x = 1 (mod p). Protože a ^ 0,1, p — 1, je zřejmé, že rovněž pro řešení c této kongruence platí c ^ 0,1, —1 (mod p). Číslo a nemůže být ve dvojici samo se sebou; kdyby totiž a ■ a = 1 (mod p), pak nutně a = ±1 (mod p). Součin všech čísel uvedené množiny je tedy tvořen součinem (p — 3)/2 dvojic (jejichž součin je vždy kongruentnís 1 modulo p). Proto máme (p - 1)! = 1(P-3)/2 • (p - 1) = -1 (mod p). Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry oooooooo»oooooooooooooo ooooo ooooooooooooo ooo 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 m,-). Dostaneme tak soustavu kongruencí x = ci (mod mi) x = ci< (mod mk) 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í. Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry ooooooooo»ooooooooooooo ooooo ooooooooooooo ooo Věta Necht ci, C2 jsou celá čísla, m\, rri2 přirozená. Označme d = (mi, m2). Soustava dvou kongruencí x = ci (mod m\) x = C2 (mod ni2) v případě ci ^ C2 (mod c/) 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 [mi,/7i2]). Důkaz. Má-li soustava nějaké řešení xěZ, platí nutně x = c\ (mod d), x = C2 (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í. Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry oooooooooo»oooooooooooo ooooo ooooooooooooo ooo Dokončení důkazu. Předpokládejme dále c\ = c2 (mod d). První kongruenci řešené soustavy vyhovují všechna celá čísla x tvaru x = c\ + tmi, kde ŕ G Z je libovolné. Toto x bude vyhovovat i druhé kongruenci soustavy, právě když bude platit ci + tmi = Q (mod m2), tj. tmi = C2 — ci (mod m2). Podle věty o řešitelnosti lineárních kongruencí má tato kongruence (vzhledem k t) řešení, neboť d = (mi, dělí C2 — ci, a t G Z splňuje tuto kongruenci právě když c2 - Cl mi mod ÍT72 mi \^("^") _|_ rrmn c + r ■ [mi, m2], tj. právě když x = ci + tmi = ci + (c2 - ci) • kde r G Z je libovolné a c = q + (c2 - cx) • (mi/c/)^m2/c'), neboť /D1/D2 = í/ • [mi, m2]. Našli jsme tedy takové c G Z, že libovolné x G Z splňuje soustavu, právě když x = c (mod [mi, ^2]), což jsme chtěli dokázat. □ Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry ooooooooooo»ooooooooooo ooooo ooooooooooooo ooo Všimněme si, že důkaz této věty je konstruktivní, tj. udává vzorec, jak číslo c najít. Věta nám tedy dává metodu, jak pomocí jediné kongruence zachytit podmínku, že x vyhovuje této soustavě . Podstatné je, že tato nová kongruence je téhož tvaru jako obě původní. Můžeme proto tuto metodu aplikovat i na soustavu -nejprve z první a druhé kongruence vytvoříme kongruenci jedinou, které vyhovují právě ta x, která vyhovovala původním dvěma kongruencím, pak z nově vzniklé a z třetí kongruence vytvoříme další atd. Při každém kroku se nám počet kongruencí soustavy sníží o 1, po k — 1 krocích tedy dostaneme kongruenci jedinou, která nám bude popisovat všechna řešení dané soustavy. Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry oooooooooooo»oooooooooo ooooo ooooooooooooo ooo Čí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. Řešení Odpověď je (prý) ukryta v následující písni: í£-3^3£ SunziGe Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry ooooooooooooo#ooooooooo ooooo ooooooooooooo ooo Důsledek (Čínská zbytková věta) Nechi mi,,..., G N jsou po dvou nesoudělná, a\,. Pak platí: soustava . ,ak G Z x = a\ (mod m\) x = 3fr (mod mk) má jediné řešení modulo m\ • ni2 • • • m^. Důkaz. Jde o jednoduchý důsledek předchozího tvrzení, který lze ale rovněž elegantně dokázat přímo. □ Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry oooooooooooooo^oooooooo ooooo ooooooooooooo ooo 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. 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). Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry ooooooooooooooo»ooooooo ooooo ooooooooooooo ooo Čínskou zbytkovou větu můžeme použít také „v opačném směru". Řešte kongruenci 23 941x = 915 (mod 3564). Řešení Rozložme 3564 = 22 • 34 • 11. Protože ani 2, ani 3, ani 11 nedělí číslo 23 941, platí (23 941,3564) = 1 a má tedy kongruence řešení Protože (^(3564) = 2 • (33 • 2) • 10 = 1080, je řešení tvaru x = 915 • 23 9411079 (mod 3564). Úprava čísla stojícího na pravé straně by však vyžádala značné úsilí. Proto budeme kongruenci řešit poněkud jinak. Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry oooooooooooooooo»oooooo ooooo ooooooooooooo ooo Řešení Víme, že x G Z řešením dané kongruence, právě když je řešením soustavy 23941x = 915 (mod 22) 23941x = 915 (mod 34) 23941x = 915 (mod 11). Vyřešíme-li postupně každou z kongruencí soustavy, 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. Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry OOOOOOOOOOOOOOOOO0OOOOO ooooo ooooooooooooo ooo rní reprezentao 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 paralelizaci výpočtů s velkými čísly. Takový systém je určen /c-ticí modulů (obvykle po dvou nesoudělných) a každé číslo menší než jejich součin je pak jednoznačně reprezentováno /c-ticí zbytků (jejichž hodnoty nepřevyšují příslušné moduly) - viz např. http://goo.gl/oM25m. Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry oooooooooooooooooosoooo ooooo ooooooooooooo ooo 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. Literatura Řešení kongruencí a jejich soustav Polynomiální kongruence Kvadratické kongruence Šifry OOOOOOOOOOOOOOOOOOO0OOO ooooo 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, podobně jako výše, substituci x = 3 • xi, 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 oooooooooooooooooooo»oo ooooo 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 ooooooooooooooooooooo»o ooooo 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, (a, m) = 1. Pak kongruence xn = a (mod m) je řešitelná (tj. a je n-tý mocninný zbytek modulo m), právě když a 1, můžeme nahradit tuto kongruencí soustavou kongruencí která má stejnou množinu řešení, a řešit každou kongruencí 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, jak ukážeme, možné 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 ooooooooooooooooooooooo o#ooo ooooooooooooo ooo Příklad Řešte kongruencí x5 + 1 = 0 (mod 11). Příklad Řešte kongruencí 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 ooooooooooooooooooooooo oo»oo 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 ooooooooooooooooooooooo ooo»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 ooooooooooooooooooooooo oooo» 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á ní kongruence Kvadratické kongruence Šifry ooooooooooooooooooooooo ooooo •oooooooooooo ooo Kvadt 'atické kongruence 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 = 0 (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 ooooooooooooooooooooooo ooooo 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,