Скінченне поле

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

Додавання			Множення
+	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}^{*}}$. Ця група є циклічною, тобто вона має породжуючий елемент, а всі інші елементи отримуються піднесенням до степеня породжуючого.

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

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

• Кожен елемент поля ${\displaystyle \mathbb {F} _{q}}$ задовольняє рівності ${\displaystyle a^{q}=a}$.
• Поле ${\displaystyle \mathbb {F} _{p^{n}}}$ містить в собі як підполе ${\displaystyle \mathbb {F} _{p^{k}}}$ тоді і тільки тоді, коли ${\displaystyle k}$ є дільником ${\displaystyle n}$.
• Якщо ${\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}}$.
• Для кожного скінченного поля ${\displaystyle \mathbb {F} _{q}}$ та натурального числа ${\displaystyle n}$ добуток усіх нормованих незвідних над ${\displaystyle \mathbb {F} _{q}}$ многочленів, степінь яких ділить ${\displaystyle n}$, дорівнює ${\displaystyle x^{q^{n}}-x}$. Зокрема, сума степенів таких многочленів дорівнює ${\displaystyle q^{n}}$.
• Число ${\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)}$ після застосування формули обертання Мебіуса.

Приклади

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

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

• Як множина з двох чисел «${\displaystyle 0}$» і «${\displaystyle 1}$», на якій операції додавання та множення визначені як додавання та множення чисел з приведенням результату по модулю ${\displaystyle 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

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

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

Поле ${\displaystyle \mathbb {F} _{3}=\{0,1,2\}}$. Додавання та множення визначені як додавання та множення чисел по модулю ${\displaystyle 3}$. Таблиці операцій ${\displaystyle \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

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

Поле ${\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}}$ мають вигляд:

+ 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]).

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

Коли поле ${\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).

Многочлен	Степінь ${\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 століть. Над цією темою працювали такі вчені, як П'єр Ферма, Леонард Ейлер, Жозеф-Луї Лагранж та Адрієн-Марі Лежандр, яких можна вважати засновниками теорії скінченних полів простого порядку. Однак великий інтерес представляє загальна теорія скінченних полів, що бере свій початок з робіт Гауса та Галуа. До деякого часу ця теорія знаходила застосування лише в алгебрі та теорії чисел, проте згодом були знайдені нові точки дотику з алгебричною геометрією, комбінаторикою та теорією кодування.

Внесок Галуа

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

У 1830 році вісімнадцятирічний Еварист Галуа опублікував працю, яка поклала основу загальної теорії скінченних полів. У цій праці Галуа (у зв'язку з дослідженнями перестановок та алгебраїчних рівнянь) запровадив уявний корінь порівняння ${\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}}}$, які назвали полями Галуа на його честь.

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

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

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

Див. також

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

Примітки

1. Ю.И.Журавлев, Ю.А.Флеров, М.Н.Вялый. Дискретный анализ. Основы высшей алгебры. — М. : МЗ Пресс, 2007. — С. 151.
2. Лидл, Нидеррайтер, 1998, с. 69-70.
3. Лидл, Нидеррайтер, 1998, с. 66.
4. Лидл, Нидеррайтер, 1998, с. 68.
5. Лидл, Нидеррайтер, 1998, с. 71.
6. Лидл, Нидеррайтер, 1998, с. 119.
7. Лидл, Нидеррайтер, 1998, с. 121.
8. Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И., Владимиров С. М. Защита информации. Учебное пособие. Версия от 22 ноября 2015 года. — С. 249.
9. Mullen, Gary L.; Panario, Daniel. Handbook of Finite Fields. — CRC Press, 2013. — .
10. Ю.И.Журавлев, Ю.А.Флеров, М.Н.Вялый. Дискретный анализ. Основы высшей алгебры. — М. : МЗ Пресс, 2007. — С. 152.
11. Лидл, Нидеррайтер, 1998, с. 10.
12. Лидл, Нидеррайтер, 1998, с. 5.
13. Evariste Galois (1830), Sur la théorie des nombres. Bulletin des sciences mathématiques de M. Férussac 13, pp 428—435 (1830)
14. Бурбаки Н. Очерки по истории математики. — М. : ИЛ, 1963. — С. 102.
15. Israel Kleiner. A History of Abstract Algebra. — Birkhäuser, 2007. — С. 70. — .
16. G. Frei. The Unpublished Section Eight: On the Way to Function Fields over a Finite Field. — Goldstein Schappacher Schwermer, 2007. — С. 159-198.
17. Moore, Eliakim Hastings. Архівована копія. — Chicago Congr. Papers, 1896. — С. 208-242. з джерела 19 листопада 2015. Процитовано 2016-05-26.
18. H. Weber, "Die allgemeinen Grundlagen der Galois'schen Gleichungstheorie", Mathematische Annalen, vol. 43, 1893, p. 521—549
19. Ernst Steinitz, "Algebraische Theorie der Körper", Journal für die reine und angewandte Mathematik, vol. 137,‎ 1910, p. 167—309 (ISSN 0075-4102)

Джерела

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

• ^[en]. An Introduction to the Theory of Groups. — 4th. — Springer (Graduate Texts in Mathematics), 1994. — 532 с. — .(англ.)
• Лидл Р., Нидеррайтер Г. Конечные поля. В 2-х тт. — М. : Мир, 1998. — 430 с. — .
• Журавлев Ю. И., Флеров Ю. А., Вялый М. Н. Дискретный анализ. Основы высшей алгебры. — 2-е изд. — М. : МЗ Пресс, 2007. — 224 с. — 1000 прим. — .
• 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. — .