Поле Галуа

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

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

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

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

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

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

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

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

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

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

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

Властивості

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

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

Породжуючий елемент ${𝔽}_q^{*}$ називається також примітивним елементом поля ${𝔽}_q$. Поле ${𝔽}_q$ містить $\phi (q-1)$ примітивних елементів, де $\phi$ — Функція Ейлера.Шаблон:Sfn

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

• Кожен елемент поля ${𝔽}_q$ задовольняє рівності $a^q=a$Шаблон:Sfn.
• Поле ${𝔽}_{p^n}$ містить в собі як підполе ${𝔽}_{p^k}$ тоді і тільки тоді, коли $k$ є дільником $n$Шаблон:Sfn.
• Якщо $f\in {𝔽}_q[x]$ — незвідний многочлен степеня $m$, то поле ${𝔽}_{q^m}$ містить будь-який його корінь $\alpha$, причому множина усіх його коренів має вигляд $\{\alpha ,{\alpha }^q,\dots ,{\alpha }^{q^{m-1}}\}$. Таким чином, ${𝔽}_{q^m}$ є полем розкладу многочлена $f$ над полем ${𝔽}_q$Шаблон:Sfn.
• Для кожного скінченного поля ${𝔽}_q$ та натурального числа $n$ добуток усіх нормованих незвідних над ${𝔽}_q$ многочленів, степінь яких ділить $n$, дорівнює $x^{q^n}-x$. Зокрема, сума степенів таких многочленів дорівнює $q^n$Шаблон:Sfn.
• Число $N(q,n)$ нормованих многочленів степеня $n$, незвідних над полем ${𝔽}_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)$ після застосування формули обертання МебіусаШаблон:Sfn.

Приклади

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

Поле ${𝔽}_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

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

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

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

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

Поле ${𝔽}_4$ можна задати як множину $\{0,1,\alpha ,\alpha +1\}$ (де $\alpha$ — корінь многочлена $f(x)=x^2+x+1$, тобто ${\alpha }^2=-\alpha -1=\alpha +1$). Таблиці операцій ${𝔽}_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$

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

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

$x^2+1$

$x^2+x+2$

$x^2+2x+2$

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

Таблиця додавання в ${𝔽}_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$

Таблиця множення в ${𝔽}_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 {𝔽}_3[x]$ не є Шаблон:Нп).

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

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

Внесок Галуа

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

У 1830 році вісімнадцятирічний Еварист Галуа опублікував працю, яка поклала основу загальної теорії скінченних полів. У цій праці Галуа (у зв'язку з дослідженнями перестановок та алгебраїчних рівнянь) запровадив уявний корінь порівняння $F(x)\equiv 0(\mathrm{mod}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 }$ значень. Далі Галуа показав, що ці значення утворюють поле й мультиплікативна група цього поля є циклічною. Таким чином, із цієї праці почались фундаментальні дослідження загальної теорії скінченних полів. На відміну від попередників, які досліджували лише поля ${𝔽}_p$, Галуа вивчав уже поля ${𝔽}_{p^n}$, які назвали полями Галуа на його честь.

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

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

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

Див. також

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

Джерела

• Шаблон:Винберг.Курс алгебры
• Шаблон:Rotman.An Introduction to the Theory of Groups
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Книга