7. МАТЕМАТИКА ПОЛЕЙ ГАЛУА
В теории помехоустойчивого кодирования широко используются конечные поля, называемые полями Галуа в честь французского математика Эвариста Галуа (1811–1832), чьи работы легли в основу теории групп.
Теория полей Галуа подробно освещены во многих работах, как относительно давно написанных трудах Н. Г. Чеботарёва [ 16 , 17 , 18 ], М. М. Постникова [ 14 , 15 ], Р. Лиддла и Г. Нидеррайтера [ 19 ] и других авторов, так и недавно вышедших трудах, таких как монография О. С. Когновицкого [ 4 ].
Поле Галуа, обозначаемое GF(q), представляет собой конечное множество, состоящее из q элементов, обладающих свойствами поля. Число элементов поля q является простым числом или степенью простого числа. Если q — простое число, то элементами поля GF(q) с характеристикой q являются числа 0, 1, 2, . . . , (q 1). При этом в соответствии со свойствами поля сложение и умножение элементов такого поля осуществляется с приведением по модулю q. Такое поле Галуа называется простым.
Если характеристика q является степенью простого числа p, т. е. q = p m , где m — целое, то элементами поля GF(p m ) будут многочлены степени (m 1) вида
a 0 + a 1 x + a 2 x 2 + . + a m 1 x m 1 ;
где все коэффициенты a i пробегают полную систему вычетов по модулю p, т. е. принадлежат простому полю GF(p). В этом случае p называется основанием поля, а m — степенью поля. Само поле Галуа называется расширенным.
В дальнейшем будем рассматривать только поля Галуа по основанию 2 — двоичные поля Галуа GF(2 m ). Соответственно, коэффициенты a i из формулы ( 7.1 ) равны 0 или 1.
7.1.1. Образующий полином поля Галуа
Поле Галуа GF(p m ) строится на основе так называемого образующего (порождающего) многочлена p(x), который является неприводимой примитивной функцией степени m.
Важно: Кроме обозначения p(x) для образующего многочлена поля в некоторых источниках используется обозначение g(x) (также используется для обозначения порождающего многочлена кода). Здесь, чтобы избежать путаницы, мы будем использовать p(x)
для образующего многочлена поля, а g(x) для порождающего многочлена кода.
Как уже было сказано выше, существуют готовые таблицы с образующими полиномами. Их можно как найти в литературе [ 4 ], так и воспользоваться математическими пакетами, например Matlab или Octave. Если же нет
возможности воспользоваться таблицами, то можно проверить, является ли многочлен неприводимым и примитивным путем построения поля, которое в ином случае построено быть не может. Также возможность построения поля можно оценить, попытавшись определить значение полинома x p m 1 mod p(x). Так как поле Галуа является циклическим, то, в случае, если поле может быть построено, остаток от деления x p m 1 на p(x) должен быть равен единице.
В табл. 7.1 приведены примеры образующих полиномов p(x) для некоторых степеней поля GF(2 m ).
ГАЛУА ПОЛЕ
Число элементов любого Г. п. есть степень 
нек-рого натурального простого числа 
, являющегося характеристикой этого поля. Для любого натурального простого р и любого натурального псуществует (и единственно, с точностью до изоморфизма) поле из 
элементов. Оно обозначается 
или 
. Поле 
содержит в качестве подполя поле 
в том и только в том случае, когда тделится на п. В частности, в любом поле 
содержится поле 
, наз. простым полем характеристики р. Поле 
изоморфно полю 
классов вычетов кольца целых чисел по простому модулю р. В любом фиксированном алгебраическом замыкании 
поля 
существует точно одно подполе 
для каждого п. Соответствие 
является изоморфизмом между решеткой натуральных чисел относительно делимости и решеткой конечных алгебраич. расширений поля 
, лежащих в 
, относительно включения. Такова же решетка множества конечных алгебраич. расширений любого Г. п., лежащих в его фиксированном алгебраич. замыкании.
Алгебраич. расширение 
является простым, т. е. существует примитивный элемент 
такой, что 
Таким 
будет любой корень каждого неприводимого многочлена степени пиз кольца 
. Число примитивных элементов расширения 
равно
где 
— Мёбиуса функция. Аддитивная группа поля 
естественным образом наделяется структурой n-мерного векторного пространства над 
. В качестве базиса можно взять 
. Ненулевые элементы поля 
образуют мультипликативную группу 
порядка 
, т. е. каждый элемент из 
является корнем многочлена 
Группа 
циклическая, ее образующие — первообразные корни из единицы степени 
число К-рых равно 
где 
— Эйлера функция. Каждый первообразный корень из единицы степени 
является примитивным элементом расширения 
но не наоборот. Точнее, среди
неприводимых унитарных многочленов степени пнад 
имеется 
таких, корни к-рых будут образующими для 
.
Множество элементов поля 
в точности совпадает с множеством корней многочлена 
в 
, т. е. 
характеризуется как подполе элементов из 
, инвариантных относительно автоморфизма 
, наз. автоморфизмом Фробениуса. Если 
то расширение 
нормально (см. Расширение поля), его Галуа группа 
циклическая порядка ml п. В качестве образующей группы 
может быть взят автоморфизм т.
Лит.:[1] Галуа Э., Сочинения, пер. с франц., М.-Л., 1936: [2] Ван дер Варден Б. Л., Алгебра, пер. с нем., М., 1976, с. 158-62; [3] Чеботарев Н. Г., основы теории Галуа, М.-Л., 1934, ч. 1, с. 154-62; [4] Бурбаки Н., Алгебра. Многочлены и поля. Упорядоченные группы, пер. с франц., М., 1965, с. 185-203. А. И. Скопин
Математическая энциклопедия. — М.: Советская энциклопедия . И. М. Виноградов . 1977—1985 .
Конечное поле
Конечное поле или поле Галуа (названо в честь Эвариста Галуа ) — поле, состоящее из конечного числа элементов. Простейшим примером конечного поля является поле вычетов по простому модулю.
Содержание
Свойства конечных полей
- простым числом
Коне́чное по́ле, или по́ле Галуа́ в общей алгебре — поле, состоящее из конечного числа элементов; это число называется поря́дком поля.
Конечное поле обычно обозначается [math]\displaystyle< \mathbb
_q >[/math] или [math]\displaystyle< \mathrm (q) >[/math] (сокращение от англ. Galois field ) и называется полем Галуа порядка [math]\displaystyle< q >[/math] , где [math]\displaystyle< q >[/math] — число элементов поля [1] . С точностью до изоморфизма конечное поле полностью определяется его порядком, который всегда является степенью какого-нибудь простого числа, то есть [math]\displaystyle< q=p^n >[/math] , где [math]\displaystyle< p >[/math] — простое число, а [math]\displaystyle< n >[/math] — любое натуральное число. При этом [math]\displaystyle< p >[/math] будет являться характеристикой этого поля [2] . Содержание
Определение и свойства
Конечным полем называется конечное множество, на котором определены произвольные операции, называемые сложением, умножением, вычитанием и делением (кроме деления на 0) в соответствии с аксиомами поля [5] .
Мультипликативная группа конечного поля циклична. То есть все ненулевые элементы поля [math]\displaystyle< \mathbb F_q >[/math] образуют группу относительно операции умножения (эта группа называется мультипликативной группой поля и обозначается [math]\displaystyle< \mathbb F_q^* >[/math] ). Эта группа является циклической, то есть в ней есть порождающий элемент, а все остальные элементы получаются возведением в степень порождающего [5] . То есть, существует [math]\displaystyle< g >[/math] — порождающий элемент, такой что для любого [math]\displaystyle< a \in \mathbb F_q^* >[/math] , можно записать:
Порождающий элемент [math]\displaystyle< \mathbb F_q^* >[/math] называется также примитивным элементом поля [math]\displaystyle< \mathbb F_q. >[/math] Поле [math]\displaystyle< \mathbb F_q >[/math] содержит [math]\displaystyle< \varphi(q-1) >[/math] примитивных элементов, где [math]\displaystyle< \varphi >[/math] — функция Эйлера. [6]
Также поле обладает рядом других свойств:
- Согласно малой теореме Ферма, каждый элемент поля [math]\displaystyle< \mathbb
_ >[/math] удовлетворяет равенству [math]\displaystyle< a^q = a >[/math] [2] .
- Поле [math]\displaystyle< \mathbb
_ _ - Если [math]\displaystyle< f\in \mathbb F_q[x] >[/math] — неприводимый многочлен степени [math]\displaystyle< m >[/math] , то поле [math]\displaystyle < \mathbb F_
- Для каждого конечного поля [math]\displaystyle< \mathbb F_q >[/math] и натурального числа [math]\displaystyle< n >[/math] произведение всех нормированных неприводимых над [math]\displaystyle< \mathbb F_q >[/math] многочленов, степень которых делит [math]\displaystyle< n >[/math] , равно [math]\displaystyle< x^
- Число [math]\displaystyle< N(q, n) >[/math] нормированных многочленов степени n, неприводимых над полем [math]\displaystyle< \mathbb
_q, >[/math] определяется по формуле [math]\displaystyle< N(q,n)=\frac<1> \sum_ > >[/math] , где [math]\displaystyle< \mu >[/math] — функция Мёбиуса. Это утверждение следует из формулы [math]\displaystyle < q^n=\sum_
Поле с простым числом элементов
Любое поле простого порядка может быть представлено кольцом вычетов (т.е. любое поле из [math]\displaystyle< \mathbb
_ >[/math] элементов изоморфно кольцу вычетов [math]\displaystyle< \mathbb
/(p) >[/math] ). Наиболее известный пример конечного поля — поле классов вычетов по модулю простого числа [math]\displaystyle< p >[/math] , обозначаемое [math]\displaystyle< \mathbb /(p) >[/math] [10] . Это поле можно представить следующим образом. Для простого числа [math]\displaystyle< p >[/math] элементами поля будут числа [math]\displaystyle < \<0, 1, . p - 1\>>[/math] . Сложение и умножение определены как сложение и умножение чисел с приведением результата по модулю [math]\displaystyle< p >[/math] [11] . Ниже приведены примеры таких полей с двумя элементами и тремя элементами. Связь с кольцами вычетов
Не следует путать конечные поля [math]\displaystyle< \mathbb
_ /(p^n) >[/math] . Только когда порядок простое число, кольцо вычетов является полем. [12] При n > 1 кольцо вычетов [math]\displaystyle< \mathbb
/(p^n) >[/math] полем не является. Пример. В поле [math]\displaystyle< \mathbb
_8 >[/math] для любого элемента верно [math]\displaystyle< x + x = 0 >[/math] . В кольце [math]\displaystyle< \mathbb _8 >[/math] , вычисляя [math]\displaystyle< x + x >[/math] , мы получим 0 только в двух случаях, когда [math]\displaystyle< x = 4, x = 0 >[/math] . Это кольцо имеет делители нуля: [math]\displaystyle< 2 \cdot 4 = 0 \pmod 8 >[/math] . Характеризация конечных полей
Характеристика каждого конечного поля является простым числом. Пусть [math]\displaystyle< F >[/math] — конечное поле. Тогда оно состоит из [math]\displaystyle< p^n >[/math] элементов, где [math]\displaystyle< p >[/math] — характеристика поля [math]\displaystyle< F >[/math] , а натуральное число [math]\displaystyle< n >[/math] — степень поля [math]\displaystyle< F >[/math] над его простым подполем [2] .
Согласно теореме о существовании и единственности конечных полей, для каждого простого числа [math]\displaystyle< p >[/math] и натурального числа [math]\displaystyle< n >[/math] существует конечное поле из [math]\displaystyle< p^n >[/math] элементов и любое конечное поле из [math]\displaystyle< q=p^n >[/math] элементов изоморфно полю разложения многочлена [math]\displaystyle< x^q - x >[/math] над полем [math]\displaystyle< \mathbb
_p >[/math] . Данная теорема позволяет говорить о вполне определённом поле данного порядка [math]\displaystyle< q >[/math] (то есть о поле Галуа из [math]\displaystyle< q >[/math] элементов) [13] . Построение
Поле [math]\displaystyle < \mathbb F_
=\mathbb F_p[x]/(f(x)) >[/math] , где [math]\displaystyle< f(x) >[/math] — неприводимый многочлен степени n над полем [math]\displaystyle< \mathbb F_p >[/math] . Таким образом, для построения поля из [math]\displaystyle< p^n >[/math] элементов достаточно отыскать многочлен степени [math]\displaystyle< n >[/math] , неприводимый над полем [math]\displaystyle< \mathbb F_p >[/math] (такой многочлен всегда существует). Элементами поля [math]\displaystyle < \mathbb >[/math] являются классы вычетов многочленов степени меньшей [math]\displaystyle< n >[/math] с коэффициентами из [math]\displaystyle< \mathbb F_p >[/math] по модулю главного идеала, порождённого многочленом [math]\displaystyle< f(x) >[/math] . Элемент [math]\displaystyle< \alpha=x+(f(x))\in \mathbb
_p[x]/(f(x)) >[/math] является корнем многочлена [math]\displaystyle< f(x) >[/math] , и поле [math]\displaystyle< \mathbb _p[x]/(f(x)) >[/math] порождается этим элементом над полем [math]\displaystyle< \mathbb _p >[/math] , поэтому переход от поля [math]\displaystyle< \mathbb _p >[/math] к полю [math]\displaystyle< \mathbb _p[x]/(f(x)) >[/math] называется присоединением к полю [math]\displaystyle< \mathbb _p >[/math] корня неприводимого многочлена [math]\displaystyle< f(x) >[/math] . [14] [15] Примеры
Поле из двух элементов
Поле [math]\displaystyle< \mathbb
_2 >[/math] состоит из двух элементов, но оно может быть задано разными способами в зависимости от выбора элементов и определения операций сложения и умножения на них: [16] - Как множество из двух чисел «0» и «1», на котором операции сложения и умножения определены как сложение и умножение чисел с приведением результата по модулю 2 ( [math]\displaystyle< \mathbb
_<2>=\ <0,1\>>[/math] ):
- Как множество из двух логических объектов «ЛОЖЬ» (F) и «ИСТИНА» (T), на котором операции сложения и умножения определены как булевые операции «исключающее или» и «и» соответственно:
Данные поля являются изоморфными друг другу, т. е. это фактически два разных способа задания одного и того же поля.
Поле из трёх элементов
Поле [math]\displaystyle< \mathbb
_3 = \ <0, 1, 2\>>[/math] . Сложения и умножения определены как сложение и умножение чисел по модулю 3. Таблицы операций [math]\displaystyle< \mathbb _3 >[/math] имеют вид: Остатки от деления на 3 образуют [math]\displaystyle< \mathbb
_3 >[/math] из трёх элементов (где [math]\displaystyle< \frac<1><2>=2, >[/math] поскольку [math]\displaystyle< 2\cdot 2=1 >[/math] для остатков от деления на 3). Остатки же от деления на 4 поля не образуют, ибо элемент 2 не имеет обратного.
Поле из четырёх элементов
Поле [math]\displaystyle< \mathbb
_4 >[/math] можно представить как множество [math]\displaystyle < \<0, 1, \alpha, \alpha+1\>>[/math] (где [math]\displaystyle< \alpha >[/math] — корень многочлена [math]\displaystyle< f(x)=x^2+x+1 >[/math] над полем [math]\displaystyle< \mathbb _2 >[/math] , то есть [math]\displaystyle< \alpha^2=-\alpha-1=\alpha+1 >[/math] ). Таблицы операций [math]\displaystyle< \mathbb _4 >[/math] имеют вид: [17] Поле из девяти элементов
Для построения поля [math]\displaystyle< \mathbb F_9 = \mathrm
(3^2) >[/math] достаточно найти нормированный многочлен степени 2, неприводимый над [math]\displaystyle< \mathbb _3 >[/math] . Такими многочленами являются: [math]\displaystyle< x^2+1 >[/math] [math]\displaystyle< x^2+x+2 >[/math] [math]\displaystyle< x^2+2x+2 >[/math] Для [math]\displaystyle< x^2+1 >[/math] искомое поле есть [math]\displaystyle< \mathbb F_9=\mathbb
_3[x]/(x^2+1) >[/math] (если вместо [math]\displaystyle< x^2+1 >[/math] взять другой многочлен, то получится новое поле, изоморфное старому). В приведённых ниже таблицах символ [math]\displaystyle< i >[/math] обозначает класс эквивалентности многочлена [math]\displaystyle< x >[/math] в факторкольце [math]\displaystyle< \mathbb _3[x]/(x^2+1) >[/math] , удовлетворяющий уравнению [math]\displaystyle< i^2+1=0 >[/math] . Таблица сложения в [math]\displaystyle< \mathbb F_9 >[/math] определяется, исходя из соотношения [math]\displaystyle< 1+1+1=0 >[/math] :
+ 0 1 2 [math]\displaystyle< i >[/math] [math]\displaystyle< i+1 >[/math] [math]\displaystyle< i+2 >[/math] [math]\displaystyle< 2i >[/math] [math]\displaystyle< 2i+1 >[/math] [math]\displaystyle< 2i+2 >[/math] 0 0 1 2 [math]\displaystyle< i >[/math] [math]\displaystyle< i+1 >[/math] [math]\displaystyle< i+2 >[/math] [math]\displaystyle< 2i >[/math] [math]\displaystyle< 2i+1 >[/math] [math]\displaystyle< 2i+2 >[/math] 1 1 2 0 [math]\displaystyle< i+1 >[/math] [math]\displaystyle< i+2 >[/math] [math]\displaystyle< i >[/math] [math]\displaystyle< 2i+1 >[/math] [math]\displaystyle< 2i+2 >[/math] [math]\displaystyle< 2i >[/math] 2 2 0 1 [math]\displaystyle< i+2 >[/math] [math]\displaystyle< i >[/math] [math]\displaystyle< i+1 >[/math] [math]\displaystyle< 2i+2 >[/math] [math]\displaystyle< 2i >[/math] [math]\displaystyle< 2i+1 >[/math] [math]\displaystyle< i >[/math] [math]\displaystyle< i >[/math] [math]\displaystyle< i+1 >[/math] [math]\displaystyle< i+2 >[/math] [math]\displaystyle< 2i >[/math] [math]\displaystyle< 2i+1 >[/math] [math]\displaystyle< 2i+2 >[/math] 0 1 2 [math]\displaystyle< i+1 >[/math] [math]\displaystyle< i+1 >[/math] [math]\displaystyle< i+2 >[/math] [math]\displaystyle< i >[/math] [math]\displaystyle< 2i+1 >[/math] [math]\displaystyle< 2i+2 >[/math] [math]\displaystyle< 2i >[/math] 1 2 0 [math]\displaystyle< i+2 >[/math] [math]\displaystyle< i+2 >[/math] [math]\displaystyle< i >[/math] [math]\displaystyle< i+1 >[/math] [math]\displaystyle< 2i+2 >[/math] [math]\displaystyle< 2i >[/math] [math]\displaystyle< 2i+1 >[/math] 2 0 1 [math]\displaystyle< 2i >[/math] [math]\displaystyle< 2i >[/math] [math]\displaystyle< 2i+1 >[/math] [math]\displaystyle< 2i+2 >[/math] 0 1 2 [math]\displaystyle< i >[/math] [math]\displaystyle< i+1 >[/math] [math]\displaystyle< i+2 >[/math] [math]\displaystyle< 2i+1 >[/math] [math]\displaystyle< 2i+1 >[/math] [math]\displaystyle< 2i+2 >[/math] [math]\displaystyle< 2i >[/math] 1 2 0 [math]\displaystyle< i+1 >[/math] [math]\displaystyle< i+2 >[/math] [math]\displaystyle< i >[/math] [math]\displaystyle< 2i+2 >[/math] [math]\displaystyle< 2i+2 >[/math] [math]\displaystyle< 2i >[/math] [math]\displaystyle< 2i+1 >[/math] 2 0 1 [math]\displaystyle< i+2 >[/math] [math]\displaystyle< i >[/math] [math]\displaystyle< i+1 >[/math] Таблица умножения в [math]\displaystyle< \mathbb F_9 >[/math] определяется из соотношения [math]\displaystyle< i^2=-1 >[/math] :
× 0 1 2 [math]\displaystyle< i >[/math] [math]\displaystyle< i+1 >[/math] [math]\displaystyle< i+2 >[/math] [math]\displaystyle< 2i >[/math] [math]\displaystyle< 2i+1 >[/math] [math]\displaystyle< 2i+2 >[/math] 0 0 0 0 0 0 0 0 0 0 1 0 1 2 [math]\displaystyle< i >[/math] [math]\displaystyle< i+1 >[/math] [math]\displaystyle< i+2 >[/math] [math]\displaystyle< 2i >[/math] [math]\displaystyle< 2i+1 >[/math] [math]\displaystyle< 2i+2 >[/math] 2 0 2 1 [math]\displaystyle< 2i >[/math] [math]\displaystyle< 2i+2 >[/math] [math]\displaystyle< 2i+1 >[/math] [math]\displaystyle< i >[/math] [math]\displaystyle< i+2 >[/math] [math]\displaystyle< i+1 >[/math] [math]\displaystyle< i >[/math] 0 [math]\displaystyle< i >[/math] [math]\displaystyle< 2i >[/math] 2 [math]\displaystyle< i+2 >[/math] [math]\displaystyle< 2i+2 >[/math] 1 [math]\displaystyle< i+1 >[/math] [math]\displaystyle< 2i+1 >[/math] [math]\displaystyle< i+1 >[/math] 0 [math]\displaystyle< i+1 >[/math] [math]\displaystyle< 2i+2 >[/math] [math]\displaystyle< i+2 >[/math] [math]\displaystyle< 2i >[/math] 1 [math]\displaystyle< 2i+1 >[/math] 2 [math]\displaystyle< i >[/math] [math]\displaystyle< i+2 >[/math] 0 [math]\displaystyle< i+2 >[/math] [math]\displaystyle< 2i+1 >[/math] [math]\displaystyle< 2i+2 >[/math] 1 [math]\displaystyle< i >[/math] [math]\displaystyle< i+1 >[/math] [math]\displaystyle< 2i >[/math] 2 [math]\displaystyle< 2i >[/math] 0 [math]\displaystyle< 2i >[/math] [math]\displaystyle< i >[/math] 1 [math]\displaystyle< 2i+1 >[/math] [math]\displaystyle< i+1 >[/math] 2 [math]\displaystyle< 2i+2 >[/math] [math]\displaystyle< i+2 >[/math] [math]\displaystyle< 2i+1 >[/math] 0 [math]\displaystyle< 2i+1 >[/math] [math]\displaystyle< i+2 >[/math] [math]\displaystyle< i+1 >[/math] 2 [math]\displaystyle< 2i >[/math] [math]\displaystyle< 2i+2 >[/math] [math]\displaystyle< i >[/math] 1 [math]\displaystyle< 2i+2 >[/math] 0 [math]\displaystyle< 2i+2 >[/math] [math]\displaystyle< i+1 >[/math] [math]\displaystyle< 2i+1 >[/math] [math]\displaystyle< i >[/math] 2 [math]\displaystyle< i+2 >[/math] 1 [math]\displaystyle< 2i >[/math] Элемент [math]\displaystyle< i+1 >[/math] имеет порядок 8 и является примитивным. Элемент [math]\displaystyle< i >[/math] не является примитивным, так как [math]\displaystyle< i^4=1 >[/math] (другими словами, многочлен [math]\displaystyle< x^2+1\in\mathbb F_3[x] >[/math] не является примитивным) [17] .
Мультипликативная группа поля из 16 элементов
Когда поле [math]\displaystyle < \mathbb F_<16>= \mathrm
(2^4) >[/math] строится с помощью неприводимого многочлена [math]\displaystyle< x^4 + x + 1 >[/math] , элементы расширения задаются наборами коэффициентов многочлена, который получается в остатке при делении на [math]\displaystyle< x^4 + x + 1 >[/math] , записанными в порядке возрастания степеней. Мультипликативная группа порождается элементом [math]\displaystyle< \alpha = x >[/math] , который записывается как (0, 1, 0, 0) [18] . Многочлен Степень [math]\displaystyle< \alpha >[/math] [math]\displaystyle< 1, x, x^2, x^3 >[/math] 1 [math]\displaystyle< \alpha^0 >[/math] (1, 0, 0, 0) [math]\displaystyle< \alpha >[/math] [math]\displaystyle< \alpha >[/math] (0, 1, 0, 0) [math]\displaystyle< \alpha^2 >[/math] [math]\displaystyle< \alpha^2 >[/math] (0, 0, 1, 0) [math]\displaystyle< \alpha^3 >[/math] [math]\displaystyle< \alpha^3 >[/math] (0, 0, 0, 1) [math]\displaystyle< 1 + \alpha >[/math] [math]\displaystyle< \alpha^4 >[/math] (1, 1, 0, 0) [math]\displaystyle< \alpha + \alpha^2 >[/math] [math]\displaystyle< \alpha^5 >[/math] (0, 1, 1, 0) [math]\displaystyle< \alpha^2 + \alpha^3 >[/math] [math]\displaystyle< \alpha^6 >[/math] (0, 0, 1, 1) [math]\displaystyle< \alpha^3 + \alpha + 1 = \alpha^3 + \alpha^4 >[/math] [math]\displaystyle< \alpha^7 >[/math] (1, 1, 0, 1) [math]\displaystyle< 1 + \alpha^2 =\alpha + 1 + \alpha^2 + \alpha >[/math] [math]\displaystyle< \alpha^8 >[/math] (1, 0, 1, 0) [math]\displaystyle< \alpha + \alpha^3 >[/math] [math]\displaystyle< \alpha^9 >[/math] (0, 1, 0, 1) [math]\displaystyle< \alpha^2 + 1 + \alpha = \alpha^2 + \alpha^4 >[/math] [math]\displaystyle < \alpha^<10>>[/math] (1, 1, 1, 0) [math]\displaystyle< \alpha + \alpha^2 + \alpha^3 >[/math] [math]\displaystyle < \alpha^<11>>[/math] (0, 1, 1, 1) [math]\displaystyle< 1 + \alpha + \alpha^2 + \alpha^3 = \alpha^2 + \alpha^3 + \alpha^4 >[/math] [math]\displaystyle < \alpha^<12>>[/math] (1, 1, 1, 1) [math]\displaystyle< 1 +\alpha^2 + \alpha^3 = \alpha + \alpha^2 + \alpha^3 + \alpha^4 >[/math] [math]\displaystyle < \alpha^<13>>[/math] (1, 0, 1, 1) [math]\displaystyle< 1 + \alpha^3 = \alpha + \alpha^3 + \alpha^4 >[/math] [math]\displaystyle < \alpha^<14>>[/math] (1, 0, 0, 1) [math]\displaystyle< 1 = \alpha + \alpha^4 >[/math] [math]\displaystyle < \alpha^<15>>[/math] (1, 0, 0, 0) История изучения
Начала теории конечных полей восходят к XVII и XVIII веку. Над этой темой работали такие учёные, как Пьер Ферма, Леонард Эйлер, Жозеф Луи Лагранж и Адриен Мари Лежандр, которых можно считать основателями теории конечных полей простого порядка. Однако больший интерес представляет общая теория конечных полей, берущая своё начало с работ Гаусса и Галуа [19] . До некоторого времени эта теория находила применение только в алгебре и теории чисел, однако впоследствии были найдены новые точки соприкосновения с алгебраической геометрией, комбинаторикой и теорией кодирования [3] .
Вклад Галуа
В 1830 году восемнадцатилетний Эварист Галуа опубликовал работу [20] , которая положила основу общей теории конечных полей. В этой работе Галуа (в связи с исследованиями по теории групп перестановок и алгебраических уравнений [21] ) вводит воображаемый корень сравнения [math]\displaystyle< F(x)\equiv 0\pmod p >[/math] , где [math]\displaystyle< F(x) >[/math] — произвольный многочлен степени [math]\displaystyle< \nu >[/math] , неприводимый по модулю p. После этого рассматривается общее выражение [math]\displaystyle< A = a_0 +
i + i^2 + \ldots + a_<\nu-1>i^ <\nu-1>>[/math] , где [math]\displaystyle < a_0, a_1, . a_<\nu-1>>[/math] — некие целые числа по модулю p. Если присваивать этим числам всевозможные значения, выражение [math]\displaystyle< A >[/math] будет принимать [math]\displaystyle < p^<\nu>>[/math] значений. Далее Галуа показывает, что эти значения образуют поле и мультипликативная группа этого поля является циклической. Таким образом, эта работа является первым камнем в фундаменте общей теории конечных полей. В отличие от его предшественников, рассматривающих только поля [math]\displaystyle< \mathbb F_p >[/math] , Галуа рассматривает уже поля [math]\displaystyle < \mathbb F_ Первая работа в этом направлении была написана Гауссом примерно в 1797 году, однако при его жизни это исследование так и не было издано. Вероятно, данное исследование было проигнорировано редактором его сочинений, поэтому на свет эта работа появилась только в посмертном издании в 1863 году [23] .
Дальнейшее развитие
В 1893 году математик Элиаким Мур доказал теорему о классификации конечных полей, утверждающую, что любое конечное поле является полем Галуа, то есть любое поле из [math]\displaystyle< p^n >[/math] элементов изоморфно полю классов вычетов многочленов с коэффициентами из [math]\displaystyle< \mathbb F_p >[/math] по модулю неприводимого многочлена степени [math]\displaystyle< n >[/math] [24] . К этому же году относится первая попытка дать аксиоматический подход к теории конечных полей, осуществленная Генрихом Вебером, который пытался объединить в своей работе понятия, возникшие в различных разделах математики, в том числе и понятие конечного поля [25] . Далее в 1905 году Джозеф Веддербёрн доказывает малую теорему Веддербёрна о том, что любое конечное тело коммутативно, то есть является полем. Современное аксиоматическое определение поля (с конечными полями в качестве частного случая) принадлежит Эрнсту Штайницу и изложено в его работе 1910 года [26] .
Приложения
Диофантовы уравнения
Диофантово уравнение является уравнением с целыми коэффициентами, в котором переменные также принимают целочисленные значения. Большую волну обсуждения таких уравнений вызвал Ферма, сформулировав свои теоремы. Малая теорема Ферма утверждает, что если [math]\displaystyle< p >[/math] — простое число, не являющееся делителем другого числа [math]\displaystyle< a >[/math] , то [math]\displaystyle< a^
\equiv 1\pmod p >[/math] . В теории конечных полей эта теорема является следствием теоремы Лагранжа, применённой к мультипликативной подгруппе, порождённой элементом [math]\displaystyle< a >[/math] , так как вся мультипликативная группа поля [math]\displaystyle< \mathbb F_p >[/math] состоит из [math]\displaystyle< p-1 >[/math] элементов [5] . Ферма замечает, что единственные простые числа, которые можно разложить в сумму двух квадратов — это те простые числа, которые дают остаток 1 при делении на 4. В частности, он отмечает, что
В своём письме к Марену Мерсенну, датированном 25 декабря 1640 года, Ферма предлагает решить уравнение [math]\displaystyle< a^2+b^2=p >[/math] [27] .
Юлиус Дедекинд исследовал это уравнение в конечном поле [math]\displaystyle< \mathbb
_p >[/math] , где оно принимает вид [math]\displaystyle< a^2+b^2=0 >[/math] . Если [math]\displaystyle< b=0 >[/math] , то решение тривиально. В противном случае можно разделить обе части на [math]\displaystyle< b^2 >[/math] и, введя замену, получить уравнение вида [math]\displaystyle< x^2+1=0 >[/math] . Домножением на [math]\displaystyle< x^2-1=0 >[/math] получается уравнение [math]\displaystyle< x^4-1=0 >[/math] . Считая [math]\displaystyle< x >[/math] генератором мультипликативной подгруппы порядка 4, можно получить необходимые и достаточные условия на p, при которых уравнение имеет решение. Дальнейшее доказательство теоремы Ферма — Эйлера, проведённое Дедекиндом, не использует понятия конечных полей и его можно найти в соответствующей статье [28] . Теория корректирующих кодов
Годом создания теории корректирующих кодов считается 1948 год, в котором была опубликована статья Клода Шеннона, в которой он показывает, что наличие ошибок при передаче информации по какому-либо каналу зависит в том числе от соотношения скорости передачи и пропускной способности канала. Скорость передачи должна быть выше пропускной способности. Шеннон привел доказательства, но они были признаны несостоятельными [29] .
Конструктивный подход предложил Ричард Хэмминг, задав тем самым вектор развития многих более поздних статей данной тематики. В своей работе Хэмминг построил простой код, исправляющий ошибки определенным образом. Хэмминг рассматривал корректирующие коды только над полем [math]\displaystyle< \mathbb F_2 >[/math] [30] . Вскоре подобные коды были построены над произвольными конечными полями Голеем в 1949 году [31] . Однако наибольший вклад в эту теорию принадлежит Хэммингу [30] .
Криптография
Конечные поля получили широчайшее применение в криптографии. Основополагающей работой считается статья Диффи и Хелмана по криптографии с открытым ключом, в которой был предложен протокол обмена ключами [4] . В этой работе использовались конечные поля определенного вида. Позже появилось великое множество криптографических протоколов и криптосистем, основанных на применении конечных полей. В их число входят схема Эль-Гамаля, Advanced Encryption Standard [32] , схема Шнорра, алгоритм Чаума (слепая подпись), криптосистема XTR (англ.) ( рус. и многие другие. Алгоритмы на основе эллиптических кривых, являющиеся одним из ключевых объектов изучения в современной криптографии, также используют конечные поля [33] .
Также зачастую качество шифрования зависит от способности быстро генерировать большие простые числа. Соответственно, встает задача построения алгоритма разложения числа на простые множители (определение простоты того или иного числа). Михаэль Рабин опубликовал исследование, в котором он предлагает тест простоты на основе свойств мультипликативной группы поля [34] .
Прочее
В 1960 году Р. К. Боуз [en] и Д. К. Рой-Чоудхури [en] опубликовали работу, в которой исследовали семейства многочленов над конечными полями. А. Хоквингем [en] обобщил их теорию, что привело к созданию кода БЧХ, частным случаем которого является широко известный код Рида — Соломона, имеющий очень обширное применение. Он используется при записи и чтении в контроллерах оперативной памяти, при архивировании данных, записи информации на жесткие диски (ECC), записи на CD/DVD диски. Примечательно то, что при повреждении значительного объёма информации, или если испорчено несколько секторов дискового носителя, код Рида — Соломона позволяет восстановить большую часть потерянной информации. Код БЧХ используется также в системе связи некоторых зондов NASA (таких как Voyager) [35] .
- Согласно малой теореме Ферма, каждый элемент поля [math]\displaystyle< \mathbb
