Поле Галуа

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Арифметичні операції у полі Галуа з двох елементів
Додавання Множення
+ 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=\Z/p\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^*. Ця група є циклічною, тобто вона має породжуючий елемент, а всі інші елементи отримуються піднесенням до степеня породжуючого[1].

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

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

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

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

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

Поле \mathbb{F}_2 складається з двух елементів, але воно може бути задано різними способами в залежності від вибору елементів і визначення операцій додавання та множення на них:[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

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

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

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

+ 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] не є примітивним[en])[9].

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

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

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

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

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

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

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

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

У 1893 році математик Еліаким Мур[en] довів теорему о класифікації скінченних полів, яка стверджує, що будь-яке скінченне поле є полем Галуа, тобто будь-яке поле з p^n елементів ізоморфно полю класів залишків многочленів з коефіцієнтами з \mathbb F_p по модулю неприводимого многочлена степеня n[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.