1.
a) Číslo 0 ≤ x < 10000 je v tzv. modulání reprezentaci vzhledem k prvočíslům 17, 23, 29 dáno
svými zbytky (5, 13, 9) po dělení těmito prvočísly:
x ≡ 5 (mod 17), x ≡ 13 (mod 23), x ≡ 9 (mod 29).
Převeďte jej do modulární reprezentace vzhledem k prvočíslům 19, 31, 37.
(Nápověda: Určete prvně x.)
b) Jak se odpověď změní, nebudeme-li nadále požadovat 0 ≤ x < 10000?
(Nápověda: pro jaké reprezentace (a, b, c) vzhledem k 17, 23, 29 a (d, e, f) vzhledem k 19, 31, 37
bude nějaké x existovat?)
2.
a) Ukažte, že 55 je primitivní kořen modulo 106.
b) Kolik existuje primitivních kořenů modulo 106?
3.
V šifrovacím systému RSA s veřejným klíčem daným modulem 1763 a exponentem 97 došlo k
prozrazení faktorizace modulu:
1763 = 41.43
Dešifrujte zprávu 11. (Nic nešifrujte, chce se po vás pouze dešifrování.)
4.
Zbytková třída a (mod m) splňuje a48
≡ 1 (mod m), a38
≡ 1 (mod m). Jaký může být řád této
zbytkové třídy? Pro obě možnosti uveďte příklad takové zbytkové třídy, tj. čísla a. (Nápověda:
Využijte Eukleidova algoritmu k postupnému dělení mocnin a48
/a38
atd.)
5.
Najděte všechna přirozená čísla m, pro něž φ(m) = 46, kde φ značí Eulerovu funkci.