Канечнае поле

Кане́чнае по́ле ці по́ле Галуа́ — поле, якое складаецца з канечнай колькасці элементаў. Другую назву канечныя палі атрымалі ў гонар французскага матэматыка Эварыста Галуа.

Канечнае поле звычайна абазначаецца  ці  (скарачэнне ад Galois field), дзе  — колькасць элементаў поля (магутнасць).
З дакладнасцю да ізамарфізму канечнае поле поўнасцю вызначаецца яго магутнасцю, якая заўсёды з'яўляецца ступенню нейкага простага ліку (, дзе  — просты лік, які з'яўляецца характарыстыкаю поля).

Паняцце канечнага поля выкарыстоўваецца, сярод іншага, у тэорыі лікаў, алгебраічнай геаметрыі, тэорыі Галуа, крыптаграфіі, у распрацоўцы сакрэтных ключоў розных шыфраў (напрыклад, AES).

Найпрасцейшым прыкладам канечнага поля з'яўляецца  — колца вылікаў па модулю простага ліку .

 Гісторыя вывучэння 
Першыя ўпамінанні пра нешта, блізкае да тэорыі канечных палёў, можна знайсці яшчэ ў XVII стагоддзі. Над гэтаю тэмай працавалі такія навукоўцы, як П’ер Ферма, Леанард Эйлер, Жазеф Луі Лагранж і Адрыен Мары Лежандр, якіх можна лічыць заснавальнікамі тэорыі простых канечных палёў. Аднак большую цікавасць прадстаўляе агульная тэорыя канечных палёў, якая бярэ пачатак з прац Гауса і Галуа. У гонар апошняга канечныя палі і атрымалі сваю другую назву — палі Галуа. Да некаторага часу гэтая тэорыя прымянялася толькі ў алгебры і тэорыі лікаў, аднак у другой палавіне XX стагоддзя выявіліся новыя вобласці дотыку з , тэорыяй груп, алгебраічнаю геаметрыяй, камбінаторыкаю і тэорыяй кадзіравання.

 Уклад Галуа 
У 1830 годзе Эварыст Галуа апублікаваў працуEvariste Galois (1830), Sur la théorie des nombres. Bulletin des sciences mathématiques de M. Férussac 13, pp 428—435 (1830), якая стала асноваю агульнай тэорыі канечных палёў. Зыходнаю мэтаю Галуа было вывучэнне параўнання

якое з'яўляецца абагульненнем квадратычных параўнанняў, даследаваных Гаусам (гл. квадратычны закон узаемнасці). Тут  — адвольны непрыводны мнагачлен ступені . У гэтай рабоце Галуа ўводзіць уяўны корань параўнання  і абазначае яго . Пасля гэтага разглядаецца агульны выраз

дзе  — нейкія цэлыя лікі па модулю . Калі прысвойваць гэтым лікам усе магчымыя значэнні, выраз  будзе прымаць  значэнняў. Далей Галуа паказвае, што гэтыя значэнні ўтвараюць поле магутнасці  і яго мультыплікатыўная група з'яўляецца цыклічнаю. Такім чынам, гэтая праца стала першым каменем у падмурку агульнай тэорыі канечных палёў. У адрозненне ад яго папярэднікаў, якія разглядалі толькі палі  Галуа разглядае ўжо палі  якія пачалі называць палямі Галуа ў яго гонар.

На самай справе, Гаус пачаў працаваць у гэтым напрамку прыкладна на 30 гадоў раней, але пры яго жыцці гэтыя даследаванні так і не былі выдадзены. Верагодна, гэтае даследаванне было праігнаравана рэдактарам яго твораў, таму ў свет гэтая праца выйшла толькі ў пасмяротным выданні ў 1863.

 Далейшае развіццё 
У 1893 годзе матэматык  даказаў тэарэму аб класіфікацыі канечных палёў, якая сцвярджае, што любое канечнае поле з'яўляецца полем Галуа.

Да гэтага ж года адносіцца першая спроба аксіяматычнага падыходу да тэорыі канечных палёў, ажыццёўленая , які спрабаваў аб'яднаць у сваёй працыH. Weber, " Die allgemeinen Grundlagen der Galois'schen Gleichungstheorie ", Mathematische Annalen, vol. 43, 1893, p. 521—549 паняцці, якія ўзніклі ў розных раздзелах матэматыкі, у тым ліку і паняцце канечнага поля.

Далей у 1905 годзе  даказвае  аб тым, што любое канечнае цела камутатыўнае, г.зн. з'яўляецца полем.

Сучаснае аксіяматычнае азначэнне поля (з канечнымі палямі ў якасці асобнага выпадку) належыць  і выкладзена ў яго працы 1910 годаErnst Steinitz, " Algebraische Theorie der Körper ", Journal für die reine und angewandte Mathematik, vol. 137, 1910, p. 167—309 (ISSN 0075-4102).

Далейшае развіццё тэорыі адбываецца ў тэарэтычных і прыкладных галінах, якія выкарыстоўваюць канечныя палі ў той ці іншай ролі.

 Уласцівасці і факты 
 Характарыстыка канечнага поля з'яўляецца простым лікам, і лік элементаў канечнага поля ёсць яго характарыстыка ў натуральнай ступені: .
 Канечнае поле не можа быць , бо ўпарадкаванае поле ўтрымлівае бесканечна многа элементаў.
 Канечнае поле не з'яўляецца алгебраічна замкнутым. Мнагачлен

 не мае каранёў у , прычым 
 Для кожнага простага ліку  і натуральнага  існуе канечнае поле з  элементаў, адзінае, з дакладнасцю да ізамарфізму. Гэтае поле ізаморфнае полю раскладання мнагачлена .
 Мультыплікатыўная група  канечнага поля  з'яўляецца цыклічнай групай парадку .
 У прыватнасці, у канечным полі заўсёды існуе  , парадак якога роўны , г. зн.  і  для .
 Любы ненулявы элемент  з'яўляецца некаторай ступенню прымітыўнага элемента:
 .
 Поле  утрымлівае ў сабе ў якасці падполя  тады і толькі тады, калі  з'яўляецца дзельнікам .
 Лік  непрыводных мнагачленаў ступені  вызначаецца па формуле

 дзе  — функцыя Мёбіуса.

 Прыклады 

 F2 
 +  0  1 0 0  1 1 1  0 ×  0  1 0 0  0 1 0  1

 F3 
 +  0  1  2 0 0  1  2 1 1  2  0 2 2  0  1 ×  0  1  2 0 0  0  0 1 0  1  2 2 0  2  1

 F4 
 +  0  1  A  B 0 0  1  A  B 1 1  0  B  A A A  B  0  1 B B  A  1  0 ×  0  1  A  B 0 0  0  0  0 1 0  1  A  B A 0  A  B  1 B 0  B  1  A

 Іншае 
 , дзе  — просты:  і гэтак далей.
 , дзе  — галоўны ідэал кальца , спароджаны непрыводным мнагачленам  ступені .

 Пабудова 

Пабудова поля , дзе p — просты лік, n — натуральны лік, пачынаецца з пабудовы ягонага простага падполя  (якое супадае з усім полем пры n=1).

 Простае поле  будуецца як кальцо  вылікаў па модулю , якое дзякуючы прастаце  не мае дзельнікаў нуля і таму з'яўляецца полем.
 Элементы  — лікі . Аперацыі праводзяцца як са звычайнымі цэлымі лікамі з прывядзеннем выніку па модулю .
 Поле  пры n>1 будуецца як фактарколца , дзе  — непрыводны мнагачлен ступені n над полем . Такім чынам, каб пабудаваць поле з  элементаў, дастаткова адшукаць мнагачлен ступені , непрыводны над полем .
 Элементамі поля  з'яўляюцца ўсе мнагачлены ступені, меншай чым  з каэфіцыентамі з . Арыфметычныя аперацыі (складанне і множанне) ажыццяўляюцца па модулю мнагачлена , г.зн. вынік адпаведнай аперацыі — гэта астача ад дзялення на  з прывядзеннем каэфіцыентаў па модулю .

 Прыклад пабудовы поля GF(9) 
Каб пабудаваць поле , неабходна знайсци мнагачлен ступені 2, непрыводны над . Такімі мнагачленамі з'яўляюцца:

Возьмем, напрыклад, , тады шуканае поле ёсць . Калі замест  узяць іншы мнагачлен, то атрымаецца новае поле, ізаморфнае старому.

 Табліца складання ў GF(9) 

 + 0 1 2       0 0 1 2       1 1 2 0       2 2 0 1              0 1 2        1 2 0        2 0 1     0 1 2        1 2 0        2 0 1   

 Табліца множання ў GF(9) 

 × 0 1 2       0 0 0 0 0 0 0 0 0 0 1 0 1 2       2 0 2 1        0   2   1    0     1  2   0    1    2  0   1   2    0    2    1  0     2  1 

 Прыкладанні 

 Дыяфантавы ўраўненні 
Дыяфантава ўраўненне — ураўненне з цэлымі каэфіцыентамі, у якім зменныя таксама прымаюць цэлалікавыя значэнні. Вялікую хвалю абмеркавання такіх ураўненняў выклікаў Ферма, сфармуляваўшы свае тэарэмы. Малая тэарэма Ферма сцвярджае, што калі  — просты лік, які не з'яўляецца дзельнікам другога ліку , то . У тэорыі канечных палёў гэтая тэарэма з'яўляецца відавочным вынікам з тэарэмы Лагранжа, прымененай да мультыплікатыўнай падгрупы, спароджанай элементам , бо ўся мультыплікатыўная група поля  складаецца з  элементаў.

Ферма заўважае, што адзіныя простыя лікі, якія можна раскласці ў суму двух квадратаў — гэта тыя простыя лікі, якія даюць астачу 1 пры дзеленні на 4. Сярод іншага, ён адзначае, што
.
У сваім пісьме Марену Мерсенну, датаваным 25 снежня 1640 года, Ферма прапануе рашыць ураўненне 

Юліус Дэдэкінд даследаваўR. Dedekind, Supplément XI des Leçons en théorie des nombres de Dirichlet, 1894 падобныя ўраўненні ў нейкім канечным полі . У гэтым полі ўраўненне прымае від . Калі , то рашэнне будзе трывіяльнае. У процілеглым выпадку можна падзяліць абедзве часткі на  і, зрабіўшы замену, атрымліваем ураўненне выгляду . Дамножыўшы на , атрымліваем . Лічачы  утваральнікам мультыплікатыўнай падгрупы парадку 4, можна атрымаць неабходныя і дастатковыя ўмовы на p, пры якіх ураўненне мае рашэнне. Далейшы доказ тэарэмы, праведзены Дэдэкіндам, не выкарыстоўвае паняцці канечных палёў, і яго можна знайсці ў адпаведным артыкуле.

 Тэорыя карэкціруючых кодаў 
Годам стварэння тэорыі карэкціруючых кодаў лічыцца 1948 год, у якім быў апублікаваны артыкул Клода ШэнанаШеннон, К. Математическая теория связи [Текст] / К. Шеннон // Работы по теории информации и кибернетике. — М. : Издательство иностранной литературы, 1963. — С. 243—332., у якой ён паказвае, што наяўнасць памылак пры перадачы інфармацыі па якім-небудзь канале залежыць у тым ліку ад суадносін скорасці перадачы і прапускной здольнасці канала. Скорасць перадачы павінна быць вышэйшая за прапускную здольнасць. Шэнан прывёў доказы, але яны былі прызнаны няслушнымі. Канструктыўны падыход прапанаваў Хэмминг, К. Коды с обнаружением и исправлением ошибок [Текст] / К. Хэмминг // Коды с обнаружением и исправлением ошибок. — М. : Издательство иностранной литературы, 1956. — С. 7-23., задаўшы тым самым напрамак развіцця многіх пазнейшых артыкулаў па тэме. У сваёй працы Хэмінг пабудаваў просты , які пэўным чынам выпраўляе памылкі. Хэмінг разглядаў карэкціруючыя коды толькі над полем . Неўзабаве падобныя коды былі пабудаваны над адвольнымі канечнымі палямі  у 1949 годзеGolay M.J.E. Notes on digital coding // Proceedings IRE. 1949. V. 37, P.657.. Аднак найбольшы ўклад у гэту тэорыю належыць усё ж Хэмінгу.

 Крыптаграфія 
Канечныя палі шырока прымяняюцца ў крыптаграфіі. Асноватворнаю працай лічыцца артыкул  і W. Diffie and M.E. Hellman. New directions in cryptography. IEEE Trans. Info. Theory, IT-22(6):644-654, 1976. па крыптаграфіі з адкрытым ключом, у якім быў прапанаваны . У гэтай працы выкарыстоўваліся канечныя палі пэўнага віду. Цяпер жа існуе вялікае мноства крыптаграфічных пратаколаў і крыптасістэм, заснаваных на выкарыстанні канечных палёў. Гэта і , і , і , і , крыптасістэма , і шмат іншага. Алгарытмы на аснове эліптычных крывых, якія з'яўляюцца адным з ключавых аб'ектаў у сучаснай крыптаграфіі, таксама выкарыстоўваюць канечныя палі.

Таксама часта якасць шыфравання залежыць ад здольнасці хутка генераваць вялікія простыя лікі. Адпаведна, паўстае задача пабудовы алгарытму раскладання на простыя множнікі (вызначэнне простасці таго ці іншага ліку).  апублікаваў даследаваннеM. Rabin, Probabilistic Algorithm for Testing Primality, J. Number Th. 12 (1980), 128—138, у якім ён прапануе тэст прастаты на аснове ўласцівасцей мультыплікатыўнай групы поля.

 Іншае 
Тэорыя канечных палёў самым цесным чынам звязана з модульнаю арыфметыкай. У прыватнасці, паняцце аб канечных палях (якое існавала на той час) памагло Гаусу сфармуляваць квадратычны закон узаемнасціC. F. Gauss, Disquisitiones Arithmeticae, 1801.

 выкарыстаў інструментарый тэорыі канечных палёў для рашэння знакамітай  (ён аналізаваў аналаг дзэта-функцыі Рымана над канечнымі палямі). Найбольш актыўнае абагульненне арыфметычнай геаметрыі на канечныя структуры адбывалася ў другой палавіне XX стагоддзя, калі Андрэ Вейль абагульніў падыход да вывучэння , а П’ер Дэлінь — .  аб алгебраічных мнагастайнасцях над канечнымі палямі, канчаткова даказаныя ў 1940 годзе, былі адным з важных пытанняў таго часу.

У 1960 годзе  і  апублікавалі працуR. C. Bose et D. K. Ray-Chaudhuri, On a class of error-correcting binary group codes, Inform. Control, vol. 3, mars 1960, p. 68-79, у якой даследавалі сямейства мнагачленаў над канечнымі палямі.  абагульніў іх тэорыю і гэта прывяло да стварэння , асобным выпадкам якога з’яўляецца шырока вядомы , які прымяняецца вельмі шырока. Ён выкарыстоўваецца пры запісе і чытанні ў кантролерах аператыўнай памяці, пры архіваванні даных, запісе інфармацыі на жорсткія дыскі (), запісе на CD/DVD дыскі. Цікава тое, што пры пашкоджанні значнага аб’ёму інфармацыі, ці калі сапсавана некалькі сектараў дыскавага накапляльніка, коды Рыда — Соламана дазваляюць аднавіць большую частку згубленай інфармацыі.  выкарыстоўваецца таксама ў сістэме сувязі некаторых зондаў NASA (такіх як Вояджэр)

 Гл. таксама 
 Поле




 Зноскі 

 Літаратура 



Катэгорыя:Абстрактная алгебра
Катэгорыя:Тэорыя палёў