Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo ooooooooooo ooo o Diskrétní matematika - 4. týden Elementární teorie čísel - Řešení kongruencí Jan Slovák Masarykova univerzita Fakulta informatiky jaro 2015 Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo ooooooooooo ooo o Obsah přednášky Q Řád čísla Q Lineární kongruence O Soustavy lineárních kongruencí o jedné neznámé Q Binomické kongruence Q Diskrétní logaritmus Řád čísla 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. □ s Řád čísla 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. • 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. o William Stein, Elementary Number Theory: Primes, Congruences, and Secrets, Springer, 2008. Dostupné na http://wstein.org/ent/ent.pdf o 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 Řád čísla " I ' f I ' Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo ooooooooooo ooo o Následující věta je zobecněním předchozího Lemmatu Necht m, n 6 N, a e Z, (a, m) = 1. Je-li řád čísla a modulo m roven r 6 N, /e řác/ č/s/a an modulo m roven -r^- Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo ooooooooooo ooo o Následující věta je zobecněním předchozího Lemmatu Necht m, n G N, a G Z, (a, m) = 1. Je-li řád čísla a modulo m roven r G N, /e řác/ č/s/a an modulo m roven -r^- Důkaz Protože jy^j = [r, r?], což je zřejmě násobek r, máme (a")(^) = a^ = 1 (mod m) (plyne z předchozího Důsledku, neboť r | [r, r?]). Na druhou stranu, je-li k G N libovolné takové, že (an)^ = an/c = 1 (mod m), dostáváme (r je řád a), že r n • k a dále víme, že I • /c a V J 7' ' (n,r) I (n,r) díky nesoudělnosti čísel -r-^ a dostáváme -r-^ k. Proto je y {n,r) (n,r) (n,r) J řádem čísla an modulo m. □ >0 0,0 Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo ooooooooooo ooo o Poslední z této řady tvrzení dává do souvislosti řády dvou čísel a řád jejich součinu: Lemma Necht m 6 N, a, b e Z, (a, m) = (b, m) = 1. Jestliže a je řac/i/ r a b je řác/u s modulo m, kde (r, s) = 1, pa/c č/s/o a • b je řádu r • s modulo m. Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo ooooooooooo ooo o Poslední z této řady tvrzení dává do souvislosti řády dvou čísel a řád jejich součinu: Lemma Necht m 6 N, a, b e Z, (a, m) = (b, m) = 1. Jestliže a je řac/i/ r a b je řác/u s modulo m, kde (r, s) = 1, pa/c č/s/o a • b je řádu r • s modulo m. Důkaz. Označme S řád čísla a • b. Pak (ab)^ = 1 (mod m) a umocněním obou stran kongruence dostaneme arSbrS = 1 (mod m). Protože je r řádem čísla a, je ar = 1 (mod m), tj. brS = 1 (mod m), a proto s | rS. Z nesoudělnosti ras plyne s | 5. Analogicky dostaneme i r | ô, a tedy (opět s využitím nesoudělnosti r, s) r • s | S. Obráceně zřejmě platí (ab)rs = 1 (mod m), proto S | rs. Celkem tedy S = rs. □ Řád čísla 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 -3 m o Řád čísla 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 ŕ(x) = g(x) (mod m) nazýváme 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 £ Z, pro která f(c) = g(c) (mod m). Dvě kongruence o jedné neznámé nazveme ekvivalentní, mají-li stejnou množinu řešení. Řád čísla 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 ŕ(x) = g(x) (mod m) nazýváme 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 £ Z, pro která f(c) = g(c) (mod m). Dvě kongruence o jedné neznámé nazveme ekvivalentní, mají-li stejnou množinu řešení. Uvedená kongruence je ekvivalentní s kongruencí f(x) — g[x) = 0 (mod m). \__✓ €Z[x] Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus O0OOOOO ooooooooooo ooo o Hledání řešení výčtem všech možností Věta Necht m e N, f (x) G Z [x]. Pro libovolná a, b f (a) = f (b) (mod m). Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus O0OOOOO ooooooooooo ooo o Hledání řešení výčtem všech možností Věta Necht m e N, f (x) G Z [x]. Pro libovolná a, b f (a) = f (b) (mod m). Důkaz. Necht je f (x) = cnxn + cn_ixn_1 + • • • + c\x + co, kde co, ci,..., cn G Z. Protože a = b (mod m), pro každé / = 1, 2,..., n platí c,-a' = c\tí (mod m), a tedy sečtením těchto kongruencí pro / = 1, 2,..., n a kongruence co = co (mod rn) dostaneme cnan H-----h cia + c0 = tj. f(a) = ŕ(b) (mod m). cnbn + • • • + c\b + co (mod rn), □ Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus OO0OOOO 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. Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus OO0OOOO 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. Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus OO0OOOO 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 O Kongruence 2x = 3 (mod 3) má jedno řešení (modulo 3). Q Kongruence lOx = 15 (mod 15) má pět řešení (modulo 15). O Kongruence z příkladu (1) a (2) jsou ekvivalentní. Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus OOO0OOO ooooooooooo ooo o Nechť m 6 N, a, b e Z. Označme d = (a, m). Pa/c 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 čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus OOO0OOO ooooooooooo ooo o Necht m £ N, a, b £ 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. Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus oooo«oo ooooooooooo ooo o 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 ai, b\ £ Z a m\ £ N tak, že a = d - ai, b — d - b\ a m = d • m\. Řešená kongruence je tedy ekvivalentní s kongruencí a\ • x = b\ (mod mi), kde (ai, mi) = 1. Tuto kongruencí můžeme vynásobit číslem <9^(mi) 1 a díky Eulerově větě obdržíme x = b\ • a^™1^ 1 (mod mi). Tato kongruence má jediné řešení modulo m\ a tedy d — m/mi řešení modulo m. □ Řád čísla 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. Řád čísla 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) Řád čísla 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. Řád čísla 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. O Další možností je využít Bezoutovu větu. Řád čísla 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. O Další možností je využít Bezoutovu větu. O Obvykle nej rychlejším, ale nejhůře algoritmizovatelným způsobem řešení je metoda takových úprav kongruence, které zachovávají množinu řešení. Řád čísla 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. Řešte 39x = 41 (mod 47) O Nejprve využijeme Eulerovu větu, stejně jako v důkazu předchozí věty. O Další možností je využít Bezoutovu větu. O Obvykle nej rychlejší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) < Řád čísla 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. O Další možností je využít Bezoutovu větu. O Obvykle nej rychlejší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) Řád čísla 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. Řešte 39x = 41 (mod 47) O Nejprve využijeme Eulerovu větu, stejně jako v důkazu předchozí věty. O Další možností je využít Bezoutovu větu. O Obvykle nej rychlejší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) 4 > -8x = -6 (mod 47) < > 4x = -44 (mod 47) <= > x = 36 (mod 47) Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus oooooo* 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. Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus oooooo* ooooooooooo ooo o 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. Přirozené číslo n > 1 je prvočíslo, právě když (ii-l)! 1 (mod n) Vcelku přímočarý důkaz je v učebnici. Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo ooooooooooo ooo o Plán prednášky Q Soustavy lineárních kongruencí o jedné neznámé >0 Q,o Řád čísla 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 = q (mod m;). Řád čísla 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 = q (mod m;). Dostaneme tak soustavu kongruencí x = q (mod at?i) x = Ck (mod trik) Řád čísla 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 = q (mod m;). Dostaneme tak soustavu kongruencí x = q (mod at?i) x = Ck (mod trik) 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í. Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo O0OOOOOOOOO ooo O Věta Necht ci, C2 jsou celá čísla, mi, rr?2 přirozená. Označme d = (mi, m2). Soustava dvou kongruencí x = ci (mod at?i) x = C2 (mod at?2) v případě ci ^ C2 (mod c/) r?ema řešení Jestliže naopak c\ = C2 (mod c/), pa/c existuje celé číslo c tak, že x G Z vyhovuje soustavě, právě když vyhovuje kongruencí x = c (mod [at?i. at?2])- Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo O0OOOOOOOOO ooo O Věta Necht ci, C2 jsou celá čísla, mi, rr?2 přirozená. Označme d = (mi, m2). Soustava dvou kongruencí x = ci (mod at?i) x = C2 (mod at?2) v případě ci ^ C2 (mod c/) r?erna řešení Jestliže naopak c\ = C2 (mod c/), pa/c existuje celé číslo c tak, že x G Z vyhovuje soustavě, právě když vyhovuje kongruencí x = c (mod [at?i. at?2])- Důkaz. Má-li soustava nějaké řešení x £ Z, platí nutně x = ci (mod c/), x = C2 (mod d), a tedy i c\ = C2 (mod c/). Odtud plyne, že v případě ci ^ C2 (mod d) soustava nemůže mít řešení. Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus OOOOOOO OO0OOOOOOOO 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 c\ + tmi = C2 (mod 1712), tj. tmi = C2 — ci (mod at?2). Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus OOOOOOO OO0OOOOOOOO ooo o 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 c\ + tmi = C2 (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 = (/7?i, rn2) dělí C2 - q, a í G Z splňuje tuto kongruenci právě když Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus OOOOOOO OO0OOOOOOOO ooo o 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 c\ + tmi = C2 (mod 1712), tj. tmi = C2 — ci (mod /712). Podle věty o řešitelnosti lineárních kongruencí má tato kongruence (vzhledem k t) řešení, neboť d = (/7?i, 1712) dělí C2 - q, a í G Z splňuje tuto kongruenci právě když c2 - ci /mi\^(^r)-i / _. m2 —ď~ • (t) (mod t tj. právě když ŕ = x = c1 + ŕm1 = c1 + (c2-c1).(^)^(^) + r^ = c + r.K,m2], kde r e Z je libovolné a c = q + (c2 - ci) • {mi/d)^m2/d\ neboť mim2 — d • [/7?i, /712]. 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. □ Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus OOOOOOO OOO0OOOOOOO 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 kongruencí 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 kongruencí jedinou, která nám bude popisovat všechna řešení dané soustavy. Řád čísla Lineární kongruence Soustavy lineárních kongruenci o jedné neznámé Binomické kongruence Diskrétní logaritmus OOOOOOO OOOO0OOOOOO 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. Řád čísla 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) Nechť mi,,..., m/f e N jsou po dvou nesoudělná, ai,..., a^ e Pa/c p/at/; soustava x = ai (mod rni) x = a/f (mod m^) má jediné řešení modulo m\ • rr?2 • • • at?^. □ g = Řád čísla 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) Necht /7?i,,..., m/f e N jsou po dvou nesoudělná, ai,...,a^6Z. Pak platí: soustava x = a\ (mod m\) x = a^ (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. □ Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo oooooo«oooo 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. Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo oooooo«oooo 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. Řešte systém kongruencí x x x 5 1 (mod 10) (mod 18) (mod 25). Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo oooooo«oooo 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. Příklad ■v Reste systém kongruencí X 1 (mod 10) X 5 (mod 18) X -4 (mod 25). Řešení Výsledkem je x = 221 (mod 450) >0 0,0 Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus OOOOOOO OOOOOOO0OOO ooo o Čí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) 1 Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus OOOOOOO OOOOOOO0OOO ooo o Čí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) 1 Ř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 v?(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 kongruencí řešit poněkud jinak. Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo OOOOOOOO0OO ooo O Ř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). Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus OOOOOOO OOOOOOOO0OO ooo o Ř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). 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), Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo OOOOOOOO0OO ooo o ■v Ř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. Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus OOOOOOO OOOOOOOOO0O ooo o 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 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. Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo oooooooooo* 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]. Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo oooooooooo* 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. Řád čísla 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 Binomické kongruence Řád čísla 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šaího stupně, tzv. binomických kongruencí. Jde o analogii binomických rovnic, kdy polynomem f(x) je dvojčlen xn — 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á. Řád čísla 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šaího stupně, tzv. binomických kongruencí. Jde o analogii binomických rovnic, kdy polynomem f(x) je dvojčlen xn — 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 substituci x = 3 • xi, dostáváme která zřejmě nemá řešení, proto; x. Užijeme-li, podobně jako výše, kongruencí 27xf = 3 (mod 18), že (27,18)|3. Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo ooooooooooo o«o o Mocninné zbytky Definice Necht m £ N, a £ Z, (a, m) = 1. Číslo a nazveme n-tým mocninným zbytkem modulo m, pokud je kongruence xn = a (mod m) řešitelná. V opačném případě nazveme a n-tým mocninným nezbyt ke m modulo m. Pro n = 2,3,4 používáme termíny kvadratický, kubický a bikvadratický zbytek, resp. nezbytek modulo m. Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo ooooooooooo o«o o Mocninné zbytky Definice Necht m G N, a G Z, (a, m) = 1. Číslo a nazveme n-tým mocninným zbytkem modulo m, pokud je kongruence xn = a (mod m) řešitelná. V opačném případě nazveme a n-tým mocninným nezbyt ke m 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). Řád čísla Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus ooooooo ooooooooooo oom o Řešení binomických kongruencí Věta Buď m G N takové, že modulo m existují primitivní kořeny. Dále nechť a G Z, (a, m) — 1. Pa/c kongruence xn = a (mod m) je řešitelná (tj. a je n-tý mocninný zbytek modulo m), právě když a