Арифметичні операції у полі Галуа з двох елементів

Додавання			Множення
+	0	1	×	0	1
0	${\displaystyle 0}$	${\displaystyle 1}$		${\displaystyle 0}$	${\displaystyle 0}$
1	${\displaystyle 1}$	${\displaystyle 0}$		${\displaystyle 0}$	${\displaystyle 1}$

Скінченне поле або поле Галуа (на честь Евариста Галуа) — поле, яке складається зі скінченної множини елементів.

Найменше поле Галуа ${\displaystyle GF(2)=\mathbb {F} _{2}}$ містить лише два елементи: ${\displaystyle 0}$ та ${\displaystyle 1}$, арифметичні операції над якими поводяться майже як звичайно, за винятком правила ${\displaystyle 1+1=0}$. Це поле широко застосується в дискретній математиці, комп'ютерних науках і теорії кодування.

Ідея застосування поля ${\displaystyle \mathbb {F} _{2}}$ полягає в тому, що доцільно розглядати послідовності з нулів й одиниць як елементи деякої алгебраїчної структури: векторного простору над цим полем, розширення ${\displaystyle \mathbb {F} _{2^{n}}}$, кільця многочленів ${\displaystyle \mathbb {F} _{2}[t]}$, тощо.

Алгебраїчні операції в цій структурі приводять до низки важливих конструкцій в означених галузях, наприклад, скінчених проективних площин, кодів Ріда-Мюлера і кодів Гоппа. Засновані на теорії скінчених полів алгоритми перевірки на простоту і факторизації цілих чисел відіграють важливу роль у сучасній прикладній теорії чисел.

Для будь-якого простого числа ${\displaystyle p}$, кільце залишків ${\displaystyle (\operatorname {mod} \,p)}$ — це скінчене поле з ${\displaystyle \ p}$ елементів, яке позначається ${\displaystyle GF(p)=\mathbb {F} _{p}=\mathbb {Z} /p\mathbb {Z} }$. Елементи цього поля можуть бути представлені цілими числами ${\displaystyle 0,1,\ldots ,p-1}$, які додаються і множаться «за модулем ${\displaystyle p}$».

Будь-яке скінчене поле містить ${\displaystyle p^{n}}$ елементів і однозначно задається своєю характеристикою ${\displaystyle p}$ і степенем ${\displaystyle n}$.

Будь-яке скінчене поле ${\displaystyle \mathbf {K} }$ має просту характеристику ${\displaystyle p>0}$, тому воно містить в собі просте підполе ${\displaystyle \mathbb {F} _{p}}$. З аксіом поля випливає, що ${\displaystyle \mathbf {K} }$ являє собою скінченновимірний векторний простір над ${\displaystyle \mathbb {F} _{p}}$ розмірності ${\displaystyle n\geq 1}$.

Довільний елемент ${\displaystyle \mathbf {K} }$ задається своїми ${\displaystyle n}$ координатами відносно певного базису, які належать до ${\displaystyle \mathbb {F} _{p}}$. Таким чином, поле ${\displaystyle \mathbf {K} }$ складається з ${\displaystyle q=p^{n}}$ елементів. Виявляється, що і навпаки, для даних простого ${\displaystyle p}$ і натурального ${\displaystyle n\geq 1}$. існує єдине, не враховуючи автоморфізмів, поле Галуа з ${\displaystyle q=p^{n}}$ елементів, яке має характеристику ${\displaystyle p}$ і позначається ${\displaystyle GF(q)=\mathbb {F} _{q}=\mathbb {F} _{p^{n}}}$.

Ненульові елементи поля ${\displaystyle \mathbb {F} _{q}}$ утворюють групу щодо операції множення, яка називається мультиплікативною групою поля і позначається ${\displaystyle \mathbb {F} _{q}^{*}}$. Ця група є циклічною, тобто вона має породжуючий елемент, а всі інші елементи отримуються піднесенням до степеня породжуючого^[1].

Породжуючий елемент ${\displaystyle \mathbb {F} _{q}^{*}}$ називається також примітивним елементом поля ${\displaystyle \mathbb {F} _{q}}$. Поле ${\displaystyle \mathbb {F} _{q}}$ містить ${\displaystyle \varphi (q-1)}$ примітивних елементів, де ${\displaystyle \varphi }$ — Функція Ейлера.^[2]

• Кожен елемент поля ${\displaystyle \mathbb {F} _{q}}$ задовольняє рівності ${\displaystyle a^{q}=a}$^[3].
• Поле ${\displaystyle \mathbb {F} _{p^{n}}}$ містить в собі як підполе ${\displaystyle \mathbb {F} _{p^{k}}}$ тоді і тільки тоді, коли ${\displaystyle k}$ є дільником ${\displaystyle n}$^[4].
• Якщо ${\displaystyle f\in \mathbb {F} _{q}[x]}$ — незвідний многочлен степеня ${\displaystyle m}$, то поле ${\displaystyle \mathbb {F} _{q^{m}}}$ містить будь-який його корінь ${\displaystyle \alpha }$, причому множина усіх його коренів має вигляд ${\displaystyle \{\alpha ,\alpha ^{q},\ldots ,\alpha ^{q^{m-1}}\}}$. Таким чином, ${\displaystyle \mathbb {F} _{q^{m}}}$ є полем розкладу многочлена ${\displaystyle f}$ над полем ${\displaystyle \mathbb {F} _{q}}$^[5].
• Для кожного скінченного поля ${\displaystyle \mathbb {F} _{q}}$ та натурального числа ${\displaystyle n}$ добуток усіх нормованих незвідних над ${\displaystyle \mathbb {F} _{q}}$ многочленів, степінь яких ділить ${\displaystyle n}$, дорівнює ${\displaystyle x^{q^{n}}-x}$. Зокрема, сума степенів таких многочленів дорівнює ${\displaystyle q^{n}}$^[6].
• Число ${\displaystyle N(q,n)}$ нормованих многочленів степеня ${\displaystyle n}$, незвідних над полем ${\displaystyle \mathbb {F} _{q},}$ визначається за формулою ${\displaystyle N(q,n)={\frac {1}{n}}\sum _{d|n}\mu (d)q^{\frac {n}{d}},}$ де ${\displaystyle \mu }$ — Функція Мебіуса. Це твердження випливає з формули ${\displaystyle q^{n}=\sum _{d|n}dN(q,d)}$ після застосування формули обертання Мебіуса^[7].

Поле ${\displaystyle \mathbb {F} _{2}}$ складається з двох елементів, але воно може бути задано різними способами залежно від вибору елементів і визначення операцій додавання та множення на них:^[8]

• Як множина з двох чисел «${\displaystyle 0}$» і «${\displaystyle 1}$», на якій операції додавання та множення визначені як додавання та множення чисел з приведенням результату по модулю ${\displaystyle 2}$:

• Як множина з двох логічних об'єктів «Хибність» (F) і «Істина» (T), на якій операції додавання та множення визначено як булеві операції «виключна диз'юнкція» і «кон'юнкція» відповідно:

Ці поля ізоморфні, тобто фактично це два різні способи задання одного й того ж поля.

Поле ${\displaystyle \mathbb {F} _{3}=\{0,1,2\}}$. Додавання та множення визначені як додавання та множення чисел по модулю ${\displaystyle 3}$. Таблиці операцій ${\displaystyle \mathbb {F} _{3}}$ мають вигляд:

Поле ${\displaystyle \mathbb {F} _{4}}$ можна задати як множину ${\displaystyle \{0,1,\alpha ,\alpha +1\}}$ (де ${\displaystyle \alpha }$ — корінь многочлена ${\displaystyle f(x)=x^{2}+x+1}$, тобто ${\displaystyle \alpha ^{2}=-\alpha -1=\alpha +1}$). Таблиці операцій ${\displaystyle \mathbb {F} _{4}}$ мають вигляд:^[9]

+ 0 1 ${\displaystyle \alpha }$ ${\displaystyle \alpha +1}$ 0 0 1 ${\displaystyle \alpha }$ ${\displaystyle \alpha +1}$ 1 1 0 ${\displaystyle \alpha +1}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha +1}$ 0 1 ${\displaystyle \alpha +1}$ ${\displaystyle \alpha +1}$ ${\displaystyle \alpha }$ 1 0

× 0 1 ${\displaystyle \alpha }$ ${\displaystyle \alpha +1}$ 0 0 0 0 0 1 0 1 ${\displaystyle \alpha }$ ${\displaystyle \alpha +1}$ ${\displaystyle \alpha }$ 0 ${\displaystyle \alpha }$ ${\displaystyle \alpha +1}$ 1 ${\displaystyle \alpha +1}$ 0 ${\displaystyle \alpha +1}$ 1 ${\displaystyle \alpha }$

Щоб задати поле ${\displaystyle \mathbb {F} _{9}=\mathrm {GF} (3^{2})}$ достатньо знайти нормований многочлен степеня ${\displaystyle 2}$, незвідний над ${\displaystyle \mathbb {F} _{3}}$. Такими многочленами є:

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

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

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

Для ${\displaystyle x^{2}+1}$ полем є ${\displaystyle \mathbb {F} _{9}=\mathbb {Z} _{3}[x]/(x^{2}+1)}$ (якщо замість ${\displaystyle x^{2}+1}$ взяти інший многочлен, то буде нове поле, ізоморфне старому). В наведених нижче таблиця символ ${\displaystyle i}$ означає клас еквівалентності многочлена ${\displaystyle x}$ у фактор-кільці ${\displaystyle \mathbb {Z} _{3}[x]/(x^{2}+1)}$, який задовольняє рівнянню ${\displaystyle i^{2}+1=0}$.

Таблиця додавання в ${\displaystyle \mathbb {F} _{9}}$ визначається, виходячи з відношення ${\displaystyle 1+1+1=0}$:

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

Таблиця множення в ${\displaystyle \mathbb {F} _{9}}$ визначається з співвідношення ${\displaystyle i^{2}=-1}$:

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

Можна перевірити, що елемент ${\displaystyle i+1}$ має порядок ${\displaystyle 8}$ і є примітивним. Елемент ${\displaystyle i}$ не є примітивним, так як ${\displaystyle i^{4}=1}$ (іншими словами, многочлен ${\displaystyle x^{2}+1\in \mathbb {F} _{3}[x]}$ не є примітивним^[en])^[9].

Коли поле ${\displaystyle \mathbb {F} _{16}=\mathrm {GF} (2^{4})}$ задається з допомогою неприводимого многочлена ${\displaystyle x^{4}+x+1}$, елементи розширення задаються наборами коефіцієнтів многочлена, який отримується в залишку при діленні на ${\displaystyle x^{4}+x+1}$, записаними в порядку зростання степенів. Мультиплікативна група породжується елементом ${\displaystyle \alpha =x}$, який записується як (0, 1, 0, 0)^[10].

Многочлен	Степінь ${\displaystyle \alpha }$	${\displaystyle 1,x,x^{2},x^{3}}$
	${\displaystyle \alpha }$	(0, 1, 0, 0)
	${\displaystyle \alpha ^{2}}$	(0, 0, 1, 0)
	${\displaystyle \alpha ^{3}}$	(0, 0, 0, 1)
${\displaystyle 1+\alpha }$	${\displaystyle \alpha ^{4}}$	(1, 1, 0, 0)
${\displaystyle \alpha +\alpha ^{2}}$	${\displaystyle \alpha ^{5}}$	(0, 1, 1, 0)
${\displaystyle \alpha ^{2}+\alpha ^{3}}$	${\displaystyle \alpha ^{6}}$	(0, 0, 1, 1)
${\displaystyle \alpha ^{3}+\alpha +1=\alpha ^{3}+\alpha ^{4}}$	${\displaystyle \alpha ^{7}}$	(1, 1, 0, 1)
${\displaystyle 1+\alpha ^{2}=\alpha +1+\alpha ^{2}+\alpha }$	${\displaystyle \alpha ^{8}}$	(1, 0, 1, 0)
${\displaystyle \alpha +\alpha ^{3}}$	${\displaystyle \alpha ^{9}}$	(0, 1, 0, 1)
${\displaystyle \alpha ^{2}+1+\alpha =\alpha ^{2}+\alpha ^{4}}$	${\displaystyle \alpha ^{10}}$	(1, 1, 1, 0)
${\displaystyle \alpha +\alpha ^{2}+\alpha ^{3}}$	${\displaystyle \alpha ^{11}}$	(0, 1, 1, 1)
${\displaystyle 1+\alpha +\alpha ^{2}+\alpha ^{3}=\alpha ^{2}+\alpha ^{3}+\alpha ^{4}}$	${\displaystyle \alpha ^{12}}$	(1, 1, 1, 1)
${\displaystyle 1+\alpha ^{2}+\alpha ^{3}=\alpha +\alpha ^{2}+\alpha ^{3}+\alpha ^{4}}$	${\displaystyle \alpha ^{13}}$	(1, 0, 1, 1)
${\displaystyle 1+\alpha ^{3}=\alpha +\alpha ^{3}+\alpha ^{4}}$	${\displaystyle \alpha ^{14}}$	(1, 0, 0, 1)
${\displaystyle 1=\alpha +\alpha ^{4}}$	${\displaystyle \alpha ^{15}}$	(1, 0, 0, 0)

Початки теорії скінченних полів беруть початок із XVII і XVIII століть. Над цією темою працювали такі вчені, як П'єр Ферма, Леонард Ейлер, Жозеф-Луї Лагранж та Адрієн-Марі Лежандр, яких можна вважати засновниками теорії скінченних полів простого порядку. Однак великий інтерес представляє загальна теорія скінченних полів, що бере свій початок з робіт Гауса та Галуа^[11]. До деякого часу ця теорія знаходила застосування лише в алгебрі та теорії чисел, проте згодом були знайдені нові точки дотику з алгебричною геометрією, комбінаторикою та теорією кодування^[12].

У 1830 році вісімнадцятирічний Еварист Галуа опублікував працю^[13], яка поклала основу загальної теорії скінченних полів. У цій праці Галуа (у зв'язку з дослідженнями перестановок та алгебраїчних рівнянь^[14]) запровадив уявний корінь порівняння ${\displaystyle F(x)\equiv 0{\pmod {p}}}$, де ${\displaystyle F(x)}$ — довільний многочлен степеня ${\displaystyle \nu }$, незвідний по модулю ${\displaystyle p}$. Після цього розглядається загальний вираз ${\displaystyle A=a_{0}+{a_{1}}i+{a_{2}}i^{2}+...+a_{\nu -1}i^{\nu -1}}$, де ${\displaystyle a_{0},a_{1},...,a_{\nu -1}}$ — деякі цілі числа по модулю ${\displaystyle p}$. Якщо надавати цим числам різні значення, вираз ${\displaystyle A}$ набуватиме ${\displaystyle p^{\nu }}$ значень. Далі Галуа показав, що ці значення утворюють поле й мультиплікативна група цього поля є циклічною. Таким чином, із цієї праці почались фундаментальні дослідження загальної теорії скінченних полів. На відміну від попередників, які досліджували лише поля ${\displaystyle \mathbb {F} _{p}}$, Галуа вивчав уже поля ${\displaystyle \mathbb {F} _{p^{n}}}$, які назвали полями Галуа на його честь^[15].

Насправді, першу працю в цій галузі написав Гаусс приблизно 1797 року, однак за його життя дослідження не було видано. Імовірно, його проігнорував редактор творів Гаусса, тому опублікували цю працю тільки в посмертному виданні 1863 року^[16].

У 1893 році математик Еліаким Мур^[en] довів теорему про класифікацію скінченних полів, яка стверджує, що будь-яке скінченне поле є полем Галуа, тобто будь-яке поле з ${\displaystyle p^{n}}$ елементів ізоморфне полю класів залишків многочленів з коефіцієнтами з ${\displaystyle \mathbb {F} _{p}}$ по модулю незвідного многочлена степеня ${\displaystyle n}$^[17]. Того ж року першу спробу аксіоматичного підходу до теорії скінченних полів зробив Генріх Мартін Вебер^[en], який намагався поєднати в своїй праці визначення, які виникли в різних розділах математики, зокрема, і визначення скінченного поля^[18]. Далі у 1905 році Джозеф Веддерберн^[en] довів теорему Веддерберна про те, що будь-яке скінченне тіло — комутативне, тобто, є полем. Сучасне аксіоматичне визначення поля (зі скінченними полями як окремим випадком) належить Ернсту Стейніцу^[en] і викладено в його праці 1910 року^[19].

• Побудова Пелі

• Винберг Э. Б. Курс алгебри. — 4-е изд. — Москва : МЦНМО, 2011. — 592 с. — ISBN 978-5-94057-685-3.(рос.)

• Джозеф Ротман^[en]. An Introduction to the Theory of Groups. — 4th. — Springer (Graduate Texts in Mathematics), 1994. — 532 с. — ISBN 978-0387942858.(англ.)
• Лидл Р., Нидеррайтер Г. Конечные поля. В 2-х тт. — М. : Мир, 1998. — 430 с. — ISBN 5-03-000065-8.
• Журавлев Ю. И., Флеров Ю. А., Вялый М. Н. Дискретный анализ. Основы высшей алгебры. — 2-е изд. — М. : МЗ Пресс, 2007. — 224 с. — 1000 прим. — ISBN 5-94073-101-5.
• Ernst Steinitz. Algebraische Theorie der Körper. — Journal für die reine und angewandte Mathematik, 1910. — Т. 137. — С. 167—309.
• W. Diffie and M.E. Hellman. New Directions in Cryptography. — 1976.
• Israel Kleiner. A History of Abstract Algebra. — Birkhäuser, 2007. — ISBN 978-0-8176-4684-4.