Конечное поле

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Конечное поле или поле Галуа — поле, состоящее из конечного числа элементов.

Конечное поле обычно обозначается \mathbb{F}_q или \mathrm{GF}(q) (сокращение от Galois field), где q — число элементов поля (мощность). С точностью до изоморфизма конечное поле полностью определяется его мощностью, которая всегда является степенью какого-либо простого числа (q=p^n, где p — простое число, являющееся характеристикой поля).

Понятие конечного поля используется, в частности, в теории чисел, алгебраической геометрии, теории Галуа, криптографии, в разработке секретных ключей различных шифров (например, AES).

Простейшим примером конечного поля является \mathbb{Z}_p=\{0,1,\ldots,p-1\} — кольцо вычетов по модулю простого числа p.

История изучения[править | править исходный текст]

Первые упоминания о чём-то, похожем на теорию конечных полей можно найти ещё в XVII в. Над этой темой работали такие учёные, как Пьер Ферма, Леонард Эйлер, Жозеф Луи Лагранж и Адриен Мари Лежандр. Их можно считать основателями теории простых конечных полей. Однако больший интерес представляет общая теория конечных полей, берущая свое начало с работ Гаусса и Галуа. В честь последнего конечные поля и получили свое второе название — поля Галуа. До некоторого времени эта теория находила применение лишь в алгебре и теории чисел, однако во второй половине XX века она нашла новые точки соприкосновения с теорией полей, теорией групп, алгебраической геометрией, комбинаторикой и теорией кодирования[1].

Вклад Галуа[править | править исходный текст]

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

В 1830 году Эварист Галуа опубликовал работу[2], которая положила основу общей теории конечных полей. Исходной целью Галуа было изучение сравнения F(x)\equiv 0\pmod p, которое является обобщением квадратичных сравнений, изученных Гауссом (см. Квадратичный закон взаимности). Здесь F(x) — произвольный неприводимый многочлен степени \nu. В этой работе Галуа вводит воображаемый корень сравнения F(x)\equiv\pmod p и обозначает его i. После этого рассматривается общее выражение 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^{\nu}, и его мультипликативная группа является циклической[3]. Таким образом, эта работа является первым камнем в фундаменте общей теории конечных полей. В отличие от его предшественников, рассматривающих только поля F_p, Галуа рассматривает уже поля F_{p^n}, которые начали называть полями Галуа в честь него.

На самом деле, Гаусс начал работу в этом направлении примерно на 30 лет раньше, однако при его жизни эти исследования так и не были изданы. Вероятно, данное исследование было проигнорировано редактором его сочинений[4], поэтому на свет эта работа появилась только в посмертном издании в 1863.

Дальнейшее развитие[править | править исходный текст]

В 1893 году математик Элиаким Мур доказал теорему о классификации конечных полей[5], смысл которой заключается в том, что любое конечное поле является полем Галуа.

К этому же году относится первая попытка дать аксиоматический подход к теории конечных полей, осуществленная Генрихом Вебером, который пытался объединить в своей работе[6] понятия, возникшие в различных разделах математики, в том числе и понятие конечного поля.

Далее в 1905 году Джозеф Веддербёрн доказывает малую теорему Веддербёрна о том, что любое конечное тело коммутативно, то есть является полем.

Современное аксиоматическое определение поля (с конечными полями в качестве частного случая) принадлежит Эрнсту Стейницу и изложена в его известной работе 1910 года[7].

Дальнейшее развитие теория получает уже в теоретических и прикладных приложениях, которые используют конечные поля в той или иной роли.

Свойства и факты[править | править исходный текст]

  1. Характеристика конечного поля является простым числом, и число элементов конечного поля есть его характеристика в натуральной степени: |\mathbb{F}_q|=q=p^n.
  2. Конечное поле не может быть упорядоченным, так как упорядоченное поле содержит бесконечно много элементов.
  3. Конечное поле не является алгебраически замкнутым. Полином f(T)=1+\prod_{\alpha \in F}\left(T-\alpha\right) не имеет корней в F, причём f(\alpha)=1, \forall \alpha \in F
  4. Для каждого простого числа p и натурального n существует конечное поле из q=p^n элементов, единственное с точностью до изоморфизма. Это поле изоморфно полю разложения многочлена x^q-x\in\mathbb{F}_p[x].
  5. Мультипликативная группа  \mathbb{F}^*_q конечного поля \mathbb{F}_q является циклической группой порядка q-1.
    • В частности, в конечном поле всегда существует примитивный элемент \alpha, порядок которого равен q-1, то есть \alpha^{q-1}=1 и \alpha^i \neq 1 для 0<i<q-1.
    • Любой ненулевой элемент \beta является некоторой степенью примитивного элемента:
      \beta = \alpha^i,\quad i \in \{0,1,...,q-2\}.
  6. Поле \mathbb{F}_{p^n} содержит в себе в качестве подполя \mathbb{F}_{p^k} тогда и только тогда, когда k является делителем n.
  7. Число N неприводимых полиномов степени n определяется по формуле N(q,n)=\frac{1}{n}\sum_{d|n} \mu(d)q^{\frac{n}{d}}, где \mu — функция Мёбиуса.

Примеры[править | править исходный текст]

F2[править | править исходный текст]

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

F3[править | править исходный текст]

+ 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

F4[править | править исходный текст]

+ 0 1 A B
0 0 1 A B
1 1 0 B A
A A B 0 1
B B A 1 0
× 0 1 A B
0 0 0 0 0
1 0 1 A B
A 0 A B 1
B 0 B 1 A

Прочее[править | править исходный текст]

  • \mathbb{Z}_p, где p — простое: \mathbb{Z}_2,\;\mathbb{Z}_3,\;\mathbb{Z}_5,\;\mathbb{Z}_7 и так далее.
  • \mathrm{GF}(p^n)=\mathbb{Z}_p[x]/\langle f(x)\rangle, где \langle f(x)\rangle — главный идеал кольца \mathbb{Z}_p[x], порождённый неприводимым многочленом f(x)\in\mathbb{Z}_p[x] степени n.

Приложения[править | править исходный текст]

Диофантовы уравнения[править | править исходный текст]

Диофантово уравнение является уравнением с целыми коэффициентами, в котором переменные также принимают целочисленные значения. Большую волну обсуждения таких уравнений вызвал Ферма, сформулировав свои теоремы. Малая теорема Ферма утверждает, что если p — простое число, не являющегося делителем другого числа a, то a^{p-1}\equiv 1\pmod p. В теории конечных полей эта теорема является очевидным следствием теоремы Лагранжа, применённой к мультипликативной подгруппе, порождённой элементом a, так как вся мультипликативная группа поля \mathbb F_pсостоит из p-1 элементов.

Ферма замечает, что единственные простые числа, которые можно разложить в сумму двух квадратов — это те простые числа, которые дают остаток 1 при делени на 4. В частности, он отмечает, что

5 = 1^2 + 2^2, \quad 13 = 2^2 + 3^2, \quad 17 = 1^2 + 4^2, \quad 29 = 2^2 + 5^2, \quad 37 = 1^2 + 6^2, \quad 41 = 4^2 + 5^2.

.

В своём письме к Марену Мерсенну, датированному 25 декабря 1640 года, Ферма предлагает решить уравнение a^2+b^2=p.

Юлиус Дедекинд исследовал[8] подобные уравнения в каком-то конечном поле \mathbb{F}_p. В этом поле уравнение принимает вид a^2+b^2=0. Если b=0, то решение тривиально. В противном случае можно разделить обе части на b^2 и, введя замену, получаем уравнение вида x^2+1=0. Домножив на x^2-1=0, получаем x^4-1=0. Считая x генератором мультипликативной подгруппы порядка 4, можно получить необходимые и достаточные условия на p, при которых уравнение имеет решение. Дальнейшее доказательство теоремы, проведённое Дедекиндом, не использует понятия конечных полей и его можно найти в соответствующей статье.

Теория корректирующих кодов[править | править исходный текст]

Годом создания теории корректирующих кодов считается 1948 год, в котором была опубликована статья Клода Шеннона[9], в которой он показывает, что наличие ошибок при передаче информации по какому-либо каналу зависит в том числе от соотношения скорости передачи и пропускной способности канала. Скорость передачи должна быть выше пропускной способности. Шеннон привел доказательства, но они были признаны несостоятельными. Конструктивный подход предложил Ричард Хэмминг[10], задав тем самым вектор развития многих более поздних статей данной тематики. В своей работе Хэмминг построил простой код, исправляющий ошибки определенным образом. Хэмминг рассматривал корректирующие коды только над полем F_2. Вскоре подобные коды были построены над произвольными конечными полями Голеем в 1949 году.[11]. Однако наибольший вклад в эту теорию принадлежит все же Хэммингу.

Криптография[править | править исходный текст]

Конечные поля получили широчайшее применение в криптографии. Основополагающей работой считается статья Диффи и Хелмана[12] по криптографии с открытым ключом, в которой был предложен протокол обмена ключами. В этой работе использовались конечные поля определенного вида. Теперь же существует великое множество криптографических протоколов и криптосистем, основанных на применении конечных полей. Это и схема Эль-Гамаля, и Advanced Encryption Standard, и схема Шнорра, и алгоритм Чаума (слепая подпись), криптосистема XTR, и многое другое. Алгоритмы на основе эллиптических кривых, являющиеся одним из ключевых объектов изучения в современной криптографии также используют конечные поля.

Также зачастую качество шифрования зависит от способности быстро генерировать большие простые числа. Соответственно, встает задача построения алгоритма разложения числа на простые множители (определение простоты того или иного числа). Майкл Рабин опубликовал исследование[13], в котором он предлагает тест простоты на основе свойств мультипликативной группы поля.

Прочее[править | править исходный текст]

Теория конечных полей теснейшим образом пересекается с модульной арифметикой. В частности, понятие о конечных полях (существовавшее на тот момент), помогли Гауссу сформулировать квадратичный закон взаимности[14].

Эмиль Артин использовал инструментарий теории конечных полей для решения знаменитой девятой проблемы Гильберта (он анализировал аналог дзета-функции Римана над конечными полями). Наиболее активное обобщение арифметической геометрии на конечные структуры происходило во второй половине XX века, когда Андре Вейль обобщил подход к изучению алгебраических кривых, а Пьер Делинь — алгебраических многообразий. Гипотезы Вейля[en] об алгебраических многообразиях над конечными полями, окончательно доказанные в 1940 году, были одним из важных вопросов того времени.

Космический зонд «Вояджер»

В 1960 году Raj Chandra Bose и Dwijendra Kumar Ray-Chaudhuri опубликовали работу[15], в которой исследовали семейства многочленов над конечными полями. Alexis Hocquenghem обобщил их теорию и это привело к созданию кода БЧХ, частным случаем которого является широко известный код Рида — Соломона, имеющий очень обширное применение. Он используется при записи и чтении в контроллерах оперативной памяти, при архивировании данных, записи информации на жесткие диски (ECC), записи на CD/DVD диски. Примечательно то, что при повреждении значительного объема информации, или если испорчено несколько секторов дискового носителя, код Рида — Соломона позволяют восстановить большую часть потерянной информации. Код БЧХ используется также в системе связи некоторых зондов NASA (таких как Voyager)

Построение[править | править исходный текст]

Построение поля \mathrm{GF}(p^n), где p — простое число, n — натуральное число, начинается с построения его простого подполя \mathrm{GF}(p) (которое совпадает со всем полем при n=1).

  • Простое поле \mathrm{GF}(p) строится как кольцо \mathbb{Z}_p вычетов по модулю p, которое в виду простоты p не имеет делителей нуля и поэтому является полем.
    Элементы \mathbb{Z}_p — числа 0,\;1,\;2,\;\ldots,\;p-1. Операции проводятся как с обычными целыми числами с приведением результата по модулю p.
  • Поле \mathrm{GF}(p^n) при n>1 строится как факторкольцо \mathbb{K}=\mathbb{Z}_p[x]/\langle f(x)\rangle, где f(x) — неприводимый многочлен степени n над полем \mathbb{Z}_p. Таким образом, для построения поля из p^n элементов достаточно отыскать многочлен степени n, неприводимый над полем \mathbb{Z}_p.
    Элементами поля \mathbb{K} являются все многочлены степени меньшей n с коэффициентами из \mathbb{Z}_p. Арифметические операции (сложение и умножение) проводятся по модулю многочлена f(x), то есть, результат соответствующей операции — это остаток от деления на f(x) с приведением коэффициентов по модулю p.

Пример построения поля GF(9)[править | править исходный текст]

Для построения поля \mathrm{GF}(9) = \mathrm{GF}(3^2) необходимо найти многочлен степени 2, неприводимый над \mathbb{Z}_3. Такими многочленами являются:

x^2+1
x^2+x+2
x^2+2x+2
2x^2+2
2x^2+x+1
2x^2+2x+1

Возьмём, например, x^2+1, тогда искомое поле есть \mathrm{GF}(9)=\mathbb{Z}_3[x]/\langle x^2+1\rangle. Если вместо x^2+1 взять другой многочлен, то получится новое поле, изоморфное старому.

Таблица сложения в GF(9)[править | править исходный текст]

\mathrm{GF}(9)=\mathbb{Z}_3[x]/\langle x^2+1\rangle

+ 0 1 2 x x+1 x+2 2x 2x+1 2x+2
0 0 1 2 x x+1 x+2 2x 2x+1 2x+2
1 1 2 0 x+1 x+2 x 2x+1 2x+2 2x
2 2 0 1 x+2 x x+1 2x+2 2x 2x+1
x x x+1 x+2 2x 2x+1 2x+2 0 1 2
x+1 x+1 x+2 x 2x+1 2x+2 2x 1 2 0
x+2 x+2 x x+1 2x+2 2x 2x+1 2 0 1
2x 2x 2x+1 2x+2 0 1 2 x x+1 x+2
2x+1 2x+1 2x+2 2x 1 2 0 x+1 x+2 x
2x+2 2x+2 2x 2x+1 2 0 1 x+2 x x+1

Таблица умножения в GF(9)[править | править исходный текст]

\mathrm{GF}(9)=\mathbb{Z}_3[x]/\langle x^2+1\rangle

× 0 1 2 x x+1 x+2 2x 2x+1 2x+2
0 0 0 0 0 0 0 0 0 0
1 0 1 2 x x+1 x+2 2x 2x+1 2x+2
2 0 2 1 2x 2x+2 2x+1 x x+2 x+1
x 0 x 2x 2 x+2 2x+2 1 x+1 2x+1
x+1 0 x+1 2x+2 x+2 2x 1 2x+1 2 x
x+2 0 x+2 2x+1 2x+2 1 x x+1 2x 2
2x 0 2x x 1 2x+1 x+1 2 2x+2 x+2
2x+1 0 2x+1 x+2 x+1 2 2x 2x+2 x 1
2x+2 0 2x+2 x+1 2x+1 x 2 x+2 1 2x

См. также[править | править исходный текст]

Примечания[править | править исходный текст]

  1. Лидл Р., Нидеррайтер Г. Конечные поля. — М.: Мир, 1988. — С. 5. — 808 с. — ISBN 5-03-000065-8
  2. Evariste Galois (1830), Sur la théorie des nombres. Bulletin des sciences mathématiques de M. Férussac 13, pp 428—435 (1830)
  3. Israel Kleiner. A History of Abstract Algebra. — Birkhäuser, 2007. — С. 70. — 168 с. — ISBN 978-0-8176-4684-4
  4. G. Frei. The Unpublished Section Eight: On the Way to Function Fields over a Finite Field. — Goldstein Schappacher Schwermer, 2007. — С. 159-198.
  5. Moore E. H. A double–infinite systems of simple groups. — Mathematical Papers Read at the International Mathematical Congress in Chicago, 1893. — С. 208–242.
  6. H. Weber, " Die allgemeinen Grundlagen der Galois’schen Gleichungstheorie ", Mathematische Annalen, vol. 43,‎ 1893, p. 521—549
  7. Ernst Steinitz, " Algebraische Theorie der Körper ", Journal für die reine und angewandte Mathematik, vol. 137,‎ 1910, p. 167—309 (ISSN 0075-4102)
  8. R. Dedekind, Supplément XI des Leçons en théorie des nombres de Dirichlet, 1894
  9. Шеннон, К. Математическая теория связи [Текст] / К. Шеннон // Работы по теории информации и кибернетике. — М. : Издательство иностранной литературы, 1963. — С. 243—332.
  10. Хэмминг, К. Коды с обнаружением и исправлением ошибок [Текст] / К. Хэмминг // Коды с обнаружением и исправлением ошибок. — М. : Издательство иностранной литературы, 1956. — С. 7-23.
  11. Goley M.J.E. Notes on digital coding // Proceedings IRE. 1949. V. 37, P.657.
  12. W. Dime and M.E. Hellman. New directions in cryptography. IEEE Trans. Info. Theory, IT-22(6):644-654, 1976.
  13. M. Rabin, Probabilistic Algorithm for Testing Primality, J. Number Th. 12 (1980), 128—138
  14. C. F. Gauss, Disquisitiones Arithmeticae, 1801
  15. R. C. Bose et D. K. Ray-Chaudhuri, On a class of error-correcting binary group codes, Inform. Control, vol. 3, mars 1960, p. 68-79

Литература[править | править исходный текст]

  • Винберг Э. Б. Курс алгебры. — 3-е изд. — М.: Факториал Пресс, 2002. — 544 с. — 3000 экз. — ISBN 5-88688-060-7
  • Лидл Р. Нидеррайтер Г. Конечные поля. В 2-х тт. — М.: Мир, 1998.