Ciało skończone

Ciało skończone lub ciało Galois – ciało skończonego rzędu, tj. o skończonej liczbie elementów; druga z nazw pochodzi od nazwiska Évariste’a Galois, który znacząco przyczynił się do rozwoju badań nad ciałami skończonymi (zob. Rys historyczny).

Galois wskazał ich zastosowanie w tzw. teorii Galois dającej m.in. definitywną odpowiedź na pytania o rozstrzygnięcie możliwości wykonania klasycznych konstrukcji w geometrii euklidesowej czy też zgrabnie uzasadniającej brak ogólnych wzorów na pierwiastki wielomianów wyższych stopni.

W artykule za naturalne uważa się dodatnie liczby całkowite, ciało proste o $p$ elementach (tzn. rzędu $p,$ gdzie $p$ jest liczbą pierwszą) oznaczane będzie zamiennie jednym z symboli ${𝐅}_p$ oraz $\mathbb{Z}/(p);$ inną stosowaną notacją jest $\mathrm{G}\mathrm{F}(p)$ (od ang. Galois field, ciało Galois).

Konstrukcja i własności

Szablon:Zobacz też Niech $p$ będzie liczbą pierwszą, a $\pi$ będzie unormowanym (monicznym) wielomianem nierozkładalnym stopnia $n$ należącym do ${𝐅}_p[x]$ (tj. zmiennej $x$ o współczynnikach z ciała ${𝐅}_p$). Pierścień ${𝐅}_p[x]/(\pi )$ (pierścień ilorazowy ${𝐅}_p[x]$ przez ideał główny generowany przez $\pi ,$ który jest ideałem maksymalnym, co wynika z nierozkładalności i unormowania $\pi$) jest wtedy ciałem (reszt) rzędu $p^n$. Każde ciało skończone ma rząd wyrażający się naturalną potęgą liczby pierwszej, a ponadto jest izomorficzne z ${𝐅}_p[x]/(\pi )$ dla pewnej liczby pierwszej $p$ i unormowanego wielomianu nierozkładalnego $\pi$ należącego do ${𝐅}_p[x]$ (grupa multiplikatywna ciał skończonych jest cykliczna).

Dowolne ciało skończone można opisać jako ciało rozkładu wielomianu wyłącznie w zależności od rzędu ciała: ciało skończone o rzędzie $p^n$ będącym potęgą liczby pierwszej jest ciałem rozkładu wielomianu $x^{p^n}-x$ nad ciałem ${𝐅}_p$; wynika stąd, że ciała skończone tego samego rzędu są izomorficzne. Wychodząc stąd, można dowieść istnienia ciał skończonych dowolnego rzędu będącego potęgą liczby pierwszej. Dla dowolnej liczby pierwszej $p$ i naturalnej liczby $n$ istnieje unormowany wielomian nierozkładalny stopnia $n$ należący do ${𝐅}_p[x]$. Podciała ${𝐅}_{p^n}$ są rzędu $p^d,$ gdzie $d|n,$ przy czym istnieje jedno i tylko jedno takie ciało dla każdego $d$.

Zbiór pierwiastków wielomianu $x^{p^n}-x$ zawiera wszystkie elementy ${𝐅}_{p^n},$ zatem ciało to jest ciałem rozkładu tego wielomianu rozdzielczego nad ciałem ${𝐅}_p.$ Stąd ciało ${𝐅}_{p^n}/{𝐅}_p$ jest rozszerzeniem Galois – zasadniczą cechą ciał skończonych jest to, iż grupa Galois $\mathrm{G}\mathrm{a}\mathrm{l}({𝐅}_{p^n}/{𝐅}_p)$ jest cykliczna i ma kanoniczny generator w postaci endomorfizmu Frobeniusa ${\phi }_p:t\mapsto t^p$. Jeśli $\pi \in {𝐅}_q[x]$ jest wielomianem nierozkładalnym stopnia $d$ i ma pierwiastek $\alpha$ w pewnym rozszerzeniu ciała ${𝐅}_q,$ to jego pierwiastki tworzą zbiór złożony z elementów $\alpha ,{\alpha }^p,{\alpha }^{p^2},\dots ,{\alpha }^{p^{d-1}}$.

Powyższe twierdzenia można uogólnić, zastępując ciało ${𝐅}_p$ rzędu wyrażającego się pewną liczbą pierwszą $p$ ogólnym ciałem ${𝐅}_q$ rzędu $q=p^n,$ wykorzystując obserwację, iż dla każdego $a\in {𝐅}_q$ zachodzi $a^q=a,$ zatem rolę endomorfizmu Frobeniusa $x\mapsto x^p$ dla skończonych rozszerzeń ${𝐅}_p$ przejmuje odwzorowanie $x\mapsto x^q$ dla skończonych rozszerzeń ${𝐅}_q$.

Ciała skończone nie są algebraicznie domknięte (dla każdego jednak ciała istnieje ciało algebraicznie domknięte je zawierające). Twierdzenie Wedderburna mówi, że każdy skończony pierścień całkowity (w szczególności: pierścień z dzieleniem) jest przemienny, a więc jest ciałem (skończonym); teza zachodzi również dla pierścieni alternatywnych, czyli przy zrezygnowaniu z założenia łączności pierścienia na rzecz jego alternatywności, o czym mówi Szablon:Link-interwiki.

Przykłady

Pierścień $\mathbb{Z}/7\mathbb{Z}$ tworzy ciało 7-elementowe; jego elementami są ideały $0\mathbb{Z},\dots ,6\mathbb{Z}$ z naturalnie określonymi działaniami (zob. pierścień ilorazowy). Innym ciałem 7-elementowym jest pierścień ${\mathbb{Z}}_7$ o elementach $0,\dots ,6$ z działaniami arytmetyki modularnej; ciało to ma tę postać, co ${\mathbb{Z}}_7[x]/(x)={𝐅}_7[x]/(x).$ W gruncie rzeczy wszystkie ciała o 7 elementach mają tę samą strukturę. Pierścień ${\mathbb{Z}}_4$ nie jest ciałem, ponieważ ma on (właściwy) dzielnik zera 2; skoro $2\cdot 2=0,$ to 2 jest niezerowym elementem nieodwracalnym (a więc przeczy definicji ciała, w którym każdy niezerowy element jest odwracalny). Tabliczki działań dodawania i mnożenia w jedynym (z dokładnością do izomorfizmu) 4-elementowym ciele ${𝐅}_2[x]/(x^2+x+1)$ (wielomian $x^2+x+1$ jest jedynym nierozkładalnym wielomianem drugiego stopnia nad ${𝐅}_2$) przedstawiono niżej:

$\begin{array}{ccccc}+& 0& 1& x& x+1\\ 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}{ccccc}\cdot & 0& 1& x& x+1\\ 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}$

Odpowiednio 8- i 9-elementowe pierścienie $\mathbb{Z}/2^3\mathbb{Z}$ i $\mathbb{Z}/3^2\mathbb{Z}$ nie są poprawnymi konstrukcjami ciał – pierścień $\mathbb{Z}/m\mathbb{Z}$ jest ciałem wyłącznie wtedy, gdy $m$ jest liczbą pierwszą – niemniej ciała skończone tych rzędów istnieją: ciałami rzędu 8 są np. ${𝐅}_2[x]/(x^3+x+1)$ oraz ${𝐅}_2[x]/(x^3+x^2+1),$ a przykładami ciał rzędu 9 są np. ${𝐅}_3[x]/(x^2+1),$ bądź ${𝐅}_3[x]/(x^2+x+2)$ albo ${𝐅}_3[x]/(x^2+2x+2)$ – są to wszystkie ciała postaci ${𝐅}_p[x]/(\pi )$ dla unormowanego wielomianu $\pi \in {𝐅}_p[x]$ dla $p=3$ i $n=\mathrm{deg}\pi =2,$ czyli rzędu $p^n=9;$ innym ciałem rzędu 9 jest $\mathbb{Z}[i]/(3),$ które jest izomorficzne z ${𝐅}_3[x]/(x^2+1),$ a nawet wszystkimi innymi ciałami rzędu 9. Wielomian $x^3-2$ jest nierozkładalny w ${𝐅}_7[x],$ zatem ${𝐅}_7[x]/(x^3-2)$ jest ciałem rzędu $7^3=343.$

Zbiór niezerowych elementów ciała ${𝐅}_3[x]/(x^2+1)$ tworzy grupę (cykliczną) rzędu 8; element $x$ nie generuje tej grupy – jego kolejnymi potęgami są $x,x^2=-1=2,x^3=2x,x^4=2x^2=-2=1,$ jednakże element $x+1$ jest jej generatorem – jego kolejne potęgi to $x+1,2x,2x+1,2,2x+2,x,x+2,1$ (w pozostałych ciałach rzędu 9 w „modelu wielomianowym”, generatorem grupy multiplikatywnej jest $x$).

Wielomian $T^3+T^2+1$ jest nierozkładalny w ${𝐅}_2[x];$ jednym z jego pierwiastków w ciele $F={𝐅}_2[x]/(x^3+x^2+1)$ jest element $x,$ dwoma pozostałymi są $x^2,x^4.$ Ponieważ $x^3+x^2+1=0$ w $F,$ to $x^3=x^2+1$ (gdyż $-1=1$), zatem $x^4=x^3+x=(x^2+1)+x=x^2+x+1,$ skąd wynika, że pierwiastki $T^3+T^2+1=0$ w $F$ można zapisać jako $x,x^2,x^2+x+1.$ Element $x+1$ jest jednym z pierwiastków $T^3+T+1$ w $F;$ dwoma pozostałymi są $(x+1{)}^2=x^2+1$ oraz $(x+1{)}^4=(x^2+1{)}^2=x^4+1=(x^2+x+1)+1=x^2+x.$

Element $x^2+x+2$ ciała ${𝐅}_7[x]/(x^3-2)$ ma wielomian minimalny $T^3+T^2+6T+5$ nad ${𝐅}_7.$ Pozostałymi dwoma pierwiastkami tego wielomianu są nad $(x^2+x+2{)}^7$ oraz $(x^2+x+2{)}^{49};$ potęgi tych elementów można zredukować, korzystając z tożsamości $x^3=2,$ mianowicie: $(x^2+x+2{)}^7=2x^2+4x+2$ oraz $(x^2+x+2{)}^{49}=4x^2+2x+2.$

Rys historyczny

Ciała o rzędzie wyrażającym się liczbą pierwszą, $\mathbb{Z}/p\mathbb{Z},$ były przedmiotem badań wielu pionierów teorii liczb, m.in. Pierre’a de Fermata, Leonharda Eulera, Josepha Louisa Lagrange’a, Adriena-Marie Legendre’a, czy Carla Friedricha Gaussa. Pierwszym matematykiem piszącym o innych ciałach skończonych był Évariste Galois, który przedstawił o nich pracę w 1830 roku (ciałami o rzędach niewyrażających się liczbami pierwszymi zajmował się wcześniej Gauss, co odkryto jednak dopiero po jego śmierci w 1855 roku, wydając jego prace na ten temat w 1863 roku, lecz przeszły one bez większego echa).

Galois konstruował ciała skończone jako Szablon:Link-interwiki ${𝐅}_p(\alpha ),$ gdzie $\alpha$ jest pierwiastkiem wielomianu nierozkładalnego $\pi$ zmiennej $x$ nad ciałem ${𝐅}_p$ (tzn. należącego do ${𝐅}_p[x]$); jest to równoważne rozpatrywaniu ${𝐅}_p[x]/(\pi ).$ Galois nie pokazał, że w ${𝐅}_p[x]$ istnieje wielomian nierozkładalny dowolnego stopnia.

W 1893 roku na Międzynarodowym Kongresie Matematycznym w Chicago Szablon:Link-interwiki dowiódł, że każde ciało skończone jest izomorficzne z ciałem postaci ${𝐅}_p[x]/(\pi );$ twierdzenie opatrzył komentarzem „Nigdzie indziej nie widziałem sformułowania tego interesującego wyniku”. Moore był pierwszą osobą, która użyła angielskiego słowa field (dosł. „pole”) w sensie algebraicznym, choć traktował je jako synonim niemieckiego endlicher Körper (dosł. „ciało skończone”). Każde skonstruowane ciało postaci ${𝐅}_p[x]/(\pi ).$ nazywał on ciałem Galois, były więc one dla niego konkretnymi modelami wszystkich ciał skończonych. W informatyce wyrażenie Moore’a „ciało Galois” jest synonimem ciała skończonego, a stosowana przez niego notacja $\mathrm{G}\mathrm{F}(q)$ (od ang. Galois field) stosowana jest często zamiast ${𝐅}_q.$

Bibliografia

• Szablon:Cytuj pismo

Literatura dodatkowa

• Szablon:Cytuj książkę
• Rudolf Lidl, Harald Niederreiter, „Finite Fields”, Addison-Wesley 1983.

Linki zewnętrzne

• Szablon:MathWorld