Поле Галуа

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

Додавання			Множення
+	0	1	×	0	1
0	$0$	$1$		$0$	$0$
1	$1$	$0$		$0$	$1$

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

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

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

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

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

Класифікація

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

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

Властивості

Циклічність мультиплікативної групи

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

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

Інші властивості

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

Приклади

Поле з двох елементів

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

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

+ 0 1 0 0 1 1 1 0

× 0 1 0 0 0 1 0 1

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

+ F T F F T T T F

× F T F F F T F T

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

Поле з трьох елементів

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

+ 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

Поле з чотирьох елементів

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

+ 0 1 $\alpha$ $\alpha +1$ 0 0 1 $\alpha$ $\alpha +1$ 1 1 0 $\alpha +1$ $\alpha$ $\alpha$ $\alpha$ $\alpha +1$ 0 1 $\alpha +1$ $\alpha +1$ $\alpha$ 1 0

× 0 1 $\alpha$ $\alpha +1$ 0 0 0 0 0 1 0 1 $\alpha$ $\alpha +1$ $\alpha$ 0 $\alpha$ $\alpha +1$ 1 $\alpha +1$ 0 $\alpha +1$ 1 $\alpha$

Поле з дев'яти елементів

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

$x^{2}+1$

$x^{2}+x+2$

$x^{2}+2x+2$

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

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

+	0	1	2	$i$	$i+1$	$i+2$	$2i$	$2i+1$	$2i+2$
0	0	1	2	$i$	$i+1$	$i+2$	$2i$	$2i+1$	$2i+2$
1	1	2	0	$i+1$	$i+2$	$i$	$2i+1$	$2i+2$	$2i$
2	2	0	1	$i+2$	$i$	$i+1$	$2i+2$	$2i$	$2i+1$
$i$	$i$	$i+1$	$i+2$	$2i$	$2i+1$	$2i+2$	0	1	2
$i+1$	$i+1$	$i+2$	$i$	$2i+1$	$2i+2$	$2i$	1	2	0
$i+2$	$i+2$	$i$	$i+1$	$2i+2$	$2i$	$2i+1$	2	0	1
$2i$	$2i$	$2i+1$	$2i+2$	0	1	2	$i$	$i+1$	$i+2$
$2i+1$	$2i+1$	$2i+2$	$2i$	1	2	0	$i+1$	$i+2$	$i$
$2i+2$	$2i+2$	$2i$	$2i+1$	2	0	1	$i+2$	$i$	$i+1$

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

×	0	1	2	$i$	$i+1$	$i+2$	$2i$	$2i+1$	$2i+2$
0	0	0	0	0	0	0	0	0	0
1	0	1	2	$i$	$i+1$	$i+2$	$2i$	$2i+1$	$2i+2$
2	0	2	1	$2i$	$2i+2$	$2i+1$	$i$	$i+2$	$i+1$
$i$	0	$i$	$2i$	2	$i+2$	$2i+2$	1	$i+1$	$2i+1$
$i+1$	0	$i+1$	$2i+2$	$i+2$	$2i$	1	$2i+1$	2	$i$
$i+2$	0	$i+2$	$2i+1$	$2i+2$	1	$i$	$i+1$	$2i$	2
$2i$	0	$2i$	$i$	1	$2i+1$	$i+1$	2	$2i+2$	$i+2$
$2i+1$	0	$2i+1$	$i+2$	$i+1$	2	$2i$	$2i+2$	$i$	1
$2i+2$	0	$2i+2$	$i+1$	$2i+1$	$i$	2	$i+2$	1	$2i$

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

Мультиплікативна група поля з 16 елементів

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

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

Історія вивчення

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

Внесок Галуа

Еварист Галуа

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

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

Подальший розвиток

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

Див. також

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

Джерела

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

• Джозеф Ротман. 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.