dr. Gollové vyjít, se podívat sem. Když si budete ty příklady jen tupě pročítat, tak se naučíte lim 0. Pokud máte

´ Uvod Pr´ avˇe se d´ıv´ ate na moje ˇreˇsen´ı pˇr´ıklad˚ u z X01AVT z roku 2007/2008. Zajisté obsahuj´ı spousty chyb a nedok´ aˇze je pochopit nikdo vˇcetnˇe autora, ale aspoˇ n m˚ uˇzou poslouˇzit jako menˇs´ı návod k tomu, jak poˇc´ıtat pˇr´ıklady u zkouˇsky. D˚ uraznˇ e doporuˇcuji ty pˇr´ıklady si vypoˇc´ıtat sám a teprve potom, co vyjde nˇejak´ y v´ ysledek jinak, neˇz jak m´ a podle dr. Gollové vyj´ıt, se pod´ıvat sem. Kdyˇz si budete ty pˇr´ıklady jen tupˇe proˇc´ıtat, tak se nauˇc´ıte lim → 0. Pokud m´ ate pocit, ˇze tu nˇeco chyb´ı, ˇci snad pˇreb´ yv´ a, m´ ate naprosto volnou ruku k u ´pravám, za pˇredpokladu, ˇze své u ´pravy zveˇrejn´ıte, a to vˇcetnˇe zdrojového k´ odu v .tex a obrázk˚ u. Odkazy na pouˇzitou literaturu jsou na konci. Obr´ azky nakresleny pomoc´ı maker XY-pic. T´ımto bych také chtˇel podˇekovat dr. Alenˇe Gollové za jej´ı peˇclivou kontrolu m´ ych v´ ypoˇct˚ u a mnoˇzstv´ı cenn´ ych pˇripom´ınek a oprav. Hodnˇe ˇstˇest´ı u zkouˇsek a co nejménˇe tr´ apen´ı s algebrou, ˇ ep´ Stˇ an Rezek

Obsah 1 Koneˇ cn´ e grupy 1.1 Pˇr´ıklad 1 . 1.2 Pˇr´ıklad 2 . 1.3 Pˇr´ıklad 3 . 1.4 Pˇr´ıklad 4 . 1.5 Pˇr´ıklad 5 . 1.6 Pˇr´ıklad 6 . 1.7 Pˇr´ıklad 7 . 1.8 Pˇr´ıklad 8 . 1.9 Pˇr´ıklad 9 . 1.10 Pˇr´ıklad 10 . 1.11 Pˇr´ıklad 11 . 1.12 Pˇr´ıklad 12 . 1.13 Pˇr´ıklad 13 . 1.14 Pˇr´ıklad 14 . 1.15 Pˇr´ıklad 15 . 1.16 Pˇr´ıklad 16 .

a . . . . . . . . . . . . . . . .

poˇ c´ıt´ an´ı v . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

3 3 3 4 4 5 6 6 6 7 8 9 9 10 10 11 12

2 Polynomy nad Zn a koneˇ cn´ a tˇ elesa 2.1 Pˇr´ıklad 1 . . . . . . . . . . . . . . 2.2 Pˇr´ıklad 2 . . . . . . . . . . . . . . 2.3 Pˇr´ıklad 3 . . . . . . . . . . . . . . 2.4 Pˇr´ıklad 4 . . . . . . . . . . . . . . 2.5 Pˇr´ıklad 5 . . . . . . . . . . . . . . 2.6 Pˇr´ıklad 6 . . . . . . . . . . . . . . 2.7 Pˇr´ıklad 7 . . . . . . . . . . . . . . 2.8 Pˇr´ıklad 8 . . . . . . . . . . . . . . 2.9 Pˇr´ıklad 9 . . . . . . . . . . . . . . 2.10 Pˇr´ıklad 10 . . . . . . . . . . . . . . 2.11 Pˇr´ıklad 11 . . . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

14 14 14 15 15 15 16 17 17 18 19 20

3 Line´ arn´ı a cyklick´ e k´ ody 3.1 Pˇr´ıklad 1 . . . . . . . 3.2 Pˇr´ıklad 2 . . . . . . . 3.3 Pˇr´ıklad 3 . . . . . . . 3.4 Pˇr´ıklad 4 . . . . . . . 3.5 Pˇr´ıklad 5 . . . . . . . 3.6 Pˇr´ıklad 6 . . . . . . . 3.7 Pˇr´ıklad 7 . . . . . . . 3.8 Pˇr´ıklad 8 . . . . . . . 3.9 Pˇr´ıklad 9 . . . . . . . 3.10 Pˇr´ıklad 10 . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

21 21 22 23 23 24 24 25 25 26 27

. . . . . . . . . .

. . . . . . . . . .

Zn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

1

3.11 Pˇr´ıklad 11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Homomorfismy 4.1 Pˇr´ıklad 1 . 4.2 Pˇr´ıklad 2 . 4.3 Pˇr´ıklad 3 . 4.4 Pˇr´ıklad 4 . 4.5 Pˇr´ıklad 5 . 4.6 Pˇr´ıklad 6 . 4.7 Pˇr´ıklad 7 .

a podgrupy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 Svazy a Booleovy algebry 5.1 Pˇr´ıklad 1 . . . . . . . . 5.2 Pˇr´ıklad 2 . . . . . . . . 5.3 Pˇr´ıklad 3 . . . . . . . . 5.4 Pˇr´ıklad 4 . . . . . . . . 5.5 Pˇr´ıklad 5 . . . . . . . . 5.6 Pˇr´ıklad 6 . . . . . . . . 5.7 Pˇr´ıklad 7 . . . . . . . . 5.8 Pˇr´ıklad 8 . . . . . . . .

. . . . . . . .

27

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

29 29 29 30 31 31 32 32

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

33 33 34 34 35 37 39 39 40

2

1

Koneˇ cn´ e grupy a poˇ c´ıt´ an´ı v Zn

1.1

Pˇ r´ıklad 1

V Z267 najdˇete vˇsechna x, pro kter´ a plat´ı 114x = 15. Poˇc´ıt´ a se pomoc´ı rozˇs´ıˇreného eukleidova algoritmu.

114x + 267y = 15 267 = 2 · 114 + 39

39 = 367 − 2 · 114

114 = 2 · 39 + 36

36 = 114 − 2 · 39 = 114 + 4 · 114 − 267 · 2

39 = 1 · 36 + 3

3 = 39 − 36 = 3 · 267 − 7 · 114

Na levé stranˇe vyˇsla trojka, coˇz znamen´ a, ˇze nejmenˇs´ı spoleˇcn´ y dˇelitel 114 a 267 (gcd ) je 3. Na pravé stranˇe (Bezoutova nerovnost) pak m´ am tu trojku vyjádˇrenou pomoc´ı násobk˚ u 114 a 267. Jelikoˇz c = gcd(114, 267) dˇel´ı d = 15, pak rovnice má tolik ˇreˇsen´ı, kolik je c. V tomto pˇr´ıpadˇe tedy 3. Dále mus´ım vyj´ adˇrit d pomoc´ı n´ asobk˚ u 114 a 267. Vydˇel´ım tedy d/c a z´ıskám ˇc´ıslo 5, kter´ ym vynásob´ım Bezoutovu nerovnost. Tedy 15 = 5 · 3 = 5 · (3 · 267 − 7 · 114) = 15 · 267 − 35 · 114 T´ım jsem z´ıskal partikul´ arn´ı ˇreˇsen´ı rovnice: (xp , yp ) = (−35, 15) (protoˇze 267 je u y a 114 u x). Nyn´ı hled´ am nesoudˇelné ˇreˇsen´ı homogenn´ı rovnice. To najdu tak, ˇze vezmu zadanou rovnici a na levou stranu nap´ıˇsu 0. Pak ji vyˇreˇs´ım a dostanu nˇejaké koeficienty u x a y: ·3−1

114x + 267y = 0 38x + 89y = 0

Z této rovnice snadno vyˇctu, ˇze aby se pravá strana rovnala nule, na levé stranˇe mus´ı x = 89 a y = −38. Z toho tedy (x0 , y0 ) = (89, −38). Celkové ˇreˇsen´ı v Z je tedy (x, y) = (xp , yp ) + k · (x0 , y0 ), k ∈ Z V tomto pˇr´ıpadˇe (x, y) = (−35, 15) + k · (89, −38), k ∈ Z A pro Z267 m´ a x tˇri ˇreˇsen´ı: x1 = −35 + 1 · 89 = 54 x2 = −35 + 2 · 89 = 143 x3 = −35 + 3 · 89 = 232

1.2

Pˇ r´ıklad 2

Spoˇctˇete 18−1 a 19−1 v Z26 , pokud existuj´ı. Aby k nˇejakému prvku existoval inverz, mus´ı b´ yt nejvˇetˇs´ı spoleˇcn´ y dˇelitel toho prvku a základu soustavy 1. Jin´ ymi slovy, prvek a v Zm m´ a inverzi pr´ avˇe tehdy, kdyˇz plat´ı gcd(a, m) = 1. Jelikoˇz gcd(18, 26) = 2, 18 nem´ a v Z26 inverzi. 19 inverzi má, spoˇc´ıtat se dá pomoc´ı eukleidova algoritmu:

3

(1)

19x + 26y = 15 v Z 26 = 1 · 19 + 7 19 = 2 · 7 + 5

7 = 26 − 19 5 = 19 − 2 · 7 = 3 · 19 − 2 · 26

7=1·5+2

2 = 7 − 5 = 3 · 26 − 4 · 19

5=2·2+1

1 = 5 − 2 · 2 = 11 · 19 + (−8) · 26

Jelikoˇz 1 = 11 · 19 v Z26 , 19−1 = 11 v Z26 .

1.3

Pˇ r´ıklad 3

Spoˇctˇete zbytky po dˇelen´ı ˇc´ısel 49107 a 622 ˇc´ıslem 40. Tady se d´ asu ´spˇehem pouˇz´ıt Euler-Fermatova vˇeta1 : Je-li gcd(a, m) = 1, potom plat´ı aϕ(m) = 1 v Zm

(2)

D´ al si mus´ım uvˇedomit, ˇze 49107 se d´ a napsat jako 49 · ·}· = (49 mod 40)107 = 9107 v Z40 . |49 · {z 107×

D´ al um´ım vypoˇc´ıtat ϕ(40) = ϕ(23 · 5) = (8 − 4) · 4 = 16. Ted’ tedy m˚ uˇzu pouˇz´ıt E-F (Euler-Fermat): E−F

9107 = 96·16+11 → 911 = 9 · (92 )5 = 9 · 815 = 9 · 15 = 9 Podobnˇe ovˇsem nem˚ uˇzu postupovat v tomhle pˇr´ıpadˇe, jelikoˇz základ 6 je soudˇeln´ y s t´ım, kolik modulo se poˇc´ıt´ a (tj. 40), neboli gcd(6, 40) 6= 1. Proto mi nezb´ yvá nic jiného, neˇz pouˇz´ıt rovnou opakované ˇctverce, 22 = 1 · 16 + 0 · 8 + 1 · 4 + 1 · 2 + 0 · 1: 1 X

0 S

S

1 X

S

1 X

0 S

Jin´ ymi slovy, rozepsal jsem si 22 do bin´ arn´ı podoby, mezi kaˇzdou ˇc´ıslici jsem vepsal S a tam, kde je jedniˇcka, jsem napsal X. Ted’ to nap´ıˇsu pod sebe (nejlevˇejˇs´ı X je nahoˇre, nejpravˇejˇs´ı dole) a dostanu: X S S X S X S

1.4

61 = 6 62 = −4 64 = 16 65 = 16 610 = 16 611 = 16 622 = 16

Pˇ r´ıklad 4

Najdˇete pˇrirozené ˇc´ıslo x takové, ˇze plat´ı: x ≡ 2 (mod 8), x ≡ 5 (mod 11), x ≡ 7 (mod 15) ˇ ınsk´ Tady pˇrich´ az´ı na ˇradu C´ a vˇeta o zbytc´ıch. Pokud si to nahoˇre nap´ıˇsu jako x ≡ a1 (mod m1 ), pak postup je n´ asleduj´ıc´ı: 1. Najdu ˇc´ıslo M , M = m1 · m2 · · · mk . 2. Pro kaˇzdé mi si najdu ˇc´ıslo qi = s ·

Y

−1  Y mj , kde s =  mj  v Zmi

j6=i

j6=i

1 Velebil to ve skriptech naz´ yv´ a jen Eulerova vˇ eta, na wikipedii se to naz´ yv´ a zase jen Mal´ a Fermatova vˇ eta - mal´ a Fermatova vˇ eta je vyslovena jen pro poˇ c´ıt´ an´ı modulo prvoˇ c´ıslo, Euler ji zobecnil pro libovoln´ en

4

3. Celkov´ y v´ ysledek bude a1 · q1 + a2 · q2 · · · ak · qk v ZM V tomhle pˇr´ıpadˇe tedy M = 8 · 11 · 15 = 1320 a −1

q1 = s1 · 11 · 15 = s1 · 168 = s1 · 5

[5]8 = 5

= 5 · 11 · 15 = 825 −1

q2 = 8 · s2 · 15 = s2 · 120 = s2 · 10

[10]11 = 10

= 8 · 10 · 15 = 1200 = −120 −1

q3 = 8 · 11 · s3 = s3 · 88 = s3 · 13

[13]15 = 7

= 8 · 11 · 7 = 616

Mimochodem, je lepˇs´ı si ps´ at m´ısto tˇreba q1 , q2 atd. sp´ıˇs q8 , q11 atd., protoˇze ˇclovˇek pak pˇresnˇe v´ı, v kterém Z poˇc´ıt´ a ty inverzy. Po vyn´ asoben´ı to d´ a 2 · 825 − 5 · 120 + 7 · 616 = 5362 = 82 v Z1320 , coˇz se dá napsat jako x = 82 + 1320k, k ∈ Z

1.5

Pˇ r´ıklad 5

Urˇcete ˇr´ ad prvku 11 v aditivn´ı grupˇe (Z26 , +) a ˇrád prvku 11 v multiplikativn´ı grupˇe (Z∗26 , ·) vˇsech invertibiln´ıch prvk˚ u v Z26 . V obou pˇr´ıpadech hled´ am prvek, kter´ y dokáˇze vygenerovat vˇsechny ostatn´ı, a to tak, ˇze na nˇej aplikuju operaci ⊕ tolikr´ at, kolik je prvk˚ u v grupˇe. Pokud mi po n opakován´ıch té operace dá neutráln´ı prvek vzhledem k operaci ⊕, tak n je jeho ˇr´ ad. Aditivn´ı grupa je takov´ a, kde se ty prvky sˇc´ıtaj´ı, a poˇcet prvk˚ u je tedy 26. Multiplikativn´ı grupa je takov´ a, kdy prvky umocˇ nuji, a prvk˚ u takové mnoˇziny (invertibiln´ıch) je ϕ(26) = ϕ(2 · 13) = 12 (protoˇze eulerova funkce mi d´ av´ a poˇcet prvk˚ u nesoudˇeln´ ych s dan´ ym ˇc´ıslem, a prvek a je invertibiln´ı, pokud má gcd(a, m) = 1 v Zm ) Zkus´ım tedy na 11 (zadan´ a) aplikovat operaci · (v Z26 ): 111 = 11 112 = 121 = 17 113 = 17 · 11 = 187 = 5 114 = 5 · 11 = 55 = 3 115 = 3 · 11 = 33 = 7 116 = 7 · 11 = 77 = 25 117 = 25 · 11 = 275 = 15 118 = 15 · 11 = 165 = 9 119 = 9 · 11 = 99 = 21 1110 = 21 · 11 = 231 = 23 1111 = 23 · 11 = 253 = 19 1112 = 19 · 11 = 209 = 1

Vid´ım, ˇze mi vygenerovala 12 prvk˚ u, jej´ı ˇrád je tedy r(a) = 12. Vzhledem k tomu, ˇze jej´ı ˇrád je roven poˇctu prvk˚ u mnoˇziny, je i jej´ı gener´ ator. V´ ypoˇcet se d´ a v´ yraznˇe zjednoduˇsit, kdyˇz si uvˇedom´ım, ˇze ˇrád prvku mus´ı b´ yt dˇelitelem poˇctu prvk˚ u grupy, v tomto pˇr´ıpadˇe tedy staˇc´ı ovˇeˇrit jen ˇr´ ady 1, 2, 3, 4, 6 (a 12 uˇz ani nemus´ım, protoˇze to jsou to zbylé). Co se t´ yˇce aditivn´ı grupy, v´ ypoˇcet by vypadal podobnˇe, jen by tam bylo 11 · 1, 11 · 2, · · · , 11 · 26, kde 11 · 26 = 0. Takˇze 11 je i jej´ı gener´ ator, protoˇze dok´ azala vygenerovat 26 prvk˚ u; r(a) = 26. Stejnˇe tak i tady staˇc´ı vyzkouˇset ˇr´ ady 1,2 a 13.

5

1.6

Pˇ r´ıklad 6

Najdˇete vˇsechny gener´ atory grupy (Z∗13 , ·). Kolik r˚ uzn´ ych generátor˚ u má tato grupa? Cyklick´ a grupa m´ a ϕ(r) gener´ ator˚ u ˇr´ adu r (kde r je soudˇelné s velikost´ı grupy), takˇze generátor˚ u ˇrádu |M | je ϕ(|M |), coˇz je ϕ(ϕ(13)) = ϕ(12) = 4 (ta hvˇezdiˇcka nad Z znamená, ˇze je to grupa invertibiln´ıch prvk˚ u). Abych naˇsel prvky zadaného ˇr´ adu, tak mus´ım naj´ıt generátor grupy. To se bohuˇzel dá dˇelat pouze postupn´ ym zkouˇsen´ım, poˇcet generátor˚ u grupy 4 = 12 = 1/3. pˇriˇcemˇz pravdˇepodobnost, ˇze se tref´ım, je poˇcet prvk˚ u grupy Takˇze zaˇcnu postupnˇe zkouˇset vˇsechny prvky grupy. Jedniˇcka generátor evidentnˇe nebude, protoˇze 1cokoliv = 1. Jej´ı ˇr´ ad je tedy 1. Zkus´ım dvojku (v Z13 ): 21 = 2 22 = 4 23 = 8 24 = 3 25 = 6 26 = 12 27 = 11 28 = 9 29 = 5 210 = 10 211 = 7 212 = 1 Stejnˇe jako minule se to d´ a v´ yraznˇe zjednoduˇsit, kdyˇz budu zkouˇset jen ˇrády soudˇelné s poˇctem prvk˚ u grupy. Dostal jsem celou mnoˇzinu ˇc´ısel, jejichˇz gcd(a, 13) = 1. 2 je tedy generátor. Mimo dvojky jeˇstˇe ovˇsem mus´ı existovat dalˇs´ı gener´ atory, protoˇze jsem si nahoˇre spoˇc´ıtal, ˇze jsou celkem ˇctyˇri. Ty dalˇs´ı m˚ uˇzu naj´ıt bud’ zase systémem BruteForceTM , coˇz je ponˇekud zdlouhavé, nebo pomoc´ı vzorce r(ak ) =

r(a) gcd(r(a), k)

(3)

V tomto pˇr´ıpadˇe, m´ am prvek 21 , r(21 ) = 12, a hledám dalˇs´ı prvky, jejichˇz ˇrád je taky 12. Jin´ ymi slovy, ˇreˇs´ım rovnici pro k: r(21 ) =

12 = 12 gcd(12, k)

Z toho vypl´ yv´ a, ˇze k budou vˇsechna ˇc´ısla nesoudˇelná s 12. Tedy k ∈ {1, 5, 7, 11} a ty generátory jsou {21 , 25 , 27 , 211 } = (podle tabulky, co jsem si vytvoˇril nahoˇre) {2, 6, 11, 7}.

1.7

Pˇ r´ıklad 7

Najdˇete vˇsechny gener´ atory grupy (Z13 , +). Kolik r˚ uzn´ ych generátor˚ u má tato cyklická grupa? Pˇr´ıklad v z´ asadˇe stejn´ y jako 1.5. Pro kaˇzdou cyklickou grupu plat´ı, ˇze cyklická grupa ˇrádu n má pr´ avˇe ϕ(n) r˚ uzn´ ych gener´ ator˚ u, zde tedy cyklick´ a grupa ˇr´ adu 13 má 12 r˚ uzn´ ych generátor˚ u (a jsou to vˇsechny jej´ı prvky kromˇe nuly).

1.8

Pˇ r´ıklad 8

Vypiˇste vˇsechny podgrupy multiplikativn´ı grupy (Z∗13 , ·). Nejdˇr´ıve si uvˇedomte, kolik prvk˚ u tyto podgrupy mohou m´ıt. ˇ ad pogrupy d mus´ı dˇelit ˇr´ ˇ ady podgrup tedy mohou b´ R´ ad grupy, tedy d|ϕ(13) = 12. R´ yt 1, 2, 3, 4, 6, 12 (pogrupa ˇr´ adu r je generov´ ana prvky ˇr´ adu r). Podgrupa ˇrádu 12 je tedy celá grupa, pogrupa ˇrádu 1 bude generována prvkem 1. U tˇech ostatn´ıch mus´ım naj´ıt gener´ atory daného ˇrádu, v pˇr´ıkladu 1.6 uˇz jsem naˇsel generátor ˇrádu 12, coˇz je dvojka. Z toho uˇz se daj´ı dost jednoduˇse naj´ıt generátory poˇzadovaného ˇrádu: pouˇzit´ım vzorce 3 dopoˇc´ıtám ostatn´ı: 6

ˇ ad 2: • R´

12 gcd(12,k)

= 2: k ∈ {6}, a = 26 = 64 = 12 ⇒ M2 = {1, 12}

ˇ ad 3: • R´

12 gcd(12,k)

= 3: k ∈ {4, 8}, a = 24 ∧ 28 , 24 = 16 = 3 ⇒ M3 = {1, 3, 9}

ˇ ad 4: • R´

12 gcd(12,k)

= 4: k ∈ {3, 9}, a = 23 ∧ 29 , 23 = 8 ⇒ M4 = {1, 5, 8, 12}

ˇ ad 6: • R´

12 gcd(12,k)

= 6: k ∈ {2, 10}, a = 22 ∧ 210 , 22 = 4 ⇒ M6 = {1, 3, 4, 9, 10, 12}

1.9

Pˇ r´ıklad 9

Vypiˇste vˇsechny podgrupy aditivn´ı grupy (Z12 , +). Nejdˇr´ıve si uvˇedomte, kolik prvk˚ u tyto podgrupy mohou m´ıt. ˇ ad pogrupy d mus´ı dˇelit ˇrád grupy, tedy d|12 (protoˇze prvk˚ Pˇr´ıklad podobn´ y (dokonce izomorfn´ı :-) ) s 1.8. R´ uv ˇ grupˇe je 12). R´ ady podgrup tedy mohou b´ yt 1, 2, 3, 4, 6, 12 (pogrupa ˇrádu r je generována prvky ˇrádu r). Podgrupa ˇr´ adu 12 je tedy cel´ a grupa generovan´ a prvkem 1 (a grupa (Z12 , +) tud´ıˇz je i cyklická, protoˇze má gener´ ator). Podgrupa ˇr´ adu 1 je zase generov´ ana prvkem 0 (to jsou tzv. trivi´ aln´ı podgrupy, tedy celá grupa a podgrupa generovan´ a jednotkov´ ym prvkem). U tˇech ostatn´ıch mus´ım naj´ıt generátory daného ˇrádu. Znám vˇsak generátor ˇrádu 12, coˇz je jedniˇcka. Z toho uˇz se daj´ı dost jednoduˇse naj´ıt generátory poˇzadovaného ˇrádu: pouˇzit´ım vzorce 3 dopoˇc´ıt´ am ostatn´ı: ˇ ad 2: • R´

12 gcd(12,k)

= 2: k ∈ {6}, a = 1 · 6 ⇒ M2 = {0, 6}

ˇ ad 3: • R´

12 gcd(12,k)

= 3: k ∈ {4, 8}, a = 1 · 4 ∧ 1 · 8 ⇒ M3 = {0, 4, 8}

ˇ ad 4: • R´

12 gcd(12,k)

= 4: k ∈ {3, 9}, a = 1 · 3 ∧ 1 · 9 ⇒ M4 = {0, 3, 6, 9}

ˇ ad 6: • R´

12 gcd(12,k)

= 6: k ∈ {2, 10}, a = 1 · 2 ∧ 1 · 10 ⇒ M6 = {0, 2, 4, 6, 8, 10}

Zad´ an´ı pokraˇcuje: ”Grupy (Z∗13 , ·) a (Z12 , +) jsou izomorfn´ı. Najdˇete nˇejak´ y izomorfismus mezi nimi.” Co to je vlastnˇe ten izomorfismus? Izomorfismus je bijektivn´ı homomorfismus. Super. Takˇze dalˇs´ı otázka: Co to je homomorfismus? Definice 1.1. Homomorfismus je zobrazen´ı φ : A → B mezi dvˇema algebraickými strukturami stejného typu takové, ˇze pro kaˇzdou definovanou operaci f a pro vˇsechna xi v A plat´ı φ(fA (x1 , . . . , xn )) = fB (φ(x1 ), . . . , φ(xn )) Pˇreloˇzeno do ˇceˇstiny, je homomorfismus jakési mapován´ı (zobrazen´ı) mezi dvˇema algebraick´ ymi strukturami, které zachov´ av´ a strukturu. Napˇr´ıklad mnoˇzina pˇrirozen´ ych ˇc´ısel s operac´ı sˇc´ıtán´ı. Funkce, která zachováv´ a sˇc´ıt´ an´ı mus´ı splˇ novat: f (a + b) = f (a) + f (b). Takˇze tˇreba f (x) = 3x je jeden takov´ y homomorfismus, jelikoˇz f (a + b) = 3(a+b) = 3a+3b = f (a)+f (b). Dalˇs´ı pˇr´ıklad m˚ uˇze b´ yt pro grupoid reáln´ ych ˇc´ısel s operac´ı sˇc´ıtán´ı a grupoid kladn´ ych re´ aln´ ych ˇc´ısel s operac´ı n´ asoben´ı. Funkce, která bude zachovávat operace mus´ı tedy splˇ novat f (a + b) = f (a) · f (b), jelikoˇz sˇc´ıt´ an´ı je operace v prvn´ım grupoidu a násoben´ı ve druhém. Tuto vlastnost splˇ nuje napˇr. f (x) = ex : 2 + 3 2 3 5 = 5 se zobraz´ı na e · e = e . U homomorfism˚ u plat´ı, ˇze jestliˇze existuje neutráln´ı prvek, mus´ı b´ yt zachován. Takˇze pro prvn´ı pˇr´ıklad, f (0) = 0, a 0 je netr´ aln´ı prvek v˚ uˇci sˇc´ıt´ an´ı. V druhém pˇr´ıpadˇe, f (0) = 1, jelikoˇz 0 je neutráln´ı v˚ uˇci sˇc´ıtán´ı a 1 v˚ uˇci n´ asoben´ı. Dalˇs´ı pˇr´ıklad, z Velebilov´ ych skript [3], je pro pro grupoid (Z, ·) a (Z4 , 4 ) (násoben´ı modulo 4). Zobrazen´ı [−]4 : Z → Z4, kde [−]4 pˇriˇrazuje kaˇzdému ˇc´ıslu ([−]) ze Z zbytek po dˇelen´ı 4, je homomorfismus. Pokud si totiˇz zkus´ım dosadit p´ ar ˇc´ısel, pak pro [x · y]4 = [x]4 4 [y]4 dostanu [0 · 1]4 = [0]4 4 [1]4

⇒1=1

[50 · 20]4 = [50]4 4 [20]4 | {z } | {z } | {z } 0 2 2 {z } |

⇒0=0

0

(Postup: snaˇz´ım se naj´ıt zobrazen´ı z, které splˇ nuje z(u ⊕1 v) = z(u) ⊕2 z(v)) 7

Kdyˇz se vr´ at´ım k izomorfismu, tak to je tzv. oboustranný homomorfismus. Tud´ıˇz, je to podmnoˇzina homomorfism˚ u. Definice (jen pro pologrupy, monoidy a grupy!) tedy bude podobná jako u homomorfismu, jen mus´ı existovat k zobrazen´ı A → B i inverzn´ı zobrazen´ı B → A. Jako pˇr´ıklad izomorfismu se d´ a (´ uplnˇe mimo od matematiky) oznaˇcit hran´ı kartami. Dejme tomu, ˇze m´ am 52 hrac´ıch karet, jejichˇz 4 barvy (nebo jak se tomu nadává) jsou {♥, ♦, ♠, ♣}. Kdybych si ty 4 barvy oznaˇcil m´ısto toho jako {α, β, γ, }, tak m˚ uˇzu hr´ at u ´plnˇe stejnˇe, jen si mus´ım zapamatovat, ˇze k(α) = ♥ k(β) = ♦ k(γ) = ♠ k() = ♣ Zobrazen´ı k je tedy izomorfismus (neboli struktury se aˇz na oznaˇcen´ı prvk˚ u sobˇe rovnaj´ı). Dalˇs´ı pˇr´ıklad izomorfismu jsou tˇreba logaritmy. Jak do nás hustili uˇz v EO1 a naposledy PARech, násoben´ı se d´ a pomoc´ı logaritmu pˇrevést na sˇc´ıt´ an´ı. Takˇze m´ am dvˇe grupy. Jedna pro násoben´ı (kladn´ ych ˇc´ısel): G1 = (R+ , ·, 1,−1 )2 a druh´ a pro sˇc´ıt´ an´ı: G2 = (R, +, 0, −). Homomorfismus je zobrazen´ı exp : R → R+ , zadáno pˇredpisem x 7→ ex (protoˇze splˇ nuje definici homomorfismu, tedy pro ∀(x, y) : exp(x + y) = ex+y = ex · ey = (exp x) · (exp y)). A je z´ aroveˇ n i izomorfn´ı, protoˇze ln : (R+ , ·, 1,−1 ) → (R, +, 0, −) a inverzn´ı zobrazen´ı je ln−1 = exp: exp : (R, +, 0, −) → (R+ , ·, 1,−1 ). Ted’ uˇz je koneˇcnˇe jasné, co se po mnˇe v poznámce k zadán´ı pˇr´ıkladu vlastnˇe chce. Mám naj´ıt takové zobrazen´ı, které pˇrevede (Z∗13 , ·) na (Z12 , +). Prvk˚ u maj´ı obˇe stejnˇe 12, takˇze to asi nˇejak p˚ ujde. (Z∗13 , ·) je generov´ ana prvkem 2, tedy (Z∗13 , ·) = <2> = {21 = 2, 22 = 4, 23 = 8, 24 = 8, . . . , 212 = 1}. To si m˚ uˇzu pˇredstavit jako zobrazen´ı, které kaˇzdému prvku pˇriˇrad´ı ”jakou je mocninou generátoru 2”, tedy f (a) = f (2k ) = k. To je zˇrejmˇe bijekce (jednoznaˇcné zobrazen´ı, kaˇzd´ y prvek má jednoznaˇcn´ y obraz a naopak) do Z12 . Ted’ mus´ım ovˇeˇrit, ˇze se skuteˇcnˇe jedn´ a o homomorfismus. To znamená, ˇze respektuje binárn´ı operace, neutrály a inverzy se pak podle vˇety z pˇredn´ aˇsky respektuj´ı automaticky: Dejme tomu, ˇze a = 2k , b = 2l jsou prvky ze Z∗13 . f (a · b) = f (2k · 2l ) = k + l = f (2k ) + f (2l ) = f (a) + f (b) Jin´ ymi slovy, n´ asoben´ı mezi vzory (operace v grupˇe, z n´ıˇz zobrazuji), se pˇrevede na sˇc´ıtán´ı mezi obrazy (coˇz je operace v grupˇe, do n´ıˇz zobrazuji). Dostal jsem tedy homomorfismus. Podrobnˇeji viz kapitola 4.

1.10

Pˇ r´ıklad 10

Nejdˇete ˇr´ ady vˇsech prvk˚ u v (Z∗11 , ·). Pˇr´ıklad podobn´ y asi tˇrem minul´ ym, v z´ asadˇe spoˇc´ıvá pouze v nalezen´ı generátoru a pak dopoˇc´ıtán´ı ˇrád˚ u prvk˚ u podle 3. V´ım, ˇze r(1) = 1. Standardnˇe zkouˇs´ım dvojku, která zat´ım vˇzdycky vyˇsla jako generátor a mocn´ım do ϕ(11) = 10: 2 Tohle oznaˇ cen´ı zmamen´ a, ˇ ze grupa je definovan´ a na mnoˇ zinˇ e R+ , s operac´ı n´ asoben´ı, neutr´ aln´ı prvek je 1 a inverzi k prvku x vytvoˇr´ım aplikac´ı x−1

8

21 = 2 22 = 4 23 = 8 24 = 5 25 = 10 26 = 9 27 = 7 28 = 3 29 = 6 210 = 1

Dvojka je gener´ ator (pˇrekvapivˇe), r(2) = 10. Dalˇs´ı generátory budou 2k , kde gcd(k, ϕ(11)) = 1, coˇz jsou {6, 7, 8}. gcd(k = 5, 10) = 2, takˇze r(10) = 5. Zbylé prvky budou m´ıt ˇrád 5, protoˇze moˇzné ˇrády jsou jen ty, co dˇel´ı 10.

1.11

Pˇ r´ıklad 11

V Z21 najdˇete vˇsechna ˇreˇsen´ı rovnice x2 = x. ˇ ınskou vˇetou o zbytc´ıch. Z21 si rozdˇel´ım na Z3 × Z7 a ˇreˇs´ım pro Pˇr´ıklady tohoto typu je asi nejrychlejˇs´ı ˇreˇsit C´ tyto dvˇe grupy: • Z3 : x2 = x ⇒ x ∈ 0, 1 • Z7 : x2 = x ⇒ x ∈ 0, 1 Ted’ si vypoˇc´ıt´ am koeficenty pro vˇetu: −1

q3 = s · 7 = s · 1

[1]3 = 1

=1·7=7 −1

q7 = 3 · s

[3]7 = 15

= 3 · 5 = 15

Vˇsechna ˇreˇsen´ı pak uˇz jen budou vˇsechny kombinace: {0, 1} · 7 + {0, 1} · 15 = {0, 1, 7, 15}.

1.12

Pˇ r´ıklad 12

V Z39 najdˇete vˇsechna ˇreˇsen´ı rovnice x4 = 1. Podobn´ y pˇr´ıklad jako 1.4 a 1.11. Zase rozloˇz´ım 39 na souˇcin prvoˇc´ısel, takˇze Z39 = Z3 × Z13 a ˇreˇs´ım pro obˇe zvl´ aˇst’. Obecnˇe, rovnice xk = 1 v Z∗n m´ a gcd(k, ϕ(n)) = d ˇreˇsen´ı a jsou to prvky ˇrád˚ u r, kde r|d. v Z3

r(x) dˇel´ı ϕ(3): x = 1 ∧ x = −1

v Z13 Rovnice m´ a gcd(4, 12) = 4 ˇreˇsen´ı a jsou to prvky ˇrád˚ u 1, 2, 4. Prvek ˇrádu jedna je jeden, x = 1. Prvek ˇr´ adu dva je taky jeden, a je to (−1) = 12. Prvky ˇrádu 4 jsou dva (= ϕ(4)), a najdu je nejlépe pˇres generátor (tipnu si dvojku):

9

21 = 2 22 = 4 23 = 8 24 = 3 25 = 6 26 = 12 27 = 11 28 = 9 29 = 5 210 = 10 211 = 7 212 = 1 r(2k ) =

12 = 4 ⇒ k = {3, 9} gcd(12, k)

Z toho vypl´ yv´ a, ˇze hledan´ a x jsou 8 a 5. Ted’ v´ ypoˇcet koeficient˚ u: −1

q3 = s · 13 = s · 1

[1]3 = 1

= 1 · 13 = 13 −1

q1 3 = 3 · s

[3]7 = 9

= 3 · 9 = 27 = −12

Vˇsechna ˇreˇsen´ı jsou tedy x = {1, −1} · 13 + {1, 5, 8, 12} · (−12) = {1, 5, 8, 14, 25, 31, 34, 38}.

1.13

Pˇ r´ıklad 13

1. Najdˇete gener´ ator grupy (Z∗37 , ·). Kolik r˚ uzn´ ych prvk˚ u poslouˇz´ı jako generátor v této cyklické grupˇe? 2. Najdˇete vˇsechny prvky ˇr´ adu 6 v grupˇe (Z∗37 , ·). ˇ ste rovnici x30 = 1 v Z37 . 3. Reˇ Moˇznost´ı, jak zvolit gener´ ator je pˇresnˇe tolik, kolik je generátor˚ u vˇsech prvk˚ u nesoudˇeln´ ych s 37. Takov´ ych prvk˚ u je ϕ(37) = 36 a jejich gener´ ator˚ u je ϕ(36) = 12. Zkus´ım tedy naj´ıt generátor ˇrádu 36, coˇz je napˇr´ıklad 2 (tabulku vypisovat nebudu a douf´ am, ˇze to po mnˇe nikdo nikdy nebude cht´ıt). Dále postupuji podle profláknutého vzorce 3: r(2k ) =

36 = 6 ⇒ k = {6, 30} gcd(36, k)

Tud´ıˇz (Z∗37 , ·) m´ a prvky 11 a 27 ˇr´ adu 6. uˇzu ˇreˇsit rovnou v Z37 , protoˇze 37 je prvoˇc´ıslo. Rovnice má gcd(30, 36) = 6 ˇreˇsen´ı a jsou Rovnici x30 = 1 v m˚ prvky ˇr´ ad˚ u dˇel´ıc´ıch 6, tedy r(a) = {1, 2, 3, 6} a to jsou a = {1, 10, 11, 26, 27, 36} (zase podle generátoru a vzorce 3).

1.14

Pˇ r´ıklad 14

Pro RSA ˇsifrov´ an´ı je d´ ano N = 247 a veˇrejn´ y kl´ıˇc t = 11. Spoˇctˇete soukrom´ y kl´ıˇc a deˇsifrujte zprávu b = 147. Pro ˇ ınskou vˇetu o zbytc´ıch. deˇsifrov´ an´ı pouˇzijte C´ V tˇechto typech pˇr´ıklad˚ u je zapotˇreb´ı si zapamatovat pár vzorc˚ u. Je-li t veˇrejn´ y kl´ıˇc, s soukrom´ y, a deˇsifrovan´ a zpr´ ava a b zaˇsifrovan´ a zpr´ ava, pak 10

a = bs v ZN .

(4)

b = at v ZN .

(5)

t · s = 1 v Zϕ(N ) .

(6)

Prvn´ı, co mus´ım udˇelat, je vypoˇc´ıtat rozklad N na prvoˇc´ısla. To udˇelám hrubou silou, testován´ım vˇsech ˇc´ısel od 3. T´ım z´ısk´ am N = 13 · 19. Z toho jednoduˇse vypoˇctu ϕ(N ) = 216 a vyˇreˇs´ım rovnici 6:

11s + 216y = 1 216 = 19 · 11 + 7

7 = 216 − 19 · 11

11 = 1 · 7 + 4

4 = 11 − 1 · 7 = 20 · 11 − 216

7=1·4+3

3 = 7 − 4 = 2 · 216 − 39 · 11

4=3·1+1

1 = 4 − 3 = 59 · 11 − 3 · 216

Z´ıskal jsem s = 59. Ted’ mus´ım odˇsifrovat b, neboli dosadit a vypoˇc´ıtat rovnici 4: a = 14759 v Z247 Tohle vypoˇc´ıt´ am tak, ˇze si rozloˇz´ım Z247 = Z13 × Z19 a poˇc´ıtám pro kaˇzdé zvláˇst’: Pro Z13 :

14759 = 459 = 44·12+11

E−F (2)

→

E−F

411 = 222 = 21·12+10 → 210 = 1024 = 10

E−F

Pro Z19 : 14759 = 1459 = 143·18+5 → 145 . Tohle ˇc´ıslo uˇz bych sice asi nacpal do kalkulaˇcky, ale ve zkouˇsce se stejnˇe p´ıˇse jeˇstˇe ”spoˇc´ıtejte pomoc´ı rezidu´ aln´ıho umocˇ nován´ı”. Takˇze tady jsou opakované ˇctverce, 5 = 1·4+0·2+1·1: 0

1 X

S

S

1 X

Jin´ ymi slovy, rozepsal jsem si 5 do bin´ arn´ı podoby, mezi kaˇzdou ˇc´ıslici jsem vepsal S a tam, kde je jedniˇcka, jsem napsal X. Ted’ to nap´ıˇsu pod sebe (nejlevˇejˇs´ı X je nahoˇre, nejpravˇejˇs´ı dole) a dostanu: X S S X

141 142 144 145

= 14 =6 = 17 = 10

ˇ ınskou vˇetu o zbytc´ıch: V´ ysledek je tedy 14759 = 10 v Z19 . Ted’ vypoˇc´ıtám koeficenty pro C´ −1

q13 = s · 19 = s · 6

[6]13 = 11

= 11 · 19 = 209 = −38 −1

q19 = 13 · s

[13]19 = 3

= 13 · 3 = 39

A v´ ysledek a = −38 · 10 + 39 · 10 = 10.

1.15

Pˇ r´ıklad 15

Pro RSA ˇsifrov´ an´ı je d´ ano N = 247 a veˇrejn´ y kl´ıˇc t = 11. Najdˇete vˇsechny zprávy x, které se po zaˇsifrován´ı nezmˇen´ı, tj. plat´ı xt = x v ZN , pro dané t a N . ˇ ınské vˇety o zbytc´ıch tato Pˇr´ıklad podobn´ y pˇr´ıkladu 1.12. V z´ asadˇe jenom ˇreˇs´ım x11 = x v Z13 a Z19 a pomoc´ı C´ ˇreˇsen´ı nakombinuji. 11

Pro Z13 : Nejdˇr´ıv vydˇel´ım rovnici x a zap´ıˇsu si ˇreˇsen´ı x = 0. Dostanu x10 = 1, pˇriˇcemˇz rovnice má gcd(10, 12) = 2 = d ˇreˇsen´ı, a jsou to prvky ˇr´ adu 1 a 2. Prvek ˇrádu 1 je x = 1, prvek ˇrádu 2 je jen jeden, jelikoˇz grupa ma za z´ aklad prvoˇc´ıslo a je tud´ıˇz cyklick´ a (prvk˚ u ˇr´ adu r, kde r dˇel´ı mohutnost grupy, je právˇe ϕ(r). Takov´ y prvek je -1. Hledan´ a ˇreˇsen´ı jsou tedy x13 = {0, 1, −1} Pro Z19 : Totéˇz jako v pˇredchoz´ım, rovnice má gcd(10, 18) = 2 = d ˇreˇsen´ı, ˇrádu 1 a 2. Hledaná ˇreˇsen´ı jsou tedy x19 = {0, 1, −1} Z minulého pˇr´ıkladu 1.14 zn´ am q13 = −38 a q19 = 39, vˇsechna ˇreˇsen´ı budou jen kombinace −38 · {0, 1, −1} + 39 · {0, 1, −1} = {0, 1, 38, 39, 77, 170, 208, 209, 246}.

1.16

Pˇ r´ıklad 16

Pro RSA ˇsifrov´ an´ı V´ am byla pˇridˇelena prvoˇc´ısla p = 23, q = 59 a veˇrejn´ y kl´ıˇc t = 181. 1. Spoˇctˇete sv˚ uj soukrom´ y kl´ıˇc 2. P´ısmena anglické abecedy k´ odujte dvojˇc´ısl´ımi A = 01, B = 02, . . . Z = 26, mezera = 00. Pos´ıláte zpr´ avu HARD DAY a chcete ji digit´ alnˇe podepsat. Domluvená haˇsovac´ı funkce vybere ze zprávy kaˇzdou pátou ˇc´ıslici ˇ ınskou vˇetu o zbytc´ıch. (poˇc´ıt´ ano zleva). Spoˇctˇete tento podpis a pouˇzijte k tomu C´ Ze zad´ an´ı vypl´ yv´ a, ˇze N = 23 · 59 = 1357. Spoˇcten´ı soukromého kl´ıˇce se ˇreˇs´ı stejn´ ym zp˚ usobem jako v 1.14, zde v Zϕ(N ) = Z22·58 = Z1276 . Po v´ ypoˇctu eukleida vyjde 1 = 141 · 181 − 20 · 1276, tud´ıˇz s = 141. Ted’ mus´ım zak´ odovat HARD DAY do ˇc´ısel: H 08

A 01

R 18

D 04

00

D 04

A 01

Y 25

Haˇsovac´ı funkce je tedy f (a) = 102. Ted’ tenhle podpis mus´ım zaˇsifrovat, coˇz znamená vypoˇc´ıtat f (a)s v ZN = 102141 v Z1357 . ˇ ınskou vˇetou o zbytc´ıch, pro Z23 a Z59 . Nejdˇr´ıv to umocn´ım pomoc´ı reziduáln´ıho umocˇ To se udˇel´ a nejlépe C´ nov´ an´ı: E−F

Pro Z23 : 102141 = 10141 = 106·22+9 → 109 . 9=1·8+0·4+0·2+1·1: 1 X

0 S

0 S 101 102 104 108 109

X S S S X

S

1 X

= 10 =8 = 18 =2 = 20

E−F

Pro Z59 : 102141 = 43141 = 432·58+25 → 4325 . 25 = 1 · 16 + 1 · 8 + 0 · 4 + 0 · 2 + 1 · 1 : 1 X

S

1 X X S X S S S X

0 S

0 S

431 = 43 432 = 20 433 = −25 436 = −24 4312 = −14 4324 = 19 4325 = 50 12

S

1 X

Koeficienty (pro jejich v´ ypoˇcet je jeˇstˇe zapotˇreb´ı 2× e-euklid, ale ˇsetˇr´ım m´ıstem): −1

q23 = s · 59 = s · 13

[13]23 = −7

= −7 · 59 = −413 −1

q59 = 23 · s

[23]59 = 18

= 23 · 18 = 414

Podpis pak bude −413 · 20 + 414 · 50 = 12440 = 227 (v Z1357 ).

13

2

Polynomy nad Zn a koneˇ cn´ a tˇ elesa

2.1

Pˇ r´ıklad 1

V Z2 [x] najdˇete nejvˇetˇs´ı spoleˇcn´ y dˇelitel d(x) polynom˚ u p(x) = x7 + x6 + x5 + x a q(x) = x3 + 1. Polynom d(x) napiˇste jako kombinaci polynom˚ u p(x) a q(x). Postup je takov´ y, ˇze dˇel´ım polynomy, dokud to jde (tzn., dokud nedostanu nulov´ y zbytek) a toto si p´ıˇsu do tabulky podobné euklidovˇe algoritmu. Nejdˇr´ıv tedy ty dva polynomy vydˇel´ım a uvid´ım, co vznikne: x7 +x6 +x5 +x4 +x : (x3 + 1) = x4 + x3 + x2 + 1 −x7 −x4 x6 +x5 +x −x6 +x3 x5 +x3 +x 5 −x +x2 x3 +x2 +x −x3 +1 x2 +x +1 Vid´ım, ˇze mi vznikl nˇejak´ y pod´ıl a nˇejak´ y zbytek po dˇelen´ı. Pokraˇcuji dál: p(x)

q(x)

z }| { z }| { x7 + x6 + x5 + x4 + x = (x3 + 1)(x4 + x3 + x2 ) + (x2 + x + 1) q(x) = (x + 1)(x2 + x + 1) + 0 Zde (x + 1) vzniklo jako pod´ıl (x3 + 1) : (x2 + x + 1). Z toho je jasnˇe viditelné, ˇze gcd je d(x) = (x2 + x + 1) a d(x) = p(x) − (x4 + x3 + x2 ) · q(x) (v dané soustavˇe je + totéˇz co −, takˇze z´ aroveˇ n d(x) = p(x) + (x4 + x3 + x2 ) · q(x)).

2.2

Pˇ r´ıklad 2

Najdˇete vˇsechny ireducibiln´ı polynomy p´ atého stupnˇe v Z2 [x] a dokaˇzte, ˇze jsou ireducibiln´ı. Polynomy p´ atého stupnˇe v Z2 [x] budou vˇzdy tvaru a · x5 + b · x4 + c · x3 + d · x2 + e · x + f · 1 Jelikoˇz polynom s nulov´ ym absolutn´ım ˇclenem má koˇren 0, pak absolutn´ı ˇclen mus´ı b´ yt roven 1. Dál v´ım, ˇze mus´ı m´ıt lich´ y poˇcet nenulov´ ych ˇclen˚ u, jelikoˇz kdyby mˇel sud´ y, tak by ˇreˇsen´ım byla jedniˇcka (protoˇze (1 + 1) = 0). T´ım jsem vyˇcerpal vˇsechny moˇznosti, jak ˇreˇsen´ı osekat a nastává ˇcas na BruteForceTM . K ireducibiln´ım polynom˚ um se m˚ uˇzu chovat podobnˇe jako k prvoˇc´ısl˚ um. Tˇreba na to, abych dokázal, ˇze 5 je prvoˇc´ıslo, mi staˇc´ı vyzkouˇset √ 5 . Stejnˇe tak na to, abych zjistil zda-li je polynom ˇrádu n ireducibiln´ı, mi staˇc´ı vyskouˇset ho dˇelit jen ˇc´ısla do polynomu do stupnˇe bn/2c. Tud´ıˇz mus´ım naj´ıt ireducibiln´ı polynomy stupnˇe 1 a 2 (to jsou (x + 1) a (x2 + x + 1)) a zkusit jimi vydˇelit polynom ˇr´ adu 5 (protoˇze polynom ˇrádu 5 m˚ uˇze vzniknout jen jako násobek 1 · 4, 2 · 3, 3 · 2, 4 · 1). Polynomy si pro zkr´ acen´ı nap´ıˇsu jako n-tici (a, b, c, d, e, f ), hned vyˇrad´ım ty se sud´ ym poˇctem ˇclen˚ u a zkus´ım dˇelit (kdyˇz to dˇelitelné dan´ ym polynomem nen´ı, ˇskrtnu ho): • (1, 0, 0, 0, 1, 1): (x + 1), (x2 + x + 1) · (x3 + x2 + 1) 2 (x + 1), (x + x + 1) • (1, 0, 0, 1, 0, 1): 2 • (1, 0, 1, 0, 0, 1): (x + 1), (x + x + 1) 2 • (1, 0, 1, 1, 1, 1): (x + 1), (x + x + 1) • (1, 1, 0, 0, 0, 1): (x + 1), (x2 + x + 1) · (x3 + x + 1) 2 (x + 1), (x + x + 1) • (1, 1, 0, 1, 1, 1): 2 • (1, 1, 1, 0, 1, 1): (x + 1), (x + x + 1)

14

2 • (1, 1, 1, 1, 0, 1): (x + 1), (x + x + 1) V´ ypoˇcet se zase d´ a ponˇekud zkr´ atit, kdyˇz si uvˇedom´ım, ˇze pokud polynom nemá koˇren, pak zaruˇcenˇe nen´ı ani dˇeliteln´ y line´ arn´ım polynomem (ˇc´ımˇz mi v tomto pˇr´ıpadˇe vypadne dˇelen´ı (x + 1)). Ireducibiln´ı polynomy p´ atého stupnˇe v Z2 [x] jsou: x5 + x2 + 1, x5 + x3 + 1, x5 + x3 + x2 + x + 1, x5 + x4 + x2 + 5 4 3 x + 1, x + x + x + x + 1, x5 + x4 + x3 + x2 + 1.

2.3

Pˇ r´ıklad 3

Rozloˇzte polynom p(x) = x7 − x na souˇcin ireducibiln´ıch polynom˚ u v okruz´ıch Z2 [x] a Z7 [x]. V okruhu Z7 [x] je to jednoduché, jelikoˇz v Zp [x] plat´ı: xp − x = x(x − 1) · · · (x − (p − 1)) a polynom x7 − x se d´ a rozloˇzit na x(x − 1)(x − 2)(x − 3)(x − 4)(x − 5)(x − 6) = x(x + 1)(x + 2)(x + 3)(x + 4)(x + 5)(x + 6). V Z2 [x] je to o nˇeco horˇs´ı, protoˇze takov´ y krásn´ y vzoreˇcek nemám. Takˇze mus´ım postupnˇe dˇelit, nejdˇr´ıv xkem a pak postupnˇe ireducibiln´ımi polynomy: x7 + x = x · (x6 + 1) = x · (x + 1)(x5 + x4 + x3 + x2 + x + 1) = x · (x + 1)(x + 1)(x4 + x2 + 1) = x · (x + 1)(x + 1)(x2 + x + 1)(x2 + x + 1)

Ten souˇcin je tedy x · (x + 1)2 (x2 + x + 1)2 .

2.4

Pˇ r´ıklad 4

V Z3 [x] rozloˇzte na souˇcin ireducibiln´ıch polynom˚ u polynom p(x) = x7 + 2x6 + x + 2. x7 + 2x6 + x + 2 si nap´ıˇsu jako x6 (x + 2) + x + 2 = (x6 + 1)(x + 2). Ted’ si vzpomenu na dalˇs´ı krásn´ y vzoreˇcek: Vˇ eta 2.1. (a + b)p = ap + bp nad kaˇzdým tˇelesem charakteristiky p, tedy (x6 + 1) = ((x2 )3 + 1) = (x2 + 1)3 a koneˇcn´ y v´ ysledek je p(x) = (x2 + 1)3 (x + 2).

2.5

Pˇ r´ıklad 5

Najdˇete vˇsechny prvky, které jsou invertibiln´ı v Z3 [x]/(x2 + 2). Spoˇctˇete k nim inverzn´ı prvky. Pˇredevˇs´ım je nutné si uvˇedomit, které vˇsechny prvky m˚ uˇze obsahovat okruh: Zp [x]/q(x) = {[a(x)]|st(a) < st(q)} Jin´ ymi slovy, okruh je mnoˇzina polynom˚ u (+ operace sˇc´ıtán´ı a násoben´ı), které maj´ı stupeˇ n niˇzˇs´ı neˇz q(x). Poˇcet jej´ıch prvk˚ u je pst(q(x)) . Jeˇstˇe jinak se d´ a ˇr´ıct, ˇze je to okruh zbytkov´ ych tˇr´ıd modulo q(x), coˇz je nˇeco jako grupa v Zp , jen prvky nejsou ˇc´ısla, n´ ybrˇz polynomy. Prvn´ı, co mus´ım udˇelat, je zjistit, jestli ten okruh je taky tˇeleso. Pokud je, tak to znamená, ˇze vˇsechny prvky (mimo 0) maj´ı inverz. Takˇze mus´ım udˇelat std::deleni ireducibiln´ımi polynomy. Zkus´ım (x + 1), dostanu p(x) = (x + 1)(x + 2). Takˇze to nen´ı tˇeleso, a inverzy budou m´ıt jen polynomy nesoudˇelné s (x + 1)(x + 2) (obdoba toho, co se dˇelalo u grup, pokud by gcd bylo > 1, pak neum´ım naj´ıt inverz). Prvky okruhu jsou 0, 1, 2, x, x + 1, x + 2, 2x, 2x + 1, 2x + 2: • 0 inverz je asi −∞, zkr´ atka ho nem´ a :-) • 1 → 1−1 = 1

15

• 2 → 2−1 = 2 (poˇc´ıt´ am to jakoby v Zp ) • x → x−1 = x (protoˇze pouˇz´ıv´ am pˇrepisovac´ı pravidlo x2 = −2 ⇒ x2 = 1) • x + 1 - soudˇelné s q(x), nem´ a inverz • x + 2 - soudˇelné s q(x), nem´ a inverz • 2x → 2x−1 = 2x (2x · 2x = 4x2 = 1) • 2x + 1 - soudˇelné s q(x), protoˇze x2 + 2 = (2x + 1) · (2x + 2), nemá inverz • 2x + 2 = 2(x + 1) - soudˇelné s q(x), nemá inverz

2.6

Pˇ r´ıklad 6

Zjistˇete, zda okruh A = Z3 [x]/P (x), kde P (x) = x3 + x2 + x + 2, tvoˇr´ı tˇeleso. Kolik má okruh A prvk˚ u? Necht’ je α koˇren polynomu P (x) v okruhu A. Vypiˇste vˇsechny prvky okruhu A ve tvaru polynom˚ u v promˇenné α a odvod’te pravidla pro pˇrepisov´ an´ı vyˇsˇs´ıch mocnin pˇri násoben´ı. Ovˇeˇrte, zda je α také koˇrenem polynomu Q(x) = 2x4 + x3 + x2 + 1 v okruhu A. Najdˇete inverzn´ı prvek k (2α2 + α + 2) v okruhu A, pokud existuje. Okruh tvoˇr´ı tˇeleso, protoˇze P (x) je ireducibiln´ı, protoˇze je stupnˇe 3 a nemá koˇren: Vˇ eta 2.2. Polynom stupnˇe 2 nebo 3 je ireducibiln´ı pr´ avˇe tehdy, kdyˇz nem´ a koˇren. M´ a pst(P ) = 33 = 27 prvk˚ u (viz pˇr´ıklad 2.5). Pro imagin´ arn´ı koˇren α plat´ı: α3 + α2 + α + 2 = 0. Z toho se daj´ı odvodit pˇrepisovac´ı pravidla pro násoben´ı: α3 = 2α2 + 2α + 1 α4 = α · (2α2 + 2α + 1) = 2α3 + 2α2 + α = 2(2α2 + 2α + 1) + 2α2 + α = 2α + 2 To, jestli je α koˇrenem nˇeˇceho, zjist´ım snadno - za x dosad´ım α a pokud se to zredukuje na 0, je α koˇren. 2α4 + α3 + α2 + 1 = 4α + 4 + 2α2 + 2α + 1 + α2 + 1 = 6α + 3α2 + 6 = 0 Nalezen´ı inverzn´ıho prvku k (2α2 + α + 2) se dá udˇelat dvˇema zp˚ usoby: 1. Vyˇreˇsen´ı rovnice (2α2 + α + 2) · (a · α2 + b · α + c) = 1 pro nalezen´ı a, b, c 2aα4 + 2bα3 + 2cα2 + aα3 + bα2 + cα + 2aα2 + 2bα + 2c = . . . n´ asleduje asi 7 ˇrádk˚ u upravován´ı a dosazován´ı . . . = a(α2 + 1) + b(2α2 ) + c(2α2 + α + 2) α2 : α1 : 1:

a

+2b

a

+2c +c +c

=0 =0 =1

Z toho vypl´ yv´ a jednak to, ˇze inverz je (α2 + α) a také to, ˇze je to zp˚ usob extrémnˇe náchyln´ y na chyby P (x)

R(x)

z }| { z }| { 2. Vyˇreˇsen´ı rozˇs´ıˇreného euklida A(x) (2x2 + x + 2) +B(x) (x3 + x2 + x + 2) = 1

R(x) = P (x) · (2x + 1) + 2x

2x = R(x) − P (x)(2x + 1)

P (x) = 2x · (x + 2) + 2

2 = P (x) − 2x · (x + 2)

Jako gcd mi vyˇsla dvojka, kdyˇz vyn´ asob´ım obˇe strany inverzem k 2 dostanu (nˇeco) +1. V Bezoutovˇe rovnosti tedy na zaˇc´ atku nech´ am na pravé stranˇe 2, aby se mi to lépe vyjadˇrovalo, a nakonec to vynásob´ım 2−1 , abych dostal na pravé stranˇe 1: 16

2 = P (x) − 2x(x + 2) 2 = P (x) − (R(x) − P (x)(2x + 1))(x + 2) 2 = P (x) − R(x)(x + 2) + P (x)(2x2 + 4x + x + 2) 2 = P (x)(1 + 2x2 + 4x + x + 2) − R(x)(x + 2) 2 = P (x)(2x2 + 2x) − R(x)(x + 2) 1 = P (x)(x2 + x) − R(x)(2x + 1) V´ ysledek stejn´ y, postup taky pracn´ y :-)

2.7

Pˇ r´ıklad 7

Zjistˇete, zda okruh B = Z3 [x]/Q(x), kde Q(x) = x3 + x + 2, tvoˇr´ı tˇeleso. Kolik má okruh B prvk˚ u? Vypiˇste vˇsechny prvky okruhu B ve tvaru polynom˚ u v promˇenné x. Najdˇete inverzn´ı prvek k (x2 + 1) a k (x2 + 2x + 1) v okruhu B, pokud existuj´ı (ˇreˇste polynomiáln´ı rovnice). Aby okruh tvoˇril tˇeleso, mus´ı b´ yt Q(x) ireducibiln´ı. Jelikoˇz polynom je stupnˇe 3 a nemá koˇren, pak je ireducibiln´ı; v opaˇcném pˇr´ıpadˇe ireducibiln´ı nen´ı (je reducibiln´ı :-) ). Koˇren má, a to 2, takˇze je je dˇeliteln´ y polynonem (x − 2) = (x + 1): x3 + x + 2 = (x + 1)(x2 + 2x + 2) Ireducibiln´ı nen´ı, a B nen´ı tˇeleso. Okruh B má pst(P ) = 33 = 27 prvk˚ u. Vˇsechny prvky jsou vˇsechny polynomy stupnˇe nejv´ yˇse 2 v Z3 [x]. R(x)

P (x)

z z }| { }| { Inverzn´ı prvek k (x + 1) najdu vyˇreˇsen´ım A(x) (x2 + 1) +B(x) (x3 + x + 2) = 1: 2

R(x) = x · P (x) + 2

2 = R(x) − x · P (x) ⇒ 1 = 2R(x) + x · P (x)

Z toho plyne, ˇze (x2 + 1)−1 = x. R(x)

P (x)

}| { z }| { z Inverzn´ı prvek k (x2 + 2x + 1) najdu podobnˇe: A(x) (x2 + 2x + 1) +B(x) (x3 + x + 2) = 1 R(x) = (x + 1) · P (x) + (x + 1) P (x) = (x + 1)(x + 1) + 0 Jak je vidno, k (x2 + 2x + 1) inverz naj´ıt nedokáˇzu, protoˇze je soudˇeln´ y s Q(x).

2.8

Pˇ r´ıklad 8

Zd˚ uvodnˇete, proˇc je okruh Z2 [x]/(x5 + x2 + 1) tvoˇr´ı tˇeleso. Kolik má prvk˚ u? Najdˇete v tomto tˇelese inverzn´ı prvek k x2 + 1 (ˇreˇste polynomiáln´ı rovnici). Kolik primitivn´ıch prvk˚ u m´ a toto tˇeleso? Naleznˇete nˇejak´ y primitivn´ı prvek. Polynom x5 + x2 + 1 je v Z2 ireducibiln´ı (viz pˇr´ıklad 2.2), okruh je tedy i tˇelesem. Má pst(P ) = 25 = 32 prvk˚ u. P (x)

R(x)

z }| { z }| { Pro nalezen´ı inverzu k (x + 1) mus´ım ˇreˇsit rovnici A(x) (x2 + 1) +B(x) (x5 + x2 + 2) = 1 2

R(x) = P (x) · (x3 + x + 1) + x

x = R(x) − P (x)(x3 + x + 1)

P (x) = x · x + 1

1 = P (x) − x · x

Podle Bezoutovy vˇety dopoˇc´ıt´ am inverz: 17

1 = P (x) − (R(x) − (P (x)(x3 + x + 1))) · x = x · R(x) + P (x)(x4 + x2 + x + 1) Primitivn´ı prvek tˇelesa (F, +, ·, 0, 1) je generátor grupy (F \ {0}, ·, 1), pˇriˇcemˇz takov´ ych primitivn´ıch prvk˚ u je ϕ(m−1), kde m je poˇcet prvk˚ u tˇelesa. Jin´ ymi slovy, primitivn´ı prvek tˇelesa je prvek, jeˇz mi postupn´ ym umocˇ nov´ an´ım dok´ aˇze vytvoˇrit vˇsechny nenulové prvky tˇelesa. Prvek ˇrádu 1 je 1, a jelikoˇz primitivn´ıch prvk˚ u tˇelesa je ϕ(m − 1) = ϕ(31) = 30, tak vˇsechny ostatn´ı (vyjma 0 a 1) mus´ı b´ yt primitivn´ı. Obecnˇe jsou v grupˇe prvky takov´ ych ˇrád˚ u, které dˇel´ı mohutnost grupy - v tomto pˇr´ıpadˇe tedy 1 a 31.

2.9

Pˇ r´ıklad 9

Zkonstruujte tˇeleso GF (16), popiˇste jeho konstruován´ı a odvod’te pˇrepisovac´ı pravidla pro násoben´ı. Naleznˇete ve vaˇsem tˇelese vˇsechny primitivn´ı prvky. Vˇ eta 2.3. Koneˇcné tˇeleso s n prvky existuje pr´ avˇe tehdy, kdyˇz n je mocnina prvoˇc´ısla. Pak existuje pr´ avˇe jedno (aˇz na isomorfismus, tedy pˇreznaˇcen´ı prvk˚ u‘). ’ Toto tˇeleso se naz´ yv´ a Galoisovo a znaˇc´ı se GF (pk ), kde pk je poˇcet jeho prvk˚ u, k je stupeˇ n generuj´ıc´ıho (ireducibiln´ıho) polynomu a n je z´ aklad soustavy grupy Zn . V tomto pˇr´ıpadˇe tedy m´ am tˇeleso GF (24 ) a mus´ım naj´ıt ireducibiln´ı polynom stupnˇe 4 v Z2 . Vyzkouˇs´ım tedy postupnˇe polynomy nemaj´ıc´ı koˇren a nemaj´ıc´ı nulov´ y absolutn´ı ˇclen (rozep´ıˇsu si je podobnˇe jako v pˇr´ıkladˇe 2.2 a jedu): 2 (x + 1), (x + x + 1) • (1, 0, 0, 1, 1): Hned prvn´ı pokus byl u ´spˇeˇsn´ y, polynom x4 + x + 1 je ireducubiln´ı a m˚ uˇzu ho pouˇz´ıt jako generuj´ıc´ı. Pˇrepisovac´ı pravidla budou: α4 = α + 1 α5 = (α4 + 1) · α = α2 + α Co se t´ yˇce primitivn´ıho prvku, plat´ı pravidla z pˇr´ıkladu 2.8, tedy primitivn´ıch prvk˚ u je ϕ(16 − 1) = 8. Tyto prvky budou evidentnˇe ˇr´ adu 15. Zp˚ usob, jak takov´ y prvek naj´ıt je obdobn´ y tomu, co jsem dˇelal v prvn´ı ˇcásti, napˇr. pˇr´ıkladu 1.6. Zkus´ım tˇreba koˇren α: 4α1 = α1 α2 = α2 4α3 = α3 α4 = α + 1 4α5 = α2 + α α6 = α3 + α2 α7 = α4 + α3 α8 = α2 + 1 α9 = α3 + α α10 = α2 + α + 1 α11 = α3 + α2 + α α12 = α3 + α2 + α + 1 α13 = α3 + α2 + 1 α14 = α3 + 1 4α15 = 1 Poˇcet prvk˚ u grupy je T \ {0} = 15, a jak v´ım, tak ˇrády prvk˚ u mus´ı dˇelit ˇrád grupy - v tomto pˇr´ıpadˇe tedy ty ˇr´ ady mohou b´ yt 1, 3, 5 a 15. Z toho vypl´ yvá, ˇze jen pro rozhodnot´ı, zda-li je dan´ y prvek generátor, mi ho staˇc´ı umocnit na tyhle ˇr´ ady (oznaˇceny 4). Ty ostatn´ı se mi pak ale taky budou hodit. Evidentnˇe α je hledan´ y gener´ ator, dalˇs´ı najdu pomoc´ı vzorce 3: 18

r(ak ) =

r(a) 15 ⇒ = 15 ⇒ gcd(15, k) = 1 gcd(r(a), k) gcd(15, k)

Hledané primitivn´ı prvky jsou tedy {α, α2 , α4 , α7 , α8 , α11 , α13 , α14 } = {α, α2 , α + 1, α4 + α3 , α2 + 1, α3 + α2 + α, α3 + α2 + 1, α3 + 1}.

2.10

Pˇ r´ıklad 10

Okruh komplexn´ıch ˇc´ısel nad Zp je mnoˇzina Kp = {a + bı, kde a, b ∈ Zp } s operacemi sˇc´ıtán´ı a násoben´ı jako u komplexn´ıch ˇc´ısel, tj. ı2 = −1. Dokaˇzte, ˇze okruh komplexn´ıch ˇc´ısel nad Z7 tvoˇr´ı tˇeleso, zat´ımco okruh komplexn´ıch ˇc´ısel nad Z5 tˇeleso netvoˇr´ı. (N´ avod: Najdˇete izomorfismus na nˇejak´ y faktorov´ y okruh okruhu polynom˚ u nad Zp .) Najdˇete ˇr´ ady prvk˚ u ı, ı + 1 a ı + 2 v multiplikativn´ı grupˇe tˇelesa K7 . Je nˇekter´ y z nich primitivn´ım prvkem v tˇelese K7 ? N´ avod smˇeˇruje na pouˇzit´ı n´ asleduj´ıc´ı vˇety: Vˇ eta 2.4. Faktorový okruh Zp [x]/q(x) je tˇelesem pr´ avˇe tehdy, kdyˇz polynom q(x) je ireducibiln´ı polynom nad Zp . Jin´ ymi slovy, pokud dok´ aˇzu naj´ıt izomorfismus na faktorov´ y okruh polynom˚ u, tak k rozhodnut´ı, jestli je dan´ a vˇec tˇeleso ˇci nikoliv mi pak jen staˇc´ı otestovat, zda-li je q(x) ireducibiln´ı v Z5 a Z7 . Podle zad´ an´ı je sˇc´ıt´ an´ı definov´ ano n´ asledovnˇe: (aı + b) + (cı + d) = (a + c)ı + (b + d) a n´ asoben´ı jako (aı + b) · (cı + d) = ac |{z} ı2 +(ad + bc)ı + bd = (ad + bc)ı + (bd − ac) =−1

Kdyˇz se na n´ asoben´ı pod´ıv´ am poˇr´ adnˇe, tak mˇe m˚ uˇze napadnout, ˇze to, co dˇelám, je vlastnˇe násoben´ı modulo x2 + 1 (na to by se asi dalo pˇrij´ıt tak, ˇze si ˇreknu, ˇze x = ı a x2 + 1 = 0): (ax + b) · (cx + d) = (acx2 + (ad + bc)ı + bd) mod (x2 + 1) = (ad + bc)x + (bd − ac) Hledan´ y izomorfismus je tedy Zp [x]/x2 + 1 (ovˇsem jak se tohle dá dokázat podle definice od Demlové fakt netuˇs´ım). Dalˇs´ı, v z´ asadˇe trivi´ aln´ı z´ aleˇzitost, je zjistit, jestli je x2 + 1 ireducibiln´ı v Z5 . Má koˇren 2 a 3, takˇze (x2 + 1) = (x + 2)(x + 3) v Z5 . V Z5 tedy ireducibiln´ı nen´ı, zat´ımco v Z7 uˇz koˇren nemá - tady ireducibiln´ı je. Co se t´ yˇce ˇra´d˚ u prvk˚ u v grupˇe, tak ty dˇel´ı poˇcet prvk˚ u v grupˇe. Poˇcet prvk˚ u v grupˇe K7 − {0} (neboli vˇsechny kombinace ax + b, kde pro a m´ am 7 moˇznost´ı a pro b taky 7 moˇznost´ı) je 72 − 1 = 48 prvk˚ u, ˇrády mohou b´ yt 1, 2, 3, 4, 6, 8, 12, 16, 24, 48. V Z7 : ı1 = ı

(ı + 1)1 = ı + 1

(ı + 2)1 = ı + 2

ı2 = −1

(ı + 1)2 = 2ı

(ı + 2)2 = 4ı + 3

ı3 = −ı

(ı + 1)3 = 2ı + 5

(ı + 2)3 = 4ı + 2

ı4 = 1

(ı + 1)4 = 3

(ı + 2)4 = 3ı

(ı + 1)6 = 6ı

(ı + 2)6 = 2ı + 2

(ı + 1)8 = 2

(ı + 2)8 = 5

(ı + 1)12 = 6

(ı + 2)12 = ı

(ı + 1)16 = 4

(ı + 2)16 = 4

(ı + 1)24 = 1

(ı + 2)24 = 6 (ı + 2)48 = 1

Z toho vypl´ yv´ a, ˇze (ı + 2) je primitivn´ı prvek; r(ı + 2) = 48, r(ı + 1) = 24 a r(ı) = 4. 19

2.11

Pˇ r´ıklad 11

Rozloˇzte polynom f (x) = x4 + 2x2 + x + 1 na souˇcin ireducibiln´ıch polynom˚ u nad Z3 a potom na tˇelesem GF (27), které si pro tento u ´ˇcel vhodnˇe zkonstruujte. Nejdˇr´ıv zkus´ım vydˇelit polynom f (x) ireducibiln´ımi polynomy niˇzˇs´ıch stupˇ n˚ u, zaˇcnu polynomem (x + 1): f (x) = (x + 1)(x3 + 2x + 1) A pr´ avˇe jsem dostal rozklad f (x), jelikoˇz polynom (x3 + 2x + 1) nemá koˇren, a pokud polynom stupnˇe 2 ˇci 3 nem´ a koˇren, tak je ireducibiln´ı. T´ım jsem z´ıskal takov´ y pˇekn´ y ireducibiln´ı polynom, vhodn´ y jako základ tˇelesa GF (27): GF (27) = GF (33 ) = 3 Z3 [x]/x + 2x + 1. Vˇ eta 2.5. Prvek a ∈ K je koˇren polynomu p(x), pokud plat´ı rovnost p(a) = 0. Takˇze m˚ uˇzu zkouˇset koˇreny 1, 2, α . . . a pokud to po dosazen´ı dá jako v´ ysledek 0, je to koˇren, vydˇel´ım j´ım f (x) a jedu d´ al. ´ sledky dr. Gollove ´! FIXME: Nesed´ı s vy

20

3

Line´ arn´ı a cyklick´ e k´ ody

3.1

Pˇ r´ıklad 1

 2 Line´ arn´ı k´ od K nad Z3 délky 5 m´ a generuj´ıc´ı matici G = 2 0

2 0 2

0 2 2

1 2 0

 2 2 . 0

a) Zak´ odujte informaci a ¯ = (102) pomoc´ı matice G. Spoˇctˇete systematickou generuj´ıc´ı matici GS kódu K a opˇet zak´ odujte informaci a ¯ = (102) pomoc´ı systematické matice GS . b) Spoˇctˇete kontroln´ı matici H k´ odu K a zkontrolujte, zda je slovo v¯ = (12201) kódové. c) Dek´ odujte v¯ za pˇredpokladu, ˇze bylo pouˇzito systematické kódován´ı, a potom za pˇredpokladu, ˇze bylo pouˇzito k´ odov´ an´ı pomoc´ı matice G.

a) K´ odov´ an´ı se prov´ ad´ı pomoc´ı vzorce w ¯=a ¯·G

(7)

  2 2 0 1 2 Zde tedy w ¯ = (102) · 2 0 2 2 2 = (1 · 2 + 0 · 2 + 2 · 0, 1 · 2 + 0 · 0 + 2 · 2, 1 · 0 + 0 · 2 + 2 · 2, 1 · 1 + 0 · 0 2 2 0 0 2 + 0 · 0, 1 · 2 + 0 · 2 + 2 · 0) = (2, 6, 4, 1, 2) = (2, 0, 1, 1, 2) Pˇrevést matici na systematickou matici znamená udˇelat z n´ı Gaussovou eliminac´ı matici typu G = ( E B ), kde E je jednotkov´ a matice. Takˇze hur´ a do toho:



2

2

0

1

 2 0

0

2

2

2

2

0

    2 1 1 0 2 1 1 1 0 2 1      − + ∼  0 2 1 2 0 ← −+ 2 | · 2 ∼ 1 0 1 1 1 ← 2 0 1 1 0 0 0 | ·2 0 1 1 0 0     1 1 0 2 1 ← −+ 1 0 0 0 1     2 2 ∼ 0 1 0 2 0 (= GS ) ∼ 0 1 0 2 0 0 0 1 1 0 0 1 1 0 0 ←−−−− + 2



| ·2

Systematické zak´ odov´ an´ı znamen´ a vypoˇc´ıtat w ¯S = a ¯ · GS = (10221) (prvn´ı tˇri ˇc´ıslice m˚ uˇzu opsat, d´ıky jednotkové matici). b) Kontroln´ı matici vypoˇc´ıt´ am podle n´ asleduj´ıc´ı vˇety: Vˇ eta 3.1. Je-li generuj´ıc´ı matice GS systematick´ a tvaru GS = ( E B ), pak kontroln´ı matice H je rovna H = ( −BT E ), kde E je jednotkov´ a matice ˇr´ adu n − k. K´ od K m´ a k informaˇcn´ıch znak˚ u a n − k kontroln´ıch - napˇr. tenhle kód má 3 informaˇcn´ı znaky a 2 kontroln´ı (n je délka k´ odu, ze Znp , v tomhle pˇr´ıpadˇe Z53 ).   0  H = ( −BT E ) = − 2 1

T 1 1 0 0 0

 0  0 = 1  2

1 0

2 0

1 0

0 1

Kontrola spr´ avnosti slova se prov´ ad´ı pomoc´ı v´ ypoˇctu syndromu s¯T = H · v¯T

21

(8)

Pokud je syndrom nulov´ y, pak je v¯ k´ odové slovo. V tomhle pˇr´ıkladu to vycház´ı   1 2  0 1 2 1 0  2 = (6, 3) = (0, 0) = o¯. s¯T = H · v¯T = ·  2 0 0 0 1   0 1 Slovo je k´ odové. c) Dek´ odov´ an´ı je v pˇr´ıpadˇe systematického kódován´ı jednoduché, jednoduˇse vezmu informaˇcn´ı znaky: v¯ = ( 122 01), slovo je a ¯S = (122). Obecnˇe je to troˇsku sloˇzitˇejˇs´ı, mus´ım naj´ıt souˇradnice kódového slova v¯ v˚ uˇci bázi v G. To znamen´ a vyˇreˇsit soustavu n rovnic o k nezn´ am´ ych, (12201) = a1 · (22012) + a2 · (20222) + a3 (02200). 2a1 2a1

+2a2 2a2 +2a2 +2a2

a1 2a1

=1 =2 =2 =0 =1

+2a3 +2a3

Od posledn´ıho ˇr´ adku m˚ uˇzu odeˇc´ıst pˇredposledn´ı, vyjde mi a1 = 1. Pak uˇz staˇc´ı jen dosazovat, a2 = 1, a3 = 0. Tedy slovo a ¯ = (110). Trochu vˇetˇs´ı problém by nastal, kdyby základ soustavy nebylo prvoˇc´ıslo, protoˇze bych pak nemohl pouˇz´ıt Gaussovu eliminaci, ale musel bych to poˇc´ıtat pˇres inverzn´ı matici a matici doplˇ nk˚ u.

3.2

Pˇ r´ıklad 2

Je d´ ana kontroln´ı matice line´ arn´ıho k´ odu K nad Z7 , H =

1 0

2 2

2 3

0 6

4 . 1

a) Kolik informaˇcn´ıch a kolik kontroln´ıch znak˚ u má kód K? Kolik je kódov´ ych slov v K? b) Spoˇctˇete systematickou generuj´ıc´ı matici a zakódujte pomoc´ı n´ı informaci a ¯ = (a1 . . . ak ), kde ai = 2 pro vˇsechna i = 1, . . . , k. c) Slovo v¯ = (13360) bylo zak´ odov´ ano systematicky. Ovˇeˇrte, zda je bez chyby, pˇr´ıpadnou chybu opravte a dek´ odujte (Pˇredpokl´ ad´ ame, ˇze chyba je nejv´ yˇse jedna).

a) Kontroln´ı matice nen´ı urˇcena jednoznaˇcnˇe, a proto ani generuj´ıc´ı matice nem˚ uˇze b´ yt urˇcena jednoznaˇcnˇe. Nicménˇe vˇzdy plat´ı, ˇze m´ a vˇzdy n sloupc˚ u a jej´ı hodnost je n − k. Takˇze zadan´ y kód má 5 znak˚ u, 2 kontroln´ı a 3 informaˇcn´ı. Dejme tomu, ˇze m´ am b´ azi (β1 . . . βk ) kódu K. Potom libovolné kódové slovo lze právˇe jedn´ım zp˚ usobem vyj´ adˇrit jako line´ arn´ı kombinaci a1 β1 + a2 β2 + . . . + ak βk , pˇriˇcemˇz koeficienty ai vol´ım nezávisle p (v Zp ) zp˚ usoby. Takˇze existuje celkem p · p · p . . . ... = pk r˚ uzn´ ych lineárn´ıch kombinac´ı. Neboli poˇcet slov je 73 . b) Spoˇc´ıt´ an´ı systematické generuj´ıc´ı matice z H je obrácená aplikace vˇety 3.1, lépe ˇreˇceno vzorce H = ( −BT E ). Postup je takov´ y, ˇze si tu kontroln´ı matici pˇrevedu do tvaru, kdy na konci bude jednotková matice a pak pomoc´ı tohohle vzorce z´ısk´ am B. To staˇc´ı uˇz jen dosadit do GS = ( E B ) a mám generuj´ıc´ı matici. H=

1 0

2 2

2 3

0 6

4 1

← −+ 3

∼

B=−

1 0

1 2

2 2

4 3

2 4

 1 GS = 0 0

1 4 0 1 0

4 6 T

0 0 1

0 1

2

| ·2

← −+   5 5 = 5 3 6 3  5 5 5 3 . 6 3

∼

2 2

Zak´ odov´ an´ı slova se ˇr´ıd´ı vzorcem 7, takˇze a ¯ = (222) se zakóduje na w ¯ = (22241). 22

2 4

1 4

1 0

0 1

c) Ovˇeˇren´ı spr´ avnosti slova se ˇr´ıd´ı stejn´ ymi pravidly jako v pˇr´ıkladu 3.1; mus´ım spoˇc´ıtat syndrom, a pokud nebude nulov´ y, tak opravit chybu.   1 3  6 1 2 2 0 4  3 = s¯T = H · v¯T = ·  2 0 2 3 6 1   6 0 Syndrom vyˇsel nenulov´ y, takˇze slovo obsahuje chybu. Pro jej´ı nalezen´ı mus´ım naj´ıt, se kter´ ym sloupcem H je syndrom line´ arn´ı kombinac´ı. Takov´ y sloupec je sloupec tˇret´ı, jelikoˇz 3 · 2 = 6 a 3 · 3 = 2. Dalˇs´ı takov´ y sloupec nen´ı, slovo obsahuje jednu chybu (a v´ıc stejnˇe neum´ım opravit). Chybové slovo e¯ vytvoˇr´ım tak, ˇze si oznaˇc´ım koeficient, kter´ ym jsem vyn´ asobil syndrom tak, abych dostal l-t´ y sloupec v H a tento koeficient nap´ıˇsu na l-té m´ısto v e¯, ostatn´ı koeficienty budou nulové: e¯ = (00300). Ted’ tenhle vektor odeˇctu od pˇrijatého slova a dostanu opravené slovo w: ¯ w ¯ = v¯ − e¯ = (13360) − (00300) = (13060).

3.3

Pˇ r´ıklad 3

Line´ arn´ı k´ od nad Z3 m´ a generuj´ıc´ı matici G =

1 2

0 1

2 . Najdˇete jeho kontroln´ı matici. 2

1 0

a) Opravte slovo v¯ = (1020) za pˇredpokladu, ˇze obsahuje nejv´ yˇse jednu chybu. b) Jak by se dalo slovo v¯ = (1020) opravit, kdyby v nˇem byly právˇe dvˇe chyby? Najdˇete vˇsechna kódov´ a slova, jejichˇz Hammingova vzd´ alenost od v¯ je 2. c) Dokaˇzte, ˇze k´ od (vˇzdy) opravuje jednu chybu. Kontroln´ı matici najdu jedin´ ym krokem GEM 1 0 1 G= 2 1 0

2 2

1

∼

← −+

1 0

0 1

1 1

2 1

a dosazen´ım do H = ( −BT E ): H=

1 − 1

2 1

T

! E

=

2 1

2 2

1 0

0 1

a) Totéˇz co v pˇr´ıkladu 3.2. Nejdˇr´ıv si vypoˇc´ıtám syndrom

s¯T = H · v¯T =

2 1

2 2

1 0

  1 0 0  = 1 . · 1 1 2 0

Vid´ım, ˇze line´ arnˇe z´ avisl´ y je s 2. sloupcem, koeficient je 2. e¯ = (0200), w ¯ = v¯ − e¯ = (1020) − (0200) = (1120). b) Opravit by se s jistotou nedalo, jediné, co o nˇem v´ım, ˇze by se liˇsilo pˇresnˇe ve dvou bitech. To znamen´ a, ˇze jsou to vˇsechna slova s Hammingovou vzdálenost´ı 2. Coˇz jsou {(0000), (2021), (1012)}. c) D˚ ukaz spoˇc´ıv´ a v tom, ˇze ˇz´ adn´ y sloupec H nen´ı násobkem jiného sloupce v H.

3.4

Pˇ r´ıklad 4

ISBN (International Standard Book Number) je lineárn´ı délky 10 nad Z11 , jehoˇz kódová slova splˇ nuj´ı rovnici P10 ˇ ıslo 10 se v tomto kódu znaˇc´ı X, tedy jako ˇr´ımská des´ıtka.) i · v = 0 v Z . (Pozn. C´ i 11 i=1 a) Opravte slovo v¯ = (1020) za pˇredpokladu, ˇze obsahuje nejv´ yˇse jednu chybu. b) Jak by se dalo slovo v¯ = (1020) opravit, kdyby v nˇem byly právˇe dvˇe chyby? Najdˇete vˇsechna kódov´ a slova, jejichˇz Hammingova vzd´ alenost od v¯ je 2. c) Dokaˇzte, ˇze k´ od (vˇzdy) opravuje jednu chybu. Podrobnˇe vysvˇetleno ve Velebilov´ ych skriptech [3], str. 80-82. Staˇcil by copy/paste, tak radˇsi nebudu zapl´ ac´ avat m´ısto. Mimochodem, dokonce je tu Easter Egg - to ISBN maj´ı ”Malé dˇejiny filozofie”. 23

3.5

Pˇ r´ıklad 5

Ovˇeˇrte, zda mnoˇzina slov tvoˇr´ı bin´ arn´ı line´ arn´ı kód. Pokud ano, naleznˇete jeho generuj´ıc´ı matici a) A = {(11111), (11110), (11101), (11100), (00011), (00010), (00001), (00000)} b) B = {(1111), (1110), (1101), (0011), (0010), (0001), (0000)} K´ od je bin´ arn´ı, tzn. z´ aklad soustavy je 2 a mus´ı m´ıt 2k slov - t´ım okamˇzitˇe vypadává moˇznost B), jelikoˇz m´ a jen 7 slov (a tˇreba (0010) + (0011) = (0101) nen´ı kódové slovo). Co se t´ yˇce 1. moˇznosti, tak dalˇs´ı test mus´ı b´ yt ten, zda-li libovoln´ a line´ arn´ı kombinace k´ odov´ ych slov je zase kódové slovo. Evidentnˇe je, protoˇze protoˇze nenajdu slovo, které bych nedostal line´ arn´ı kombinac´ı jin´ ych dvou. Zkus´ım tedy naj´ıt bázi prostoru, tzn. 3 takové vektory (protoˇze 23 ), které mi daj´ı libovolné slovo u = a1 · g1 + a2 · g2 + a3 · g3 , kde an je 0 nebo 1. Nejlepˇs´ı bude naj´ıt takové, které mi daj´ı souˇctem nulov´ y vektor, ale z nichˇz ani jeden nebude nulov´ y. Taková kombinace je jen jedna:   1 1 1 0 0 G = 0 0 0 1 0 . 0 0 0 0 1 Na tuhle matici se d´ a pˇrij´ıt tˇreba tak, ˇze si vezmu vˇsechna kódová slova, nap´ıˇsu si je do matice a nad n´ı provedu GEM. Vypadne mi matice o 3 ˇr´ adc´ıch, coˇz je hledaná G (A je podprostor s báz´ı G).

3.6

Pˇ r´ıklad 6

Line´ arn´ı k´ od délky 4 nad Z3 m´ a generuj´ıc´ı matici G =

2 2

2 0

1 1

1 . 0

a) Vypiˇste vˇsechna k´ odov´ a slova a ovˇeˇrte, ˇze se jedná o cyklick´ y kód. b) Najdˇete generuj´ıc´ı polynom a pomoc´ı nˇej zakódujte informaci a ¯ = (12). c) Najdˇete generuj´ıc´ı matici, kter´ a urˇcuje stejné kódován´ı jako generuj´ıc´ı polynom. Ovˇeˇrte to zak´ odov´ an´ım informace a ¯ = (12) pomoc´ı této matice.

a) K´ odov´ a slova budou vˇsechny kombinace báze, tedy K = {a1 β1 + a2 β2 , ai ∈ Z3 }. Kódov´ ych slov bude pk = 32 (viz pˇr´ıklad 3.2). Ta slova jsou (2211), (2112), (1122), (1221), (0000), (2010), (0102), (1020), (0201). Jak je vidno, pro kaˇzdé slovo existuje v K i jeho cyklick´ y posun ⇒ kód je cyklick´ y. b) Generuj´ıc´ı polynom je nenulov´ y polynom nejniˇzˇs´ıho stupnˇe (= n − k). Takov´ y polynom je tady stupnˇe 2 a z tˇech k´ odov´ ych slov, co jsem si nahoˇre vypsal, jsou takov´ı adepti 2. Já si vyberu (0102), pak g(z) = z 2 + 2 (4) je monick´ y. Zak´ odov´ an´ı (12) znamen´ a vynásobit polynom g(z) polynomem u(z) = 1 + 2z (v Z3 , coˇz je jiné 4 2 3 oznaˇcen´ı pro okruh Z3 [x]/(x − 1)). Takˇze zakódovanˇe v(z) = 2 + z + z + 2z . c) Generuj´ıc´ı matice k´ odu je rovna    G= 

g(z) z · g(z) .. .



 2 + z2 2  ≡ = 2z + z 3 0  k−1 g(z) z

0 2

Zkus´ım zak´ odovat (12) a uvid´ıme, jestli mi vyjde (2112): 2 0 1 0 1 w ¯= · = (2112) 0 2 0 1 2 Vyˇslo, matice urˇcuje stejné k´ odov´ an´ı.

24

1 0

0 1

3.7

Pˇ r´ıklad 7

Cyklick´ y k´ od délky 6 nad Z3 m´ a generuj´ıc´ı polynom g(z) = z 2 + z + 1. a) Kolik informaˇcn´ıch znak˚ u a kolik kontroln´ıch znak˚ u má kód K? Kolik je kódov´ ych slov v K? b) Zak´ odujte pomoc´ı g(z) informaci ze sam´ ych 1, tj. a ¯ = (a1 . . . ak ), kde ai = 1 pro vˇsechna i = 1, . . . , k. c) Najdˇete kontroln´ı polynom a ovˇeˇrte pomoc´ı nˇej, zda je slovo v¯ = (100200) bez chyb. Pokud ano, dek´ odujte.

a) Generuj´ıc´ı polynom m´ a stupeˇ n n − k = 2 (k je poˇcet info-znak˚ u a n délka kódu), a tedy kontroln´ı znaky jsou 2 a informaˇcn´ı znaky jsou 4. K´ odov´ ych slov je pk = 34 . b) Zak´ odov´ an´ı a ¯ = (1111): w(z) = g(z) · a(z) = (z 2 + z + 1)(1 + z + z 2 + z 3 ) = 1 + 2z + 2z 4 + z 5 c) Kontroln´ı polynom h(z) z´ısk´ am jako pod´ıl (z n − 1) : g(z), tedy h(z) = (z 6 − 1) : (z 2 + z + 1) = z 4 + 2z 3 + z + 2. Ovˇeˇren´ı znamen´ a vyn´ asobit h(z) · v(z) v Z3 podle pravidla z 6 = 1 a jako v´ ysledek dostat 0: (z 4 + 2z 3 + z + 3 4 3 2) · (1 + 2z ) = 3z + 6z + 3z + 6 = 0 ⇒ je bez chyb. Dekódován´ı v¯ = (100200) znamená vydˇelit kódové slovo generuj´ıc´ım polynomem: w ¯ = (2z 3 + 1) : (z 2 + z + 1) = 2z + 1 ≡ a ¯ = (1200).

3.8

Pˇ r´ıklad 8

Ovˇeˇrte, ˇze polynom g(z) = 1 + 2z + 2z 2 + z 3 m˚ uˇze generovat cyklick´ y kód délky 6 nad Z3 . a) Zak´ odujte systematicky zpr´ avu a ¯ = (122) pomoc´ı g(z). b) Najdˇete kontroln´ı polynom h(z) a ovˇeˇrte, ˇze váˇs polynom je kódov´ y. c) Naleznˇete systematickou generuj´ıc´ı matici daného kódu a pomoc´ı n´ı opˇet systematicky zakódujte zpr´ avu a ¯ = (122). Aby polynom mohl generovat line´ arn´ı k´ od délky 6 nad Z3 , mus´ı dˇelit generuj´ıc´ı polynom (z 6 − 1) v Z3 beze zbytku. Jelikoˇz (z 6 − 1) : (z 3 + 2z 2 + 2z + 1) = z 3 + z 2 + 2z + 2 (= h(z)), tak g(x) je generuj´ıc´ı polynom. a) Systematické zak´ odov´ an´ı zpr´ avy znamená udˇelat z n´ı polynom takov´ y, kter´ y bude na zaˇcátku stejn´ y jako k´ odové slovo a na konci bude m´ıt nˇejaké kontroln´ı znaky (podobnˇe to bylo v lineárn´ıch kódech, viz. tˇreba pˇr´ıklad 3.1). Aby se prohloubila schizofrenie studenta algebry, tak ted’ uˇz slova nebudou kódovat jako (a1 a2 a3 ) ∼ (a1 · z 0 + a2 · z 1 + a3 · z 2 ), jak tomu bylo v pˇr´ıpadˇe cyklick´ ych nesystematick´ ych kód˚ u, ale pro zmˇenu jako (a1 a2 a3 ) ∼ (a1 · z 2 + a2 · z 1 + a3 · z 0 ). Zak´ odovanou zpr´ avu vytvoˇr´ım tak, ˇze si vytvoˇr´ım polynom s nejvˇsˇs´ımi koeficienty na zaˇcátku, tedy v tomto pˇr´ıpadˇe (122) jako (z 5 + 2z 4 + 2z 3 ) a tenhle polynom vydˇel´ım polynomem generuj´ıc´ım. T´ım z´ıskám nˇejak´ y zbytek po dˇelen´ı, kter´ y odeˇctu od pos´ılaného polynomu. Takˇze: (z 5 + 2z 4 + 2z 3 ) : (z 3 + 2z 2 + 2z + 1) = z 2 , zbytek r(z) = 2z 2 w(z) = v(z) − r(z) = z 5 + 2z 4 + 2z 3 + z 2 b) Kontroln´ı polynom h(z) uˇz jsem naˇsel na zaˇcátku, ovˇeˇren´ı znamená vynásobit h(z) · w(z) = (z 3 + z 2 + 2z + 2) · (z 5 + 2z 4 + 2z 3 + z 2 ) = 0, m˚ uj polynom je kódov´ y.

25

c) Systematickou generuj´ıc´ı matici daného kódu najdu u ´plnˇe stejn´ ym postupem jako v pˇr´ıkladu 3.6. Nejdˇr´ıv si mus´ım uvˇedomit, jak z´ısk´ am k. Dr. Gollová pouˇz´ıvá nˇejak´ y sofistikovan´ y v´ ypoˇcet, já postupuji systémem Kouknu a vidimTM : generujc´ı polynom je nejniˇzˇs´ıho stupnˇe, jak´ y se v tom kódu vyskytuje, a ten stupeˇ n je roven n − k = 3. Evidentnˇe n − (n − k) = k, takˇze n − 3 = k ⇒ n = 6, k = 3 (ono je to u ´plnˇe jasné, pokud si ˇclovˇek uvˇedom´ı, ˇze pokud se vyuˇz´ıvaj´ı jen znaky od 3 a v´ yˇs, protoˇze nejmenˇs´ı polynom je z 3 . . . tak ty k´ odovˇe nevyuˇzité znaky ˇr´ adu 0, 1, 2 se pouˇzij´ı na kontroln´ı znaky). 

g(z) z · g(z) .. .



 3   z + 2z 2 + 2z + 1 1     4  G=  = z + 2z 3 + 2z 2 + z  ≡ 0   z 5 + 2z 4 + 2z 3 + z 2 0 k−1 z g(z)

2 1 0

2 2 1

1 2 2

0 1 2

 0 0 1

Tahle matice zrovna moc systematicky nevypadá, takˇze ji jeˇstˇe proˇzenu GEM, abych takovou z´ıskal:

1

2

2

1

0

0



← −+

 0 0

1

2

2

1

 0

1

0

1

2

2

1





0

1

0

1

0

 ← − + ∼ 0 1 0

1

0

1

0

 1

0

1

2

2

1

N´ asleduje zak´ odov´ an´ı a ¯ = (122), coˇz uˇz jsem dˇelal vzorce 7.  1 w ¯=a ¯ · GS = (122) · 0 0

3.9



1

← −+ 2

 1  ∼ 0 0



0

0

1

2

2

1

0

1

0

 1 (= GS )

0

1

2

2

1

minimálnˇe ve tˇrech pˇredchoz´ıch pˇr´ıkladech, a to podle  0 0 1 2 2 1 0 1 0 1 = (122100) 0 1 2 2 1

Pˇ r´ıklad 9

Najdˇete generuj´ıc´ı polynomy vˇsech cyklick´ ych kód˚ u délky 5 nad Z5 . a) Vyberte nˇejak´ y generuj´ıc´ı polynom cyklického kódu délky 5 nad Z5 se 3 informaˇcn´ımi znaky. Najdˇete nˇekterou jeho generuj´ıc´ı matici a nˇekterou jeho kontroln´ı matici. b) Zjistˇete, zda je v¯ = (12221) k´ odové slovo vámi vybraného kódu. Pokud ne, opravte chybu, je-li to moˇzné. Generuj´ıc´ı polynom mus´ı dˇelit polynom (x5 − 1) v Z5 [x]. Jelikoˇz 5 je prvoˇc´ıslo, a tedy to, nad ˇc´ım poˇc´ıt´ am je tˇeleso, tak plat´ı n´ asleduj´ıc´ı vzorec: (a + b)p = ap + bp (x5 −1) si tedy m˚ uˇzu napsat jako (x5 +(−1)5 ), coˇz se podle vzorce rovná (x−1)5 . Ted’ uˇz je pomˇernˇe jednoduché naj´ıt vˇsechny generuj´ıc´ı polynomy: jsou to polynomy (x − 1)i , kde i ∈< 0; 5 >. Jelikoˇz vˇsak polynom (x − 1)0 nem´ a kontroln´ı znaky, a (x − 1)5 zase nem´ a ˇz´ adné informaˇcn´ı, tak netriviáln´ı generuj´ıc´ı polynomy jsou jen tvaru (x − 1)i , kde i ∈ {1, 2, 3, 4}. a) Generuj´ıc´ı polynom se 3 informaˇcn´ımi znaky je g(z) = (z − 1)2 = z 2 − 2z + 1 = z 2 + 3z + 1 (k = 3). Generuj´ıc´ı matici najdu stejnˇe jako minule: 

g(z) z · g(z) .. .



 2   z + 3z + 1 1      3 G=  = z + 3z 2 + z  ≡ 0   z 4 + 3z 3 + z 2 0 k−1 z g(z)

3 1 0

1 3 1

0 1 3

 0 0 1

Pro vytvoˇren´ı kontroln´ı matice mus´ım nejdˇr´ıv naj´ıt kontroln´ı polynom. Ten najdu vydˇelen´ım: h(z) = (z −1)5 : (z − 1)2 = (z − 1)3 = z 3 + 2z 2 + 3z + 4. Kontroln´ı matici pak vytvoˇr´ım tak, ˇze vezmu postupnˇe koeficienty od nejvyˇsˇs´ıho do nejniˇzˇs´ıho ˇr´ adu a p´ıˇsu je do ˇrádk˚ u matice, zaˇcnu vlevo a na kaˇzdém ˇrádku posunu koeficienty o 1 doprava. Zbylé budou 0. Poˇcet ˇr´ adk˚ u je tolik, kolik je kontroln´ıch znak˚ u = 2. 0 1 2 3 4 H= 1 2 3 4 0 26

b) Zjiˇstˇen´ı, zda je v¯ = (12221) k´ odové slovo se provád´ı stejn´ ym zp˚ usobem jako v pˇr´ıkladu 3.2. Nejdˇr´ıv si vypoˇc´ıt´ am syndrom:

s¯T = H · v¯T =

0 1

1 2

2 3

3 4

  1 2  1 4  2 = ·  4 0   2 1

Syndrom je nenulov´ y, a je line´ arn´ı kombinac´ı sloupce 3, s koeficientem e = 2. Tedy e¯ = (00200) a w ¯ = v¯ − e¯ = (12221) − (00200) = (12021).

3.10

Pˇ r´ıklad 10

Najdˇete generuj´ıc´ı polynomy vˇsech bin´ arn´ıch cyklick´ ych kód˚ u délky 5 a napiˇste jejich systematické generuj´ıc´ı matice. Stejn´ y postup jako minule, generuj´ıc´ı polynom mus´ı dˇelit polynom (x5 − 1) v Z2 [x]. Bohuˇzel uˇz tady nem˚ uˇzu pouˇz´ıt ten zupa vzorec, protoˇze polynom m´ a jin´ y ˇrád neˇz je základ soustavy. Takˇze zkus´ım dˇelit ireudicibiln´ımi polynomy: (x5 + 1) = (x + 1)(x4 + x3 + x2 + x + 1) Takˇze jsem naˇsel jeden g1 (x) = (x + 1). Ted’ je otázka, jestli je (x4 + x3 + x2 + x + 1) ireducibiln´ı. Nem´ a koˇren, takˇze zˇrejmˇe uˇz nep˚ ujde vydˇelit (x + 1). Mohl by j´ıt tedy vydˇelit (x2 + x + 1), coˇz je ireducibiln´ı polynom stupnˇe 2. To ovˇsem taky nejde ⇒ g2 (x) = (x4 + x3 + x2 + x + 1). (z + 1)

: 

g(z) z · g(z) .. .





  z+1 0    2   z + z     0 G1 =  = 3 2 ≡  z + z 0   4 3 k−1 1 z + z z g(z)

0 0 1 1

0 1 1 0

1 1 0 0

  1 1 0 0 ∼ 0 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1

 1 1  1 1

Kdyˇz se na to ˇclovˇek pod´ıv´ a, tak se jedn´ a o slova délky 5 se sud´ ym poˇctem jedniˇcek - takˇze jde o paritn´ı k´ od. (x4 + x3 + x2 + x + 1)

: 

g(z) z · g(z) .. .



    G2 =   = z4 + z3 + z2 + z + 1 ≡ 1   z k−1 g(z)

1

1

1

1

Moˇzn´ a slova jsou jen {(00000), (11111)}, tud´ıˇz se jedná o opakovac´ı kód.

3.11

Pˇ r´ıklad 11

Najdˇete cyklick´ y k´ od nad Z3 , jehoˇz kontroln´ı matice má ve sloupc´ıch vˇsechna nenulová slova délky 2 nad Z3 . Najdˇete generuj´ıc´ı polynom tohoto k´ odu. N´ avod: vyuˇzijte tˇeleso GF(9) a jeho primitivn´ı prvek. To tˇeleso GF (9) = GF (32 ), Z3 , st(g(x)) = 2, generuj´ıc´ı polynom tˇreba P (x) = x2 + x + 2 má primitivn´ı prvek napˇr. α = i + 1. Ten mi dok´ aˇze vygenerovat vˇsechny nenulové prvky, které chci (pˇrepisovac´ı pravidlo i2 = 2i + 1):

27

α1 = i + 1 α2 = i + 2 α3 = 2i α4 = 2 α5 = 2i + 2 α6 = 2i + 1 α7 = i α8 = 1 Pˇreps´ ano do matice H: 1 H= 1

1 2

2 0

0 2

2 2

2 1

1 0

0 1

Protoˇze sloupce H jsou uspoˇr´ ad´ any podle mocnin, tak H · v T = oT iff v(α) = 0, aneb kódová jsou pr´ avˇe ta slova, kter´ a maj´ı koˇren α ve vytvoˇreném tˇelese GF (9). Polynom p(x) pouˇzit´ y k vytváˇren´ı tˇelesa má koˇren α a ˇz´ adn´ y polynom niˇzˇs´ıho stupnˇe nem´ a v tˇelese koˇren α (nebot’ pomoc´ı toho α se zapisuj´ı prvky tˇelesa a jsou to vˇsechny polynomy niˇzˇs´ıho stupnˇe neˇz st(p), a nejsou to nuly). Takˇze p(z) je nenulov´ y kódov´ y polynom nejniˇzˇs´ıho stupnˇe, tedy generuj´ıc´ı polynom.

28

4

Homomorfismy a podgrupy You asked me once, what was in Room 101. I told you that you knew the answer already. Everyone knows it. The thing that is in Room 101 is the worst thing in the world. –George Orwell, 1984

4.1

Pˇ r´ıklad 1

Popiˇste obraz libovolného bin´ arn´ıho slova u v homomorfismu ϕ : ({0, 1}∗ , ◦) → (Z12 , +), je-li dáno φ(0) = 3, φ(1) = ∗ 7. (Pozn.: {0, 1} je mnoˇzina vˇsech bin´ arn´ıch slov vˇcetnˇe prázdného a ◦ je zˇretˇezen´ı binárn´ıch slov. Co ˇr´ık´ a to zad´ an´ı je, ˇze chci nˇejaké mapov´ an´ı, nˇejaké zobrazen´ı, funkci, které mi ˇrekne, jakou hodnotu bude m´ıt zˇretˇezen´ı dvou bin´ arn´ıch slov v zadaném homomorfismu. Jinak ˇreˇceno, tupˇe si op´ıˇsu definici 1.1: φ(fA (x1 , . . . , xn )) = fB (φ(x1 ), . . . , φ(xn )) Nejdˇr´ıv zkus´ım, co mi to udˇel´ a po dosazen´ı dvou prvk˚ u: φ(fA (x1 , x2 )) = fB (φ(x1 ), φ(x2 )) φ(x1 ◦ x2 ) = φ(x1 ) + φ(x2 ) φ(0 ◦ 1) = φ(0) + φ(1) |{z} |{z} 3

7

Jak vid´ım, φ(0 ◦ 1) mus´ı m´ıt hodnotu 10. Zkus´ım to teda pro v´ıce hodnot: φ(0 ◦ 0 ◦ 1) = φ(0) + φ(0) + φ(1) | {z } |{z} |{z} |{z} 13

3

3

7

φ(0 ◦ 1 ◦ 1) = φ(0) + φ(1) + φ(1) | {z } |{z} |{z} |{z} 17

3

7

7

Takhle to budu zkouˇset do zblbnut´ı, nebo do té doby, neˇz mi dojde, ˇze ta hodnota na levé stranˇe je 3x poˇcet nul + 7x poˇcet jedniˇcek. Takˇze obraz bin´ arn´ıho slova u je ϕ(u) = 3n + 7j, kde n je poˇcet jeho nul a j je poˇcet jedniˇcek.

4.2

Pˇ r´ıklad 2

Najdˇete vˇsechny grupové homomorfismy f : (Z6 , +) → (Z15 , +) a g : (Z6 , +) → (Z∗15 , ·). Nejdˇr´ıve je nutné si uvˇedomit, co to vlastnˇe hledám: Definice 4.1. Necht’ (G, ·) a (H, ◦) jsou grupy. Zobrazen´ı f : G → H je grupový homomorfismus, pokud pro kaˇzdé a, b ∈ G plat´ı f (a · b) = f (a) ◦ f (b), z´ aroveˇ n f (eG ) = eH a pro kaˇzdé a plat´ı f (a−1 ) = (f (a))−1 . V podstatˇe se jedn´ a o pˇreps´ an´ı definice 1.1. Jin´ ymi slovy, hledám takovou funkci, zobrazen´ı, která mi d´ a stejnou hodnotu na pravé i levé stranˇe rovnice pro libovolné a, b. Co v´ım je, ˇze generátor prvn´ı grupy je <1>, takˇze libovolné x si m˚ uˇzu vyj´ adˇrit jako n·1. Co d´ al v´ım je, ˇze ϕ(0) = 0, podle druhého bodu definice. Oznaˇc´ım si tedy obraz jedniˇcky jako a, neboli ϕ(a) = 1. Ted’ si tyhle informace dosad´ım do definice: ϕ(x) = ϕ(1 + . . . + 1) = ϕ(1) + . . . + ϕ(1) = a · n. | {z } | {z } n

n

29

Neboli jsem dostal ϕ(x) = a · n. Pokud bych mˇel jako zadán´ı naj´ıt homomorfismus Z → Z, tak to m˚ uˇzu oznaˇcit za v´ ysledek pro libovolné x a a, a konˇc´ım. Nicménˇe to nem˚ uˇzu, protoˇze grupy maj´ı pouze omezen´ y poˇcet prvk˚ u. Zkus´ım si to rozepsat:

ϕ(1) = 1a ϕ(2) = 2a ϕ(3) = 3a ϕ(4) = 4a ϕ(5) = 5a ϕ(6) = 6a Problém je, ˇze 6 je totéˇz co 0 v Z6 , neboli ϕ(6) = 6a = ϕ(0) = 0. Nyn´ı tedy mus´ım vyˇreˇsit tuto rovnici: 6a = 0 v Z15 . Tato rovnice m´ a pˇresnˇe 3 ˇreˇsen´ı, jelikoˇz gcd(6, 15) = 3, a jsou to a1 = 0, a2 = 5, a3 = 10. Ted’ uˇz mám koneˇcnˇe hotové ˇreˇsen´ı, a to ϕ1 (x) = 0 · x, ϕ2 (x) = 5 · x, ϕ3 (x) = 10 · x. Jiná ˇreˇsen´ı nejsou, kdybych si napsal tˇreba ϕs (x) = 4x, tak ϕs (6) = 4 · 6 = 24 = 9 6= f (0) = 0 v Z15 . Pro druh´ y homomorfismus budu postupovat podobnˇe, nejdˇr´ıv vyˇreˇs´ım neutráln´ı prvky. T´ım dostanu rovnici ϕ(0) = 1. D´ al postupuji jako minule, gener´ ator v prvn´ı grupˇe je opˇet <1>, ϕ(1) = a: ϕ(x) = ϕ(1 + . . . + 1) = ϕ(1) · . . . · ϕ(1) = an . | {z } | {z } n

n

n

6

Dost´ av´ am tvar ϕ(x) = a . Zb´ yv´ a doˇreˇsit ϕ(6) : ϕ(6) = a = ϕ(0) = 1. Dostávám rocnici a6 = 1 v Z15 , jej´ıˇz vyˇreˇsen´ı v praxi znamen´ a vyˇreˇsit pˇr´ıklad podobn´ y pˇr´ıkladu 1.12: a Rozloˇz´ım 15 na souˇcin prvoˇc´ısel, takˇze Z15 = Z3 × Z5 a ˇreˇs´ım pro obˇe zvláˇst’. Obecnˇe, rovnice xk = 1 v Z∗n m´ gcd(k, ϕ(n)) = d ˇreˇsen´ı a jsou to prvky ˇr´ ad˚ u r, kde r|d. v Z3

M´ a gcd(6, ϕ(3)) = 2 ˇreˇsen´ı, a jsou to prvky ˇrád˚ u 1 a 2 ⇒ x = 1 ∧ x = −1

v Z3 M´ a gcd(6, ϕ(5)) = 2 ˇreˇsen´ı, a jsou to prvky ˇrád˚ u 1 a 2 ⇒ x = 1 ∧ x = −1 Ted’ v´ ypoˇcet koeficient˚ u ˇc´ınské vˇety: −1

q3 = s · 5 = s · 2

[2]3 = 2

= 2 · 5 = 10 −1

q5 = 3 · s

[3]5 = 2

=3·2=6

Vˇsechna ˇreˇsen´ı jsou tedy a = {1, −1} · 10 + {1, −1} · 6 = {1, 4, 11, 14}. Isomorfismy tedy budou 4, a to g1 (x) = 1, g2 (x) = 4x , g3 (x) = 11x , g4 (x) = 14x , x ∈ Z6 .

4.3

Pˇ r´ıklad 3

Najdˇete vˇsechny grupové homomorfismy f : (Z∗9 , ·) → (Z21 , +) a g : (Z∗9 , ·) → (Z∗21 , ·). Pouˇziju stejn´ y postup co minule - nejprve vyˇreˇs´ım neutrály, ˇc´ımˇz dostanu f (1) = 0. Jelikoˇz <2> je gener´ ator 1. grupy, m˚ uˇzu vyj´ adˇrit libovoln´ y prvek x v n´ı jako x = 2n . Homomorfismus tohoto generátoru si tedy nap´ıˇsu jako ϕ(2) = a, a jedu jako motorov´ a myˇs: ϕ(x) = ϕ(2n ) = ϕ(2 . . · 2}) = ϕ(2) + . . . + ϕ(2) = a · n. | · .{z | {z } n

n

30

Neboli tvar homomorfismu je ϕ(x) = ϕ(2n ) = a · n, zb´ yvá naj´ıt, pro která a to plat´ı: ϕ(29 ) = 9a = ϕ(20 ) = ϕ(1) = 0, neboli 9a = 0 v Z21 . ˇ sen´ı jsou gcd(9, 21) = 3, a to a1 = 0, a2 = 7, a3 = 14, v´ Reˇ ysledek ϕ1 (x) = 0 · n, ϕ2 (x) = 5 · n, ϕ3 (x) = 10 · n. kde x = 2n . Druh´ y pˇr´ıklad je ponˇekud zapeklitˇejˇs´ı, ale jeho ˇreˇsen´ı podobné, jako minule. Dejme tomu, ˇze mám homomorfismus ϕ. Protoˇze (Z∗9 , ·) = < 2 >, z hodnoty v bodˇe 2 m˚ uˇzu dopoˇc´ıtat hodnoty vˇsech bodech: je-li ϕ(2) = a, a ϕ(1) = 1, pak ϕ(x) = ϕ(2n ) = ϕ(2| · .{z . . · 2}) = ϕ(2) · . . . · ϕ(2) = an . | {z } n

n

Zb´ yv´ a vyˇreˇsit ϕ(26 ) = a6 = ϕ(20 ) = 1, neboli a6 = 1 v Z∗21 . To splˇ nuj´ı vˇsechny prvky v (necyklické) Z∗21 , takˇze ˇreˇsen´ı je gi (x) = an , kde a ∈ Z∗21 , pro x = 2k ∈ Z∗9 .

4.4

Pˇ r´ıklad 4

Najdˇete podgrupu v grupˇe Z∗19 , kter´ a je izomorfn´ı s grupou Z∗9 . Najdˇete pˇredpis nˇejakého izomorfismu mezi nimi. y poˇcet prvk˚ u jako Z∗9 . Cyklická grupa má ϕ(n) prvk˚ u, takˇze Pro zaˇc´ atek mus´ım naj´ıt podgrupu Z∗19 maj´ıc´ı stejn´ 2 ∗ m´ a ϕ(9) = 3 − 3 = 6 prvk˚ u. V Z19 hledám takové prvky, které maj´ı ˇrád 6 - k tomu mus´ım nejprve naj´ıt gener´ ator, zkus´ım 2:

Z∗9

21 = 2

210 = 7

22 = 4

211 = 5

23 = 8

212 = 1

24 = 7

213 = 2

25 = 5

214 = 4

26 = 1

215 = 8

27 = 2

216 = 7

28 = 4

217 = 5

29 = 8

218 = 1

Dvojka je, jako obvykle, gener´ ator Z∗19 . Nalezen´ı generátoru ˇrádu 6 je uˇz je jednoduché, gcd(18, k) = 18/3 ⇒ k = 3 ∧ k = 12 ⇒ g1 = 8 ∧ g2 = 12. Podgrupa izomorfn´ı s Z∗9 je <8> = <12> = {1, 7, 8, 11, 12, 18}. Nalezen´ı izomorfismu znamen´ a nalezen´ı jakéhosi mapován´ı 1:1 mezi nosn´ ymi mnoˇzinami (viz ˇc´ıslován´ı karet v pˇr´ıkladu 1.9). Takové mapov´ an´ı najdu zˇrejmˇe snadno - na levé stranˇe mám 6 prvk˚ u generovan´ ych 2a , a = h1, 6i, a a na pravé stranˇe m´ am 6 prvk˚ u generovan´ ych 8 , a = h1, 6i (nebo 12 ). Izomorfismus tedy bude 2a ∼ = 8a , neboli a a a a ∗ ϕ(x = 2 ) = 8 (nebo ϕ(x = 2 ) = 12 ), a ∈ Z9 .

4.5

Pˇ r´ıklad 5

Necht’ T je tˇeleso o dev´ıti prvc´ıch. Najdˇete n ∈ N tak, aby multiplikativn´ı grupa (T ∗ , ·) byla izomorfn´ı s grupou (Zn , +). Zkonstruujte nˇejaké GF(9) na napiˇste pˇredpis hledaného izomorfismu.

31

Vˇ eta 4.1. Cyklick´ a grupa ˇr´ adu n je izomorfn´ı s (Zn , +). ˇ ad grupy je 8, jelikoˇz je cyklick´ R´ a a obsahuje vˇsechny prvky tˇelesa vyjma nuly - coˇz je osm prvk˚ u. Proto je izomorfn´ı se (Z8 , +), pˇriˇcemˇz n = 8. Tˇeleso GF(9) jsem uˇz zkonstruoval v pˇr´ıkladu 3.11. T ∗ je cyklick´ a grupa, dvˇe cyklické grupy o stejném poˇctu prvku jsou izomorfn´ı, priˇcemˇz izomorfismus zobraz´ı gener´ ator na gener´ ator (a pak stejné mocniny na stejné mocniny). Zb´ yva u zkonstruovaného tˇelesa naj´ıt primitivn´ı prvek (generator T ∗ ) - tedy (i+1) (viz 3.11) a napsat pˇredpis homomorfismu f : Z8 → T ∗ : f (k) = (i + 1)k .

4.6

Pˇ r´ıklad 6

Necht’ T = Z5 [x]/x2 + x + 1. Kolik prvk˚ u mohou m´ıt podgrupy multiplikativn´ı grupy (T ∗ , ·)? Vypiˇste tabulku pro n´ asoben´ı v nˇejaké tˇr´ıprvkové podgrupˇe a v nˇejaké ˇctyˇrprvkové podgrupˇe. Prvn´ı, co mus´ım zjistit je, jestli je x2 + x + 1 ireducibiln´ı polynom. Zˇrejmˇe je, jelikoˇz nemá koˇren, a polynomy stupnˇe 2 a 3 jsou ireducibiln´ı, kdyˇz nemaj´ı koˇren. T je tedy tˇeleso, a to dokonce GF (25) = GF (52 ). Jak jsem popsal v pˇredchoz´ım pˇr´ıkladu, tak jeho grupa m´ a 25 − 1 = 24 prvk˚ u, a jelikoˇz je i cyklická, tak obsahuje podgrupy ˇr´ ad˚ u d, ˇ ady jsou tedy 1, 2, 3, 4, 6, 8, 12, 24. Proto, abych naˇsel nˇejakou tˇr´ıprvkovou a kde d dˇel´ı 24 (viz. tˇreba pˇr´ıklad 1.8). R´ ˇctyˇrprvkovou grupu, mus´ım naj´ıt nejlépe primitivn´ı prvek tˇelesa grupy, nebo alespoˇ n prvky ˇrádu 3 a 4. Zkus´ım α ⇒ r(α) = 3, prvek dok´ aˇze vygenerovat podgrupu o 3 prvc´ıch, P3 = {1, α, 4α + 4, }. D´ al zkus´ım (α + 1) ⇒ r(α + 1) = 6. Tak zkouˇs´ım (α + 2) ⇒ r(α + 2) = 24, koneˇcnˇe u ´spˇech. Ted’ uˇz mi jen staˇc´ı naj´ıt nˇejak´ y prvek ˇr´ adu 4, tzn. gcd(24, k) = 24/4 ⇒ k = 6 (tˇreba). (α + 2)6 = 3, P4 = {1, 2, 3, 4}. · 1 α 4α + 4

4.7

1 1 α α

α α 4α + 4 α

· 1 2 3 4

4α + 4 4α + 4 1 α

1 1 2 3 4

2 2 4 1 3

3 3 1 4 2

4 4 3 2 1

Pˇ r´ıklad 7

Které z n´ asleduj´ıc´ıch zobrazen´ı fi : K → K, kde K je tˇeleso komplexn´ıch ˇc´ısel nad Z3 , je homomorfismus tˇeles? a) f1 (aı + b) = (aı + b)3 , b) f2 (aı + b) = (aı + b)6 , c) f2 (aı + b) = (aı + b)9 . Tady je nutné ovˇeˇrit, ˇze se jedn´ a tˇelesov´ y homomorfismus, tedy ˇze respektuje sˇc´ıtán´ı, násoben´ı, 0 a 1. Tedy napˇr. zda plat´ı f (a + b) = f (a) + f (b) pro libovolné a, b ∈ K atd. D˚ uleˇzitou roli hraje vzorec (a + b)p = ap + bp v tˇelese charakteristiky p (nedopoˇ c´ıt´ ano). a) (ı + ı)3 = (2ı)3 = −2ı = (ı)3 + (ı)3 = −ı − ı, b) (ı + ı)6 = (2ı)6 = −1 6= (ı)6 + (ı)6 = ı2 + ı2 = −2, c) (ı + ı)9 = (2ı)9 = 2ı = (ı)9 + (ı)9 = 2ı.

32

5

Svazy a Booleovy algebry And now for something completely different.

5.1

Pˇ r´ıklad 1

Je d´ ana mnoˇzina A∗ vˇsech slov nad abecedou A. Na mnoˇzinˇe A∗ je definovaná operace pˇredpisem u v v iff v = wu pro nˇejaké slovo w ∈ A∗ . Rozhodnˇete, zda se jedn´ a o uspoˇr´ ad´ an´ı a zda existuj´ı suprema a infima vˇsech dvojic prvk˚ u z A∗ , pˇr´ıpadnˇe jak se suprema a infima najdou. Co to znamen´ a, kdyˇz se ˇrekne, ˇze relace je uspoˇrádán´ı? To znamená, ˇze relace je reflexivn´ı, antisymetrick´ a a tranzitivn´ı (ve zkratce RAT): Relace v na mnoˇzinˇe A se naz´ yv´ a • reflexivn´ı, jestliˇze pro ∀a ∈ A plat´ı a v a • antisymetrick´ a, jestliˇze pro ∀a, b ∈ A plat´ı: je-li a v b a b v a, pak a = b • tranzitivn´ı, jestliˇze pro ∀a, b, c ∈ A plat´ı: je-li a v b a b v c, pak a v c Ted’ zp´ atky k zad´ an´ı. Co se tu ˇr´ık´ a je, ˇze slovo u je ”menˇs´ı” neˇz v, pokud v má na svém konci ˇcást u (u je suffixem u). Neboli, jeˇstˇe lépe, pokud tˇreba u = 4 a v = 1234, pak u v v. Ted’ vyˇreˇs´ım podm´ınky pro uspoˇr´ ad´ an´ı: • reflexivn´ı: pro ∀a ∈ A plat´ı a v a, tzn. tˇreba 1234 v 1234 ⇒ to je splnˇeno, jelikoˇz pokud w = ∅, pak u = v. • antisymetrick´ a : pro ∀a, b ∈ A plat´ı: je-li a v b a b v a, pak a = b ⇒ to je splnˇeno také. Nedokáˇzu totiˇz naj´ıt dvˇe rozd´ıln´ a slova, pro nˇeˇz by platily obˇe nerovnosti. • tranzitivn´ı: pro ∀a, b, c ∈ A plat´ı: je-li a v b a b v c, pak a v c ⇒ to plat´ı také, znamená to, ˇze a je suffixem jak b, tak i c. Relace je tedy uspoˇr´ ad´ an´ı. Ted’ co je to z´ avora: Definice 5.1. Pokud je mnoˇzina A uspoˇr´ ad´ ana relac´ı v a B je podmnoˇzina A, pak prvek a ∈ A je horn´ı z´ avorou B, pr´ avˇe kdyˇz pro ∀b ∈ B plat´ı b v a. Nen´ı to tedy nutnˇe prvek mnoˇziny, v n´ıˇz hledám horn´ı závoru, a dokonce nemus´ı b´ yt jen jeden, ale m˚ uˇze jich b´ yt v´ıce - tˇreba pro mnoˇzinu re´ aln´ ych ˇc´ısel (0, 1) jsou horn´ı závory napˇr. ˇc´ısla 1, 5, π ad. Doln´ı závora m´ a definici podobnou, pro tu mnoˇzinu jsou doln´ı z´ avory tˇreba ˇc´ısla 0, −1, −π. Definice 5.2. Supremum mnoˇ ziny B je nejmenˇs´ı ze spoleˇcných horn´ıch z´ avor vˇsech prvk˚ u mnoˇziny B, podobnˇe infimem mnoˇ ziny B je nejvetˇs´ı ze spoleˇcných doln´ıch z´ avor vˇsech prvk˚ u mnoˇziny B. Pro ten pˇr´ıklad (0, 1) je tedy supremum = 1, infimum = 0, a stejné supremum/infimum má i h0, 1i. Zpˇet k zad´ an´ı. M´ am zjistit, jestli existuj´ı suprema a infima vˇsech dvojic prvk˚ u. To slovo dvojic je d˚ uleˇzité, jelikoˇz jinak bych hledal supremum nekoneˇcné mnoˇziny. Podstatná vˇec, kterou m˚ uˇzu vyˇc´ıst ze zadán´ı je, ˇze dva prvky nemus´ı b´ yt v˚ ubec porovnatelné - dejme tomu slovo a = 12 a slovo b = 34 - ani jedno nen´ı suffixem druhého, takˇze nem˚ uˇzu rozhodnout, které je menˇs´ı a které vˇetˇs´ı. Pozor vˇsak na to, ˇze aˇc jsou prvky neporovnatelné, jeˇstˇe to neznamen´ a, ˇze nemaj´ı infimum nebo supremum. Dejme tomu, ˇze m´ am dva neporovnatelné prvky, tˇreba 234 a 567. Nejsem schopen naj´ıt jejich spoleˇcnou horn´ı z´ avoru, jelikoˇz pro 234 (kter´ y je menˇs´ı3 neˇz 1234 < 11234 atd.) uˇz nikdy nenajdu stejn´ y prvek, kter´ y by byl z´ aroveˇ n vˇetˇs´ı neˇz 567 (< 1567 < 11567 atd.). Supremum nemohu naj´ıt. V pˇr´ıpadˇe, ˇze jsou prvky porovnatelné, tˇreba 1 a 21, tak nejmenˇs´ı horn´ı z´ avora je prvek 21, neboli ten vˇetˇs´ı z nich. V pˇr´ıpadˇe infima, pokud jsou prvky neporovnatelné, jsem ale st´ ale schopen naj´ıt nejvˇetˇs´ı doln´ı z´ avoru - prázdn´ y ˇretˇezec. Pokud porovnatelné jsou, pak infimum je jejich nejdelˇs´ı spoleˇcn´ y suffix (tˇreba pro 1 a 21 je doln´ı závora 1). 3 Pozor

na znaˇ cen´ı, v p´ısemce je vˇ zdy nutn´ e pouˇ z´ıvat ”v” nam´ısto n´ azornˇ ejˇs´ıho ”≤”

33

5.2

Pˇ r´ıklad 2

Oznaˇcme F mnoˇzinu vˇsech posloupnost´ı {an }∞ rirozen´ ych ˇc´ısel a definujme relaci v takto: n=0 pˇ ∞ {an }∞ avˇe tehdy, kdyˇz 1) a0 = b0 , 2) an ≥ bn n=0 v {bn }n=0 pr´

Ukaˇzte, ˇze (F, v) je uspoˇr´ adan´ a mnoˇzina. Pro které dvojice posloupnost´ı existuje supremum a pro které infimum a jak se utvoˇr´ı? Je (F, v) svaz? Nejdˇr´ıv je zase nutné pochopit zad´ an´ı - jedná se o posloupnosti nekoneˇcnˇe mnoha ˇc´ısel, pˇriˇcemˇz posloupnost je tˇreba {1, 2, 1, 2, . . .}, nebo tˇreba {10, 20, 30, . . .}. D˚ uleˇzité je, ˇze maj´ı stejn´ y poˇcet prvk˚ u (= ∞). Nastáv´ a ot´ azka, jestli se jedn´ a o uspoˇr´ ad´ an´ı: • reflexivita: pro ∀a ∈ A plat´ı a v a, tzn. tˇreba {2, 3, 2, . . .} v {2, 3, 2, . . .} ⇒ to je splnˇeno, a0 = a0 a libovolné an ≥ an . • antisymetriˇcnost: pro a, b ∈ A plat´ı: je-li a v b a b v a, pak a = b ⇒ to taky plat´ı, a0 = b0 a pro kaˇzdé an plat´ı, ˇze je-li an ≤ bn a z´ aroveˇ n an ≥ bn , pak an = bn . • tranzitivita: pro ∀a, b, c ∈ A plat´ı: je-li a v b a b v c, pak a v c ⇒ to plat´ı také, znamená to, ˇze a0 = b0 = c0 a je-li an ≥ bn a bn ≥ cn , pak an ≥ cn . (F, v) je uspoˇr´ adan´ a mnoˇzina. Podle definice je menˇs´ı ta posloupnost, kde kaˇzdé an ≥ bn . Tzn. ˇc´ıslo, které bude urˇcitˇe menˇs´ı neˇz obˇe posloupnosti, mus´ı m´ıt ˇc´ıslo na pozici n vˇetˇs´ı, neˇz jaká jsou an i bn (a pokud to má b´ yt nejvˇetˇs´ı doln´ı z´ avora, pak toto ˇc´ıslo cn = max(an , bn ), coˇz je hledané infimum; u suprema cn = min(an , bn )). Problém nast´ av´ a, pokud ˇc´ıslo na prvn´ı pozici bude jiné v obou posloupnostech - pak totiˇz nemohu nikdy rozhodnout, jestli je nˇekter´ a posloupnost menˇs´ı nebo vˇetˇs´ı, a nem˚ uˇzu ani naj´ıt doln´ı, nebo horn´ı závoru tˇech prvn´ıch ˇc´ısel (m´ am jenom informaci o tom, co se dˇeje, kdyˇz a0 = b0 , ale uˇz ne o tom, co se dˇeje, kdyˇz a0 6= b0 ). Ot´ azka svazu se vyˇreˇs´ı rychle: Definice 5.3. Svaz je uspoˇr´ adan´ a mnoˇzina (A, v), kde pro kaˇzdé a, b ∈ A existuje sup({a, b}) a inf({a, b}). Evidentnˇe (F, v) nen´ı svaz.

5.3

Pˇ r´ıklad 3

Na mnoˇzinˇe M vˇsech bin´ arn´ıch slov délky nejv´ yˇse tˇri je dána relace pˇredpisem u v v iff |u| < |v|, anebo |u| = |v| a ui ≤ vi pro vˇsechna i a) Dokaˇzte, ˇze dan´ a relace je uspoˇr´ ad´ an´ı a nakreslete Hasseho diagram. b) Ovˇeˇrte, ˇze (M, v) tvoˇr´ı svaz (napiˇste, jak naj´ıt supremum a infimum pro libovolnou dvojici prvk˚ u). c) Vyˇsetˇrete vlastnosti daného svazu (tj. zda má nejvˇetˇs´ı a nejmenˇs´ı prvek, zda je distributivn´ı, komplement´ arn´ı ˇci dokonce Booleova algebra). Zde pˇredpokl´ ad´ am, ˇze zavis´ı na poˇctu znak˚ u ve slovˇe, tedy napˇr. ˇze 001 6= 01 a) Hasseho diagram je n´ asleduj´ıc´ı:

34

111B BB || B | | 011B 101B 110 B|B| B|B| || B || B 001B 010 100 BB | B ||| 000 || || 01 B BB B

11 B BB B

00

|| ||

10

1 0 • reflexivita: pro ∀a ∈ A plat´ı a v a, tzn. tˇreba 010 v 010 ⇒ to je splnˇeno, kaˇzd´ y znak je stejn´ y a délka slova se nemˇen´ı. • antisymetriˇcnost: pro a, b ∈ A plat´ı: je-li a v b a b v a, pak a = b ⇒ to také plat´ı. Dvˇe slova, aby se nerovnala, mus´ı m´ıt bud’ jinou délku, nebo rozd´ılné znaky na alespoˇ n jednom m´ıstˇe - pokud toto nen´ı splnˇeno, pak se nutnˇe mus´ı rovnat. • tranzitivita: pro ∀a, b, c ∈ A plat´ı: je-li a v b a b v c, pak a v c ⇒ to plat´ı také, znamená to, ˇze se slova bud’ rovnaj´ı, nebo ˇze m´ a menˇs´ı slovo alespoˇ n na jednom m´ıstˇe menˇs´ı znak a na ˇzádném m´ıstˇe nem´ a vˇetˇs´ı. To plat´ı pro vˇsechna slova, tedy tato relace je tranzitivn´ı. b) Pro kaˇzdou dvojici prvk˚ u existuje supremum a infimum, coˇz je viditelné z Hasseho diagramu. Pokud jsou jejich délky rozd´ılné, pak jejich supremum je ten menˇs´ı prvek z nich, supremum ten vˇetˇs´ı z nich. Pokud jsou jejich délky shodné, pak supremum je slovo sloˇzené z maxim odpov´ıdaj´ıc´ıch dvojic znak˚ u (tˇreba sup(101, 110) = 111) a infimum z jejich minim (sup(101, 110) = 100). Uspoˇrádaná mnoˇzina tvoˇr´ı svaz. c) Svaz m´ a nejmenˇs´ı prvek 0 a nejvˇetˇs´ı 111, coˇz vypl´ yvá z Hasseho diagramu. Aby byl svaz distributivn´ı, nesm´ı obsahovat ani jeden z n´ asleduj´ıc´ıch svaz˚ u jako podsvaz (prvn´ı se naz´ yvá trojlampiónek, L3 , druh´ y pentagon, P5 ): • •G ww GG

G

◦ GG ◦ w ◦

◦

w • ◦4 44 4 w◦ w • Evidentnˇe neobsahuje ani jeden z nich jako podsvaz, tud´ıˇz je distributivn´ı. Komplementárn´ı uˇz vˇsak nikoliv, tˇreba 000 nem´ a komplement. Definice 5.4. Kaˇzdý distributivn´ı a komplement´ arn´ı svaz nazveme Booleova algebra. Svaz nen´ı komplement´ arn´ı, nejedn´ a se o Booleovu algebru.

5.4

Pˇ r´ıklad 4

Na mnoˇzinˇe slov délky dva nad Z3 je definov´ ano uspoˇrádán´ı vztahem u v v iff ui ≤ vi pro vˇsechna i Nakreslete Hasseho diagram a rozhodnˇete podle nˇej, zda se jedná o distributivn´ı nebo komplement´ arn´ı svaz. Pokud svaz nen´ı distributivn´ı, naleznˇete trojici prvk˚ u, na které nen´ı splnˇen distributivn´ı zákon. Pokud svaz nen´ı komplement´ arn´ı, naleznˇete prvek, kter´ y nem´ a doplnˇek Nejdˇr´ıv si nap´ıˇsu, o kter´ a slova se vlastnˇe jedná: 35

00 01 02

10 11 12

20 21 22

Z toho na Hasseho diagram pˇrijdu snadno a rychle: 22 < <<< 12 < 21 < <<< <<< 02 < 11 < 20 << < < << 01 < 10 << < 00 Distributivn´ı evidentnˇe je, neobsahuje L3 ani P5 . Ted’ k problému komplementárnosti. Definice 5.5. Svaz (A, ∨, ∧, v) s nejmenˇs´ım prvkem 0 a nejvˇetˇs´ım prvkem 1 se nazýv´ a komplementárn´ı, jestliˇze kaˇzdý prvek a ∈ A m´ a doplnˇek. Co to znamen´ a, ˇze m´ a prvek doplnˇek? To znamená, ˇze prvek b ∈ A je doplˇ nkem prvku a ∈ A právˇe tehdy, kdyˇz b ∨ a = 1 a b ∧ a = 0. Pom˚ ucka m˚ uˇze b´ yt takov´ a, ˇze to ∨ jakoby ohraniˇcuje prvky zeshora, zat´ımco ∧ je ohraniˇcuje zespoda. Z téhle pom˚ ucky se d´ a vyj´ıt i pˇri urˇcov´ an´ı v´ ysledk˚ u a ∨ b = sup({a, b}) a a ∧ b = sup({a, b}): ∨ je to ”vˇetˇs´ı” (supremum), ∧ je to ”menˇs´ı” (infimum). Pro ty dvˇe operace dál plat´ı ve svazu (A, v) následuj´ıc´ı: (1) idempotence: pro ∀a ∈ A plat´ı a∨a=a a a∧a=a (2) komutativita: pro kaˇzdé dva prvky a, b ∈ A plat´ı a∨b=b∨a a a∧b=b∧a (3) asociativita (nebo taky pˇrez´ avorkov´ an´ı): pro kaˇzdé tˇri prvky a, b, c ∈ A plat´ı a ∨ (b ∨ c) = (a ∨ b) ∨ c a a ∧ (b ∧ c) = (a ∧ b) ∧ c (4) absorbce: pro kaˇzdé dva prvky a, b ∈ A plat´ı a ∨ (b ∧ a) = a a a ∧ (b ∨ a) = a Pokud nˇejak´ a mnoˇzina, nad n´ıˇz jsou definovány operace ∨ a ∧ splˇ nuj´ıc´ı pˇredchoz´ı podm´ınky, pak relace v je uspoˇr´ ad´ an´ı na mnoˇzinˇe A pokud plat´ı a v b pr´ avˇe tehdy, kdyˇz a ∧ b = b (tj. a ∨ b = a). Zp´ atky k problému komplement´ arnosti - aby byl svaz komplementárn´ı, tak mus´ım pro kaˇzd´ y jeho prvek a nalézt doplnˇek, tzn. prvek b takov´ y, ˇze b ∨ a = 1 = 22 a b ∧ a = 0 = 00, neboli, v ˇreˇci uspoˇrádan´ ych mnoˇzin: komplement k a je b iff sup(a, b) = nejvetˇs´ı prvek, inf(a, b) = nejmenˇs´ı prvek Ted’ tedy mus´ım naj´ıt zp˚ usob, jak vytvoˇrit supremum a infimum ke kaˇzdému prvku. To bude stejné jak minule, tedy sup(a, b) = (∀i)(max(ai , bi )) a inf(a, b) = (∀i)(min(ai , bi )), kde ai , bi jsou jednotlivé znaky slov. Co se t´ yˇce komplement´ arnosti, tak ˇreba pro prvek 11 doplnˇek nenajdu, svaz tedy nen´ı komplementárn´ı, a podle definice 5.4 se tedy nejedn´ a ani o Booleovu algebru.

36

5.5

Pˇ r´ıklad 5

(D60 , |) je mnoˇzina vˇsech kladn´ ych dˇelitel˚ u ˇc´ısla 60 uspoˇrádaná podle relace dˇelitelnosti. a) Ovˇeˇrte, ˇze se jedn´ a o svaz a nakreslete jeho Hasseho diagram. b) Vyˇsetˇrete vlastnosti daného svazu (tj. zda má nejvˇetˇs´ı a nejmenˇs´ı prvek, zda je distributivn´ı, komplement´ arn´ı ˇci dokonce Booleova algebra). c) Kter´ a z n´ asleduj´ıc´ıch podmnoˇzin uspoˇr´ adán´ ych podle dˇelitelnosti je podsvaz v (D60 , |)? A = {2, 4, 6, 12}, B = {2, 4, 6, 10, 60}.

a) Nejdˇr´ıve jak ovˇeˇrit, ˇze se jedn´ a o svaz - tady pouˇziju druhou definici svazu, nicménˇe podle té prvn´ı by se to dalo dok´ azat taky (ten vztah x v y, neboli uspoˇrádán´ı, je dˇelitelnost. x v y iff x dˇel´ı y beze zbytku. Jelikoˇz sup=lcm a inf=gcd a jelikoˇz gcd i lcm dvou ˇc´ısel, která dˇelá 60, je opˇet dˇelitelem 60, tak existuj´ı suprema a infima pro kaˇzdou dvojici a je to tedy svaz). Nejdˇr´ıv ale mus´ım vyˇreˇsit problém suprema a infima pro dva prvky. To je nejjednoduˇsˇs´ı urˇcit aˇz pohledem do Hasseho diagramu (HD), kter´ y se vyskytuje o pár odstavc˚ u n´ıˇze - nicménˇe by to ˇslo i bez toho (i kdyˇz sloˇzitˇeji). Vid´ım, ˇze pro dva prvky je supremum ten prvek, kter´ y je ”nahoˇre” v diagramu, a infimum ten, co je ”dole”. Ten, co je nahoˇre, je nejmenˇs´ı spoleˇcn´ y násobek (tedy a ∨ b = lcm(a, b)), ten, co je dole, je nejvˇetˇs´ı spoleˇcn´ y dˇelitel (a ∧ b = gcd(a, b)). (a) idempotence: pro ∀a ∈ A plat´ı a∨a=a a a∧a=a gcd(a, a) = a, lcm(a, a) = a ⇒ plat´ı (b) komutativita: pro kaˇzdé dva prvky a, b ∈ A plat´ı a∨b=b∨a a a∧b=b∧a u gcd i lcm je jedno, jestli je prvek na 1. nebo 2. m´ıstˇe ⇒ plat´ı (c) asociativita (nebo taky pˇrez´ avorkován´ı): pro kaˇzdé tˇri prvky a, b, c ∈ A plat´ı a ∨ (b ∨ c) = (a ∨ b) ∨ c a a ∧ (b ∧ c) = (a ∧ b) ∧ c Neboli lcm(a, lcm(b, c)) = lcm(lcm(a, b), c). D˚ ukaz tohohle je trochu sloˇzitˇejˇs´ı, protoˇze si ˇclovˇek mus´ı uvˇedomit, jak se to lcm vlastnˇe poˇc´ıtá. Poˇc´ıtá se tak, ˇze si rozloˇz´ım ˇc´ıslo na souˇcin prvoˇc´ısel (tˇreba 60 = 22 · 3 · 5 a pro druhé ˇc´ıslo udˇelám totéˇz (tˇreba 4 = 22 ). Pak si nap´ıˇsu tyhlety rozklady pod sebe a lcm(a,b) bude souˇcin prvoˇc´ısel s max. umocnˇen´ım, takˇze dostanu 60 = 4= lcm(60, 4) =

22 · 31 · 51 22 · 30 · 50 22 · 31 · 51 = 60

Co dˇel´ am je, ˇze hled´ am maxim´ aln´ı koeficienty u prvoˇc´ısel - a je u ´plnˇe jedno, jestli to udˇelám nejdˇr´ıv pro 1. a 2. ˇc´ıslo, a pak k tomu najdu 3., nebo v jiném poˇrad´ı. Je to i u ´plnˇe stejn´ y postup, jako bych dˇelal c lcm(a,b,c). Pro gcd to udˇel´ am Hard-Way : Vˇ eta 5.1. Bin´ arn´ı operace gcd je asociativn´ı, tj. pro libovoln´ a pˇrirozen´ a ˇc´ısla a, b, c plat´ı gcd(gcd(a, b), c) = gcd(a, gcd(b, c)). D˚ ukaz. Poloˇz´ım d = gcd(gcd(a, b), c). Co to znamená? To znamená, ˇze (1) d dˇel´ı gcd(a, b) a c a (2) jestliˇze d0 je nˇejaké jiné pˇrirozené ˇc´ıslo, d0 6= d, které dˇel´ı beze zbytku gcd(a, b) a c, pak nutnˇe d > d0 . K tomu, abych dok´ azal asociativitu gcd, mus´ım dokázat, ˇze (1) d dˇel´ı a a gcd(b, c) a (2) jestliˇze d0 je nˇejaké jiné pˇrirozené ˇc´ıslo, které dˇel´ı a a gcd(b, c), potom d > d0 . (1) Jelikoˇz d dˇel´ı gcd(a, b), d mus´ı dˇelit a a b. V´ım, ˇze d dˇel´ı c, tedy d mus´ı dˇelit i gcd(b, c). (2) Pˇredpokl´ ad´ am, ˇze d0 dˇel´ı a a gcd(b, c). Potom d0 dˇel´ı b a c, takˇze d0 mus´ı dˇelit i gcd(a, b). Tedy, podle pˇredpokladu, d > d0 .

37

(d) absorbce: pro kaˇzdé dva prvky a, b ∈ A plat´ı a ∨ (b ∧ a) = a a a ∧ (b ∨ a) = a Neboli lcm(a, gcd(b, a)) = a. Oznaˇc´ım si d = gcd(b, a). Toto ˇc´ıslo d ≤ min(a, b), a ˇc´ıslo a bude n´ asobkem ˇc´ısla d. Pokud si dosad´ım d, tak dostanu lcm(a, d) = a. To je vˇzdy splnˇeno, jelikoˇz a je násobkem d. Ten druh´ y tvar by se dokazoval dost podobnˇe. Vˇsechny ˇctyˇri podm´ınky splnˇeny, jedn´ a se o svaz. Jak nakreslit HD? Jedno z moˇzn´ ych ˇreˇsen´ı (a pˇrekvapivˇe pouˇziteln´ ych) spoˇc´ıvá ve ˇctyˇrech kroc´ıch: (a) Vyps´ an´ı vˇsech prvk˚ u svazu (b) Pro kaˇzd´ y prvek nakreslen´ı jeho jedno´ urovˇ nového Hasseova diagramu pˇr´ım´ ych dˇelitel˚ u, vpravo nejvˇetˇs´ı, vlevo nejmenˇs´ı. Toto dˇelat rekurzivnˇe pro kaˇzd´ y HD kaˇzdého prvku, dokud se nedostanu na prvoˇc´ıslo. Tzn. tˇreba pro prvek 20 to budou prvky 10 a 4, ale uˇz ne tˇreba 10,5,4, protoˇze 5 dˇel´ı 10. Pak znovu nakreslit HD pro 10 a 4. (c) Pospojov´ an´ı tˇechto prvk˚ u do Hasseova diagramu, zase do u ´rovn´ı ˇradit prvky zprava doleva. (d) (Pˇrekreslen´ı diagramu do nˇejaké rozumˇejˇs´ı podoby, která se objev´ı v pˇredchoz´ım bodˇe.) Pro tento pˇr´ıklad tedy (a) (D60 , |) = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60} (b) MiniHD: 60 < <<< 12 20 30

4

129 999

4 2 2

20 < 30 < <<< <<< 6 4 10 6 10 15

6 555

3 2

109 999

5 3

159 999

5

(c) MeziHD: ii 60 BB iiii||| BB i i i BB | ii i | i i BB ii || i i | i ii 12 @ ii 30 BB iii 20 BBB iiii||| BB ~~ @@@ iiiiii i i B i ~ Bi BB || ~~ iiiii@i@@ iiiiBBB BB | i ~ i i | i @ i | i ~i~iiii i i 6 i@ 10 4@ i 15 iii BB @@ iiii|| i ~~ @@@ iiiiii i B i @@ i ~ B || iiBii @@ ii@i@i@ ~~ iiii BBB ||| @ ~~~iiiiiii @ i i i | i ii i5 2 @i 3i @@ ~ iiii iiii @@ ~~ i i ~ i @@ ~ ii @ ~~~iiiiiii i i 1 Posledn´ı krok tady nebyl nutn´ y, ale kdyˇz to ˇclovˇek kresl´ı na pap´ıˇre, tak se obvykle hned netref´ı do takové kr´ asné podoby. b) Nejmenˇs´ı prvek svazu je z HD 0 = 1, nejvˇetˇs´ı 1 = 60. Distributivita se dá dokázat bud’ tak, ˇze v HD nenajdu L3 ani P5 jako podsvaz (coˇz tady opravdu nenajdu). Co je to vlastnˇe podsvaz4 : Definice 5.6. Mˇejme d´ an svaz L = (A, ∨, ∧, v). Mnoˇzinu B ⊆ A nazveme podsvaz svazu L, jestliˇze plat´ı je-li b, c ∈ B, pak b ∨ c, b ∧ c ∈ B. 4 Dr.

Gollov´ a m´ a na cviˇ cen´ı 12/2 naps´ ano, ˇ ze podsvaz je podmmoˇ zina, kde operace ∨, ∧ d´ avaj´ı stejn´ e v´ ysledky. To si mysl´ım nem˚ uˇ ze fungovat, protoˇ ze svaz jako celek je i sv´ ym podsvazem a sup(a, a ¯) nem˚ uˇ ze b´ yt stejn´ e jako inf(a, a ¯).

38

Alternativnˇe, m˚ uˇzu se problém distributivity d´ıvat i takhle: Definice 5.7. Svaz (A, ∨, ∧, v) se nazýv´ a distributivn´ı svaz, jestliˇze pro kaˇzdé tˇri prvky a, b, c ∈ A plat´ı a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c). a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c). Pˇriˇcemˇz staˇc´ı ovˇeˇrovat jen jednu z podm´ınek. Takˇze hur´ a do toho: Vˇ eta 5.2. Svaz (N, lcm, gcd, |) je distributivn´ı, neboli pro kaˇzdé a, b, c ∈ N plat´ı gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c)) D˚ ukaz. Kaˇzdému z ˇc´ısel a, b, c pˇriˇrad´ım celoˇc´ıseln´ y rozklad, tzn. tˇreba a = 23 · 31 · 71 , b = 22 · 32 · 70 . Pak operace ∪ (sjednocen´ı) prvoˇc´ısel odpov´ıdá lcm, operace ∩ (pr˚ unik) odpov´ıdá gcd. Napˇr. lcm = gcd =

23 · 32 · 71 22 · 31 · 70

↔A∪B ↔A∩B

Jelikoˇz operace ∪ a ∩ jsou distributivn´ı, pak i gcd a lcm jsou distributivn´ı. Svaz nen´ı komplement´ arn´ı, protoˇze tˇreba k prvku 2 nejsem schopen naj´ıt doplnˇek. Nen´ı to tedy ani Booleova algebra. c) Pˇri ovˇeˇrov´ an´ı, zda je nˇeco podsvazem, postupuji podle definice 5.6, mus´ım tedy zjistit, zda je pro kaˇzdou dvojici prvk˚ u v´ ysledek operace ∨ a ∧ zase prvkem svazu. U svazu A to je, ale u svazu B nikoliv - tˇreba 4 ∨ 6 = lcm(4, 6) = 22 · 3 = 12 ∈ / B.

5.6

Pˇ r´ıklad 6

Dokaˇzte, ˇze (Dn , |) je Booleova algebra pr´ avˇe, kdyˇz n je square free. (Dn , |) je mnoˇzina vˇsech kladn´ ych dˇelitel˚ u ˇc´ısla n uspoˇr´ adan´ a podle relace dˇelitelnosti. Pˇrirozené ˇc´ıslo je square free, pokud nen´ı dˇelitelné druhou mocninou ˇz´ adného prvoˇc´ısla. Nejdˇr´ıv si mus´ım uvˇedomit, jak funguje lcm a gcd: lcm vezme sjednocen´ı prvoˇc´ısel, gcd vezme jejich pr˚ unik. Kdyˇz chci, abych dostal prvek maxim´ aln´ı, tak mus´ım tˇemi prvky obsadit vˇsechna m´ısta, tzn. tˇreba pokud m´ am (D30 , |), a hled´ am doplnˇek pro a = 15 = 3 · 5, tak mus´ım naj´ıt takové ˇc´ıslo, které mi obsad´ı jeˇstˇe to posledn´ı m´ısto do 30 = 2 · 3 · 5, coˇz je supremum svazu - coˇz je evidentnˇe a ¯ = 2. Podobnˇe infimum, tam zase nesm´ım ˇz´ adn´ ym prvoˇc´ıslem (vyjma 1) obsadit m´ısta pod sebou - takˇze pro a = 15 = 3 · 5 je to zase a ¯ = 2. Kdybych ovˇsem mˇel tˇreba (D60 , |), tak m´ am problém s t´ım, ˇze v prvoˇc´ıselném rozkladu m˚ uˇzu m´ıt i mocniny. Tˇreba pro 60 = 22 · 3 · 5, 1 kdybych hledal doplnˇek k 2 = 2 a snaˇzil se pouˇz´ıt podobn´ y zp˚ usob jako u (D30 , |), tak mám problém, protoˇze 1. m´ısto uˇz bude vˇzdy obsazené 2, a tud´ıˇz nikdy nedoc´ıl´ım toho, aby pr˚ unik tˇech prvoˇc´ıseln´ ych rozklad˚ u byl pr´ azdn´ y. Proto mus´ım zabr´ anit tomu, aby ˇslo libovolné ˇc´ıslo vyjádˇrit jako a = pk11 · . . . · pknn , kde libovolné kn je vyˇsˇs´ı neˇz 1 a toho doc´ıl´ım pouze tehdy, je-li supremum square free.

5.7

Pˇ r´ıklad 7

Ukaˇzte, ˇze v kaˇzdé Booleovˇe algebˇre (B, ∧, ∨, 0, 1,¯) plat´ı: a v b iff a ∧ ¯b = 0.

D˚ ukaz. Jelikoˇz m´ am zadanou ekvivalenci, tak mus´ım dokázat obˇe implikace (tedy ⇒ a ⇐):

39

⇒ Za z´ aklad si poloˇz´ım, ˇze a v b iff a ∨ b = b (vˇeta 4.1.11 z pˇrednáˇsky 10 od Demlové [1]). Pokud obˇe strany rozˇs´ıˇr´ım o (∧¯b), pak upravenˇe dostanu (a ∨ b) ∧ ¯b = b ∧ ¯b = 0. To m˚ uˇzu d´ al rozv´ıjet: 0 = b ∧ ¯b = (a ∨ b) ∧ ¯b = (a ∧ ¯b) ∨ (b ∧ ¯b) = (a ∧ ¯b) ∨ 0 = a ∧ ¯b | {z } 0

Neboli jsem dok´ azal, ˇze a ∨ b = b je totéˇz, co a ∧ ¯b = 0. ⇐ Tady si za z´ aklad poloˇz´ım, ˇze a ∧ ¯b = 0 a snaˇz´ım se z toho dokázat, ˇze nutnˇe a v b. K tomu mi staˇc´ı dok´ azat, ˇze a ∧ b = a (z a v b iff a ∧ b = a). Oznaˇc´ım si levou stranu rovnice jako L = a ∧ b a pravou jako P = a a jedu: P = a = a ∧ 1 = a ∧ (b ∨ ¯b) = (a ∧ ¯b) = (a ∧ ¯b) ∨(a ∧ b) = 0 ∨ (a ∧ b) = a ∧ b = L | {z } a∧¯ b=0

5.8

Pˇ r´ıklad 8

Ukaˇzte, ˇze v distributivn´ım svazu m˚ uˇze m´ıt dan´ y prvek nejv´ yˇse jeden doplnˇek. D˚ ukaz. Pˇredpokl´ ad´ am, ˇze b a c jsou doplˇ nky a. Pak b = b ∧ 1 = b ∧ ( a ∨ }c ) = (b ∧ a) ∨ (b ∧ c) = b ∨ ( a ∧ }b ) ∨ c = | {z | {z | {z } | {z } a∨¯ a =1 a∧¯ a=1 a∧1=a distributivita (b ∧ 1) ∧ c = b ∧ c. Tud´ıˇz b w c, a obdobnˇe, pokud bych zaˇcal s c, bych dostal b v c, a tedy b = c (podle antisymetrie).

Reference [1] Marie Demlov´ a: Algebra pro VT. http://math.feld.cvut.cz/demlova/teaching/avt/predn-avt.html [2] Alena Gollov´ a: Algebra pro v´ ypoˇ cetn´ı techniku. http://math.feld.cvut.cz/gollova/algebra_pro_vt.html [3] Jiˇr´ı Velebil: Diskr´ etn´ı matematika. http://math.feld.cvut.cz/velebil/teaching/y01dma.html

40

dr. Gollové vyjít, se podívat sem. Když si budete ty příklady jen tupě pročítat, tak se naučíte lim 0. Pokud máte

Recommend Documents