Informatyka MIMUW

Wracamy teraz do ciał skończonych. Jedyne ciała skończone jakie poznaliśmy do tej pory to $(\mathbb{Z}_p,+,\cdot,0,1)$, gdzie $p$ jest liczbą pierwszą. Czy istnieją inne ciała skończone? Jaką liczność mogą mieć inne ciała skończone? Czy wszystkie ciała liczności $p$ są izomorficzne z ciałem $\mathbb{Z}_p$? Odpowiedzi na te pytania poznamy w pozostałej części wykładu.

Charakterystyka ciała ${\bf F}=(F,+,\cdot,0,1)$ to rząd elementu $1$ w grupie addytywnej $(F,+,0)$. Oczywiście, jeśli ciało jest skończone to jego charakterystyka też jest skończona. Co więcej, ponieważ rząd elementu musi dzielić rząd grupy, to charakterystyka ciała skończonego ${\bf F}$ dzieli $\vert$.

Przykład

• $(\mathbb{R},+,\cdot,0,1)$ i $(\mathbb{Q},+,\cdot,0,1)$ mają charakterystykę nieskończoną (czasami przyjmuje się $0$),

• charakterystyka $\mathbb{Z}_p$ równa jest $p$, gdyż tyle razy trzeba do siebie dodać $1$, aby otrzymać $0$ w $\mathbb{Z}_p$.

Obserwacja 6.19

Charakterystyka ciała skończonego jest liczbą pierwszą.

Dowód

Dla dowodu nie wprost załóżmy, że charakterystyka pewnego ciała jest liczbą złożoną $n=pq$. Wtedy

$0=(\underbrace{1+\ldots+1}_{n\ razy}) =(\underbrace{1+\ldots+1}_{p\ razy})\cdot(\underbrace{1+\ldots+1}_{q\ razy}).$

Ponieważ $p,q < n$ oba czynniki prawej strony ostatniej równości są niezerowe, to są one dzielnikami zera. Sprzeczność z Obserwacją 6.2.

Obserwacja 6.20

Grupa addytywna dowolnego ciała skończonego ${\bf F}=(F,+,\cdot,0,1)$ jest izomorficzna z $({\mathbf {Z}_p})^k$ dla pewnej liczby pierwszej $p$ i $k\geq 1$. Zatem $\vert=p^k$.

Dowód

Niech ${\bf F}=(F,+,\cdot,0,1)$ będzie ciałem o charakterystyce $p$. Z Obserwacji 6.19, $p$ jest liczbą pierwszą. Niech ${\bf 2},{\bf 3},\ldots,{\bf p-1}\in F$ będą zadane przez

$\begin{align*} {\bf 2} & =1+1, \\ {\bf 3} & =1+1+1, \\ & \ldots & \\ {\bf p-1} & =\underbrace{1+\ldots+1}_{p\ razy}. \end{align*}$

Ponieważ $1$ ma rząd $p$ w grupie $(F,+,0)$, to ${\bf 2},\ldots,{\bf p-1}$ są parami różne. Ponadto zbiór $({\{ {0,1,{\bf 2},\ldots,{\bf p-1}} \} },+,\cdot,0,1)$ jest zamknięty na dodawanie i mnożenie. A zatem jest podciałem ciała ${\bf F}$, i to izomorficznym z ciałem $\mathbb{Z}_p$.

Samo natomiast ciało ${\bf F}$ można traktować jako przestrzeń wektorową nad swoim podciałem $\mathbb{Z}_p$. Zatem, jako taka właśnie przestrzeń wektorowa, ${\bf F}$ jest izomorficzna z $\mathbb{Z}_p^k$, gdzie $k$ jest wymiarem ${\bf F}$ nad $\mathbb{Z}_p$. Stąd w szczególności grupa addytywna ciała ${\bf F}$ jest izomorficzna z produktem $k$ kopii grupy $\mathbb{Z}_p$.

Obserwacja 6.21

Grupa multyplikatywna ciała skończonego jest cykliczna.

Dowód

Niech $(F,+,\cdot,0,1)$ będzie ciałem o $q$ elementach. Jednym z warunków równoważnych cykliczności grupy multyplikatywnej $(F^*,\cdot,1)$ jest to, że

(*)dla każdego $d|q-1$ liczba elementów $f\in F^*$ spełniających $f^d=1$ wynosi $d$.

Ponieważ rząd elementu grupy dzieli rząd grupy, to

$f^{q-1}=1\qquad$ dla dowolnego $f \in F^*$.

To oznacza, że wszystkie elementy $F^*$ są pierwiastkami wielomianu $x^{q-1}-1$. Niech teraz $d|q-1$, czyli $q-1=dk$ dla pewnego $k$. Łatwo sprawdzić, iż

$x^{q-1}-1=(x^d-1)(x^{d(k-1)}+x^{d(k-2)}+\ldots+x^d+1).$

Z Obserwacji 6.18 wielomian $x^d-1$ ma co najwyżej $d$ pierwiastków, a $x^{d(k-1)}+x^{d(k-2)}+\ldots+x^d+1$ ma co najwyżej $d(k-1)$. Jednak ich iloczyn $x^{q-1}-1$ ma dokładnie $q-1$ pierwiastków, więc oba wielomiany mają odpowiednio $d$ i $d(k-1)$ pierwiastków.

Fakt, iż $x^d-1$ ma dokładnie $d$ pierwiastków to dokładnie warunek (*).

Podsumowując nasze rozważania, pokazaliśmy, że:

• dowolne ciało skończone ma $p^k$ elementów, dla pewnej liczby pierwszej $p$ i $k\geq1$,

• grupa addytywna dowolnego ciała $p^k$-elementowego jest izomorficzna z $({\mathbf {Z}_p})^n$,

• grupa multyplikatywna dowolnego ciała $p^k$-elementowego jest izomorficzna z ${\mathbf {Z}_{p^k-1}}$.

W tym kontekście nie jest zbyt zaskakujące, iż dowolne dwa ciała $p^k$-elementowe okażą się być izomorficzne. W dowodzie Obserwacji 6.20 widzieliśmy, że ciało skończone charakterystyki $p$ zawiera ciało izomorficzne z $\mathbb{Z}_p$. Odtąd będziemy więc zakładać, że $\mathbb{Z}_p$ jest po prostu podciałem takiego ciała.

Dla lepszego zrozumienia grupy i multyplikatywnej ciała przeanalizujemy jeszcze pojęcie pokrewne do pojęcia rzędu elementu $a$. W ciele skończonym, o $p^k$ elementach, rząd $r$ elementu $a$ dzieli rząd $p^k-1$ grupy multyplikatywnej, w szczególności ${\sf NWD}(p,r)=1$. Ale również lista

$a, a^p, a^{p^2}, a^{p^3},\ldots$

nie może być nieskończona. Wyrazy na niej muszą się powtarzać. Co więcej, $a^{p^i} = a^{p^j}$ wtedy i tylko wtedy, gdy $p^i-p^j$ dzieli się przez rząd $r$ elementu $a$. Niech więc $i < j$ czyli $a^{p^i(p^{j-i} -1)}=1$. Wtedy $r \mid p^i(p^{j-i} -1)$ i wobec ${\sf NWD}(p,r)=1$ mamy $p^{j-i} \equiv_r 1$. Niech $s$ będzie multyplikatywnym rzędem liczby $p$ modulo $r$, tzn najmniejsza taka liczba naturalną $s$, że $p^s \equiv_r 1$. Wtedy mamy

$a^{p^i} = a^{p^j}$ wtedy i tylko wtedy, gdy $i \equiv_s j$.

A zatem nasza lista redukuje się do:

$a, a^p, a^{p^2}, a^{p^3},\ldots, a^{p^{s-1}}.$

Stopień elementu $a\neq 0$ ciała charakterystyki $p$ to najmniejsza liczba $d$, dla której $a^{p^{s}}=a$.

Wniosek 6.22

W skończonym ciele o $p^k$ elementach, stopień każdego elemetu jest dzielnikiem liczby $k$.

Obserwacja 6.23

Dla dowolnego ciała ${\bf F}$ charakterystyki $p$ oraz $n\in\mathbb{N}$ mamy:

• jeśli $a,b \in F$, to $(a+b)^{p^n} = a^{p^n}+b^{p^n}$,

• jeśli $w(x) \in \mathbb{Z}_p[x]$, to $w(x^{p^n}) = w(x)^{p^n}$,

Dowód

Tak jak w ciele liczb rzeczywistych, można łatwo pokazać, że

$(a+b)^p = \sum_{i=0}^p {p \choose i}a^ib^{p-i}.$

To, wraz z faktem, że $p$ jako liczba pierwsza dzieli wszystkie współczynniki dwumianowe poza ${p \choose 0}$ i ${p \choose p}$ oraz, że ${\bf F}$ ma charakterystykę $p$, daje $(a+b)^p = a^p+b^p$. Łatwa indukcja względem $n$ pokazuje teraz punkt pierwszy.

Dla dowodu punktu drugiego załóżmy, że $w(x)=\sum_i c_i x^i$. Mamy wtedy $w(x)^{p^n} = \sum_i c_i^{p^n} x^{ip^n} = \sum_i c_i x^{ip^n} = w(x^{p^n})$, gdzie równość $c_i^{p^n} = c_i$ użyta w środkowym przejściu wynika z faktu, że $c_i\in \mathbb{Z}_p$.

Obserwacja 6.24

Niech ${\bf F}$ będzie ciałem skończonym charakterystyki $p$. Wtedy dla dowolnego $a\in F^*$ istnieje dokładnie jeden unormowany i nierozkładalny wielomian $w_a(x) \in \mathbb{Z}_p[x]$ taki, że w ciele ${\bf F}$ zachodzi $w_a(a)=0$. Wielomian ten to:

$w_a(a) = \prod_{i=0}^{d-1} (x-a^{p^i}),$

gdzie $d$ jest stopniem elementu $a$.

Dowód

Wielomian $w_a$ zdefiniowany w wypowiedzi obserwacji używa współczynników z ciała ${\bf F}$, które nie muszą być w ciele $\mathbb{Z}_p$. Aby zobaczyć, że w istocie po wymnożeniu dostajemy współczynniki z $\mathbb{Z}_p$ niech $w_a(x)= \sum_{i=0}^{d-1} c_i x^i$. Zauważmy, że zgodnie z Obserwacją 6.23

$w_a(x)^p = w_a(x^p) = \sum_{i=0}^{d-1} c_i^p x^{ip}.$
Z drugiej strony fakt, że $d$ jest stopniem elementu $a$, czyli równość $a^{p^d} = a= a^{p^0}$, daje środkowe przejście w ciągu:

$w_a(x)^p = \prod_{i=0}^{d-1} (x-a^{p^i})^p =\prod_{i=0}^{d-1} (x^p-a^{p^{i+1}}) =\prod_{i=0}^{d-1} (x^p-a^{p^{i}}) =w_a(x^p)=\sum_{i=0}^{d-1} c_i x^{ip}$

Przyrównując więc teraz współczynniki, dostajemy $c_i^p=c_i$. Oznacza to, że $c_0,\ldots,c_{d-1} \in F$ są pierwiastkami wielomianu $x^p-x \in {\bf F}[x]$. Ponieważ wszystkie elementy z ciała $\mathbb{Z}_p \subseteq {\bf F}$ są już pierwiastkami tego wielomianu stopnia $p$, to $c_0,\ldots,c_{d-1}$ muszą być wśród nich, a zatem $c_0,\ldots,c_{d-1} \in \mathbb{Z}_p$.

Oczywiście wielomian $w_a(x)$ jest unormowany. By zobaczyć, że jest nierozkładalny, załóżmy, że $w_a(x)=p(x)q(x)$. Skoro $w_a(a)=0$, to bez straty ogólności możemy założyć, że $p(a)=0$. Ale gdyby wielomian $p(x)$ miał współczynniki w podciele $\mathbb{Z}_p$, to wobec Obserwacji 6.23 mielibyśmy $p(a^{p^{d-1}}) = p(a^{p^{d-2}})= \ldots = p(a^{p^2})=p(a^p) = p(a)=0$, czyli

$a^{p^{d-1}}, a^{p^{d-2}},\ldots,a^{p^2}, a^p, a$

byłyby różnymi pierwiastkami wielomianu $p(x)$, skąd ${\sf deg}(p(x))=d={\sf deg}(w_a(x))$ i wielomian $q(x)$ jest stały.

Pozostaje pokazać, że $w_a(x)$ jest jedynym wielomianem spełniającym warunki podane w Obserwacji. Niech więc $v(a)$ będzie takim wielomianem. Wtedy, ponieważ $v(x)$ ma współczynniki w $\mathbb{Z}_p$, to wraz z $a$ również potęgi $a^p, a^{p^2},\ldots, a^{p^{d-2}}, a^{p^{d-1}}$ są pierwiastkami wielomianu $v(x)$. To na mocy Twierdzenia Bezout daje, że $w_a(x)$ dzieli $v(x)$. Ponieważ jednak $v(x)$ jest nierozkładalny (nad $\mathbb{Z}_p$), to $v(x) = c \cdot w_a(x)$ dla pewnego $c\in \mathbb{Z}_p$. Ale skoro obydwa wielomiany $v(x)$ i $w_a(x)$ sa unormowane, to $c=1$ i $v(x)=w_a(x)$.

Następne twierdzenie wskaże nam jak konstruować ciała liczności $p^k$ dla $k>1$. Dla niezerowego wielomianu $q(x)$ nad ciałem ${\bf F}=(F,+,\cdot,0,1)$ rozważmy dwuargumentową relację $\sim_{q(x)}$ na zbiorze $F$ zadaną przez

$a(x)\sim_{q(x)}b(x) \textrm{ wtedy i tylko wtedy, gdy } q(x)|a(x)-b(x).$

Łatwo sprawdzić, iż $\sim_{q(x)}$ jest relacja równoważności zachowującą dodawanie i mnożenie wielomianów. W istocie jest to kongruencja wyznaczona przez ideał główny pierścienia wielomianów ${\bf F}[x]$ generowany wielomianem $q(x)$. Zbiór klas równoważności tworzy więc pierścień ilorazowy ${\bf F}[x]/q(x)$.

Twierdzenie 6.25

Jeśli $q(x)$ jest nierozkładalnym wielomianem stopnia $k$ nad ciałem $\mathbb{Z}_p$, to pierścień ilorazowy $\mathbb{Z}_p[x]/q(x)$ jest $p^k$-elementowym ciałem.

Dowód

Po pierwsze w każdej klasie równoważności relacji $\sim_{q(x)}$ jest jakiś wielomian stopnia mniejszego niż $k$. Istotnie, gdy $p(x)=a(x)\cdot q(x)+r(x)$, gdzie $r(x)$ jest wielomianem zerowym lub stopnia mniejszego niż $k$, to $p(x) \sim_{q(x)} r(x)$. Ponadto, różne wielomiany stopnia mniejszego niż $k$ nie mogą być $\sim_{q(x)}$ równoważne. A zatem każda klasa równoważności jest wyznaczona przez dokładnie jeden wielomian stopnia mniejszego niż $k$. Wielomianów takich jest tyle co wektorów postaci $(a_{k-1},\ldots,a_0)$, gdzie $a_i\in\mathbb{Z}_p$. A więc $\sim_{q(x)}$ ma dokładnie $p^k$ klas równoważności.

Pozostało sprawdzić, że (przemienny) pierścień ilorazowy jest ciałem, tzn. każdy jego niezerowy element jest odwracalny. W tym miejscu kluczowa jest nierozkładalność wielomianu $q(x)$.

Niech więc $a(x)$ będzie niezerowym wielomianem stopnia mniejszego od $k$. Z nierozkładalności $q(x)$ wiemy, że $1\in\mathbb{Z}_p[x]$ jest największym wspólnym dzielnikiem $a(x)$ i $q(x)$. Z Wniosku 6.13 istnieją $\lambda(x),\mu(x)\in{\bf F}[x]$ takie, że

$\lambda(x)a(x)+\mu(x)q(x)=1.$

To oczywiście oznacza, że

$\lambda(x)a(x) \sim_{q(x)} 1,$

czyli klasa $[\lambda]_{q(x)}$ jest odwrotna do $[a(x)]_{q(x)}$.

Ciało reszt modulo nierozkładalny wielomian $w(x)\in \mathbb{Z}_p[x]$, to ciało ilorazowe $\mathbb{Z}_p[x]/q(x)$ opisane w Twierdzeniu 6.25.

Twierdzenie 6.26

Jeśli dwa skończone ciała są równoliczne, to są izomorficzne.

Dowód

Niech ciała ${\bf F}$ i ${\bf G}$ mają $p^k$ elementów. Przez $a$ oznaczmy generator grupy multyplikatywnej ciała ${\bf F}$. Wtedy stopień elementu $a$ wynosi $k$. Pokażemy, że ${\{ {1,a,a^2, \ldots, a^{k-1}} \} }$ stanowi bazę dla przestrzeni wektorowej ${\bf F}$ nad $\mathbb{Z}_p$. Istotnie, gdyby zbiór ten był liniowo zależny, to $\sum_{i=0}^{k-1} c_i a^i =0$ dla pewnych współczynników $c_i\in\mathbb{Z}_p$. Ale wtedy wielomian $\sum_{i=0}^{k-1} c_i x^i$ miałby w swoim rozkładzie pewien nierozkładalny i unormowany wielomian $w'(x)$ stopnia co najwyżej $k-1$ taki, że $w'(a)=0$. To jednak na mocy Twierdzenia 6.24 nie jest możliwe, bo jedyny taki wielomian w $\mathbb{Z}_p[x]$ to $w_a(x)$ stopnia $k$. Ponieważ liniowo niezależny zbiór ${\{ {1,a,a^2, \ldots, a^{k-1}} \} }$ ma liczność równa wymiarowi przestrzeni wektorowej ${\bf F}$ nad $\mathbb{Z}_p$, to jest jej bazą.

Podobnie, startując od generatora $b$ grupy multyplikatywnej ciała ${\bf G}$, dostaniemy bazę ${\{ {1,b,b^2, \ldots, b^{k-1}} \} }$ przestrzeni wektorowej ${\bf G}$ nad $\mathbb{Z}_p$. Teraz łatwo już sprawdzić, że jedyne odwzorowanie liniowe $F \longrightarrow G$ posyłające $a^i$ w $b^i$ jest izomorfizmem nie tylko przestrzeni wektorowych, ale i ciał ${\bf F}$ i ${\bf G}$.

Twierdzenie 6.25 pozwala na konstrukcję ciał skończonych o $p^k$ elementach, gdzie $p$ jest liczbą pierwszą i $k>1$, o ile tylko mamy nierozkładalny wielomian $k$-tego stopnia nad $\mathbb{Z}_p$. Fakt, iż taki wielomian istnieje dla dowolnej liczby pierwszej $p$ i dowolnego $k\geq 1$ jest nietrywialny i jego dowód przeprowadzimy w serii ćwiczeń do tego wykładu.

Twierdzenie 6.27

Dla dowolnej liczby pierwszej $p$ i $k\geq1$ istnieje nierozkładalny wielomian $k$-tego stopnia nad ciałem $\mathbb{Z}_p$.

Wniosek 6.28

Dla dowolnej liczby pierwszej $p$ i $k\geq 1$ istnieje dokładnie jedno, z dokładnością do izomorfizmu, ciało $p^n$-elementowe.

Ciało Galois ${\bf GF}(q)$, gdzie $q=p^k$ jest potęgą liczby pierwszej, to jedyne z dokładnością do izomorfizmu ciało $q$-elementowe.

Przykład

Opiszemy ciała ${\bf GF}(4)$ i ${\bf GF}(9)$.

• ${\bf GF}(4)$:
  • $4=2^2$ zatem potrzebujemy nierozkładalnego wielomianu stopnia $2$ nad ${\bf \mathbb{Z}_2}$.

W jednym z poprzednich przykładów widzieliśmy, iż jest tylko jeden taki wielomian:

$x^2+x+1.$

• • elementami konstruowanego ciała są $4$ klasy reszt z dzielenia wielomianów nad ${\bf \mathbb{Z}_2}$ przez $x^2+x+1$, o reprezentantach: $0,1,x,x+1$.
  • oto tabelki działań dla ciała ${\bf GF}(4)$

$\begin{array} {c|cccc} + & 0 & 1 & x & x+1 \\ \hline 0 & 0 & 1 & x & x+1 \\ 1 & 1 & 0 & x+1 & x \\ x & x & x+1 & 0 & 1 \\ x+1 & x+1 & x & 1 & 0 \end{array}$

$\begin{array} {c|cccc} \cdot & 0 & 1 & x & x+1 \\ \hline 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & x & x+1 \\ x & 0 & x & x+1 & 1 \\ x+1 & 0 & x+1 & 1 & x \end{array}$

• ${\bf GF}(9)$.
  • $9=3^2$, potrzebujemy zatem nierozkładalnego wielomianu stopnia $2$ nad $\mathbb{Z}_3$. Możemy tak jak wcześniej wygenerować wszystkie wielomiany rozkładalne stopnia $2$ nad $\mathbb{Z}_3$ i wziąć dowolny spoza tej listy. Jednak jest to bardzo żmudne. Dlatego podajemy od razu nierozkładalny wielomian: $x^2+2x+2$. Na szczęście łatwo sprawdzić, że rzeczywiście podany wielomian jest nierozkładalny. Gdyby był rozkładalny musiałby mieć w rozkładzie czynniki stopnia $1$, których istnienie łatwo zweryfikować przy pomocy Twierdzenia Bezout:
    • $0^2+2\cdot0+2=2$,
    • $1^2+2\cdot1+2=2$,
    • $2^2+2\cdot2+2=1$,

zatem rzeczywiście wielomian $x^2+2x+2$ jest nierozkładalny nad $\mathbb{Z}_3$.

• elementy konstruowanego ciała to $9$ klas reszt z dzielenia wielomianów nad ${\bf \mathbb{Z}_3}$ przez $x^2+2x+2$, o reprezentantach: $0,1,2,x,x+1,x+2, 2x,2x+1, 2x+2$