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 2017
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 Lineární kongruence
Q Soustavy lineárních kongruencí o jedné neznámé Q Binomické kongruence Q Diskrétní logaritmus
□ s1
Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni.cz/Matematika_drsne
Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé
ooooooo ooooooooooo
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
Binomické kongruence ooo
Diskrétni logaritmus O
Lineární kongruence ooooooo
Soustavy lineárních kongruencí o jedné neznámé ooooooooooo
Binomické kongruence Diskrétní logaritmus
ooo
Plán přednášky
0 Lineární kongruence
i /
□ [51
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í.
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]
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 <E Z platí a = b   (mod m) => f (a) = f (b)   (mod m).
□    3 ► < -e *■ < =
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 <E Z platí a = b   (mod m) => 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),
□
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.
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.
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í.
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).
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.
Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus
OOOO0OO 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. □
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.
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)
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.
O 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.
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í.
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) <
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)
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)
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.
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.
Lineární kongruence ooooooo
Soustavy lineárních kongruencí o jedné neznámé ooooooooooo
Binomické kongruence ooo
Diskrétní logaritmus O
Plán prednášky
0 Soustavy lineárních kongruencí o jedné nezná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 = q (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 = q (mod m;). Dostaneme tak soustavu
kongruencí
x = ci (mod at?i) x = Ck (mod trik)
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 = ci (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í.
Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus
OOOOOOO 0*000000000 ooo o
Věta
Necht ci, C2 jsou celá čísla, mi, rr?2 přirozená. Označme d = (mi, m2). Soi/sra\/a dvou kongruencí
x = ci (mod at?i) x = C2 (mod at?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 £ Z vyhovuje soustavě, právě když vyhovuje kongruencí
x = c   (mod [at?i. at?2]).
Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus
OOOOOOO 0*000000000 ooo o
Věta
Necht ci, C2 jsou celá čísla, mi, rr?2 přirozená. Označme d = (mi, m2). Soi/sra\/a dvou kongruencí
x = ci (mod at?i) x = C2 (mod at?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 [at?i. at?2]).
Důkaz.
Má-li soustava nějaké řešení x £ Z, platí nutně x = c\ (mod cf), x = C2 (mod d), a tedy i c\ = C2 (mod c/). Odtud plyne, že v případě ci ^ C2 (mod c/) 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 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 rn2), tj. tmi = C2 — ci (mod at?2).
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ž
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 /712). 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ž
c2 - ci   /mi\^(^r)-i /    _. m2
—ď~ • (t)       (mod t
tj. právě když
ŕ =
x = ci + ŕmi = ci + (c2-ci).(^)^(^) + r^ = c + r'[mum2]1 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, m2]), což jsme chtěli dokázat. □
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 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 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.
Ř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 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.
Odpověď je (prý) ukryta v následující písni:
Lineární kongruence	Soustavy lineárních kongruenci o jedné neznámé	Binomické kongruence	Diskrétní logaritmus
ooooooo	ooooo«ooooo	ooo	O
Důsledek (Čínská zbytková věta)
Nechť mi,,..., rrik G N jsou po dvou nesoudělná, ai, Pak platí: soustava
x = a\ (mod m\)
x = a^ (mod m^)
má jediné řešení modulo m\ • rr?2 • • • 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)
Necht /7?i,,..., m/f e N jsou po dvou nesoudělná, ai,..., a^ £ Pak platí: soustava
x = a\ (mod m\)
x = a^ (mod m^) má jediné řešení modulo m\ • rr?2 • • • 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 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.
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
1 (mod 10) 5 (mod 18) 4 (mod 25).
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 Ř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)
>0 0,0
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
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 kongruenci 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 kongruenci řešit poněkud jinak.
Lineární kongruence	Soustavy lineárních kongruencí o jedné neznámé	Binomické kongruence	Diskrétní logaritmus
ooooooo	oooooooo«oo	ooo	o
■v
Řešení
Víme, žexeZ ř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).
Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus
ooooooo oooooooo«oo ooo o
Víme, že x e 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),
Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus
OOOOOOO OOOOOOOO0OO ooo o
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.
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.
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].
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.
Lineární kongruence ooooooo
Soustavy lineárních kongruencí o jedné neznámé ooooooooooo
Binomické kongruence ooo
Diskrétní logaritmus O
Plán prednášky
Q Binomické kongruence
Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus
OOOOOOO OOOOOOOOOOO «00 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 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á.
Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus
OOOOOOO OOOOOOOOOOO «00 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 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.
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.
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).
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
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<p(m)/d = 1 (mQcJ m^ kde d =
Přitom, je-li tato kongruence řešitelná, má právě d řešení.
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 oo« 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ž
ap(m)/d = 1 (mQcJ m^ kde d =
Přitom, je-li tato kongruence řešitelná, má právě d řešení Vcelku přímočarý důkaz je v učebnici.
Důsledek
Za předpokladů předchozí věty, je-li navíc (n, (fi(m)) = 1, má kongruence xn = a (mod m) vždy řešení, a to jediné. Jinými slovy, umocňování na n-tou (kde n je nesoudělné s <p(m)) je bijekce na množině Z* invertibilních zbytkových tříd modulo m.
Lineární kongruence ooooooo
Soustavy lineárních kongruencí o jedné neznámé ooooooooooo
Binomické kongruence ooo
Diskrétní logaritmus O
Plán prednášky
Q Diskrétní logaritmus
Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus
ooooooo ooooooooooo ooo •
Definice
Nechť m 6 N. Celé číslo geZ, (g", m) = 1 nazveme primitivním kořenem modulo m, pokud je jeho řád modulo m roven (p(m).
Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus
ooooooo ooooooooooo ooo •
Definice
Nechť m 6 N. Celé číslo geZ, (g", m) = 1 nazveme primitivním kořenem modulo m, pokud je jeho řád modulo m roven (p(m).
Lemma
Je-// g primitivní kořen modulo m, pak pro každé číslo a £ Z, (a, m) = 1 existuje jediné xa G Z, 0 < xa < (p(m) s vlastností gXa = a (mod m).
Lineární kongruence Soustavy lineárních kongruencí o jedné neznámé Binomické kongruence Diskrétní logaritmus
ooooooo ooooooooooo ooo •
Definice
Nechť m 6 N. Celé číslo geZ, (g", m) = 1 nazveme primitivním kořenem modulo m, pokud je jeho řád modulo m roven (p(m).
Lemma
Je-// g primitivní kořen modulo m, pak pro každé číslo a £ Z, (a, m) = 1 existuje jediné x3 G Z, 0 < xa < V9(rn) s vlastnostígXa = a (mod m). Funkce a    xa se nazývá diskrétní logaritmus, př/p. /Vie/ex č/s/a 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 < <p(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 geZ, (g", m) = 1 nazveme primitivním kořenem modulo m, pokud je jeho řád modulo m roven (p(m).
Lemma
Je-// g primitivní kořen modulo m, pak pro každé číslo a G Z, (a, m) = 1 existuje jediné x3 G Z, 0 < xa < V9(rn) s vlastnostígXa = a (mod m). Funkce a    xa se nazývá diskrétní logaritmus, př/p. /Vie/ex č/s/a 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 < <p(m)}.
Předpokládejme, že pro x,y G Z, 0 < x,y < v9(rn) Je S"x = S"y (mod m). Z vlastností řádu pak x = y (mod (p(m)), tj. x = y, proto je zobrazení injektivní, a tedy i surjektivní.