Čtení: 40 minHodnotí se: minikvízy 4 a 5, písemka, ústní

3 Konečná tělesa

Varování 3.1 (Termíny)

Minikvíz 4 (konečná tělesa): středa 4. 11. ve 23:59. Minikvíz 5 (počítání v konečných tělesech): středa 18. 11. ve 23:59. Zpětně je splnit nejde a na zápočet potřebuješ aspoň 7 kvízů.

Kapitola vysvětluje látku a její otázky jsou moje. Otázky ze skutečných minikvízů neobsahuje.

Po přečtení umíš

poznat, kdy je struktura těleso, a najít inverzi rozšířeným Eukleidovým algoritmem
rozhodnout o ireducibilitě polynomu a vědět, kdy test kořenů nestačí
sestavit $GF(p^n)$ a počítat v něm včetně inverze a rovnic
najít generátory multiplikativní grupy

V praxi na ní stojí například šifra AES, která počítá v tělese $GF(2^8)$ modulo $x^8 + x^4 + x^3 + x + 1$ .

3.1 Ukázka: proč nestačí počítat modulo 4

Chceme čtyři prvky, se kterými jde sčítat, násobit a dělit. První nápad je $\mathbb{Z}_4$ :

2 \cdot 2 = 4 \equiv 0 \pmod 4.

Dvě nenulová čísla dala nulu, takže 2 nemá inverzi a dělit jí nejde. $\mathbb{Z}_4$ tedy těleso není.

Řešení je počítat s polynomy místo s čísly. Prvky budou $0,\ 1,\ x,\ x+1$ a násobit budeme „modulo“ polynom $x^2 + x + 1$ , který roli prvočísla hraje mezi polynomy. Vyjde těleso se čtyřmi prvky. Přesně to si teď složíme krok za krokem.

3.2 Okruh a těleso

Definice 3.3 (Okruh)

Trojice $(M, +, \cdot)$ je okruh, pokud $(M, +)$ je abelovská grupa, $(M, \cdot)$ je monoid a platí oba distributivní zákony.

Definice 3.4 (Těleso)

Okruh je těleso, pokud $(M \setminus \{0\}, \cdot)$ je abelovská grupa. Lidsky: každý nenulový prvek jde invertovat, takže se dá dělit vším kromě nuly.

Příklady: $\mathbb{Z}$ je okruh, ale ne těleso (2 nemá celočíselnou inverzi). $\mathbb{Q}$ a $\mathbb{R}$ tělesa jsou.

Věta 3.5 (V tělese nejsou dělitelé nuly)

Pokud $ab = 0$ , pak $a = 0$ nebo $b = 0$ .

Proto $\mathbb{Z}_6$ není těleso: $2 \cdot 3 = 0$ . Naopak $\mathbb{Z}_p$ je těleso právě pro prvočíslo $p$ .

3.3 Inverze v $\mathbb{Z}_p$

Inverzi hledáme rozšířeným Eukleidovým algoritmem (EEA). Najdeme čísla $\alpha, \beta$ taková, že $\alpha k + \beta p = 1$ . Modulo $p$ pak zbyde $\alpha k \equiv 1$ , takže $\alpha$ je inverze $k$ .

Příklad 3.6 (Inverze 5 v

\mathbb{Z}_{17}

)

Dělíme se zbytkem:

17 = 3 \cdot 5 + 2, \qquad 5 = 2 \cdot 2 + 1.

Vyjádříme 1 zpětně:

1 = 5 - 2 \cdot 2 = 5 - 2(17 - 3 \cdot 5) = 7 \cdot 5 - 2 \cdot 17.

Výsledek: $5^{-1} = 7$ . Zkouška: $5 \cdot 7 = 35 = 2 \cdot 17 + 1$ .

3.4 Polynomy a ireducibilita

Polynomy nad tělesem se sčítají, násobí a dělí se zbytkem stejně jako ve škole, jen koeficienty počítáme v $\mathbb{Z}_p$ . Stupně se při násobení sčítají.

Definice 3.7 (Ireducibilní polynom)

Polynom $P$ stupně aspoň 1 je ireducibilní nad $T$ , pokud ho nejde napsat jako součin dvou polynomů stupně aspoň 1. Je to obdoba prvočísla.

Věta 3.8 (Test pro stupeň 2 a 3)

Polynom stupně 2 nebo 3 je ireducibilní nad $T$ právě tehdy, když nemá v $T$ kořen.

Proč to platí: rozklad stupně 3 musí obsahovat činitel stupně 1 a ten dává kořen.

Příklad 3.9 (Ireducibilita nad

\mathbb{Z}_5

)

Je $P(x) = x^3 + 2x + 1$ ireducibilní? Má stupeň 3, takže stačí dosadit všech pět hodnot:

$x$	0	1	2	3	4
$P(x) \bmod 5$	1	4	3	4	3

Žádná nula, takže kořen nemá a polynom je ireducibilní.

Polynom $x^2 + 2x + 2$ naopak dává pro $x = 1$ hodnotu $5 \equiv 0$ . Má kořen, takže ireducibilní není.

Varování 3.10 (Stupeň 4 a výš)

Pro stupeň aspoň 4 test nefunguje. Polynom $x^4 + x^2 + 1$ nad $\mathbb{Z}_2$ nemá kořen, a přesto $x^4 + x^2 + 1 = (x^2 + x + 1)^2$ . Tady musíš hledat i rozklad na polynomy stupně 2.

3.5 Konstrukce $GF(p^n)$

Definice 3.11 (Postup konstrukce)

Pro prvočíslo $p$ a $n \ge 2$ :

Vezmeme těleso $T = \mathbb{Z}_p$ .
Najdeme polynom $P$ stupně $n$ ireducibilní nad $T$ .
Prvky jsou všechny polynomy stupně nejvýš $n - 1$ . Je jich $p^n$ .
Sčítáme po koeficientech. Násobíme jako polynomy a výsledek vezmeme modulo $P$ .

Zápis prvků: polynom se píše jako řetězec koeficientů od nejvyšší mocniny. V $GF(3^2)$ znamená 21 polynom $2x + 1$ . V $GF(2^3)$ znamená 010 polynom $x$ .

Proč musí být $P$ ireducibilní: kdyby $P = AB$ , pak by $A$ a $B$ byly nenulové prvky se součinem 0. Vznikli by dělitelé nuly stejně jako v $\mathbb{Z}_4$ .

Věta 3.12 (Které řády existují)

Řád konečného tělesa je vždy mocnina prvočísla $p^n$ a všechna tělesa téhož řádu jsou izomorfní. Těleso se 6, 10, 12, 14, 15 nebo 18 prvky proto neexistuje.

Číslo $p$ se nazývá charakteristika tělesa.

Příklad 3.13 (Tabulka

GF(4)

)

Počítáme modulo $x^2 + x + 1$ .

Z $x^2 + x + 1 = 0$ plyne nad $\mathbb{Z}_2$ pravidlo $x^2 = x + 1$ . Tím se zbavíme každého $x^2$ :

$10 \cdot 10 = x \cdot x = x + 1 = 11$
$10 \cdot 11 = x^2 + x = (x + 1) + x = 1 = 01$
$11 \cdot 11 = x^2 + 2x + 1 = x^2 + 1 = x = 10$

$\cdot$	01	10	11
01	01	10	11
10	10	11	01
11	11	01	10

Každý řádek obsahuje každý prvek právě jednou, takže inverze existují: $10^{-1} = 11$ .

Příklad 3.14 (Násobení v

GF(16)

)

Počítáme modulo $P = x^4 + x + 1$ .

Spočítejme $1101 \cdot 0110$ .

Přepíšeme: $(x^3 + x^2 + 1)(x^2 + x)$ .
Roznásobíme nad $\mathbb{Z}_2$ : $Q = x^5 + x^3 + x^2 + x$ .
Vydělíme $P$ : $Q = x \cdot P + x^3$ .
Zbytek je $x^3$ , tedy výsledek je 1000.

Není to bitový AND po složkách, který by dal 0100.

3.6 Inverze v $GF(p^n)$

Postup je stejný jako v $\mathbb{Z}_p$ , jen dělíme polynomy.

Příklad 3.15 (Inverze v

GF(9)

)

Počítáme modulo $P = x^2 + 2x + 2$ a hledáme inverzi prvku 20.

Označme $A = 2x$ .

Vydělíme: $P = (2x + 1) \cdot A + 2$ . Zbytek je konstanta 2.
Vyjádříme: $2 = P - (2x + 1)A$ .
Vynásobíme inverzí zbytku, $2^{-1} = 2$ v $\mathbb{Z}_3$ : $1 = 2P - 2(2x + 1)A$ .
Modulo $P$ zmizí první člen a $-2 \equiv 1$ , takže $1 \equiv (2x + 1)A$ .

Výsledek: $(20)^{-1} = 21$ .

Zkouška s $x^2 = x + 1$ : $2x(2x + 1) = 4x^2 + 2x = x^2 + 2x = (x + 1) + 2x = 1$ .

Varování 3.16 (Zbytek nemusí být 1)

EEA často skončí jinou konstantou. Celou rovnost pak vynásob její inverzí, jinak máš špatný výsledek.

3.7 Grupy uvnitř tělesa

Aditivní grupa $GF(p^n)$ má řád $p^n$ a pro $n > 1$ není cyklická: sečteš-li libovolný prvek $p$ -krát, dostaneš 0, takže žádný prvek nemá řád $p^n$ .

Multiplikativní grupa má řád $p^n - 1$ a je vždy cyklická. Generátorů je $\varphi(p^n - 1)$ .

Příklad 3.17 (Generátory

GF(9)

)

Počítáme modulo $x^2 + 2x + 2$ .

Grupa má řád 8, takže generátory jsou $\varphi(8) = 4$ . Zkusíme $g = 10$ , tedy $x$ , a násobíme s pravidlem $x^2 = x + 1$ :

$k$	0	1	2	3	4	5	6	7
$g^k$	01	10	11	21	02	20	22	12

Vyšlo všech 8 nenulových prvků, takže 10 je generátor. Ostatní jsou $g^k$ pro $k$ nesoudělná s 8, tedy $k = 3, 5, 7$ : 21, 20, 12.

Řád prvku dělí řád grupy (Lagrangeova věta). V grupě řádu 8 může mít prvek jen řád 1, 2, 4 nebo 8, takže stačí ověřit $g^4 \ne 1$ .

3.8 Typické chyby

Test kořenů u polynomu stupně 4 a výš. Bez kořene ještě neznamená ireducibilní.
Záměna $GF(4)$ a $\mathbb{Z}_4$ . Modulo 4 těleso nedává.
Násobení po složkách místo násobení polynomů modulo $P$ .
Zapomenuté zmenšení koeficientů modulo $p$ . Sčítání v $GF(2^n)$ je XOR.
Neznormovaná konstanta na konci EEA.
Zápis 21 čtený od nejnižší mocniny. Zde je to $2x + 1$ .

3.9 Kvíz

Kvíz

1. Existuje těleso se 6 prvky? Ano,

\mathbb{Z}_6

Ano,

GF(6)

přes polynomy Ne, 6 není mocnina prvočísla

2. Kolik je inverze 5 v

\mathbb{Z}_7

? Odpověď:

3. Který polynom je ireducibilní nad

\mathbb{Z}_2

x^2 + 1

x^2 + x

x^2 + x + 1

x^2

4. Polynom stupně 4 nad

\mathbb{Z}_3

nemá kořen. Co z toho plyne? Je ireducibilní Není ireducibilní Může být obojí

5. Co platí v

GF(2^4)

? Může být správně více možností, ale také žádná. Sčítání je bitový XOR Násobení je bitový AND Každý prvek je sám sobě opačný Multiplikativní grupa je cyklická

6. Kolik generátorů má multiplikativní grupa

GF(5^2)

? Odpověď:

7. Je aditivní grupa

GF(9)

cyklická? Ano Ne

8. V

GF(2^3)

modulo

x^3 + x + 1

spočítej

011 \cdot 011

. 001 100 101 110

9. V

GF(2^3)

modulo

x^3 + x + 1

spočítej

100 \cdot 011

. 011 110 111 101

10. Vysvětli vlastními slovy, proč musí být polynom

P

v konstrukci ireducibilní.

Ukázat řešení

Kdyby

P = AB

se stupni aspoň 1, byly by

A

B

nenulové prvky stupně menšího než

n

a jejich součin by modulo

P

dal 0. Těleso nemá dělitele nuly, takže by to těleso nebylo.

3.10 Příklady na procvičení

Cvičení 3.18

V tělese $\mathbb{Z}_{263}$ najdi inverzi k 112.

Řešení

EEA dá $23 \cdot 263 + (-54) \cdot 112 = 1$ , takže $112^{-1} = -54 \equiv 209 \pmod{263}$ .

Cvičení 3.19

Rozhodni, zda je $x^4 + x^3 + x + 2$ ireducibilní nad $\mathbb{Z}_3$ .

Řešení

Hodnoty pro 0, 1, 2 jsou 2, 2, 1, takže kořen nemá. Stupeň je ale 4, proto to nestačí. Polynom se rozkládá: $(x^2 + x + 2)(x^2 + 1)$ . Není ireducibilní.

Cvičení 3.20

V $GF(2^3)$ modulo $x^3 + x + 1$ spočítej $100 \cdot (010)^{-1} + 010 \cdot 010$ .

Řešení

Platí $x(x^2 + 1) = x^3 + x = (x + 1) + x = 1$ , tedy $(010)^{-1} = 101$ .

Dále $100 \cdot 101 = x^4 + x^2$ . Z $x^3 = x + 1$ plyne $x^4 = x^2 + x$ , takže $x^4 + x^2 = x$ , tedy 010.

A $010 \cdot 010 = x^2$ , tedy 100. Součet je 110.

Cvičení 3.21

V $GF(3^2)$ modulo $x^2 + 2x + 2$ najdi všechna $y$ , pro která $21(y + 11) = 01 + y$ .

Řešení

Spočítáme $21 \cdot 11 = (2x + 1)(x + 1) = 2x^2 + 1 = 2x + 2 + 1 = 2x$ , tedy 20. Rovnice je $21y + 20 = 01 + y$ .

K oběma stranám přičteme $02y + 10$ . Vlevo $20$ a $10$ dají 00, vpravo $01 + 10 = 11$ a $y + 02y = 00$ . Zůstane $(21 + 02)y = 20y = 11$ .

Podle příkladu výše je $(20)^{-1} = 21$ , takže $y = 21 \cdot 11 = 20$ . Řešení je jediné: $y = 20$ .

Cvičení 3.22

Najdi všechny ireducibilní polynomy stupně 2 nad $\mathbb{Z}_2$ .

Řešení

Kandidáti jsou $x^2$ , $x^2 + 1$ , $x^2 + x$ a $x^2 + x + 1$ . Kořen nemá jen poslední, takže jediný je $x^2 + x + 1$ .

3.11 Tahák

Tahák

Těleso = komutativní okruh, kde každý nenulový prvek má inverzi. Nemá dělitele nuly.
$\mathbb{Z}_n$ je těleso právě pro prvočíslo $n$ .
Řád tělesa je vždy $p^n$ . Těleso téhož řádu je až na izomorfismus jedno.
Stupeň 2 a 3: ireducibilní = bez kořene. Od stupně 4 to neplatí.
$GF(p^n)$ : polynomy stupně menšího než $n$ , násobení modulo ireducibilní $P$ stupně $n$ .
Trik: z $P = 0$ vyjádři nejvyšší mocninu, třeba $x^2 = x + 1$ , a dosazuj.
Inverze: EEA, $\alpha A + \beta P = c$ , pak vynásob $c^{-1}$ .
Aditivní grupa: řád $p^n$ , pro $n > 1$ necyklická.
Multiplikativní grupa: řád $p^n - 1$ , vždy cyklická, generátorů $\varphi(p^n - 1)$ .
$g$ je generátor právě tehdy, když má řád $p^n - 1$ . Rychlejší test (nad rámec slajdů): $g^{(p^n-1)/q} \ne 1$ pro všechna prvočísla $q$ dělící $p^n - 1$ .

Kapitolu mám prostudovanou

3 Konečná tělesa

3.1 Ukázka: proč nestačí počítat modulo 4

3.2 Okruh a těleso

3.3 Inverze v Zp\mathbb{Z}_pZp​

3.4 Polynomy a ireducibilita

3.5 Konstrukce GF(pn)GF(p^n)GF(pn)

3.6 Inverze v GF(pn)GF(p^n)GF(pn)

3.7 Grupy uvnitř tělesa

3.8 Typické chyby

3.9 Kvíz

Kvíz

3.10 Příklady na procvičení

3.11 Tahák

3.3 Inverze v $\mathbb{Z}_p$

3.5 Konstrukce $GF(p^n)$

3.6 Inverze v $GF(p^n)$