1. Soustavy lineárních kongruencí 19.3. 1. Skupině třinácti pirátů se podařilo uloupit bednu zlatých mincí. Zkusili je rozdělit rovným dílem na třináct hromádek, ale deset mincí jim zbylo. O zbylé mince se strhla rvačka, při níž jednoho piráta propíchli. Přestali tedy bojovat a zkusili mezi sebe znovu rozdělit mince rovným dílem. Tentokrát zbyly tři mince, o které opět začali bojovat. V boji zahynul další pirát a tak si ostatní opět zkusili mince spravedlivě rozdělit, tentokrát úspěšně. Kolik bylo nejméně mincí, které piráti ukradli? 2. Vyřešte lineární kongruenci 3446x = 8642 (mod 208). 2. kongruence vyšších řadu, primitivní kořeny, testy prvočíselnosti 2.4. 1. Vyřešte 7x4 + Í9x + 25 = 0 (mod 27). 2. Ukažte, že neexistují primitivní kořeny modulo 8. 3. Nalezněte všechny primitivní kořenymodulo 41 a vyřešte 7x17 = 11 (mod 41). 4. Vyřešte x2 - 23 = 0 (mod 77). 5. Dokažte, že čísla 2465, 2821 a 6601 jsou tzv. Carmichaelova. 6. Ukažte, že číslo 341 je Fermatovo pseudoprvočíslo o základu 2, ale že není Euler-Jacobiho pseudoprvočíslo o základu 2. Dále, že číslo 561 je E-J pseudoprvočíslo o základu 2, ale ne o základu 3 a že naopak číslo 121 není E-J pseudoprvočíslo o základu 2, ale je o základu 3. 3. Testy prvočíselnosti 9.4. 1. Pomocí Pocklington-Lehmer testu ukažte, že 1321 je prvočíslo. Řešení. N-l = 1320 = 23.3.5.11 F := 23.3.5 = 120, U := 11 (F, U) = (120,11) = 1 (2^,1321) = 1, (2^,1321) = 1, (2^,1321) = 1 a 21320 = 1 mod(1321) => Svědkové prvočíselnosti jsou a 2 — a-i — — 2. 2. Pomocí Pollardova rho algoritmu najděte faktorizaci čísla 221. [využijte funkci f(x) — x2 + 1, poč. podm. xq — 2] Řešení, x — y — 2 x:=f(x) y:=f(f(y)) (|a;-y|,221) mod(221) 5 26 1 26 197 1 14 104 1 197 145 13 221 = 13.17 4. booleovy algebry Příkladem užitečné algebraické struktury je tzv. Booleova algebra - viz přednáška. Tato abstraktní struktura pomáhá řešit různé konkrétní problémy, např. v teorii množin nebo v logice. Množinový výraz či logickou formuli můžeme přepsat do formálního výrazu v Booleově algebře, využít identit v této algebře k úpravě výrazu a výsledek formulovat zpět jako množinový výraz nebo logickou formuli, viz příklady níže. 1. Zjednodušte výraz ((A A B) V (A B)) A ((£?' 4 C) V (fl A C')). i 2 Řešení. Přepsáním do Booleovy algebry dostáváme (a. b + a' + b).(b + c + b.c') = ■ ■ ■ = a'.c + b. To znamená, že výše uvedená formule je ekvivalentní výroku (A' A C) V B. 2. Anna, Bára, Kateřina a Dana chtějí jet na výlet. Rozhodněte, která z děvčat pojedou, mají-li být dodrženy tyto zásady: Pojede aspoň jedna z dvojice Bára/Dana, nejvýše jedna z dvojice Anna/Kateřina, aspoň jedna z dvojice Anna/Dana a nejvýše jedna z dvojice Bára/Kateřina. Dále je jisté, že Bára nepojede bez Anny a že Kateřina pojede, pojede-li Dana. Řešení. Přepsáním do Booleovy algebry, úpravou a přepsáním zpět dostaneme, že na výlet pojede buď právě Anna s Bárou nebo právě Kateřina s Danou. 5. kódování Příkladem využití jiné algebraické struktury, konkrétně okruhu polynomů nad z2 (či jiným konečným polem), jsou (n,p) kódy - viz přednáška a příklady níže. 1. Uvažujme (5, 3) kód nad z2 generovaný polynomem x2 + x + 1. Vypište všechna kódová slova, najděte generující matici a matici kontroly parity. Řešení. p(x) — x2+x+í. Kódová slova jsou právě násobky generujícího polynomu: O.p, l.p, x.p, (x + l).p, x2.p, (x2 + l).p, (x2 + x).p, (x2 + x + V).p neboli neboli 00000,11100, 01110,10010, 00111,11011, 01001,10101 Bázové vektory vynásobené x5~3 — x2 dávají mod(p): x2 = x + 1 To znamená, že bázové vektory se zakódují následovně x 1—> X3 + X 100 1 y 11100 tj. 010 1 y 10010 001 1 v 01001 a proto je generující matice a matice kontroly parity G A 1 1 0 1 — 1 0 0 0 1 0 V> 0 V 0 1 1 ir 1 1 0 1, 2. Udělejte to samé se (7,4) kódem nad z2 generovaným polynomem x3 + x + 1. 3 Řešení. 0 1 1\ i 1 1 0 0 1 1 1 i 0 0 0 0 1 0 0 0 0 1 0 \o 0 0 v 6. Vytvořující funkce 1. Pomocí vytvořující funkce určete počet jedniček v náhodném binárním řetězci. Řešení. Oynačme B množinu řetězců, pro řetězec b G B \b\ počet jeho bitů a j(b) počet jedniček. Vytvořující funkce má tvar B(x) = V x^ = V 2nxn = —!— y ' ^ ^ l-2x b£B n>0 Vytvořující funkce pro počet jedniček je beB Řetězec b dostaneme z o jeden bit kratšího b' přidáním jedné nuly nebo jedničky, tj. j (b) je součtem j (b') jedniček a j(b') + 1 jedniček. Takže C{x) = (1 + 2j(&'))z|6'l+1 = 5ľ xlb'l+1 + 2 5ľ 3(P'Wb'l+1 = xB{x) + 2xC{x) b'EB b'EB b'EB Odtud c(^) = (1_x2x)2^a-^r2 a n-tý koeficient je c„ = 2™_1(rt^21) = n2™_1. Toto číslo udává počet jedniček v bitech délky n. Těch je bn — 2™. V jednom řetězci je tedy ^ — \ jedniček. To je samozřejmě očekávaný výsledek. 7. Bodované příklady, odevzdat do 21.5. 1. Pomocí přepisu do Booleovy algebry vyřešte následující úlohu: Při vyšetřování vraždy bylo zajištěno pět podezřelých Kalina, Nováček, Obrátil, Pražák, Ryvola. V době činu byl na místě Obrátil nebo Pražák, ale nejvýše jeden z dvojice Kalina, Nováček a aspoň jeden z dvojice Kalina, Obrátil. Podezřelý Ryvola tam mohl být jen v přítomnosti Pražáka, ale pokud tam Ryvola byl, nechyběl ani Obrátil. Lze vyloučit spolupráci Nováčka s Pražákem, zato Nováček a Obrátil tvoří nerozlučnou dvojici. Kdo z podezřelých vraždu spáchal? Řešení. Přepisem do Booleovské algebry, podle prvních písmen jména, dostáváme (o + p) (k' + rí) (k + o) (p + r') (V + o) (rí + p')no a s využitím x2 — x, xx' — 0 dostaneme r'p'nok'. Vinni jsou teda Nováček a Obrátil. Poslední podmínka v zadání by se ovšem měla pochopit tak, že buď tam byli oba nebo ani jeden (Nováček a Obrátil). Tím pádem bude konec výrazu v Booleovské algebře ... (no + n'o') místo ... no. Tím nám na konci po úpravě přibude člen r'pn'o'k. Vraždu tedy mohl rovněž spáchat Kalina s Pražákem. 2. Uvažme (15,11) kód generovaný polynomem 1 + x3 + x4. Přijali jsme kód 011101110111001. Určete původní 11-bitovou zprávu předpokládáme-li, že při přenosu došlo k chybě na jednom bitu. 4 Řešení. Řetězec je kódové slovo, právě tehdy, když je dělitelný generujícím polynomem, tj. v našem případě 1 + x3 + x4. Přijatý řetězec odpovídá polynomu x+x2+x3+x5 +x6+x7+x9+x10+X11 +x14. Tento polynom dává po dělení í+x3+x4 zbytek x+í. To znamená, že při přenosu došlo k chybě. Předpokládáme-li, že chyba je jen na jednom bitu, musí existovat mocnina x, která je rovna tomuto zbytku mo- dulo 1 Proto počítáme x — x' 1, 1. Chyba tedy nastala na třináctém bitu a originální zpráva byla 01110111101. Můžeme si příklad i víc rozebrat. Když si spočítáme všechny mocniny x, dostaneme x4 = x3 -i - 1 X5 = x3 -+ - X + 1 xe = x3 -+ -x2- - X x7 = x2 -i - X + 1 xs = x3 -+ -x2- - X x9 = x2 -i -1 x10 = x3 ■f X řjjl 1 - r^>3 +- x2 + 1 X12 EI-f 1 ■f X x14 — x3 +- x2 a generující matice je tedy /1 1 1 1 0 1 0 1 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 0 1 1 1 1 0 1 0 1 1 1 1 1 0 1 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 V o 0 0 0 0 0 0 0 0 0 1 Můžeme si ověřit, že vynásobením 01110111101 dostaneme kódové slovo 011101110111101, které se liší od přijatého řetězce 011101110111001 právě na tom třináctém bitu. 3. Pomocí vytvořující funkce vyřešte následující rekurenci: a,o — 1, «i — 2 an — 5a„_i — 4a„_2 n > 2 Řešení. Univerzální formule má tvar an — 5a„_i - 4a„_2 - 3[n — 1] + [n — 0] Vynásobením obou stran xn a sečtením přes všechna n dostaneme A(x) = 5x,4(a;) - Ax2A(x) - 3x + 1 Odtud A{x) 1 — 3x 2 1 1 1 (l-4x)(l-x) 31-i 3 1-4x 5