závěrečná písemka 5.1.2022, skupina A
Obecné doporučení: Čtěte pozorně, často jsou v textu informace, které Vám počítání zjednoduší. Navíc se po Vás také často chce několik věcí, tak na žádnou nezapomeňte.
1. Lukáš se zabýval počítáním odmocnin modulo 49.
a) Z učebnice vyčetl, že primitivní kořen modulo 49 existuje a že k jeho nalezení se mu bude hodit primitivní kořen modulo 7, kterým je např. 3. Poraďte mu, jakou (jednu!) mocninu čísla 3 modulo 49 má spočítat (sami ji nepočítejte!), aby zjistil, zda je 3 primitivní kořen dokonce modulo 49. Možná byste chtěli spočítat tři mocniny, ale dvě z nich stačí uvážit modulo 7.
b) Prvně zkusil využít Jacobiho symbolu (^) k ověření, zda dané x, nesoudělné s 49, je druhou mocninou. Vysvětlete, proč je to zcela nevhodné. Najděte nějaké takové x, pro které sice
= 1, ale druhou mocninou není (můžete také využít dalšího bodu).
c) Dále se dočetl, že odmocniny lze počítat snadno pomocí diskrétního logaritmu log3 vzhledem k primitvnímu kořenu 3. Poraďte mu, jak pomocí log3 x zjistit, zda x je druhou mocninou modulo 49 a jak spočítat druhé odmocniny x (stačí jako vhodné mocniny primitivního kořene 3). Demonstrujte na příkladu x = 30 (mod 49) s vypočteným log3 30 = 14 (odmocniny není potřeba dopočítávat explicitně).
(12 bodů)
2. V šifrovacím systému RSA s veřejným klíčem daným modulem n = 247 = 13 • 19 a exponentem e = 29 je zašifrována zpráva. Dešifrujte zprávu c = 35, přičemž počítejte prvně zvlášť modulo 13 a modulo 19 a tyto výpočty pak dejte dohromady (pomocí CRT). (12 bodů)
3. Polynomem í + x + x3 lze generovat lineární (k + 3, /j)-kód pro libovolné k. Pro které nejmenší k se vrchní tři prvky prvního sloupce matice kódu, tj. 110, poprvé zopakují v nějakém dalším sloupci? (Tj. generujte matici, dokud nedostanete znovu sloupec začínající 110.) Uvažujme dále toto A;, tj. šířku matice.
a) Vysvětlete, na příkladu obdrženého slova 110 | 0 • • • 0, že výsledný kód nezvládne opravovat jednoduché chyby.
b) V případě obdrženého slova 010 | 1010 • • • 0 však v něm obsaženou jednouduchou chybu opravit zvládne, ukažte jak. (klasické dekódování)
c) Určené k není nejmenší, při kterém výsledný kód nezvládne opravovat jednoduché chyby. Jaká je tato nejmenší šířka matice?
(12 bodů)
4. Cílem tohoto příkladu bude spočítat průměrný počet hodů jednou šestistěnnou kostkou potřebných na hození dvou šestek po sobě.
a) Označme pravděpodobnost, že v k po sobě jdoucích hodech nepadne šestka dvakrát po sobě a navíc poslední hod je šestka. Podobně označme pravděpodobnost, že v k po sobě jdoucích hodech nepadne šestka dvakrát po sobě a navíc poslední hod není šestka. Sestavte soustavu rekurencí pro tyto posloupnosti, počáteční podmínky budou ciq = 0, bo = 1. Najděte vytvořující funkce A(x), B(x) těchto posloupností, o explicitní vzoreček pro afe, Ďfe se nesnažte (nebude hezký a nebudete ho potřebovat).
b) Označme dále pravděpodobnost, že v k po sobě jdoucích hodech padne šestka dvakrát po sobě, ale až v úplně posledních dvou hodech a označme P{x) vytvořující funkci této posloupnosti. Dokažte, že derivace funkce P{x) v čísle 1 je rovna
P'(l) = YlPk-k
k>0
a je tedy rovna průměrnému počtu hodů jednou šestistěnnou kostkou potřebných na hození dvou šestek po sobě. Zjevně Pk = \ ' afc-i a vytvořující funkce proto bude P(x) = ^ • x ■ A(x).
c) Spočtěte tuto průměrnou hodnotu (buď jako derivaci z předchozího bodu nebo jinak, ale úplně zadarmo to asi nepůjde).
(18 bodů)