Literatura Primitivní kořeny Pár slov o šifrách Řešení kongruei ící a jejich si austav oooooooooooooooooooooo oooo oooooooo Diskrétní matematika B - 3. týden Elementární teorie čísel - Primitivní kořeny Michal Bulant Masarykova univerzita Fakulta informatiky jaro 2013 Primitivní kořeny Pár slov o šifrách Řešení kongruencí a jejich soustav oooooooooooooooooooooo oooo oooooooo Obsah přednášky Primitivní kořeny • Malá Fermatova věta, Eulerova věta • Primitivní kořeny Pár slov o šifrách Řešení kongruencí a jejich soustav • Lineární kongruence • Lineární kongruence o jedné neznámé Literatura Primitivní kořeny Pár slov o šifrách Řešení kongruencí a jejich soustav oooooooooooooooooooooo oooo oooooooo zd roje • 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 Řešení kongruencí a jejich soustav oooooooo atova věta Literatura Primitivní kořeny Par slov o šifrách •ooooooooooooooooooooo oooo Tato tvrzení patří mezi nejduležitější výsledky elementární teorie čísel. Věta (Fermatova, Malá Fermatova) Necht a G Z, p prvočíslo, p\ a. Pak a"-1 = 1 (mod p). Důkaz. Tvrzení vyplyne jako snadný důsledek Eulerovy věty. Dá se ale dokázat i přímo (např. matematickou indukcí nebo kombinatoricky) □ Důsledek Necht a G Z, p prvočíslo. Pak ap = a (mod p). Literatura Primitivní kořeny Pár slov o šifrách o»oooooooooooooooooooo oooo Řešení kongruencí a jejich soustav oooooooo Upíná a redukovaná soustava zbytků Definice Úplná soustava zbytků modulo m je libovolná m-tice čísel po dvou nekongruentních modulo m (nejčastěji 0,1,..., m — 1). Redukovaná soustava zbytků modulo m je libovolná tp(m)-ť\ce čísel nesoudělných srna po dvou nekongruentních modulo m. Lemma Necht xi, X2,..., x^m) tvoří redukovanou soustavu zbytků modulo m. Je-li a (z Z, (a, m) = 1 pak i čísla a ■ xi,..., a • x^mj tvoří redukovanou soustavu zbytků modulo m. Protože (a, m) = 1 a (x,-, m) = 1, platí (a • x,-, m) = 1. Kdyby pro nějaká /',_/' platilo a • xf- = a • x,- (mod m), po vydělení obou stran kongruence číslem a nesoudělným s m dostaneme xf- = x,-(mod m). □ Literatura Primitivní kořeny Pár slov o šifrách Řešení kongru äncí a jejich s a u sta oo»ooooooooooooooooooo oooo oooooooo Věta (Eulerova) Necht a G Z, m G N, (a, m) = 1. Pak 3^(m) = 1 (mod m). Důkaz. Bud xi)x2> • • •)xip(m) libovolná redukovaná soustava zbytků modulo m. Podle předchozího lemmatu je i a • xi,..., a ■ x^m^ redukovaná soustava zbytků modulo m. Platí tedy, že pro každé / existuje j ( /,_/' G {1,2,..., tp(m)}) tak, že a ■ x; = xj (mod m). Vynásobením dostáváme (a-xi) • (a-x2) • • • {a-x^m)) =x1-x2- ■ -x^ (mod m). Po úpravě a^™) • xi • x2 • • • x(p(m) = xi • x2 • • • x(p(m) (mod m) vydělení číslem xi • X2 • • -x^^) dostaneme požadované. □ Literatura Primitivní kořeny Pár slov o šifrách ooo»oooooooooooooooooo oooo Řešení kongruencí a jejich soustav oooooooo Poznámka Eulerova věta je rovněž důsledkem Lagrangeovy věty uplatněným na grupu (Z*, •). S Lagrangeovou větou se seznámíme o něco později, v části věnované algebře. S Eulerovou funkcí a Eulerovou větou úzce souvisí důležitý pojem řád čísla modulo m: Definice Nechť 3 6Z, m £ N (a, m) = 1. Řádem čísla a modulo m rozumíme nejmenší přirozené číslo n splňující a" = 1 (mod m). Literatura Primitivní kořeny Pár slov o šifrách oooo#ooooooooooooooooo oooo Řešení kongruencí a jejich soustav oooooooo Poznámka To, že je řád definován, plyne z Eulerovy věty - pro každé číslo nesoudělné s modulem je totiž jistě jeho řád nejvýše roven tp(m). Jak později uvidíme, velmi důležitá jsou právě ta čísla, jejichž řád je roven právě tp(m) - tato čísla nazýváme primitivními kořeny modulo m a hrají důležitou roli mj. při řešení binomických kongruencí. Tento pojem je přitom jen jiným názvem pro generátor grupy (Z*, •) (opět viz algebraická část). Příklad Pro libovolné m £ N má číslo 1 modulo m řád 1. Číslo —1 má řád • 1 pro m = 1 nebo m = 2 « 2 pro m > 2 > Literatura Primitivní kořeny Pár slov o šifrách ooooo^oooooooooooooooo oooo Řešení kongruencí a jejich soustav oooooooo Příklad Určete řád čísla 2 modulo 7. Řešení 21 = 2 £ 1 (mod 7) 22 = 4 £ 1 (mod 7) 23 = 8 = 1 (mod 7) Řád čísla 2 modulo 7 je tedy roven 3. □ Literatura Primitivní kořeny Pár slov o šifrách oooooo»ooooooooooooooo oooo Řešení kongruencí a jejich soustav oooooooo Uveďme nyní několik zásadních tvrzení udávajících vlastnosti řádu čísla modulo m: Lemma Nechi m 6 N, a, b £ Z, (a, m) = (b, m) = 1. Jestliže a = b (mod m), pak obě čísla a, b mají stejný řád modulo m. Důkaz. Umocněním kongruence a = b (mod m) na n-tou dostaneme a" = bn (mod m), tedy a" = 1 (mod m) -t=^ bn = 1 (mod m). □ Literatura Primitivní kořeny Pár slov o šifrách ooooooo^oooooooooooooo oooo Řešení kongruencí a jejich soustav oooooooo 1 Lemma_ Necht m G N, a G Z, (a, m) = 1. Je-li řád čísla a modulo m roven r ■ s, (kde r, s G N), pak řád čísla ar modulo m je roven s. Důkaz. Protože žádné z čísel a, a2, a3,... ,ars 1 není kongruentní s 1 modulo m, není ani žádné z čísel ar, a2r, a3r,..., a^-1^ kongruentní s 1. Platí ale (ar)s = 1 (mod m), proto je řád ar modulo m roven s. □ Literatura Primitivní kořeny Pár slov o šifrách oooooooo»ooooooooooooo oooo Řešení kongruencí a jejich soustav oooooooo Poznámka Opak obecně neplatí - z toho, že řád čísla ar modulo m je roven s ještě neplyne, že řád čísla a modulo m je r ■ s. Např pro m = 13 máme: a = 3, a2 = 9 (mod 13), a3 = 27 = 1 (mod 13) => 3 má řád 3 mod 13. b = -4, b2 = 16 £ 1 (mod 13), b3 = -64 = 1 (mod 13) =*> -4 má řád 3 mod 13. Přitom (—4)2 = 16 = 3 (mod 13) má stejný řád 3 jako číslo 3, ale číslo —4 nemá řád 2 • 3. Literatura Primitivní kořeny Pár slov o šifrách ooooooooosoooooooooooo oooo Řešení kongruencí a jejich soustav oooooooo Přesný popis závislosti řádu na exponentu dávají následující 2 věty: Věta Nechi m 6 N, a £ Z, (a, m) = 1. Označme r řád čísla a modulo m. Pak pro libovolná t, s £ N U {0} platí ař = as (mod m) t = s (mod r). Literatura Primitivní kořeny Pár slov o šifrách oooooooooo»ooooooooooo oooo Řešení kongruencí a jejich soustav oooooooo Bez újmy na obecnosti lze předpokládat, že t > s. Vydělíme-li číslo t — s číslem r se zbytkem, dostaneme t — s = q ■ r + z, kde q, z G N0,0 < z < r. "<í=" Protože t = s (mod r), máme z = 0, a tedy ař~s = aqr = (ar)q = lq (mod m). Vynásobením obou stran kongruence číslem as dostaneme tvrzení. "=^" Z ař = as (mod m) plyne as • aqr+z = as (mod m). Protože je aľ = 1 (mod m), je rovněž aqr+z = az (mod m). Celkem po vydělení obou stran kongruence číslem as (které je nesoudělné s modulem), dostáváme az = 1 (mod m). Protože z < r, plyne z definice řádu, že z = 0, a tedy r \ t — s. □ Literatura Primitivní kořeny Pár slov o šifrách ooooooooooo«oooooooooo oooo Řešení kongruencí a jejich soustav oooooooo Zřejmým důsledkem předchozí věty a Eulerovy věty je následující tvrzení (jehož druhá část je přeformulováním Lagrangeovy věty z Algebry pro naši situaci): Důsledek Necht m é n, a é 1 , (a, m) = 1. Označme r řád čísla a modulo m. Q Pro libovolné n g n u {0} platí a" = 1 (mod m) <í=^> r n. O r | (f{m) Literatura Primitivní kořeny Pár slov o šifrách oooooooooooo»ooooooooo oooo Řešení kongruencí a jejich soustav oooooooo Následující věta je zobecněním předchozího Lemmatu. ' Věta Necht m, n G N, a G Z, (a, m) = 1. Je-li řád čísla a modulo m roven r G N, je řád čísla a" modulo m roven t-^t. Důkaz. Protože -fjr^ = [r, n], což je zřejmě násobek r, máme (a")(^) = aM = 1 (mod m) (plyne z předchozího Důsledku, neboť r | [r, n]). Na druhou stranu, je-li k G N libovolné takové, že (an)k = ank = 1 (mod m), dostáváme (r ie řád a), že r I n • k a dále víme, že t-^ I 7-^ • k a v J J< \ < (n,r j 1 (n,r j díky nesoudělnosti čísel 7-^ a 7-^ dostáváme I /c. Proto ie 7 ("lO (":'') \nir) řádem čísla a" modulo m. □ Literatura Primitivní kořeny Pár slov o šifrách ooooooooooooo»oooooooo oooo Řešení kongruencí a jejich soustav oooooooo Poslední z této řady tvrzení dává do souvislosti řády dvou čísel a řád jejich součinu: ■1 Lemma Nechť m G N, a, b G 2 ', (a, m) = (b, m) = 1. Jestliže a je řádu r a b je řádu s modulo m, kde (r, s) = 1, pak číslo a • b je řádu r • s modulo m. Důkaz. Označme ô řád čísla a • b. Pak {aby = 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 | rô. Z nesoudělnosti ras plyne s | ô. Analogicky dostaneme i r | ô, a tedy (opět s využitím nesoudělnosti r,s) r • s \ ô. Obráceně zřejmě platí (ab)rs = 1 (mod m), proto ô | rs. Celkem tedy S = rs._□ Primitivní kořeny Pár slov o šifrách Řešení kongruencí a jejich soustav oooooooooooooo»ooooooo oooo oooooooo Primitivní kořeny 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). Lemma 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ýva diskrétní logaritmus, př/p. /ne/ex čí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 < 1. Primitivní kořeny modulo m existují právě tehdy, když m splňuje některou z následujících podmínek: » m = 2 nebo m = 4, • m je mocnina lichého prvočísla » m je dvojnásobek mocniny lichého prvočísla. Dokážeme pouze část tohoto tvrzení, se kterou ve většině případů vystačíme: Tvrzení Nechi p je liché prvočíslo. Pak existují primitivní kořeny modulo p. Literatura Primitivní kořeny Pár slov o šifrách oooooooooooooooo»ooooo oooo Řešení kongruencí a jejich soustav oooooooo Důkaz. Označme ri, r2,..., rp_i řády čísel 1, 2,..., p — 1 modulo p. Bud' ô = [i, ť2,..., rp-i] nejmenší společný násobek těchto řádů. Ukážeme, že mezi čisly 1, 2,..., p — 1 existuje číslo řádu ô a že S = p-1. Nechť ô = q^1 • • • q^k je rozklad ô na prvočísla. Pro libovolné s G {1,... k} existuje c G {1,..., p — 1} tak, že qfs | rc (jinak by existoval menší společný násobek čísel ri, r2,..., rp_i než je á), tj. ex. í? G Z tak, že rc = b ■ qfs. Protože c má řád rc, má číslo gs := cb podle tvrzení o řádech mocnin řád roven qfs. Provedením předchozí úvahy pro libovolné s G {1,... k} dostaneme gi,..., g> a můžeme položit g := gi • • • g^. Z vlastností řádu součinu dostáváme, že řád g je roven součinu řádů čísel g!,...,gk, tj. číslu q^---qakk =5. Literatura Primitivní kořeny Pár slov o šifrách ooooooooooooooooo»oooo oooo Řešení kongruencí a jejich soustav oooooooo Dokončení. Nyní dokážeme, že S = p — 1. Protože řády čísel 1, 2,..., p — 1 dělí ô, dostáváme pro libovolné x G {1, 2,..., p — 1} vztah xs = 1 (mod p). Kongruence stupně ô modulo prvočíslo p má nejvýše ô řešení (jde vlastně o hledání kořenů polynomů nad tělesem, kterých, jak uvidíme v algebraické části, je nejvýše tolik, kolik je stupeň polynomu). Podle předchozího má však kongruence p — 1 řešení, proto nutně ô > p — 1. Přitom ô | p — 1 (jakožto řád čísla g), proto zejména ô < p — 1, a celkem ô = p — 1. □ Primitivní kořeny Pár slov o šifrách Řešení kongruencí a jejich soustav oooooooooooooooooo»ooo oooo oooooooo Hledání primitivních kořenů Obecně je pro daný modul nalezení primitivního kořene velmi výpočetně náročná operace. Následující věta nám udává ekvivalentní podmínku pro to, aby zkoumané číslo bylo primitivním kořenem, jejíž ověření je o něco snazší než přímý výpočet řádu tohoto čísla. Věta Bud m takové, že modulo m existují primitivní kořeny. Zapišme (p(m) = q^1 ■ ■ ■ q^k. Pak pro libovolné g £ Z, (g, m) = 1 platí, že g je primitivní kořen modulo m, právě když g qi ^1 (mod m),... ,g qk ^1 (mod m). Literatura Primitivní kořeny Pár slov o šifrách ooooooooooooooooooo»oo oooo Řešení kongruencí a jejich soustav oooooooo Důkaz. Pokud by platila některá z uvedených kongruencí, znamenalo by to, že řád g je menší než tp(m). Obráceně, pokud g není primitivní kořen, pak existuje d G N, d I ip(m), kde d < ip(m) a gd = 1 (mod m). Je-li u = '£^- > 1, nutně existuje / G {1,..., k} tak, že q-, \ u. Pak ale g q; = g q-, = i (mod m). _□ Literatura Primitivní kořeny Pár slov o šifrách oooooooooooooooooooo^o oooo Řešení kongruencí a jejich soustav oooooooo Příklad Určíme primitivní kořeny modulo 41. Řešení Protože ■ f (a) = f (b) (mod m). Důkaz. Nechť je f (x) = cnxn + cn_ix"_1 + • • • + c\x + cq, kde Co, ci,..., cn G Z. Protože a = Ď (mod m), pro každé / = 1, 2,..., n platí c,-a' = c/b' (mod m), a tedy sečtením těchto kongruencí pro / = 1, 2,..., n a kongruence co = cq (mod m) dostaneme Cnan H-----h Ci3 + Cq tj. f(a) = f (b) (mod m). = cnĎ" + • • • + c\b + co (mod m), □ Řešení kongruencí a jejich soustav 00*00000 í kongruence Literatura Primitivní kořeny Par slov o šifrách oooooooooooooooooooooo oooo 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 Primitivní kořeny Pár slov o šifrách oooooooooooooooooooooo oooo Řešení kongruencí a jejich soustav ooo»oooo ' 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 Primitivní kořeny Pár slov o šifrách oooooooooooooooooooooo oooo Řešení kongruencí a jejich soustav oooo»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í 3i • 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 Primitivní kořeny Pár slov o šifrách oooooooooooooooooooooo oooo Řešení kongruencí a jejich soustav ooooo»oo 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) 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 n) Literatura Primitivní kořeny Pár slov o šifrách oooooooooooooooooooooo oooo Řešení kongruencí a jejich soustav 0000000» Důkaz. Dokážeme nejprve, že pro libovolné složené číslo n > 4 platí n\ (n - 1)!, tj. (n - 1)! = O (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 \ (d ■ 2d) \ (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).