Čtení: 30 minHodnotí se: písemka, ústní (minikvíz 3 na okruhy máš splněný)

2 Homomorfismy a diskrétní logaritmus

Po přečtení umíš

ověřit, zda je zobrazení homomorfismus nebo izomorfismus
poznat, co izomorfismus zachovává
vysvětlit diskrétní logaritmus a Diffie-Hellman

2.1 Ukázka: dvě grupy, jedna struktura

$\mathbb{Z}_6^+$ a $\mathbb{Z}_7^\times$ vypadají různě, ale obě mají 6 prvků a obě jsou cyklické. Zobrazení $h(k) = 3^k \bmod 7$ převádí sčítání na násobení:

3^{a+b} = 3^a \cdot 3^b.

Všech 6 hodnot je různých, takže $h$ je jen přejmenování prvků. Tomu se říká izomorfismus.

2.2 Definice

Definice 2.2 (Homomorfismus)

Zobrazení $h: G \to H$ s vlastností $h(x \circ_G y) = h(x) \circ_H h(y)$ pro všechna $x, y$ . Je-li injektivní, je to monomorfismus, surjektivní epimorfismus, bijektivní izomorfismus.

Věta 2.3 (Vlastnosti)

Homomorfismus do grupy zobrazí neutrální prvek na neutrální, zachová inverze $h(x^{-1}) = h(x)^{-1}$ a obraz je podgrupa. Izomorfismus zachovává navíc řády prvků, podgrupy a cykličnost.

Rychlý test: pokud $h(e_G) \ne e_H$ , homomorfismus to není.

Příklad 2.4 (Není homomorfismus:

f(n) = 3n + 2

(\mathbb{Z}, +)

(\mathbb{R}, +)

)

$f(0) = 2 \ne 0$ , takže neutrální prvek nejde na neutrální. Přímo: $f(1 + 1) = 8$ , ale $f(1) + f(1) = 10$ .

Příklad 2.5 (Je homomorfismus:

h(n) = 2n

\mathbb{Z}_4^+

\mathbb{Z}_8^+

)

$h(a + b) = 2a + 2b$ a sčítání mod 4 se srovná s mod 8. Obraz je podgrupa $\{0, 2, 4, 6\}$ . Je injektivní, ale ne surjektivní, takže to je monomorfismus.

2.3 Jak ukázat, že grupy nejsou izomorfní

Najdi vlastnost, kterou izomorfismus zachovává a která se liší: řád, počet prvků daného řádu, cykličnost.

Příklad 2.6 (

\mathbb{Z}_8^\times

\mathbb{Z}_4^+

)

Obě mají 4 prvky. $\mathbb{Z}_4^+$ má prvek řádu 4, ale v $\mathbb{Z}_8^\times$ mají všechny prvky kromě 1 řád 2. Izomorfní nejsou.

Věta 2.7 (Až na izomorfismus)

Každá cyklická grupa řádu $n$ je izomorfní se $\mathbb{Z}_n^+$ .

2.4 Diskrétní logaritmus

Definice 2.8 (Problém diskrétního logaritmu)

V cyklické grupě s generátorem $\alpha$ a prvkem $\beta$ najdi $k$ , aby $\alpha^k = \beta$ .

V $\mathbb{Z}_n^+$ je to snadné: stačí dělení modulo $n$ . V $\mathbb{Z}_p^\times$ se obecně považuje za těžké, i když jsou to izomorfní grupy. Izomorfismus totiž neumíme rychle spočítat.

Příklad 2.9 (Diffie-Hellman v

\mathbb{Z}_{17}^\times

\alpha = 3

)

Alice zvolí $a = 4$ a pošle $A = 3^4 \bmod 17 = 13$ .

Bob zvolí $b = 5$ a pošle $B = 3^5 \bmod 17 = 5$ .

Alice spočítá $5^4 \bmod 17 = 13$ , Bob $13^5 \bmod 17 = 13$ . Společný klíč je 13, kdo vidí jen $A$ a $B$ , by musel řešit diskrétní logaritmus.

2.5 Typické chyby

Ověřený jen jeden příklad místo všech $x, y$ . Na vyvrácení ale jeden stačí.
Záměna operací v $G$ a $H$ .
Závěr „mají stejný počet prvků, takže jsou izomorfní“.

2.6 Kvíz

Kvíz

1. Co zaručuje izomorfismus navíc oproti homomorfismu? Zachování operace Bijektivitu Komutativitu

h(0) = 1

pro zobrazení mezi

(\mathbb{Z}, +)

(\mathbb{Z}, +)

. Je to homomorfismus? Ano Ne Nelze rozhodnout

3. Co izomorfismus zachovává? Může být správně více možností, ale také žádná. Řády prvků Cykličnost Počet podgrup Názvy prvků

4. Kolik je klíč v DH s

p = 17

\alpha = 3

a = 4

b = 5

? Odpověď:

5. Proč je diskrétní logaritmus těžký v

\mathbb{Z}_p^\times

, když je tato grupa izomorfní s lehkou

\mathbb{Z}_{p-1}^+

Ukázat řešení

Izomorfismus existuje, ale jeho výpočet v opačném směru je právě diskrétní logaritmus. Struktura je stejná, výpočetní obtížnost závisí na reprezentaci.

2.7 Příklady na procvičení

Cvičení 2.10

Je $f(x) = 2x$ z $(\mathbb{Z}, +)$ do $(\mathbb{Z}, +)$ homomorfismus? Jaký?

Řešení

Ano, $2(x + y) = 2x + 2y$ . Je injektivní, ale ne surjektivní, protože liché číslo nedostaneš. Je to monomorfismus.

Cvičení 2.11

Je $f(x) = x^2$ z $(\mathbb{R} \setminus \{0\}, \cdot)$ do sebe homomorfismus? Izomorfismus?

Řešení

Homomorfismus ano, $(xy)^2 = x^2 y^2$ . Izomorfismus ne: $f(1) = f(-1)$ , takže není injektivní.

Cvičení 2.12

Jsou izomorfní $\mathbb{Z}_4^+$ a $\mathbb{Z}_2 \times \mathbb{Z}_2$ ?

Řešení

Ne. $\mathbb{Z}_4^+$ má prvek řádu 4, v $\mathbb{Z}_2 \times \mathbb{Z}_2$ mají všechny nenulové prvky řád 2.

2.8 Tahák

Tahák

$h(x \circ y) = h(x) \circ h(y)$ .
Test: neutrál na neutrál.
Injektivní mono, surjektivní epi, bijektivní izo.
Neizomorfní: najdi odlišný řád prvku.
Cyklická řádu $n$ je až na izomorfismus $\mathbb{Z}_n^+$ .
DLP: $\alpha^k = \beta$ , základ DH.

Kapitolu mám prostudovanou