Lineární kongruence Soustavy lineárních kongruencí o jedné ne známé Binomické kongruence Diskrétní lo garitmus ooooooo ooooooooooo ooo 0 Diskrétní matematika - 4. týden Elementární teorie čísel - Řešení kongruencí Jan Slovák Masarykova univerzita Fakulta informatiky jaro 2015 Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo ooooooooooo ooo O Obsah před nášky Q Lineární kongruence Q Soustavy lineárních kongruencí o jedné neznámé Q Binomické kongruence Q Diskrétní logaritmus Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo ooooooooooo ooo o Doporučené zdroje • Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni.cz/Matematika_drsne_svizne. Lineární kongruence Soustavy lineárních kongruencí o jedné neznal né Binomické kongruence Diskrétní lo garitmus ooooooo ooooooooooo ooo O Doporuče mé zdroje • Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni.cz/Matematika_drsne_svizne. • Michal Bulant, výukový text k přednášce Elementární teorie čísel, http://is.muni.cz/el/1431/podzim2012/M6520/ um/main-print.pdf • Jiří Herman, Radan Kučera, Jaromír Šimša, Metody řešení matematických úloh. MU Brno, 2001. • William Stein, Elementary Number Theory: Primes, Congruences, and Secrets, Springer, 2008. Dostupné na http://wstein.org/ent/ent.pdf • Radan Kučera, výukový text k přednášce Algoritmy teorie čísel, http://www.math.muni.cz/~kucera/texty/ATC10.pdf Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo ooooooooooo ooo o Plán přednášky Q Lineární kongruence Qi Soustavy lineárních kongruencí o jedné neznámé Qi Binomické kongruence O Diskrétní logaritmus Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus •oooooo ooooooooooo ooo o Kongruence o jedné neznámé Definice 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í. Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus •oooooo ooooooooooo ooo o 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] ■0 0.0 Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus 0*00000 ooooooooooo ooo o Hledání řešení výčtem všech možností Věta Necht m G N, f (x) G Z [x]. Pro libovolná a, b G Z platí a = b (mod m) =>■ f (a) = f (b) (mod m). Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus o»ooooo ooooooooooo ooo o m 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,..., cn G Z. Protože a = b (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 cq = cq (mod m) dostaneme (mod m). cnan H-----h cia + c0 tj. f(a) = f (b) (mod m). = cnbn + • • • + c\b + cq (mod m), □ Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus 00*0000 ooooooooooo ooo o Počet řešení kongr Důsledek Množina řešení libovolné kongruence modulo m je sjednocením některých zbytkových tříd modulo m. Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus 00*0000 ooooooooooo ooo o Počet ř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. Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus 00*0000 ooooooooooo ooo o Počet ř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í. Lineární kongruence Soustavy lineárních kongruencí o jedné ne známé Binomické kongruence Diskrétní lo garitmus ooo#ooo ooooooooooo ooo 0 ' 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). Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooo#ooo ooooooooooo ooo o ' 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. Lineární kongruence Soustavy lineárních kongruencí o jedné ne známé Binomické kongruence Diskrétní lo garitmus oooo^oo ooooooooooo ooo 0 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 (-jf^y 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. □ Lineární kongruence Soustavy lineárních kongruencí o jedné neznal né Binomické kongruence Diskrétní lo garitmus ooooo»o ooooooooooo ooo 0 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. Lineární kongruence Soustavy lineárních kongruencí o jedné ne známé Binomické kongruence Diskrétní lo garitmus ooooo»o ooooooooooo ooo 0 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) Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooo»o ooooooooooo ooo o 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. Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooo»o ooooooooooo ooo o 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. Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooo»o ooooooooooo ooo o 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í. Lineární kongruence Soustavy lineárních kongruencí o jedné nezná né Binomické kongruence Diskrétní lo garitmus ooooo»o ooooooooooo ooo 0 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) -8x = -6 (mod 47) Lineární kongruence Soustavy lineárních kongruencí o jedné nezná né Binomické kongruence Diskrétní lo garitmus ooooo»o ooooooooooo ooo 0 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) -8x = -6 (mod 47) 4x = 3 (mod 47) 4x = -44 (mod 47) Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooo»o ooooooooooo ooo o 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) -8x = -6 (mod 47) 4x = -44 (mod 47) x = 36 (mod 47) 1 -o^o Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus 000000» ooooooooooo ooo o 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. Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus 000000» ooooooooooo ooo o 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 (Wilsonova) Přirozené číslo n > 1 je prvočíslo, právě když (n-l)! = -l (mod /?) Vcelku přímočarý důkaz je v učebnici. Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo ooooooooooo ooo o ášky Qi Lineární kongruence Q Soustavy lineárních kongruencí o jedné neznámé Ql Binomické kongruence Q Diskrétní logaritmus Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus OOOOOOO »0000000000 ooo o 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 = o, (mod m,-). Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus OOOOOOO »0000000000 ooo o 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 nik) Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus OOOOOOO »0000000000 ooo o 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 nik) 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í. Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo o#ooooooooo ooo o 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 ÍT72) 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 [mi,/7i2]). Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo o#ooooooooo ooo o 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 iv2) 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 [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í. Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo oo»oooooooo ooo o 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). ■0 0.0 Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo oo»oooooooo ooo o 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 - ci /mixv^)-! / , m2\ ■0 0.0 Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo oo»oooooooo ooo o 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, m2) dělí C2 — ci, a t G Z splňuje tuto kongruenci právě když c2 - Cl mi d mod ÍT72 mi \^("^") _|_ rrmn c + r ■ [mi, m2], d V d J V c/ tj. právě když x = ci + tmi = ci + (c2 - ci) • kde r G Z je libovolné a c = q + (c2 - ci) • (mi/c/)^m2/c'), neboť /D1/D2 = í/ • [mi, "72]. 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. □ Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo ooo»ooooooo ooo o 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. Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo oooo^oooooo ooo o ■ 1! ková 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: Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo oooo»oooooo ooo o Čí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 — -S-^JS-^Ě] Jíš: Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo ooooo»ooooo ooo o Důsledek (Čínská zbytková věta) Nechi mi,,..., £ N jsou po dvou nesoudělná, a\,. Pak platí: soustava . ,ak G Z x = a\ (mod m{) x = ak (mod m^) má jediné řešení modulo m\ • m2 • • • m^. Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo ooooo»ooooo ooo o Důsledek (Čínská zbytková věta) Nechi mi,,..., £ N jsou po dvou nesoudělná, a\,. Pak platí: soustava . ,ak G Z x = a\ (mod m{) x = ak (mod m^) má jediné řešení modulo m\ • m2 • • • m^. Důkaz. Jde o jednoduchý důsledek předchozího tvrzení, který lze ale rovněž elegantně dokázat přímo. □ Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus OOOOOOO 000000*0000 ooo o 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. Lineární kongruence Soustavy lineárních kongruencí o jedné nezná Tié Binomické kongruence Diskrétní lo garitmus ooooooo 000000*0000 ooo 0 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). Lineární kongruence Soustavy lineárních kongruencí o jedné nezná Tié Binomické kongruence Diskrétní lo garitmus ooooooo 000000*0000 ooo 0 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). Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo ooooooo»ooo ooo o Čínskou zbytkovou větu můžeme použít také „v opačném směru' Příklad Řešte kongruenci 23 941x = 915 (mod 3564). Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo ooooooo»ooo ooo o Čí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. Lineární kongruence Soustavy lineárních kongruencí o jedné ne známé Binomické kongruence Diskrétní lo garitmus ooooooo oooooooo«oo ooo 0 Řešení Víme, že x £ 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). ■0 0.0 Lineární kongruence Soustavy lineárních kongruencí o jedné ne známé Binomické kongruence Diskrétní lo garitmus ooooooo oooooooo«oo ooo 0 Ř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), ■0 0.0 Lineární kongruence Soustavy lineárních kongruencí o jedné ne známé Binomické kongruence Diskrétní lo garitmus ooooooo oooooooo«oo ooo 0 Ř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. ■0 0.0 Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo ooooooooo»o ooo o reprezentace číše 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. Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus OOOOOOO 0000000000» ooo o 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]. Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus OOOOOOO 0000000000» ooo o 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. Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo ooooooooooo ooo o ášky Qi Lineární kongruence Ql Soustavy lineárních kongruencí o jedné neznámé Q Binomické kongruence Q Diskrétní logaritmus Lineární kongruence Soustavy lineárních kongruencí o jedné ne známé Binomické kongruence Diskrétní logaritmus ooooooo ooooooooooo •OO O 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á. Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo ooooooooooo »oo o 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). 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. ■0 0.0 Lineární kongruence Soustavy lineárních kongruencí o jedné nezná né Binomické kongruence Diskrétní logaritmus ooooooo ooooooooooo o»o O Mocninné zbytky Definice Nechť m 6 N, a £ 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. Lineární kongruence Soustavy lineárních kongruencí o jedné nezná né Binomické kongruence Diskrétní logaritmus ooooooo ooooooooooo o»o O Mocninné 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). Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo ooooooooooo oo» o Řešení binomických kongruencí Věta Bud m £ N takové, že modulo m existují primitivní kořeny. Dále necht 3 6Z, (a, m) = 1. Pak kongruence x" = a (mod m) je řešitelná (tj. a je n-tý mocninný zbytek modulo m), právě když a xa se nazývá diskrétní logaritmus, příp. index čísla x (vzhledem k danému m a zafixovanému primitivnímu kořeni g) a je bijekcí mezi množinami {a G Z; (a, m) = 1, 0 < a < m} a {x G Z; 0 < x < ip(m)}. Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo ooooooooooo ooo • Definice Nechť m G N. Celé číslo g G Z, (g, m) = 1 nazveme primitivním kořenem modulo m, pokud je jeho řád modulo m roven (f(m). Je-li g primitivní kořen modulo m, pak pro každé číslo a G Z, (a, m) = 1 existuje jediné xa G Z, 0 < xa < (p(m) s vlastností gXa = a (mod m). Funkce a i-> xa se nazývá diskrétní logaritmus, příp. index čísla x (vzhledem k danému m a zafixovanému primitivnímu kořeni g) a je bijekcí mezi množinami {a G Z; (a, m) = 1, 0 < a < m} a {x G Z; 0 < x < ip(m)}. Důkaz. Předpokládejme, že pro x,y G Z, 0 < x,y <