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 ${\displaystyle p}$ elementach (tzn. rzędu ${\displaystyle p,}$ gdzie ${\displaystyle p}$ jest liczbą pierwszą) oznaczane będzie zamiennie jednym z symboli ${\displaystyle \mathbf {F} _{p}}$ oraz ${\displaystyle \mathbb {Z} /(p);}$ inną stosowaną notacją jest ${\displaystyle \mathrm {GF} (p)}$ (od ang. Galois field, ciało Galois).

 Zobacz też: wielomian i pierścień wielomianów.

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

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 ${\displaystyle p^{n}}$ będącym potęgą liczby pierwszej jest ciałem rozkładu wielomianu ${\displaystyle x^{p^{n}}-x}$ nad ciałem ${\displaystyle \mathbf {F} _{p}}$^[f]; wynika stąd, że ciała skończone tego samego rzędu są izomorficzne^[g][h]. Wychodząc stąd, można dowieść istnienia ciał skończonych dowolnego rzędu będącego potęgą liczby pierwszej^[i]. Dla dowolnej liczby pierwszej ${\displaystyle p}$ i naturalnej liczby ${\displaystyle n}$ istnieje unormowany wielomian nierozkładalny stopnia ${\displaystyle n}$ należący do ${\displaystyle \mathbf {F} _{p}[x]}$^[j]. Podciała ${\displaystyle \mathbf {F} _{p^{n}}}$ są rzędu ${\displaystyle p^{d},}$ gdzie ${\displaystyle d|n,}$ przy czym istnieje jedno i tylko jedno takie ciało dla każdego ${\displaystyle d}$^[k].

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

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

Ciała skończone nie są algebraicznie domknięte^[o] (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 twierdzenie Artina-Zorna(inne języki).

Pierścień ${\displaystyle \mathbb {Z} /7\mathbb {Z} }$ tworzy ciało 7-elementowe; jego elementami są ideały ${\displaystyle 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ń ${\displaystyle \mathbb {Z} _{7}}$ o elementach ${\displaystyle 0,\dots ,6}$ z działaniami arytmetyki modularnej; ciało to ma tę postać, co ${\displaystyle \mathbb {Z} _{7}[x]/(x)=\mathbf {F} _{7}[x]/(x).}$ W gruncie rzeczy wszystkie ciała o 7 elementach mają tę samą strukturę. Pierścień ${\displaystyle \mathbb {Z} _{4}}$ nie jest ciałem, ponieważ ma on (właściwy) dzielnik zera 2; skoro ${\displaystyle 2\cdot 2=0,}$ to 2 jest niezerowym elementem nieodwracalnym^[p] (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 ${\displaystyle \mathbf {F} _{2}[x]/(x^{2}+x+1)}$ (wielomian ${\displaystyle x^{2}+x+1}$ jest jedynym nierozkładalnym wielomianem drugiego stopnia nad ${\displaystyle \mathbf {F} _{2}}$) przedstawiono niżej:

${\displaystyle {\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}}\qquad {\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}}}$

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

Zbiór niezerowych elementów ciała ${\displaystyle \mathbf {F} _{3}[x]/(x^{2}+1)}$ tworzy grupę (cykliczną) rzędu 8; element ${\displaystyle x}$ nie generuje tej grupy – jego kolejnymi potęgami są ${\displaystyle x,\ x^{2}=-1=2,\ x^{3}=2x,\ x^{4}=2x^{2}=-2=1,}$ jednakże element ${\displaystyle x+1}$ jest jej generatorem – jego kolejne potęgi to ${\displaystyle 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 ${\displaystyle x}$).

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

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

Ciała o rzędzie wyrażającym się liczbą pierwszą, ${\displaystyle \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 rozszerzenia pojedyncze(inne języki) ${\displaystyle \mathbf {F} _{p}(\alpha ),}$ gdzie ${\displaystyle \alpha }$ jest pierwiastkiem wielomianu nierozkładalnego ${\displaystyle \pi }$ zmiennej ${\displaystyle x}$ nad ciałem ${\displaystyle \mathbf {F} _{p}}$ (tzn. należącego do ${\displaystyle \mathbf {F} _{p}[x]}$); jest to równoważne rozpatrywaniu ${\displaystyle \mathbf {F} _{p}[x]/(\pi ).}$ Galois nie pokazał, że w ${\displaystyle \mathbf {F} _{p}[x]}$ istnieje wielomian nierozkładalny dowolnego stopnia.

W 1893 roku na Międzynarodowym Kongresie Matematycznym w Chicago Eliakim Hastings Moore(inne języki) dowiódł, że każde ciało skończone jest izomorficzne z ciałem postaci ${\displaystyle \mathbf {F} _{p}[x]/(\pi );}$ twierdzenie opatrzył komentarzem „Nigdzie indziej nie widziałem sformułowania tego interesującego wyniku”^[1]. 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”)^[2]. Każde skonstruowane ciało postaci ${\displaystyle \mathbf {F} _{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 ${\displaystyle \mathrm {GF} (q)}$ (od ang. Galois field) stosowana jest często zamiast ${\displaystyle \mathbf {F} _{q}.}$

• Eliakim Hastings Moore. A doubly-infinite system of simple groups. „Mathematical papers read at the International Mathematical Congress held in connection with the World’s Columbian Exposition, Chicago, 1893”, s. 208–242, 1896. Nowy Jork: Macmillan & Co.. [dostęp 2020-10-10]. 

• Jerzy Browkin: Teoria ciał. Wyd. 1. T. 49. Warszawa: Państwowe Wydawnictwo Naukowe, 1977, seria: Biblioteka Matematyczna. Brak numerów stron w książce
• Rudolf Lidl, Harald Niederreiter, „Finite Fields”, Addison-Wesley 1983.

• Eric W.E.W. Weisstein Eric W.E.W., Finite Field, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12]  (ang.).