Поле Галуа
Додавання | Множення | ||||
---|---|---|---|---|---|
+ | 0 | 1 | × | 0 | 1 |
0 | |||||
1 |
Скінченне поле або поле Галуа (на честь Евариста Галуа) — поле, яке складається зі скінченної множини елементів.
Найменше поле Галуа містить лише два елементи: та , арифметичні операції над якими поводяться майже як звичайно, за винятком правила . Це поле широко застосується в дискретній математиці, комп'ютерних науках і теорії кодування.
Ідея застосування поля полягає в тому, що доцільно розглядати послідовності з нулів й одиниць як елементи деякої алгебраїчної структури: векторного простору над цим полем, розширення , кільця многочленів , тощо.
Алгебраїчні операції в цій структурі приводять до низки важливих конструкцій в означених галузях, наприклад, скінчених проективних площин, кодів Ріда-Мюлера і кодів Гоппа. Засновані на теорії скінчених полів алгоритми перевірки на простоту і факторизації цілих чисел відіграють важливу роль у сучасній прикладній теорії чисел.
Для будь-якого простого числа , кільце залишків — це скінчене поле з елементів, яке позначається . Елементи цього поля можуть бути представлені цілими числами , які додаються і множаться «за модулем ». Будь-яке скінчене поле містить елементів і однозначно задається своєю характеристикою і степенем .
Класифікація
ред.Будь-яке скінчене поле має просту характеристику
, тому воно містить в собі просте підполе
. З аксіом поля випливає, що
являє собою скінченновимірний векторний простір над
розмірності
.
Довільний елемент задається своїми
координатами відносно певного базису, які належать до
. Таким чином, поле
складається з
елементів. Виявляється, що і навпаки, для даних простого
і натурального
. існує єдине, не враховуючи автоморфізмів, поле Галуа з
елементів, яке має характеристику
і позначається
.
Властивості
ред.Циклічність мультиплікативної групи
ред.Ненульові елементи поля утворюють групу щодо операції множення, яка називається мультиплікативною групою поля і позначається
. Ця група є циклічною, тобто вона має породжуючий елемент, а всі інші елементи отримуються піднесенням до степеня породжуючого[1].
Породжуючий елемент називається також примітивним елементом поля
. Поле
містить
примітивних елементів, де
— Функція Ейлера.[2]
Інші властивості
ред.- Кожен елемент поля
задовольняє рівності
[3].
- Поле
містить в собі як підполе
тоді і тільки тоді, коли
є дільником
[4].
- Якщо
— незвідний многочлен степеня
, то поле
містить будь-який його корінь
, причому множина усіх його коренів має вигляд
. Таким чином,
є полем розкладу многочлена
над полем
[5].
- Для кожного скінченного поля
та натурального числа
добуток усіх нормованих незвідних над
многочленів, степінь яких ділить
, дорівнює
. Зокрема, сума степенів таких многочленів дорівнює
[6].
- Число
нормованих многочленів степеня
, незвідних над полем
визначається за формулою
де
— Функція Мебіуса. Це твердження випливає з формули
після застосування формули обертання Мебіуса[7].
Приклади
ред.Поле з двох елементів
ред.Поле складається з двох елементів, але воно може бути задано різними способами залежно від вибору елементів і визначення операцій додавання та множення на них:[8]
- Як множина з двох чисел «
» і «
», на якій операції додавання та множення визначені як додавання та множення чисел з приведенням результату по модулю
:
|
|
- Як множина з двох логічних об'єктів «Хибність» (F) і «Істина» (T), на якій операції додавання та множення визначено як булеві операції «виключна диз'юнкція» і «кон'юнкція» відповідно:
|
|
Ці поля ізоморфні, тобто фактично це два різні способи задання одного й того ж поля.
Поле з трьох елементів
ред.Поле . Додавання та множення визначені як додавання та множення чисел по модулю
. Таблиці операцій
мають вигляд:
|
|
Поле з чотирьох елементів
ред.Поле можна задати як множину
(де
— корінь многочлена
, тобто
). Таблиці операцій
мають вигляд:[9]
|
|
Поле з дев'яти елементів
ред.Щоб задати поле достатньо знайти нормований многочлен степеня
, незвідний над
. Такими многочленами є:
Для полем є
(якщо замість
взяти інший многочлен, то буде нове поле, ізоморфне старому). В наведених нижче таблиця символ
означає клас еквівалентності многочлена
у фактор-кільці
, який задовольняє рівнянню
.
Таблиця додавання в визначається, виходячи з відношення
:
+ | 0 | 1 | 2 | ||||||
---|---|---|---|---|---|---|---|---|---|
0 | 0 | 1 | 2 | ||||||
1 | 1 | 2 | 0 | ||||||
2 | 2 | 0 | 1 | ||||||
0 | 1 | 2 | |||||||
1 | 2 | 0 | |||||||
2 | 0 | 1 | |||||||
0 | 1 | 2 | |||||||
1 | 2 | 0 | |||||||
2 | 0 | 1 |
Таблиця множення в визначається з співвідношення
:
× | 0 | 1 | 2 | ||||||
---|---|---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 2 | ||||||
2 | 0 | 2 | 1 | ||||||
0 | 2 | 1 | |||||||
0 | 1 | 2 | |||||||
0 | 1 | 2 | |||||||
0 | 1 | 2 | |||||||
0 | 2 | 1 | |||||||
0 | 2 | 1 |
Можна перевірити, що елемент має порядок
і є примітивним. Елемент
не є примітивним, так як
(іншими словами, многочлен
не є примітивним[en])[9].
Мультиплікативна група поля з 16 елементів
ред.Коли поле задається з допомогою неприводимого многочлена
, елементи розширення задаються наборами коефіцієнтів многочлена, який отримується в залишку при діленні на
, записаними в порядку зростання степенів. Мультиплікативна група породжується елементом
, який записується як (0, 1, 0, 0)[10].
Многочлен | Степінь | |
---|---|---|
(0, 1, 0, 0) | ||
(0, 0, 1, 0) | ||
(0, 0, 0, 1) | ||
(1, 1, 0, 0) | ||
(0, 1, 1, 0) | ||
(0, 0, 1, 1) | ||
(1, 1, 0, 1) | ||
(1, 0, 1, 0) | ||
(0, 1, 0, 1) | ||
(1, 1, 1, 0) | ||
(0, 1, 1, 1) | ||
(1, 1, 1, 1) | ||
(1, 0, 1, 1) | ||
(1, 0, 0, 1) | ||
(1, 0, 0, 0) |
Історія вивчення
ред.Початки теорії скінченних полів беруть початок із XVII і XVIII століть. Над цією темою працювали такі вчені, як П'єр Ферма, Леонард Ейлер, Жозеф-Луї Лагранж та Адрієн-Марі Лежандр, яких можна вважати засновниками теорії скінченних полів простого порядку. Однак великий інтерес представляє загальна теорія скінченних полів, що бере свій початок з робіт Гауса та Галуа[11]. До деякого часу ця теорія знаходила застосування лише в алгебрі та теорії чисел, проте згодом були знайдені нові точки дотику з алгебричною геометрією, комбінаторикою та теорією кодування[12].
Внесок Галуа
ред.![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/53/Evariste_galois.jpg/220px-Evariste_galois.jpg)
У 1830 році вісімнадцятирічний Еварист Галуа опублікував працю[13], яка поклала основу загальної теорії скінченних полів. У цій праці Галуа (у зв'язку з дослідженнями перестановок та алгебраїчних рівнянь[14]) запровадив уявний корінь порівняння , де
— довільний многочлен степеня
, незвідний по модулю
. Після цього розглядається загальний вираз
, де
— деякі цілі числа по модулю
. Якщо надавати цим числам різні значення, вираз
набуватиме
значень. Далі Галуа показав, що ці значення утворюють поле й мультиплікативна група цього поля є циклічною. Таким чином, із цієї праці почались фундаментальні дослідження загальної теорії скінченних полів. На відміну від попередників, які досліджували лише поля
, Галуа вивчав уже поля
, які назвали полями Галуа на його честь[15].
Насправді, першу працю в цій галузі написав Гаусс приблизно 1797 року, однак за його життя дослідження не було видано. Імовірно, його проігнорував редактор творів Гаусса, тому опублікували цю працю тільки в посмертному виданні 1863 року[16].
Подальший розвиток
ред.У 1893 році математик Еліаким Мур[en] довів теорему про класифікацію скінченних полів, яка стверджує, що будь-яке скінченне поле є полем Галуа, тобто будь-яке поле з елементів ізоморфне полю класів залишків многочленів з коефіцієнтами з
по модулю незвідного многочлена степеня
[17]. Того ж року першу спробу аксіоматичного підходу до теорії скінченних полів зробив Генріх Мартін Вебер[en], який намагався поєднати в своїй праці визначення, які виникли в різних розділах математики, зокрема, і визначення скінченного поля[18]. Далі у 1905 році Джозеф Веддерберн[en] довів теорему Веддерберна про те, що будь-яке скінченне тіло — комутативне, тобто, є полем. Сучасне аксіоматичне визначення поля (зі скінченними полями як окремим випадком) належить Ернсту Стейніцу[en] і викладено в його праці 1910 року[19].
Див. також
ред.Примітки
ред.- ↑ Ю.И.Журавлев, Ю.А.Флеров, М.Н.Вялый. Дискретный анализ. Основы высшей алгебры. — М. : МЗ Пресс, 2007. — С. 151.
- ↑ Лидл, Нидеррайтер, 1998, с. 69-70.
- ↑ Лидл, Нидеррайтер, 1998, с. 66.
- ↑ Лидл, Нидеррайтер, 1998, с. 68.
- ↑ Лидл, Нидеррайтер, 1998, с. 71.
- ↑ Лидл, Нидеррайтер, 1998, с. 119.
- ↑ Лидл, Нидеррайтер, 1998, с. 121.
- ↑ Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И., Владимиров С. М. Защита информации. Учебное пособие. Версия от 22 ноября 2015 года. — С. 249.
- ↑ а б Mullen, Gary L.; Panario, Daniel. Handbook of Finite Fields. — CRC Press, 2013. — ISBN 978-1-4398-7378-6.
- ↑ Ю.И.Журавлев, Ю.А.Флеров, М.Н.Вялый. Дискретный анализ. Основы высшей алгебры. — М. : МЗ Пресс, 2007. — С. 152.
- ↑ Лидл, Нидеррайтер, 1998, с. 10.
- ↑ Лидл, Нидеррайтер, 1998, с. 5.
- ↑ Evariste Galois (1830), Sur la théorie des nombres. Bulletin des sciences mathématiques de M. Férussac 13, pp 428—435 (1830)
- ↑ Бурбаки Н. Очерки по истории математики. — М. : ИЛ, 1963. — С. 102.
- ↑ Israel Kleiner. A History of Abstract Algebra. — Birkhäuser, 2007. — С. 70. — ISBN 978-0-8176-4684-4.
- ↑ G. Frei. The Unpublished Section Eight: On the Way to Function Fields over a Finite Field. — Goldstein Schappacher Schwermer, 2007. — С. 159-198.
- ↑ Moore, Eliakim Hastings. Архівована копія. — Chicago Congr. Papers, 1896. — С. 208-242. Архівовано з джерела 19 листопада 2015. Процитовано 2016-05-26.
- ↑ H. Weber, "Die allgemeinen Grundlagen der Galois'schen Gleichungstheorie", Mathematische Annalen, vol. 43, 1893, p. 521—549
- ↑ 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 с. — 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.