Algebros pratybos. Rimantas Grigutis

3 pratybos. Lyginiai.

1. Pasinaudojȩ EULERio teorema apskaičiuokite.

1) 7^{9999} (mod 1000) .

2) 11^{9999} (mod 1000) .

3) 13^{9999} (mod 1000) .

2. Išsprȩskite lyginiu̧ sistemas.

1) \{ \begin{matrix}2x ≡ −1 (mod 3) \\ 3x ≡ 2 (mod 5) \end{matrix} .

2) \{ \begin{matrix}3x ≡ 6 (mod 9) \\ 5x ≡ 1 (mod 8) \end{matrix} .

3) \{ \begin{matrix}11x ≡ 2 (mod 5) \\ −x ≡ 3 (mod 6) \end{matrix} .

4) \{ \begin{matrix}12x ≡ 15 (mod 17) \\ 10x ≡ 4 (mod 19) \\ 21x ≡ 16 (mod 23) \end{matrix} .

5) \{ \begin{matrix}5x ≡ 1 (mod 23) \\ 15x ≡ 11 (mod 43) \\ 25x ≡ 21 (mod 63) \end{matrix} .

6) \{ \begin{matrix}5x ≡ 1 (mod 41) \\ 5x ≡ 1 (mod 51) \\ 5x ≡ 1 (mod 61) \end{matrix} .

7) \{ \begin{matrix}3x ≡ 1 (mod 11) \\ 5x ≡ 2 (mod 13) \\ 7x ≡ 3 (mod 15) \end{matrix} .

3.1) Kurios iš primityviu̧ju̧ klasiu̧ multiplikaciniu̧ grupiu̧ U_{n} , 2 ≤ n ≤ 20 , yra ciklinės. Atsakyma̧ pagi̧skite.

2) Grupėje U_{n} raskite maksimalios eilės elementa̧. Atsakyma̧ pagi̧skite.

4. Kriptografijos uždavinys. Apibrežkime kriptografijos uždavini̧ tokia schema: Tekstas T

⟶^{šifravimas}
T → x ∈ Z_{n}

i̧slaptinimas

⟶

y = e (x) = x^{E} (mod n)

⇝^{y siuntimas} y ∈ Z_{n} ⟶^{išslaptinimas} d (y) = y^{D} = x^{ED(mod φ(n))} ≡ x (mod n) → x → T. Kriptosistemos {n, p, q, E, D} parinkimas:

i) n = p · q ,čia p ir q pirminiai skaičiai; ii) φ (n) = (p − 1) (q − 1) ir E yra tarpusavyje pirminis φ (n) ; iii) D yra lyginio Ex ≡ 1 (mod φ (n)) sprendinys: D = E^{−1} (mod φ (n)) .

1) I̧slaptinkite ir išslaptinkite simboli̧ x = 4, 7, 12, 18, kai n = 33, 39, 51, 57, 39, 35, 55, 85, 77.

2) Išslaptinkite simboli̧ y = 8, 12, 16, 23, kai

a) n = 3397, E = 55; b) n = 4183, E = 85; c) n = 3869, E = 2205.

3) Išslaptinkite simboli̧ y = 8, 12, 16, 23, kai

a) n = 11189, E = 17, φ (11189) = 10956;

b) n = 10229, E = 17, φ (10229) = 9984;

c) n = 8507, E = 17, φ (8507) = 8280;

d) n = 10207, E = 17, φ (10207) = 9976.