závěrečná písemka 23.1.2023, 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. Zbytková třída 5 modulo 47 je primitivní kořen (nemusíte to ověřovat). Z přednášky se nám bude hodit
as = a*   (mod n) •<=> s = t   (mod ord„ a), (★) kde ord„ a značí řád zbytkové třídy a (mod n).
a) Dokažte, že zbytková třída 10 modulo 23 je také primitivní kořen. Rozhodněte, která ze dvou odpovídajících zbytkových tříd 10 (mod 46), 33 (mod 46) je primitivním kořenem a vysvětlete proč (není potřeba za tímto účelem počítat mocniny modulo 46, stačí počítat zvlášť modulo 2 a 23). Označme tuto zbytkovou třídu g (mod 46).
b) Rozhodněte s využitím (★), která z kongruencí
5(í?x) = 25   (mod 47),    25(í?x) = 25   (mod 47) má a která nemá řešení.
c) Dokažte k \ l =>• ip(k) \ ip(l).
d) V tomto bodě jsou a, b parametry splňující (a, 47) = 1, (b,46) = 1. Vztah (★) říká, že výraz as (mod 47) nabývá právě ord47 a různých hodnot - pro ord47 a různých zbytkových tříd s (mod ord47 a). Určete podobně počet to různých hodnot výrazu cSb ) (mod 47). Kongruence cSb ) = c (mod 47) pak buď nebude mít žádné řešení nebo řešením bude jediná zbytková třída modulo to. S využitím ord„ a \ ip(n) a části c) dokažte to \ ip(ip(A7)).
e) Pro každou ze čtyř možných hodnot to \ ip(ip(A7)) najděte hodnotu parametru b tak, aby kongruence
5(ř,x)=5   (mod 47),
měla jediné řešení modulo to (kterým pak samozřejmě bude x = 0 (mod to)). Kolik řešení bude v každém případě existovat modulo <£>(<£> (47))?
(18 bodů)
2. Albert a Bedřich chtějí komunikovat Rabínovou šifrou. Albert si zvolil jako soukromý klíč prvočísla p = 19, q = 23 a jim příslušný veřejný klíč - modul n = p ■ q = 437. Bedřich mu poslal veřejným kanálem zašifrovanou zprávu c = 328 (mod 437). Dešifrujte Bedřichovu zprávu. Asi budete chtít počítat prvně zvlášť modulo 19, 23 a tyto částečné výsledky pak dát dohromady.
(12 bodů)
3. Polynom 1 + x + x4 je primitivní, takže jím generovaný lineární (12, 8)-kód rozpoznává dvojité chyby (to by platilo dokonce i pro delší kód).
a) Demonstrujte explicitně na konkrétním příkladu, že tento kód nerozpoznává trojité chyby.
b) Demonstrujte explicitně na konkrétním příkladu, že tento kód neopravuje dvojité chyby.
c) Dekódujte obdržená slova 1100 | 10010001 a 0111 | 10010001 za předpokladu nejmenšího možného počtu chyb. (12 bodů)
4. Cílem tohoto příkladu je určení počtu obarvení následujícího grafu dvěma barvami, ve kterých každý čtverec obsahuje vrcholy obou barev.
k hran
Označme počet takových obarvení, ve kterých jsou (zvýrazněné) vrcholy na pravé straně obarveny dvěma různými barvami, pevně zvolenými (počet obarvení na tomto výběru nezáleží). Protože je k počet vodorovných hran, máme a0 = 1. Označme počet takových obarvení, ve kterých jsou vrcholy na pravé straně obarveny jednou barvou, opět pevně zvolenou. Protože je k počet vodorovných hran, máme bg = 1.
a) V obou případech si zvolte libovolné vyhovující obarvení na pravé straně a (např. vypsáním všech možností pro sousedy) odvoďte rekurence pro a^, bk pomocí &fc-i, 6fe-i, která platí i pro k = 0. Dokažte, že platí = bk + bk-i a pomocí této substituce nahraďte systém rekurencí jedinou rekurencí pro posloupnost bk (odkazující se ovšem nyní na bk-i, &fc-2)-
b) Vyřešte tuto rekurencí bez explicitního dopočítávání koeficientů a odvoďte asymptotické chování bk ~ C • Bk, ve kterém určete základ B (pokud bude výraz pro B obsahovat VT7, bude pravděpodobně dobře). Rozhodněte, zda lim^^oo \b]„ — C ■ Bk\ = 0.
Poznamenejme, že počet všech obarvení je 2 • + 2 • bk a asymptoticky vypadá stejně, jen pro jiný koeficient C. Samozřejmě se jej můžete pokusit odvodit. (12 bodů)