Diskrétní matematika - cvičení 5. týden Lukáš Vokřínek Masarykova univerzita Fakulta informatiky jaro 2020 Pětice modulů 3; 5; 7; 11; 13 umožňuje jednoznačně reprezentovat čísla menší než jejich součin (tedy menší než 15015) a efektivně provádět (v případě potřeby distribuovane) běžné aritmetické operace. Určete reprezentaci čísel 1234 a 5678 v této modulární soustavě a pomocí této reprezentace vypočtěte jejich součet a součin. Pětice modulů 3; 5; 7; 11; 13 umožňuje jednoznačně reprezentovat čísla menší než jejich součin (tedy menší než 15015) a efektivně provádět (v případě potřeby distribuovane) běžné aritmetické operace. Určete reprezentaci čísel 1234 a 5678 v této modulární soustavě a pomocí této reprezentace vypočtěte jejich součet a součin. 1234 1234 1234 1234 1 (mod3) 4 (mod5) 2 (mod7) 2 (modli) 5678 5678 5678 5678 2 (mod3) 3 (mod 5) 1 (mod 7) 2 (mod 11) 1234 12 (mod 13) 5678 10 (mod 13) Řešení 1234 = 1 (mod3) 1234 = 4 (mod5) 1234 = 2 (mod7) 1234 = 2 (mod 11) 1234 = 12 (mod 13) 5678 = 2 (mod 3) 5678 = 3 (mod 5) 5678 = 1 (mod 7) 5678 = 2 (mod 11) 5678 = 10 (mod 13) 4 □ ► 4 |S 1234 = 1 (mod3) 5678 = 2 (mod 3) 1234 = 4 (mod5) 5678 = 3 (mod 5) 1234 = 2 (modľ) 5678 = 1 (mod 7) 1234 = 2 (modli) 5678 = 2 (modli) 1234 = 12 (mod 13) 5678 = 10 (mod 13) Reprezentujeme tedy číslo 1234 pomocí pětice zbytků (1,4, 2, 2,12) a číslo 5678 pomocí pětice zbytků (2, 3,1, 2,10). Součet a součin jsou pak reprezentovány 1234 + 5678 - (3,7, 3,4, 22) = (0, 2, 3,4,9) 1234 • 5678 - (2,12, 2, 4,120) = (2, 2, 2,4, 3) Řešení 1234 + 5678 - (0,2,3,4,9) Převeďme nyní tyto reprezentace zpět na čísla, řešme tedy v prvním případě soustavu kongruencí x x x x x 0 (mod3) 2 (mod5) 3 (mod7) 4 (modli) 9 (mod 13) Řešení 1234 + 5678 - (0,2,3,4,9) Převeďme nyní tyto reprezentace zpět na čísla, řešme tedy v prvním případě soustavu kongruencí x x x x x 0 (mod3) 2 (mod5) 3 (mod7) 4 (modli) 9 (mod 13) Z první kongruence máme x = 3ŕ, dosazením do druhé dostaneme kongruenci 3r = 2 (mod 5), tedy t = 4 (mod 5), tj. t = 5s + 4 a x = 15s + 12. Řešení 1234 + 5678 - (0,2,3,4,9) Převeďme nyní tyto reprezentace zpět na čísla, řešme tedy v prvním případě soustavu kongruencí x x x x x 0 (mod3) 2 (mod5) 3 (mod7) 4 (modli) 9 (mod 13) Z první kongruence máme x = 3ŕ, dosazením do druhé dostaneme kongruenci 3r = 2 (mod 5), tedy t = 4 (mod 5), tj. t = 5s + 4 a x = 15s + 12. Dosadíme do třetí kongruence: 15s = —9 (mod 7), tedy s = 5 (mod 7), tj. s = 7r + 5 x = 105r + 87. x = O (mod 3) x = 2 (mod 5) x = 3 (mod 7) x = 4 (mod 11) x = 9 (mod 13) Dosadíme x = 105r + 87 do čtvrté kongruence a dostaneme 105r = -83 (mod 11), tedy 6r = 5 (mod 11) r = 10 (mod 11), tj. r = Uq + 10 a x = 1155*7 + 1137. ■v Řešení x = O (mod 3) x = 2 (mod 5) x = 3 (mod 7) x = 4 (mod 11) x = 9 (mod 13) Dosadíme x = 105r + 87 do čtvrté kongruence a dostaneme 105r = -83 (mod 11), tedy 6r = 5 (mod 11) r = 10 (mod 11), tj. r = lig + 10 a x = 1155q + 1137. Dosadíme do poslední kongruence a dostaneme 1155q = —1128 (mod 13), tedy lig = 3 (mod 13): 13(7 = 0 lig = 3 2g = 10 lq = 5 (modl3) 0q = 0 Máme tak q = 13p + 5 a dosazením x = 15015p + 6912, tj. x = 6912 (mod 15015). Řešení 13q = 0 lig = 3 2g = 10 lq = 5 (mod 13) 0g = 0 Máme tak q = 13p + 5 a dosazením x = 15015p + 6912, tj. x = 6912 (mod 15015). Protože je součet menší než 15015, musí nutně být roven 6912. Podobně v případě součinu 1234 • 5678 - (2, 2, 2, 4, 3): x = 2 (mod3) x = 2 (mod5) x = 2 (mod7) x = 4 (mod 11) x = 3 (mod 13) dostáváme z prvních tří kongruencí x = 105r + 2 (protože je pravá strana stejná), dosadíme do čtvrté: 105r = 6r = 2 (mod 11), tedy r = 4 (mod 11), tj. r = lig + 4 a x = 1155c? + 422. Podobně v případě součinu 1234 • 5678 - (2, 2, 2, 4, 3): x = 2 (mod3) x = 2 (mod5) x = 2 (mod7) x = 4 (mod 11) x = 3 (mod 13) dostáváme z prvních tří kongruencí x = 105r + 2 (protože je pravá strana stejná), dosadíme do čtvrté: 105r = 6r = 2 (mod 11), tedy r = 4 (mod 11), tj. r = lig + 4 a x = 1155q + 422. Dosadíme do poslední kongruence a dostaneme 1155q = —419 (mod 13), tedy Uq= 10 (mod 13): 13(7 = 0 lig = 10 2q = 3 lq = 8 (modl3) 0q = 0 Máme tak q = 13p + 8 a dosazením x = 15015p + 9662, tj. x = 9662 (mod 15015). 13q = O Uq = 10 2q = 3 lq = 8 (mod 13) Og = 0 Máme tak q = 13p + 8 a dosazením x = 15015p + 9662, tj. x = 9662 (mod 15015). Kdyby byl součin menší než 15015, musel by nutně být roven 9662; ve skutečnosti ale došlo k "přetečen f. Príklad Ukažte, že jsou čísla 2n — 1; 2n; 2n + 1 po dvou nesoudělná a určete, kolik bitů mohou mít jimi určená čísla. Spočtěte reprezentaci čísla 118 v této soustavě s n = 3. Zapřemýšlejte o efeketivní realizaci této modulární aritmetiky. Ukažte, že jsou čísla 2n — 1; 2n; 2n + 1 po dvou nesoudělná a určete, kolik bitů mohou mít jimi určená čísla. Spočtěte reprezentaci čísla 118 v této soustavě s n = 3. Zapřemýšlejte o efeketivní realizaci této modulární aritmetiky. ■v Řešení Ukážeme nesoudělnost 2n — 1 a 2n + 1, nesoudělnost dvou po sobě jdoucích čísel je ještě snazší. Počítejme: (2" - 1, 2n + 1) = (2" -1,2) = (-1, 2) = (1, 2) = 1 (od 2n + 1 lze odečíst 2n — 1 a zbude 2, v dalším kroku lze od 2n — 1 odečíst 2n, protože se jedná o násobek 2). Ukažte, že jsou čísla 2n — 1; 2n; 2n + 1 po dvou nesoudělná a určete, kolik bitů mohou mít jimi určená čísla. Spočtěte reprezentaci čísla 118 v této soustavě s n = 3. Zapřemýšlejte o efeketivní realizaci této modulární aritmetiky. ■v Řešení Podle CRT pak trojice zbytků jednoznačně reprezentuje čísla modulo [2n - 1, 2", 2n + 1] = (2" - 1) • 2n • (2" + 1) = 23" - 2", tedy téměř všechna čísla čítající 3n bitů. Řešení Pišme nyní vše ve dvojkové soustavě: máme tak spočítat zbytek po dělení čísla sto osmnáct, tedy 1110 110, modulo sedm, osm, devět, tedy 111, 1000, 1001. Řešení Pišme nyní vše ve dvojkové soustavě: máme tak spočítat zbytek po dělení čísla sto osmnáct, tedy 1110 110, modulo sedm, osm, devět, tedy 111, 1000, 1001. Přesněji pišme dané číslo po trojicích cifer jako 1110 110 = 1 • 10002 + 110 • 1000 + 110 Řešení Pišme nyní vše ve dvojkové soustavě: máme tak spočítat zbytek po dělení čísla sto osmnáct, tedy 1110 110, modulo sedm, osm, devět, tedy 111, 1000, 1001. Přesněji pišme dané číslo po trojicích cifer jako 1110 110 = 1 • 10002 + 110 • 1000 + 110 Pak modulo 1000 je jistě 1110110 = 110 (modlOOO). Pišme nyní vše ve dvojkové soustavě: máme tak spočítat zbytek po dělení čísla sto osmnáct, tedy 1110 110, modulo sedm, osm, devět, tedy 111, 1000, 1001. Přesněji pišme dané číslo po trojicích cifer jako 1110 110 = 1 • 10002 + 110 • 1000 + 110 Pak modulo 1000 je jistě 1110110 = 110 (modlOOO). Protože je 1000 = 1 (mod 111), dostáváme 1110 110 = 1 + 110 + 110 = 1101 = 110 (mod 111). Pišme nyní vše ve dvojkové soustavě: máme tak spočítat zbytek po dělení čísla sto osmnáct, tedy 1110 110, modulo sedm, osm, devět, tedy 111, 1000, 1001. Přesněji pišme dané číslo po trojicích cifer jako 1110 110 = 1 • 10002 + 110 • 1000 + 110 Pak modulo 1000 je jistě 1110110 = 110 (modlOOO). Protože je 1000 = 1 (mod 111), dostáváme 1110 110 = 1 + 110 + 110 = 1101 = 110 (mod 111). Protože je 1 000 = —1 (mod 1 001), dostáváme 1110 110 = 1 — 110 + 110 = 1 (mod 1001). Šifrou RSA s veřejným klíčem e = 7, n — p - q — 33 byly poslány tři zprávy 29, 7, 21. Prolomte šifru a zprávy dešifrujte. Řešení Zatímco n — p • q je veřejným klíčem, jednotlivá prvočísla p, q jsou soukromým klíčem. Príklad Šifrou RSA s veřejným klíčem e = 7, n — p - q — 33 byly poslány tři zprávy 29, 7, 21. Prolomte šifru a zprávy dešifrujte. Řešení Zatímco n — p - q ]e veřejným klíčem, jednotlivá prvočísla p, q jsou soukromým klíčem. Rozklad se využije k výpočtu Eulerovy funkce (p • <7) = (p - 1)(<7 - 1) = 2 • 10 = 20. Nyní můžeme spočítat inverzi d k e = 7 (mod <£(/))), totiž 20c/ = 0 7c/ = 1 6c/ = -2 ld = 3 (mod20) Príklad Šifrou RSA s veřejným klíčem e = 7, n — p - q — 33 byly poslány tři zprávy 29, 7, 21. Prolomte šifru a zprávy dešifrujte. Řešení Dešifrování se tedy provádí umocňováním na třetí modulo n, pro jednotlivé zprávy vychází mi = 293 = 2 (mod 33) m2 = 73 = 13 (mod 33) m3 = 213 = 21 (mod 33) >0 0,0 Príklad Šifrou RSA s veřejným klíčem e = 7, n — p - q — 33 byly poslány tři zprávy 29, 7, 21. Prolomte šifru a zprávy dešifrujte. Řešení Dešifrování se tedy provádí umocňováním na třetí modulo n, pro jednotlivé zprávy vychází mi = 293 = 2 (mod 33) m2 = 73 = 13 (mod 33) m3 = 213 = 21 (mod 33) (u poslední zprávy je nicméně jak původní tak zašifrovaná zpráva soudělná s modulem, což je velmi nevhodné, protože tak lze pomocí největšího společného dělitele rozložit modul). Príklad Demonstrujte RSA protokol se zvolenými prvočísly 23 a 29 s vhodnou volbou veřejného klíče e. Zašifrujte a odšifrujte několik zpráv m pro ne moc velká m. Rešení Máme n — p - q — 667. Budeme volit e = 487 a m = 25 (mod 667) Zašifrovaná zpráva pak je c = 25487 (mod 667). Príklad Demonstrujte RSA protokol se zvolenými prvočísly 23 a 29 s vhodnou volbou veřejného klíče e. Zašifrujte a odšifrujte několik zpráv m pro ne moc velká m. Rešení Máme n — p - q — 667. Budeme volit e = 487 a m = 25 (mod 667) Zašifrovaná zpráva pak je c = 25487 (mod 667). Ukážeme, jak lze mocninu (snadněji?) počítat zvlášť modulo 23 a 29 (to samozřejmě bez znalosti faktorizace nelze, jde jen o zjednodušení pro účely příkladu): Príklad Demonstrujte RSA protokol se zvolenými prvočísly 23 a 29 s vhodnou volbou veřejného klíče e. Zašifrujte a odšifrujte několik zpráv m pro ne moc velká m. Rešení Máme n — p - q — 667. Budeme volit e = 487 a m = 25 (mod 667) Zašifrovaná zpráva pak je c = 25487 (mod 667). Ukážeme, jak lze mocninu (snadněji?) počítat zvlášť modulo 23 a 29 (to samozřejmě bez znalosti faktorizace nelze, jde jen o zjednodušení pro účely příkladu): c = 25487 = 23 = 8 (mod 23) c = 25487 = (-4)11 = -5 (mod 29) (exponenty lze redukovat modulo 0 0,0