Поле Галуа

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Арифметичні операції у полі Галуа з двох елементів
Додавання Множення
+ 0 1 × 0 1
0
1

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

Найменше поле Галуа містить лише два елементи, та арифметичні операції над якими поводяться майже як звичайно, за винятком правила Це поле широко застосується в дискретній математиці, комп'ютерних науках і теорії кодування.

Ідея застосування поля полягає в тому, що доцільно розглядати послідовності з нулів й одиниць як елементи деякої алгебраїчної структури: векторного простору над цим полем, розширення кільця многочленів тощо.

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

Для будь-якого простого числа кільце залишків  — це скінчене поле з елементів, яке позначається Елементи цього поля можуть бути представлені цілими числами які додаються і множаться «за модулем » Будь-яке скінчене поле містить елементів і однозначно задається своєю характеристикою і степенем

Класифікація[ред.ред. код]

Будь-яке скінчене поле має просту характеристику тому воно містить в собі просте підполе З аксіом поля випливає, що являє собою скінченновимірний векторний простір над розмірності

Довільний елемент задається своїми координатами відносно певного базису, які належать до Таким чином, поле складається з елементів. Виявляється, що і навпаки, для даних простого і натурального існує єдине, не враховуючи автоморфізмів, поле Галуа з елементів, яке має характеристику і позначається

Властивості[ред.ред. код]

Циклічність мультиплікативної групи[ред.ред. код]

Ненульові елементи поля утворюють групу щодо операції множення, яка називається мультиплікативною групою поля і позначається . Ця група є циклічною, тобто вона має породжуючий елемент, а всі інші елементи отримуються піднесенням до степеня породжуючого[1].

Породжуючий елемент називається також примітивним елементом поля Поле містить примітивних елементів, де  — Функція Ейлера.[2]

Інші властивості[ред.ред. код]

  • Кожен елемент поля задовольняє рівності [3].
  • Поле містить в собі в якості підполя тоді і тільки тоді, коли є дільником [4].
  • Якщо  — незвідний многочлен степеня , то поле містить будь-який його корінь , причому множина усіх його коренів має вигляд . Таким чином, є полем розкладу многочлена над полем [5].
  • Для кожного скінченного поля та натурального числа добуток усіх нормованих незвідних над многочленів, степінь яких ділить , дорівнює Зокрема, сума степенів таких многочленів дорівнює [6].
  • Число нормованих многочленів степеня n, незвідних над полем визначається за формулою де  — Функція Мебіуса. Це твердження випливає з формули після застосування формули обертання Мебіуса[7].

Приклади[ред.ред. код]

Поле з двух елементів[ред.ред. код]

Поле складається з двух елементів, але воно може бути задано різними способами в залежності від вибору елементів і визначення операцій додавання та множення на них:[8]

  • Як множина з двох чисел «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
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

Поле з чотирьох елементів[ред.ред. код]

Поле можна задати як множину (где  — корінь многочлена , тобто ). Таблиці операцій мають вигляд:[9]

+ 0 1
0 0 1
1 1 0
0 1
1 0
× 0 1
0 0 0 0 0
1 0 1
0 1
0 1

Поле з дев'яти елементів[ред.ред. код]

Щоб задати поле достатньо знайти нормований многочлен степеня 2, незвідний над . Такими многочленами є:

Для полем є (якщо замість взяти інший многочлен, то буде нове поле, ізоморфне старому). В наведених нижче таблиця символ означає клас еквівалентності многочлена в факторкільце , який задовольняє рівнянню .

Таблиця додавання в визначається, виходячи з відношення :

+ 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

Можна перевірити, що елемент має порядок 8 і є примітивним. Елемент не є примітивним, так як (іншими словами, многочлен не є примітивним[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].

Вклад Галуа[ред.ред. код]

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

У 1830 році вісімнадцятирічний Еварист Галуа опублікував працю[13], яка поклала основу загальної теорії скінченних полів. В цій праці Галуа (в зв'язку з дослідженнями по теорії груп перестановок та алгебраїчних рівнянь[14]) вводить уявний корень порівняння , де  — довільний многочлен степеня , незвідним по модулю p. Після цього розглядається загальний вираз , де  — деякі цілі числа по модулю p. Якщо надавати цим числам різні значення, вираз буде приймати значень. Далі Галуа показує, що ці значення утворюють поле і мультиплікативна група цього поля є циклічною. Таким чином, можна вважати що з цієї праці почались фундаментальні дослідження загальної теорії скінченних полів. На відміну від його попередників, які досліджували лише поля , Галуа вивчає вже поля , які назвали полями Галуа в його честь[15].

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

Подальший розвиток[ред.ред. код]

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

Примітки[ред.ред. код]

  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. — ISBN 978-1-4398-7378-6.
  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. — ISBN 978-0-8176-4684-4.
  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. A doubly-infinite system of simple groups. — Chicago Congr. Papers, 1896. — С. 208-242.
  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)

Джерела[ред.ред. код]

  • Винберг Э. Б. Курс алгебры. — новое изд., перераб. и доп. — М. : МЦНМО, 2011. — 592 с. — 2000 прим. — ISBN 978-5-94057-685-3.
  • Лидл Р., Нидеррайтер Г. Конечные поля. В 2-х тт. — М. : Мир, 1998. — 430 с. — ISBN 5-03-000065-8.
  • Журавлев Ю. И., Флеров Ю. А., Вялый М. Н. Дискретный анализ. Основы высшей алгебры. — 2-е изд. — М. : МЗ Пресс, 2007. — 224 с. — 1000 прим. — ISBN 5-94073-101-5.
  • Васильев К. К., Глушков В. А., Дормидонтов А. В., Нестеренко А. Г. Теория электрической связи. — Ульяновск : УлГТУ, 2008. — 452 с. — ISBN 978-5-9795-0203-8.
  • 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.