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

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

Канечнае поле звычайна абазначаецца ${\displaystyle \mathbb {F} _{q}}$ ці GF(q) (скарачэнне ад Galois field), дзе q — колькасць элементаў поля (магутнасць). З дакладнасцю да ізамарфізму канечнае поле поўнасцю вызначаецца яго магутнасцю, якая заўсёды з'яўляецца ступенню нейкага простага ліку (q = pⁿ, дзе p — просты лік, які з'яўляецца характарыстыкаю поля).

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

Найпрасцейшым прыкладам канечнага поля з'яўляецца ${\displaystyle \mathbb {Z} _{p}=\{0,1,\ldots ,p-1\}}$ — колца вылікаў па модулю простага ліку ${\displaystyle p}$.

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

У 1830 годзе Эварыст Галуа апублікаваў працу^[2], якая стала асноваю агульнай тэорыі канечных палёў. Зыходнаю мэтаю Галуа было вывучэнне параўнання

${\displaystyle f(x)\equiv 0\!\!{\pmod {p}},}$

якое з'яўляецца абагульненнем квадратычных параўнанняў, даследаваных Гаусам (гл. квадратычны закон узаемнасці). Тут ${\displaystyle f(x)}$ — адвольны непрыводны мнагачлен ступені n. У гэтай рабоце Галуа ўводзіць уяўны корань параўнання ${\displaystyle f(x)\equiv 0\!\!{\pmod {p}}}$ і абазначае яго ${\displaystyle i}$. Пасля гэтага разглядаецца агульны выраз

${\displaystyle A=a_{0}+{a_{1}}i+{a_{2}}i^{2}+...+a_{n-1}i^{n-1},}$

дзе ${\displaystyle a_{0},a_{1},...,a_{n-1}}$ — нейкія цэлыя лікі па модулю p. Калі прысвойваць гэтым лікам усе магчымыя значэнні, выраз ${\displaystyle A}$ будзе прымаць ${\displaystyle p^{n}}$ значэнняў. Далей Галуа паказвае, што гэтыя значэнні ўтвараюць поле магутнасці ${\displaystyle p^{n},}$ і яго мультыплікатыўная група з'яўляецца цыклічнаю^[3]. Такім чынам, гэтая праца стала першым каменем у падмурку агульнай тэорыі канечных палёў. У адрозненне ад яго папярэднікаў, якія разглядалі толькі палі ${\displaystyle \mathbb {F} _{p},}$ Галуа разглядае ўжо палі ${\displaystyle \mathbb {F} _{p^{n}},}$ якія пачалі называць палямі Галуа ў яго гонар.

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

У 1893 годзе матэматык Эліякім Мур  (руск.) (бел. даказаў тэарэму аб класіфікацыі канечных палёў^[5], якая сцвярджае, што любое канечнае поле з'яўляецца полем Галуа.

Да гэтага ж года адносіцца першая спроба аксіяматычнага падыходу да тэорыі канечных палёў, ажыццёўленая Генрыхам Веберам  (руск.) (бел., які спрабаваў аб'яднаць у сваёй працы^[6] паняцці, якія ўзніклі ў розных раздзелах матэматыкі, у тым ліку і паняцце канечнага поля.

Далей у 1905 годзе Джозэф Ведэрбёрн  (англ.) (бел. даказвае тэарэму  (англ.) (бел. аб тым, што любое канечнае цела камутатыўнае, г.зн. з'яўляецца полем.

Сучаснае аксіяматычнае азначэнне поля (з канечнымі палямі ў якасці асобнага выпадку) належыць Эрнсту Штайніцу  (руск.) (бел. і выкладзена ў яго працы 1910 года^[7].

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

1. Характарыстыка канечнага поля з'яўляецца простым лікам, і лік элементаў канечнага поля ёсць яго характарыстыка ў натуральнай ступені: ${\displaystyle |\mathbb {F} _{q}|=q=p^{n}}$.
2. Канечнае поле не можа быць упарадкаваным  (руск.) (бел., бо ўпарадкаванае поле ўтрымлівае бесканечна многа элементаў.
3. Канечнае поле не з'яўляецца алгебраічна замкнутым. Мнагачлен

   ${\displaystyle f(T)=1+\prod _{\alpha \in F}\left(T-\alpha \right)}$

   не мае каранёў у ${\displaystyle F}$, прычым ${\displaystyle f(\alpha )=1,\ \forall \alpha \in F}$

4. Для кожнага простага ліку ${\displaystyle p}$ і натуральнага ${\displaystyle n}$ існуе канечнае поле з ${\displaystyle q=p^{n}}$ элементаў, адзінае, з дакладнасцю да ізамарфізму. Гэтае поле ізаморфнае полю раскладання мнагачлена ${\displaystyle x^{q}-x\in \mathbb {F} _{p}[x]}$.
5. Мультыплікатыўная група ${\displaystyle \mathbb {F} _{q}^{*}}$ канечнага поля ${\displaystyle \mathbb {F} _{q}}$ з'яўляецца цыклічнай групай парадку ${\displaystyle q-1}$.
   • У прыватнасці, у канечным полі заўсёды існуе прымітыўны элемент  (руск.) (бел. ${\displaystyle \alpha }$, парадак якога роўны ${\displaystyle q-1}$, г. зн. ${\displaystyle \alpha ^{q-1}=1}$ і ${\displaystyle \alpha ^{i}\neq 1}$ для ${\displaystyle 0<i<q-1}$.
   • Любы ненулявы элемент ${\displaystyle \beta }$ з'яўляецца некаторай ступенню прымітыўнага элемента:

     ${\displaystyle \beta =\alpha ^{i},\quad i\in \{0,1,...,q-2\}}$.

6. Поле ${\displaystyle \mathbb {F} _{p^{n}}}$ утрымлівае ў сабе ў якасці падполя ${\displaystyle \mathbb {F} _{p^{k}}}$ тады і толькі тады, калі ${\displaystyle k}$ з'яўляецца дзельнікам ${\displaystyle n}$.
7. Лік N непрыводных мнагачленаў ступені n вызначаецца па формуле

   ${\displaystyle N(q,n)={\frac {1}{n}}\sum _{d|n}\mu (d)q^{\frac {n}{d}},}$

   дзе ${\displaystyle \mu }$ — функцыя Мёбіуса.

• ${\displaystyle \mathbb {Z} _{p}}$, дзе ${\displaystyle p}$ — просты: ${\displaystyle \mathbb {Z} _{2},\;\mathbb {Z} _{3},\;\mathbb {Z} _{5},\;\mathbb {Z} _{7}}$ і гэтак далей.
• ${\displaystyle \mathrm {GF} (p^{n})=\mathbb {Z} _{p}[x]/\langle f(x)\rangle }$, дзе ${\displaystyle \langle f(x)\rangle }$ — галоўны ідэал кальца ${\displaystyle \mathbb {Z} _{p}[x]}$, спароджаны непрыводным мнагачленам ${\displaystyle f(x)\in \mathbb {Z} _{p}[x]}$ ступені ${\displaystyle n}$.

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

• Простае поле ${\displaystyle \mathrm {GF} (p)}$ будуецца як кальцо ${\displaystyle \mathbb {Z} _{p}}$ вылікаў па модулю ${\displaystyle p}$, якое дзякуючы прастаце ${\displaystyle p}$ не мае дзельнікаў нуля і таму з'яўляецца полем.

  Элементы ${\displaystyle \mathbb {Z} _{p}}$ — лікі ${\displaystyle 0,\;1,\;2,\;\ldots ,\;p-1}$. Аперацыі праводзяцца як са звычайнымі цэлымі лікамі з прывядзеннем выніку па модулю ${\displaystyle p}$.

• Поле ${\displaystyle \mathrm {GF} (p^{n})}$ пры n>1 будуецца як фактарколца ${\displaystyle \mathbb {K} =\mathbb {Z} _{p}[x]/\langle f(x)\rangle }$, дзе ${\displaystyle f(x)}$ — непрыводны мнагачлен ступені n над полем ${\displaystyle \mathbb {Z} _{p}}$. Такім чынам, каб пабудаваць поле з ${\displaystyle p^{n}}$ элементаў, дастаткова адшукаць мнагачлен ступені ${\displaystyle n}$, непрыводны над полем ${\displaystyle \mathbb {Z} _{p}}$.

  Элементамі поля ${\displaystyle \mathbb {K} }$ з'яўляюцца ўсе мнагачлены ступені, меншай чым ${\displaystyle n}$ з каэфіцыентамі з ${\displaystyle \mathbb {Z} _{p}}$. Арыфметычныя аперацыі (складанне і множанне) ажыццяўляюцца па модулю мнагачлена ${\displaystyle f(x)}$, г.зн. вынік адпаведнай аперацыі — гэта астача ад дзялення на ${\displaystyle f(x)}$ з прывядзеннем каэфіцыентаў па модулю ${\displaystyle p}$.

Каб пабудаваць поле ${\displaystyle \mathrm {GF} (9)=\mathrm {GF} (3^{2})}$, неабходна знайсци мнагачлен ступені 2, непрыводны над ${\displaystyle \mathbb {Z} _{3}}$. Такімі мнагачленамі з'яўляюцца:

${\displaystyle x^{2}+1}$

${\displaystyle x^{2}+x+2}$

${\displaystyle x^{2}+2x+2}$

${\displaystyle 2x^{2}+2}$

${\displaystyle 2x^{2}+x+1}$

${\displaystyle 2x^{2}+2x+1}$

Возьмем, напрыклад, ${\displaystyle x^{2}+1}$, тады шуканае поле ёсць ${\displaystyle \mathrm {GF} (9)=\mathbb {Z} _{3}[x]/\langle x^{2}+1\rangle }$. Калі замест ${\displaystyle x^{2}+1}$ узяць іншы мнагачлен, то атрымаецца новае поле, ізаморфнае старому.

${\displaystyle \mathrm {GF} (9)=\mathbb {Z} _{3}[x]/\langle x^{2}+1\rangle }$

+	0	1	2	${\displaystyle x}$	${\displaystyle x+1}$	${\displaystyle x+2}$	${\displaystyle 2x}$	${\displaystyle 2x+1}$	${\displaystyle 2x+2}$
0	0	1	2	${\displaystyle x}$	${\displaystyle x+1}$	${\displaystyle x+2}$	${\displaystyle 2x}$	${\displaystyle 2x+1}$	${\displaystyle 2x+2}$
1	1	2	0	${\displaystyle x+1}$	${\displaystyle x+2}$	${\displaystyle x}$	${\displaystyle 2x+1}$	${\displaystyle 2x+2}$	${\displaystyle 2x}$
2	2	0	1	${\displaystyle x+2}$	${\displaystyle x}$	${\displaystyle x+1}$	${\displaystyle 2x+2}$	${\displaystyle 2x}$	${\displaystyle 2x+1}$
${\displaystyle x}$	${\displaystyle x}$	${\displaystyle x+1}$	${\displaystyle x+2}$	${\displaystyle 2x}$	${\displaystyle 2x+1}$	${\displaystyle 2x+2}$	0	1	2
${\displaystyle x+1}$	${\displaystyle x+1}$	${\displaystyle x+2}$	${\displaystyle x}$	${\displaystyle 2x+1}$	${\displaystyle 2x+2}$	${\displaystyle 2x}$	1	2	0
${\displaystyle x+2}$	${\displaystyle x+2}$	${\displaystyle x}$	${\displaystyle x+1}$	${\displaystyle 2x+2}$	${\displaystyle 2x}$	${\displaystyle 2x+1}$	2	0	1
${\displaystyle 2x}$	${\displaystyle 2x}$	${\displaystyle 2x+1}$	${\displaystyle 2x+2}$	0	1	2	${\displaystyle x}$	${\displaystyle x+1}$	${\displaystyle x+2}$
${\displaystyle 2x+1}$	${\displaystyle 2x+1}$	${\displaystyle 2x+2}$	${\displaystyle 2x}$	1	2	0	${\displaystyle x+1}$	${\displaystyle x+2}$	${\displaystyle x}$
${\displaystyle 2x+2}$	${\displaystyle 2x+2}$	${\displaystyle 2x}$	${\displaystyle 2x+1}$	2	0	1	${\displaystyle x+2}$	${\displaystyle x}$	${\displaystyle x+1}$

${\displaystyle \mathrm {GF} (9)=\mathbb {Z} _{3}[x]/\langle x^{2}+1\rangle }$

×	0	1	2	${\displaystyle x}$	${\displaystyle x+1}$	${\displaystyle x+2}$	${\displaystyle 2x}$	${\displaystyle 2x+1}$	${\displaystyle 2x+2}$
0	0	0	0	0	0	0	0	0	0
1	0	1	2	${\displaystyle x}$	${\displaystyle x+1}$	${\displaystyle x+2}$	${\displaystyle 2x}$	${\displaystyle 2x+1}$	${\displaystyle 2x+2}$
2	0	2	1	${\displaystyle 2x}$	${\displaystyle 2x+2}$	${\displaystyle 2x+1}$	${\displaystyle x}$	${\displaystyle x+2}$	${\displaystyle x+1}$
${\displaystyle x}$	0	${\displaystyle x}$	${\displaystyle 2x}$	2	${\displaystyle x+2}$	${\displaystyle 2x+2}$	1	${\displaystyle x+1}$	${\displaystyle 2x+1}$
${\displaystyle x+1}$	0	${\displaystyle x+1}$	${\displaystyle 2x+2}$	${\displaystyle x+2}$	${\displaystyle 2x}$	1	${\displaystyle 2x+1}$	2	${\displaystyle x}$
${\displaystyle x+2}$	0	${\displaystyle x+2}$	${\displaystyle 2x+1}$	${\displaystyle 2x+2}$	1	${\displaystyle x}$	${\displaystyle x+1}$	${\displaystyle 2x}$	2
${\displaystyle 2x}$	0	${\displaystyle 2x}$	${\displaystyle x}$	1	${\displaystyle 2x+1}$	${\displaystyle x+1}$	2	${\displaystyle 2x+2}$	${\displaystyle x+2}$
${\displaystyle 2x+1}$	0	${\displaystyle 2x+1}$	${\displaystyle x+2}$	${\displaystyle x+1}$	2	${\displaystyle 2x}$	${\displaystyle 2x+2}$	${\displaystyle x}$	1
${\displaystyle 2x+2}$	0	${\displaystyle 2x+2}$	${\displaystyle x+1}$	${\displaystyle 2x+1}$	${\displaystyle x}$	2	${\displaystyle x+2}$	1	${\displaystyle 2x}$

Дыяфантава ўраўненне — ураўненне з цэлымі каэфіцыентамі, у якім зменныя таксама прымаюць цэлалікавыя значэнні. Вялікую хвалю абмеркавання такіх ураўненняў выклікаў Ферма, сфармуляваўшы свае тэарэмы. Малая тэарэма Ферма сцвярджае, што калі ${\displaystyle p}$ — просты лік, які не з'яўляецца дзельнікам другога ліку ${\displaystyle a}$, то ${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$. У тэорыі канечных палёў гэтая тэарэма з'яўляецца відавочным вынікам з тэарэмы Лагранжа, прымененай да мультыплікатыўнай падгрупы, спароджанай элементам ${\displaystyle a}$, бо ўся мультыплікатыўная група поля ${\displaystyle \mathbb {F} _{p}}$ складаецца з ${\displaystyle p-1}$ элементаў.

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

${\displaystyle 5=1^{2}+2^{2},\quad 13=2^{2}+3^{2},\quad 17=1^{2}+4^{2},\quad 29=2^{2}+5^{2},\quad 37=1^{2}+6^{2},\quad 41=4^{2}+5^{2}.}$

.

У сваім пісьме Марену Мерсенну, датаваным 25 снежня 1640 года, Ферма прапануе рашыць ураўненне ${\displaystyle a^{2}+b^{2}=p.}$

Юліус Дэдэкінд даследаваў^[8] падобныя ўраўненні ў нейкім канечным полі ${\displaystyle \mathbb {F} _{p}}$. У гэтым полі ўраўненне прымае від ${\displaystyle a^{2}+b^{2}=0}$. Калі ${\displaystyle b=0}$, то рашэнне будзе трывіяльнае. У процілеглым выпадку можна падзяліць абедзве часткі на ${\displaystyle b^{2}}$ і, зрабіўшы замену, атрымліваем ураўненне выгляду ${\displaystyle x^{2}+1=0}$. Дамножыўшы на ${\displaystyle x^{2}-1=0}$, атрымліваем ${\displaystyle x^{4}-1=0}$. Лічачы ${\displaystyle x}$ утваральнікам мультыплікатыўнай падгрупы парадку 4, можна атрымаць неабходныя і дастатковыя ўмовы на p, пры якіх ураўненне мае рашэнне. Далейшы доказ тэарэмы, праведзены Дэдэкіндам, не выкарыстоўвае паняцці канечных палёў, і яго можна знайсці ў адпаведным артыкуле.

Годам стварэння тэорыі карэкціруючых кодаў лічыцца 1948 год, у якім быў апублікаваны артыкул Клода Шэнана^[9], у якой ён паказвае, што наяўнасць памылак пры перадачы інфармацыі па якім-небудзь канале залежыць у тым ліку ад суадносін скорасці перадачы і прапускной здольнасці канала. Скорасць перадачы павінна быць вышэйшая за прапускную здольнасць. Шэнан прывёў доказы, але яны былі прызнаны няслушнымі. Канструктыўны падыход прапанаваў Рычард Хэмінг  (руск.) (бел.^[10], задаўшы тым самым напрамак развіцця многіх пазнейшых артыкулаў па тэме. У сваёй працы Хэмінг пабудаваў просты код  (руск.) (бел., які пэўным чынам выпраўляе памылкі. Хэмінг разглядаў карэкціруючыя коды толькі над полем ${\displaystyle \mathbb {F} _{2}}$. Неўзабаве падобныя коды былі пабудаваны над адвольнымі канечнымі палямі Голеем  (англ.) (бел. у 1949 годзе^[11]. Аднак найбольшы ўклад у гэту тэорыю належыць усё ж Хэмінгу.

Канечныя палі шырока прымяняюцца ў крыптаграфіі. Асноватворнаю працай лічыцца артыкул Дыфі  (руск.) (бел. і Хелмана  (руск.) (бел.^[12] па крыптаграфіі з адкрытым ключом, у якім быў прапанаваны пратакол абмену ключамі  (руск.) (бел.. У гэтай працы выкарыстоўваліся канечныя палі пэўнага віду. Цяпер жа існуе вялікае мноства крыптаграфічных пратаколаў і крыптасістэм, заснаваных на выкарыстанні канечных палёў. Гэта і схема Эль-Гамаля  (руск.) (бел., і Advanced Encryption Standard  (руск.) (бел., і схема Шнора  (руск.) (бел., і алгарытм Чаўма (сляпы подпіс)  (руск.) (бел., крыптасістэма XTR  (англ.) (бел., і шмат іншага. Алгарытмы на аснове эліптычных крывых, якія з'яўляюцца адным з ключавых аб'ектаў у сучаснай крыптаграфіі, таксама выкарыстоўваюць канечныя палі.

Таксама часта якасць шыфравання залежыць ад здольнасці хутка генераваць вялікія простыя лікі. Адпаведна, паўстае задача пабудовы алгарытму раскладання на простыя множнікі (вызначэнне простасці таго ці іншага ліку). Майкл Рабін  (руск.) (бел. апублікаваў даследаванне^[13], у якім ён прапануе тэст прастаты на аснове ўласцівасцей мультыплікатыўнай групы поля.

Тэорыя канечных палёў самым цесным чынам звязана з модульнаю арыфметыкай. У прыватнасці, паняцце аб канечных палях (якое існавала на той час) памагло Гаусу сфармуляваць квадратычны закон узаемнасці^[14].

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

У 1960 годзе Рай Чандра Бозэ  (англ.) (бел. і Двіджэндра Кумар Рэй-Чаўдхуры  (англ.) (бел. апублікавалі працу^[15], у якой даследавалі сямейства мнагачленаў над канечнымі палямі. Алексіс Акенгем  (англ.) (бел. абагульніў іх тэорыю і гэта прывяло да стварэння кода БЧХ  (руск.) (бел., асобным выпадкам якога з’яўляецца шырока вядомы код Рыда — Соламана  (руск.) (бел., які прымяняецца вельмі шырока. Ён выкарыстоўваецца пры запісе і чытанні ў кантролерах аператыўнай памяці, пры архіваванні даных, запісе інфармацыі на жорсткія дыскі (ECC  (руск.) (бел.), запісе на CD/DVD дыскі. Цікава тое, што пры пашкоджанні значнага аб’ёму інфармацыі, ці калі сапсавана некалькі сектараў дыскавага накапляльніка, коды Рыда — Соламана дазваляюць аднавіць большую частку згубленай інфармацыі. Код БЧХ  (руск.) (бел. выкарыстоўваецца таксама ў сістэме сувязі некаторых зондаў NASA (такіх як Вояджэр)

• Поле
• Алгебраічнае пашырэнне  (руск.) (бел.
• Першаісны корань  (руск.) (бел.
• Аўтамарфізм Фрабеніуса  (руск.) (бел.

• Винберг Э. Б. Курс алгебры. — 3-е изд. — М.: Факториал Пресс, 2002. — 544 с. — 3 000 экз. — ISBN 5-88688-060-7.
• Лидл Р., Нидеррайтер Г. Конечные поля. В 2-х тт. — М.: Мир, 1998.