Otwórz menu główne

Spis treści

Ciało skończone lub ciało Galoisciało skończonego rzędu, tj. o skończonej liczbie elementów; druga z nazw pochodzi od nazwiska francuskiego matematyka Évariste’a Galois, który znacząco przyczynił się do rozwoju badań nad ciałami skończonymi oraz 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 elementach (tzn. rzędu gdzie jest liczbą pierwszą) oznaczane będzie zamiennie jednym z symboli oraz inną stosowaną notacją jest (od ang. Galois field, ciało Galois).

Konstrukcja i własnościEdytuj

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

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   będącym potęgą liczby pierwszej jest ciałem rozkładu wielomianu   nad ciałem  [6]; wynika stąd, że ciała skończone tego samego rzędu są izomorficzne[7][8]. Wychodząc stąd, można dowieść istnienia ciał skończonych dowolnego rzędu będącego potęgą liczby pierwszej[9]. Dla dowolnej liczby pierwszej   i naturalnej liczby   istnieje unormowany wielomian nierozkładalny stopnia   należący do  [10]. Podciała   są rzędu   gdzie   przy czym istnieje jedno i tylko jedno takie ciało dla każdego  [11].

Zbiór pierwiastków wielomianu   zawiera wszystkie elementy   zatem ciało to jest ciałem rozkładu tego wielomianu rozdzielczego nad ciałem   Stąd ciało   jest rozszerzeniem Galois – zasadniczą cechą ciał skończonych jest to, iż grupa Galois   jest cykliczna i ma kanoniczny generator w postaci endomorfizmu Frobeniusa  [12]. Jeśli   jest wielomianem nierozkładalnym stopnia   i ma pierwiastek   w pewnym rozszerzeniu ciała   to jego pierwiastki tworzą zbiór złożony z elementów  [13].

Powyższe twierdzenia można uogólnić, zastępując ciało   rzędu wyrażającego się pewną liczbą pierwszą   ogólnym ciałem   rzędu   wykorzystując obserwację, iż dla każdego   zachodzi   zatem rolę endomorfizmu Frobeniusa   dla skończonych rozszerzeń   przejmuje odwzorowanie   dla skończonych rozszerzeń  [14].

Ciała skończone nie są algebraicznie domknięte[15] (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.

PrzykładyEdytuj

Pierścień   tworzy ciało  -elementowe; jego elementami są ideały   z naturalnie określonymi działaniami (zob. pierścień ilorazowy). Innym ciałem  -elementowym jest pierścień   o elementach   z działaniami arytmetyki modularnej; ciało to ma tę postać, co   W gruncie rzeczy wszystkie ciała o   elementach mają tę samą strukturę. Pierścień   nie jest ciałem, ponieważ ma on (właściwy) dzielnik zera   skoro   to   jest niezerowym elementem nieodwracalnym[16] (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)  -elementowym ciele   (wielomian   jest jedynym nierozkładalnym wielomianem drugiego stopnia nad  ) przedstawiono niżej:

 

Odpowiednio  - i  -elementowe pierścienie   i   nie są poprawnymi konstrukcjami ciał – pierścień   jest ciałem wyłącznie wtedy, gdy   jest liczbą pierwszą – niemniej ciała skończone tych rzędów istnieją: ciałami rzędu   są np.   oraz   a przykładami ciał rzędu   są np.   bądź   albo   – są to wszystkie ciała postaci   dla unormowanego wielomianu   dla   i   czyli rzędu   innym ciałem rzędu   jest   które jest izomorficzne z   a nawet wszystkimi innymi ciałami rzędu   Wielomian   jest nierozkładalny w   zatem   jest ciałem rzędu  

Zbiór niezerowych elementów ciała   tworzy grupę (cykliczną) rzędu   element   nie generuje tej grupy – jego kolejnymi potęgami są   jednakże element   jest jej generatorem – jego kolejne potęgi to   (w pozostałych ciałach rzędu   w „modelu wielomianowym”, generatorem grupy multiplikatywnej jest  ).

Wielomian   jest nierozkładalny w   jednym z jego pierwiastków w ciele   jest element   dwoma pozostałymi są   Ponieważ   w   to   (gdyż  ), zatem   skąd wynika, że pierwiastki   w   można zapisać jako   Element   jest jednym z pierwiastków   w   dwoma pozostałymi są   oraz  

Element   ciała   ma wielomian minimalny   nad   Pozostałymi dwoma pierwiastkami tego wielomianu są nad   oraz   potęgi tych elementów można zredukować, korzystając z tożsamości   mianowicie:   oraz  

Rys historycznyEdytuj

Ciała o rzędzie wyrażającym się liczbą pierwszą,   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   gdzie   jest pierwiastkiem wielomianu nierozkładalnego   zmiennej   nad ciałem   (tzn. należącego do  ); jest to równoważne rozpatrywaniu   Galois nie pokazał, że w   istnieje wielomian nierozkładalny dowolnego stopnia.

W 1893 roku na Międzynarodowym Kongresie Matematycznym w Chicago Eliakim Hastings Moore dowiódł, że każde ciało skończone jest izomorficzne z ciałem postaci   twierdzenie opatrzył komentarzem „To interesujący wynik, którego sformułowania nie widziałem nigdzie indziej”[17]. 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”)[18]. Każde skonstruowane ciało postaci   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   (od ang. Galois field) stosowana jest często zamiast  

PrzypisyEdytuj

  1. Warstwy modulo   są reprezentowane za pomocą reszt   gdzie   przy czym jest ich   Ponieważ   jest nierozkładalny, to korzystając z tego samego argumentu, co przy dowodzie, iż   jest ciałem dla   będącego liczbą pierwszą, pierścień   jest ciałem.
  2. Charakterystyka ciała skończonego   jest liczbą pierwszą, gdyż jądro homomorfizmu   jest niepuste (z uwagi na nieskończony rząd   i skończony  ) i jest postaci   dla pewnej liczby całkowitej   zatem   zanurza się w   jako podpierścień; każdy podpierścień ciała jest dziedziną, zatem   musi być liczbą pierwszą, oznaczaną dalej   Skoro   jest zanurzeniem, to   można traktować jako przestrzeń liniową nad   skończonego wymiaru   (gdyż   jest zbiorem skończonym). Każdy element   można wtedy zapisać jednoznacznie w bazie   nad   jako kombinację liniową   dla   liczba tych kombinacji wynosi  
  3. Lemat: Jeśli ciało   jest skończone, to jego grupa multiplikatywna   jest cykliczna.
    Dowód lematu: Niech   oznacza największy rząd elementu w grupie   z teorii skończonych grup abelowych wynika, że rząd dowolnego jej elementu dzieli rząd maksymalny, zatem dla dowolnego   zachodzi   Stąd wszystkie liczby w   są pierwiastkami  
    Niech   liczba pierwiastków wielomianu jest równa co najwyżej stopniowi wielomianu, a ponieważ   ma   pierwiastków w   to   Skoro   jest rzędem elementu w   będącej grupą rzędu   to   a więc   skąd wynika, że w   istnieją elementy rzędu   co oznacza, iż   jest cykliczna.
  4. Niech   będzie ciałem skończonym o   elementów (z twierdzenia wyżej) i dane będzie zanurzenie ciał   Niech   będzie generatorem grupy cyklicznej   (z powyższego lematu). Ewaluacja   wielomianu dla elementu   dana wzorem   jest homomorfizmem pierścieni. Ponieważ każdy element   jest zerem lub potęgą   (tzn.   oraz   dla dowolnego  ), to   jest epimorfizmem („na”), zatem   Skoro jądro   jest ideałem maksymalnym w   to musi być ono równe   dla pewnego unormowanego wielomianu nierozkładalnego   należącego do  
  5. Twierdzenie to nie zapewnia o istnieniu ciał rzędów wyrażających się za pomocą wszystkich potęg liczb pierwszych; mówi jedynie, iż jeśli istnieje ciało rzędu   to jest ono izomorficzne z   odpowiedni dowód istnienia przedstawiono dalej.
  6. Niech   będzie ciałem rzędu   z dowodu twierdzenia o rzędzie ciała skończonego wynika, że   zawiera podciało rzędu   izomorficzne z   jest nim podpierścień   generowany przez   Dla każdego   zachodzi   otóż jeśli   to   gdyż   jest grupą multiplikatywną rzędu   i wtedy tożsamość wynika z obustronnego pomnożenia równania przez   co jest również prawdą w przypadku, gdy   Każdy element   jest pierwiastkiem   zatem   jest ciałem rozkładu tego wielomianu nad ciałem  
  7. Wynika to wprost z izomorficzności ciał rozkładu ustalonego wielomianu nad  
  8. Analogiczne twierdzenie dla skończonych grup lub pierścieni jest fałszywe: tak   jak i   są rzędu   lecz są nieizomorficzne jako grupy addytywne (odpowiednio grupa cykliczna i grupa czwórkowa Kleina) i pierścienie przemienne.
  9. Twierdzenie: Dla dowolnych liczb pierwszej   i naturalnej   istnieje ciało rzędu  
    Dowód: Niech   będzie rozszerzeniem ciała   nad którym wielomian   rozkłada się na czynniki liniowe (tzn. pewnym rozszerzeniem ciała rozkładu tego wielomianu; istnienie tego rodzaju rozszerzenia wynika z ogólnej teorii ciał). Pierwiastki wspomnianego wielomianu tworzą zbiór   o   elementach, gdyż wielomian   jest rozdzielczy:   gdyż   w   zatem   i jego pochodna nie mają wspólnych pierwiastków; wielomian ten rozkłada się na czynniki liniowe nad   i jest stopnia   zatem ma   pierwiastków w  
    Zbiór   tworzy ciało – wynika to wprost z własności endomorfizmu Frobeniusa   Mianowicie: zamkniętość ze względu na mnożenie i odwracanie (niezerowych rozwiązań) jest trywialna, z kolei zamkniętość ze względu na dodawanie i branie elementów przeciwnych wynika stąd, iż   jest grupą addytywną: skoro   w   to dla dowolnych elementów   zachodzi równość   (wyrazy mieszane rozwinięcia dwumianu Newtona   mają współczynniki   będące wielokrotnościami   zatem są równe zeru), co dowodzi addytywności endomorfizmu Frobeniusa, skąd wynika także addytywność jego  -tej iteracji   Zbiór   jest grupą ze względu na dodawanie jako zbiór punktów stałych tej właśnie funkcji addytywnej.
  10. Z powyższego twierdzenia wynika istnienie abstrakcyjnego ciała rzędu   a z twierdzenia wyżej musi być ono izomorficzne z ciałem   dla pewnego  
  11. Niech   będzie ciałem spełniającym   i niech   tak, iż   a   dzieli   Opisanie   wyłącznie w zależności od   zagwarantuje jedyność podciała tego rzędu w   Skoro   jest rzędu   to dla każdego   zachodzi   zatem   również dla   Wielomian   ma co najwyżej   pierwiastków w   a ponieważ   jest zbiorem   różnych pierwiastków, jest   (zależna tylko od liczby elementów) postać tego zbioru dowodzi jego jednoznaczności. Przechodząc do dowodu, iż dla każdego   istnieje podciało ciała   rzędu   zbiór   jest ciałem na mocy tego samego argumentu, co dla zbioru   w dowodzie twierdzenia o istnieniu; wykazanie, iż ma on   elementów polega na wskazaniu   niezerowych elementów w   spełniających   Otóż niech   będzie generatorem   czyli ma rząd   ponieważ   tj.   dzieli   to   jest rzędu   Wszystkie potęgi   dla   spełniają  
  12. Dla dowolnego   zachodzi   zatem   jest zbiorem punktów stałych funkcji   funkcja ta jest homomorfizmem ciał i jest różnowartościowa (wszystkie homomorfizmy ciał są monomorfizmami), a także „na”, jako że   jest skończone (innymi słowy endomorfizm Frobeniusa jest automorfizmem). Stąd   Rząd tej grupy Galois wynosi   wystarczy wykazać, że   jest rzędu   co oznaczać będzie, iż jest generatorem tej grupy. Niech dla   będzie   Wówczas jeśli   jest elementem neutralnym tej grupy, to   dla wszystkich   Wielomian   ma co najwyżej   pierwiastków, zatem   czyli   Wynika stąd, iż   ma w   rząd równy co najmniej   z drugiej strony grupa ta ma rząd co najwyżej   zatem   musi być tamże rzędu  
  13. Każde skończone ciało rzędu wyrażającego się potęgą liczby pierwszej   jest rozszerzeniem Galois nad   W szczególności dotyczy to ciała   a pozostałe pierwiastki   można otrzymać z   działając na ten element grupą   Ponieważ grupa ta jest generowana przez endomorfizm Frobeniusa, to pierwiastki   należą do zbioru   Zbiór ten jest skończony, gdyż   co wynika stąd, iż   jest rzędu   Wielomian   jest rozdzielczy, ponieważ jego pierwiastki należą do rozszerzenia Galois   ciała   a skoro ma on stopień   to parami różne elementy   tworzą zbiór jego pierwiastków.
  14. Twierdzenie: Dla dowolnej liczby naturalnej   istnieje unormowany wielomian nierozkładalny stopnia   należący do  
    Twierdzenie: Między   a   istnieje jedno i tylko jedno ciało rzędu   dla każdego   jest ono postaci  
    Twierdzenie: Dla dowolnej liczby naturalnej   ciało   jest rozszerzeniem Galois, a jego grupa Galois   jest cykliczna, przy czym jej generatorem jest przekształcenie  
    Twierdzenie: Jeśli   jest wielomianem nierozkładalnym stopnia   i ma pierwiastek   w pewnym rozszerzeniu ciała   to zbiór elementów   zawiera wszystkie jego pierwiastki.
  15. Jeśli   jest ciałem skończonym, to wartość wielomianu   dla dowolnego elementu   jest równa   (jego funkcja wielomianowa jest stale równa  ), skąd wielomian ten nie ma pierwiastków w  
  16. Jeśli (w ciele  ) element   byłby elementem odwrotnym do   to (z definicji)   jednakże wtedy   czyli   nie może mieć elementu odwrotnego.
  17. (Moore, s. 211).
  18. (Moore, s. 208).

BibliografiaEdytuj

  • J. Browkin: Teoria ciał. Wyd. 1. T. 49. Warszawa: PWN, 1977, seria: Biblioteka Matematyczna.
  • Rudolf Lidl, Harald Niederreiter, „Finite Fields”, Addison-Wesley 1983.
  • E.H. Moore: A Doubly-Infnite System of Simple Groups, s. 208–242 w „Mathematical papers read at the International Mathematical Congress held in connection with the World’s Columbian Exposition, Chicago, 1893”; Macmillan & Co., Nowy Jork, 1896.
  • Andrzej Chmielowiec, Ciała charakterystyki 2 – aspekty implementacyjne, 2007