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




Коне́чное по́ле, или по́ле Галуа́ в общей алгебре — поле, состоящее из конечного числа элементов. Число элементов в поле называется его поря́дком.


Конечное поле обычно обозначается Fq{displaystyle mathbb {F} _{q}}mathbb {F} _{q} или GF(q){displaystyle mathrm {GF} (q)}mathrm {GF} (q) (сокращение от Galois field) и называется полем Галуа порядка q{displaystyle q}q[1], где q{displaystyle q}q — число элементов поля.
С точностью до изоморфизма конечное поле полностью определяется его порядком, который всегда является степенью какого-нибудь простого числа, то есть q=pn{displaystyle q=p^{n}}q=p^{n}, где p{displaystyle p}p — простое число, а n{displaystyle n}n — любое натуральное число. При этом p{displaystyle p}p  будет являться характеристикой этого поля[2].


Понятие конечного поля используется в теории чисел[3], теории групп[3], алгебраической геометрии[3], криптографии[4].




Содержание






  • 1 Определение и свойства


  • 2 Поле с простым числом элементов


  • 3 Cвязь с кольцами вычетов


  • 4 Характеризация конечных полей


  • 5 Построение


  • 6 Примеры


    • 6.1 Поле из двух элементов


    • 6.2 Поле из трёх элементов


    • 6.3 Поле из четырёх элементов


    • 6.4 Поле из девяти элементов


    • 6.5 Мультипликативная группа поля из 16 элементов




  • 7 История изучения


    • 7.1 Вклад Галуа


    • 7.2 Дальнейшее развитие




  • 8 Приложения


    • 8.1 Диофантовы уравнения


    • 8.2 Теория корректирующих кодов


    • 8.3 Криптография


    • 8.4 Прочее




  • 9 См. также


  • 10 Примечания


  • 11 Литература





Определение и свойства |


Конечным полем называется конечное множество, на котором определены произвольные операции, называемые сложением, умножением, вычитанием и делением, (кроме деления на 0) в соответствии с аксиомами поля[5].


Мультипликативная группа конечного поля циклична. То есть все ненулевые элементы поля Fq{displaystyle mathbb {F} _{q}}mathbb {F} _{q} образуют группу относительно операции умножения (эта группа называется мультипликативной группой поля и обозначается Fq∗{displaystyle mathbb {F} _{q}^{*}}mathbb {F} _{q}^{*}). Эта группа является циклической, то есть в ней есть порождающий элемент, а все остальные элементы получаются возведением в степень порождающего[5]. То есть, существует g{displaystyle g}g — порождающий элемент, такой что для любого a∈Fq∗{displaystyle ain mathbb {F} _{q}^{*}}{displaystyle ain mathbb {F} _{q}^{*}}, можно записать:


∃n:gn=amodq{displaystyle exists n:g^{n}=amod q}{displaystyle exists n:g^{n}=amod q}.


Порождающий элемент Fq∗{displaystyle mathbb {F} _{q}^{*}}mathbb {F} _{q}^{*} называется также примитивным элементом поля Fq.{displaystyle mathbb {F} _{q}.}mathbb {F} _{q}. Поле Fq{displaystyle mathbb {F} _{q}}mathbb {F} _{q} содержит φ(q−1){displaystyle varphi (q-1)}varphi (q-1) примитивных элементов, где φ{displaystyle varphi }varphi  — функция Эйлера.[6]


Также поле обладает рядом других свойств:



  • Согласно малой теореме Ферма, каждый элемент поля Fq{displaystyle mathbb {F} _{q}}mathbb {F} _{q} удовлетворяет равенству aq=a{displaystyle a^{q}=a}a^{q}=a[2].

  • Поле Fpn{displaystyle mathbb {F} _{p^{n}}}mathbb {F} _{p^{n}} содержит в себе в качестве подполя Fpk{displaystyle mathbb {F} _{p^{k}}}mathbb {F} _{p^{k}} тогда и только тогда, когда k{displaystyle k}k является делителем n{displaystyle n}n[1].

  • Если f∈Fq[x]{displaystyle fin mathbb {F} _{q}[x]}fin mathbb {F} _{q}[x] — неприводимый многочлен степени m{displaystyle m}m, то поле Fqm{displaystyle mathbb {F} _{q^{m}}}mathbb {F} _{q^{m}} содержит любой его корень α{displaystyle alpha }alpha , причём множество всех его корней имеет вид {α,αq,…,αqm−1}{displaystyle {alpha ,alpha ^{q},ldots ,alpha ^{q^{m-1}}}}{alpha ,alpha ^{q},ldots ,alpha ^{q^{m-1}}}. Таким образом, Fqm{displaystyle mathbb {F} _{q^{m}}}mathbb {F} _{q^{m}} является полем разложения многочлена f{displaystyle f}f над полем Fq{displaystyle mathbb {F} _{q}}mathbb {F} _{q}[7].

  • Для каждого конечного поля Fq{displaystyle mathbb {F} _{q}}mathbb {F} _{q} и натурального числа n{displaystyle n}n произведение всех нормированных неприводимых над Fq{displaystyle mathbb {F} _{q}}mathbb {F} _{q} многочленов, степень которых делит n{displaystyle n}n, равно xqn−x.{displaystyle x^{q^{n}}-x.}x^{q^{n}}-x. В частности, сумма степеней таких многочленов равна qn{displaystyle q^{n}}q^{n}[8].

  • Число N(q,n){displaystyle N(q,n)}N(q,n) нормированных многочленов степени n, неприводимых над полем Fq,{displaystyle mathbb {F} _{q},}mathbb {F} _{q}, определяется по формуле N(q,n)=1n∑d|nμ(d)qnd{displaystyle N(q,n)={frac {1}{n}}sum _{d|n}mu (d)q^{frac {n}{d}}}N(q,n)={frac {1}{n}}sum _{d|n}mu (d)q^{frac {n}{d}}, где μ{displaystyle mu }mu  — функция Мёбиуса. Это утверждение следует из формулы qn=∑d|ndN(q,d){displaystyle q^{n}=sum _{d|n}dN(q,d)}q^{n}=sum _{d|n}dN(q,d) после применения формулы обращения Мёбиуса[9].



Поле с простым числом элементов |


Любое поле простого порядка может быть представлено кольцом вычетов (т.е. любое поле из GFp{displaystyle mathbb {GF} _{p}}{displaystyle mathbb {GF} _{p}} элементов изоморфно кольцу вычетов Z/(p){displaystyle mathbb {Z} /(p)}mathbb {Z} /(p)).
Наиболее известный пример конечного поля — поле классов вычетов по модулю простого числа p{displaystyle p}p, обозначаемое Z/(p){displaystyle mathbb {Z} /(p)}mathbb {Z} /(p)[10]. Это поле можно представить следующим образом.
Для простого числа p{displaystyle p}p элементами поля будут числа {0,1,...,p−1}{displaystyle {0,1,...,p-1}}{0,1,...,p-1}. Сложение и умножение определены как сложение и умножение чисел с приведением результата по модулю p{displaystyle p}p[11].
Ниже приведены примеры таких полей с двумя элементами и тремя элементами.



Cвязь с кольцами вычетов |


Не следует путать конечные поля Fpn{displaystyle mathbb {F} _{p^{n}}}mathbb {F} _{p^{n}} и кольца вычетов Z/(pn){displaystyle mathbb {Z} /(p^{n})}{displaystyle mathbb {Z} /(p^{n})}. Только когда порядок простое число, кольцо вычетов является полем.[12]


При n>1 кольцо вычетов Z/(pn){displaystyle mathbb {Z} /(p^{n})}{displaystyle mathbb {Z} /(p^{n})} полем не является. Пример.



В поле F8{displaystyle mathbb {F} _{8}}{displaystyle mathbb {F} _{8}} для любого элемента верно x+x=0{displaystyle x+x=0}x+x=0.

В кольце Z8{displaystyle mathbb {Z} _{8}}{displaystyle mathbb {Z} _{8}}, вычисляя x+x{displaystyle x+x}x+x, мы получим 0 только в двух случаях, когда x=4,x=0{displaystyle x=4,x=0}{displaystyle x=4,x=0}. Это кольцо имеет делители нуля: 2⋅4=0(mod8){displaystyle 2cdot 4=0{pmod {8}}}{displaystyle 2cdot 4=0{pmod {8}}}.



Характеризация конечных полей |


Характеристика каждого конечного поля является простым числом. Пусть F{displaystyle F}F — конечное поле. Тогда оно состоит из pn{displaystyle p^{n}}p^{n} элементов, где p{displaystyle p}p — характеристика поля F{displaystyle F}F, а натуральное число n{displaystyle n}n — степень поля F{displaystyle F}F над его простым подполем[2].


Согласно теореме о существовании и единственности конечных полей, для каждого простого числа p{displaystyle p}p и натурального числа n{displaystyle n}n существует конечное поле из pn{displaystyle p^{n}}p^{n} элементов и любое конечное поле из q=pn{displaystyle q=p^{n}}q=p^{n} элементов изоморфно полю разложения многочлена xq−x{displaystyle x^{q}-x}x^{q}-x над полем Fp{displaystyle mathbb {F} _{p}}mathbb {F} _{p}. Данная теорема позволяет говорить о вполне определённом поле данного порядка q{displaystyle q}q (то есть о поле Галуа из q{displaystyle q}q элементов)[13].



Построение |


Поле Fpn{displaystyle mathbb {F} _{p^{n}}}mathbb {F} _{p^{n}} при n > 1 можно построить как факторкольцо K=Fp[x]/(f(x)){displaystyle mathbb {K} =mathbb {F} _{p}[x]/(f(x))}mathbb {K} =mathbb {F} _{p}[x]/(f(x)), где f(x){displaystyle f(x)}f(x) — неприводимый многочлен степени n над полем Fp{displaystyle mathbb {F} _{p}}mathbb {F} _{p}. Таким образом, для построения поля из pn{displaystyle p^{n}}p^{n} элементов достаточно отыскать многочлен степени n{displaystyle n}n, неприводимый над полем Fp{displaystyle mathbb {F} _{p}}mathbb {F} _{p} (такой многочлен всегда существует). Элементами поля K{displaystyle mathbb {K} }mathbb {K} являются классы вычетов многочленов степени меньшей n{displaystyle n}n с коэффициентами из Fp{displaystyle mathbb {F} _{p}}mathbb {F} _{p} по модулю главного идеала, порождённого многочленом f(x){displaystyle f(x)}f(x).


Элемент α=x+(f(x))∈Fp[x]/(f(x)){displaystyle alpha =x+(f(x))in mathbb {F} _{p}[x]/(f(x))}alpha =x+(f(x))in mathbb {F} _{p}[x]/(f(x)) является корнем многочлена f(x){displaystyle f(x)}f(x) и поле Fp[x]/(f(x)){displaystyle mathbb {F} _{p}[x]/(f(x))}mathbb {F} _{p}[x]/(f(x)) порождается этим элементом над полем Fp{displaystyle mathbb {F} _{p}}mathbb {F} _{p}, поэтому переход от поля Fp{displaystyle mathbb {F} _{p}}mathbb {F} _{p} к полю Fp[x]/(f(x)){displaystyle mathbb {F} _{p}[x]/(f(x))}mathbb {F} _{p}[x]/(f(x)) называется присоединением к полю Fp{displaystyle mathbb {F} _{p}}mathbb {F} _{p} корня неприводимого многочлена f(x){displaystyle f(x)}f(x).[14][15]



Примеры |





Поле из двух элементов |


Поле F2{displaystyle mathbb {F} _{2}}mathbb {F} _{2} состоит из двух элементов, но оно может быть задано разными способами в зависимости от выбора элементов и определения операций сложения и умножения на них:[16]


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


Очевидно, что данные поля являются изоморфными друг другу, т. е. это фактически два разных способа задания одного и того же поля.





Поле из трёх элементов |


Поле F3={0,1,2}{displaystyle mathbb {F} _{3}={0,1,2}}mathbb {F} _{3}={0,1,2}. Сложения и умножения определены как сложение и умножение чисел по модулю 3. Таблицы операций F3{displaystyle mathbb {F} _{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





Поле из четырёх элементов |


Поле F4{displaystyle mathbb {F} _{4}}mathbb {F} _{4} можно представить как множество {0,1,α,α+1}{displaystyle {0,1,alpha ,alpha +1}}{0,1,alpha ,alpha +1} (где α{displaystyle alpha }alpha  — корень многочлена f(x)=x2+x+1{displaystyle f(x)=x^{2}+x+1}f(x)=x^{2}+x+1 над полем F2{displaystyle mathbb {F} _{2}}mathbb {F} _{2}, то есть α2=−α−1=α+1{displaystyle alpha ^{2}=-alpha -1=alpha +1}alpha ^{2}=-alpha -1=alpha +1). Таблицы операций F4{displaystyle mathbb {F} _{4}}mathbb {F} _{4} имеют вид:[17]










































+ 0 1 α{displaystyle alpha }alpha
α+1{displaystyle alpha +1}alpha +1
0
 0 1 α{displaystyle alpha }alpha
α+1{displaystyle alpha +1}alpha +1
1
 1 0 α+1{displaystyle alpha +1}alpha +1
α{displaystyle alpha }alpha

α{displaystyle alpha }alpha
α{displaystyle alpha }alpha α+1{displaystyle alpha +1}alpha +1 0 1

α+1{displaystyle alpha +1}alpha +1
 α+1{displaystyle alpha +1}alpha +1 α{displaystyle alpha }alpha 1 0






































× 0 1 α{displaystyle alpha }alpha
α+1{displaystyle alpha +1}alpha +1
0
 0 0 0 0
1
 0 1 α{displaystyle alpha }alpha
α+1{displaystyle alpha +1}alpha +1

α{displaystyle alpha }alpha
0 α{displaystyle alpha }alpha α+1{displaystyle alpha +1}alpha +1 1

α+1{displaystyle alpha +1}alpha +1
 0 α+1{displaystyle alpha +1}alpha +1 1
α{displaystyle alpha }alpha





Поле из девяти элементов |


Для построения поля F9=GF(32){displaystyle mathbb {F} _{9}=mathrm {GF} (3^{2})}mathbb {F} _{9}=mathrm {GF} (3^{2}) достаточно найти нормированный многочлен степени 2, неприводимый над F3{displaystyle mathbb {F} _{3}}mathbb {F} _{3}. Такими многочленами являются:







x2+1{displaystyle x^{2}+1}x^{2}+1

x2+x+2{displaystyle x^{2}+x+2}x^{2}+x+2

x2+2x+2{displaystyle x^{2}+2x+2}x^{2}+2x+2

Для x2+1{displaystyle x^{2}+1}x^{2}+1 искомое поле есть F9=Z3[x]/(x2+1){displaystyle mathbb {F} _{9}=mathbb {Z} _{3}[x]/(x^{2}+1)}mathbb {F} _{9}=mathbb {Z} _{3}[x]/(x^{2}+1) (если вместо x2+1{displaystyle x^{2}+1}x^{2}+1 взять другой многочлен, то получится новое поле, изоморфное старому). В приведённых ниже таблицах символ i{displaystyle i}i обозначает класс эквивалентности многочлена x{displaystyle x}x в факторкольце Z3[x]/(x2+1){displaystyle mathbb {Z} _{3}[x]/(x^{2}+1)}mathbb {Z} _{3}[x]/(x^{2}+1), удовлетворяющий уравнению i2+1=0{displaystyle i^{2}+1=0}i^{2}+1=0.


Таблица сложения в F9{displaystyle mathbb {F} _{9}}mathbb {F} _{9} определяется, исходя из соотношения 1+1+1=0{displaystyle 1+1+1=0}1+1+1=0:



























































































































+
 0
 1
 2
i{displaystyle i}i
i+1{displaystyle i+1}i+1
i+2{displaystyle i+2}i+2
2i{displaystyle 2i}2i
2i+1{displaystyle 2i+1}2i+1
2i+2{displaystyle 2i+2}2i+2
0
 0
 1
 2
i{displaystyle i}i
i+1{displaystyle i+1}i+1
i+2{displaystyle i+2}i+2
2i{displaystyle 2i}2i
2i+1{displaystyle 2i+1}2i+1
2i+2{displaystyle 2i+2}2i+2
1
 1
 2
 0
i+1{displaystyle i+1}i+1
i+2{displaystyle i+2}i+2
i{displaystyle i}i
2i+1{displaystyle 2i+1}2i+1
2i+2{displaystyle 2i+2}2i+2
2i{displaystyle 2i}2i
2
 2
 0
 1
i+2{displaystyle i+2}i+2
i{displaystyle i}i
i+1{displaystyle i+1}i+1
2i+2{displaystyle 2i+2}2i+2
2i{displaystyle 2i}2i
2i+1{displaystyle 2i+1}2i+1

i{displaystyle i}i
i{displaystyle i}i
i+1{displaystyle i+1}i+1
i+2{displaystyle i+2}i+2
2i{displaystyle 2i}2i
2i+1{displaystyle 2i+1}2i+1
2i+2{displaystyle 2i+2}2i+2
 0
 1
 2

i+1{displaystyle i+1}i+1
i+1{displaystyle i+1}i+1
i+2{displaystyle i+2}i+2
i{displaystyle i}i
2i+1{displaystyle 2i+1}2i+1
2i+2{displaystyle 2i+2}2i+2
2i{displaystyle 2i}2i
 1
 2
 0

i+2{displaystyle i+2}i+2
i+2{displaystyle i+2}i+2
i{displaystyle i}i
i+1{displaystyle i+1}i+1
2i+2{displaystyle 2i+2}2i+2
2i{displaystyle 2i}2i
2i+1{displaystyle 2i+1}2i+1
 2
 0
 1

2i{displaystyle 2i}2i
2i{displaystyle 2i}2i
2i+1{displaystyle 2i+1}2i+1
2i+2{displaystyle 2i+2}2i+2
 0
 1
 2
i{displaystyle i}i
i+1{displaystyle i+1}i+1
i+2{displaystyle i+2}i+2

2i+1{displaystyle 2i+1}2i+1
2i+1{displaystyle 2i+1}2i+1
2i+2{displaystyle 2i+2}2i+2
2i{displaystyle 2i}2i
 1
 2
 0
i+1{displaystyle i+1}i+1
i+2{displaystyle i+2}i+2
i{displaystyle i}i

2i+2{displaystyle 2i+2}2i+2
2i+2{displaystyle 2i+2}2i+2
2i{displaystyle 2i}2i
2i+1{displaystyle 2i+1}2i+1
 2
 0
 1
i+2{displaystyle i+2}i+2
i{displaystyle i}i
i+1{displaystyle i+1}i+1

Таблица умножения в F9{displaystyle mathbb {F} _{9}}mathbb {F} _{9} определяется из соотношения i2=−1{displaystyle i^{2}=-1}i^{2}=-1:



























































































































×
 0
 1
 2
i{displaystyle i}i
i+1{displaystyle i+1}i+1
i+2{displaystyle i+2}i+2
2i{displaystyle 2i}2i
2i+1{displaystyle 2i+1}2i+1
2i+2{displaystyle 2i+2}2i+2
0
 0
 0
 0
 0
 0
 0
 0
 0
 0
1
 0
 1
 2
i{displaystyle i}i
i+1{displaystyle i+1}i+1
i+2{displaystyle i+2}i+2
2i{displaystyle 2i}2i
2i+1{displaystyle 2i+1}2i+1
2i+2{displaystyle 2i+2}2i+2
2
 0
 2
 1
2i{displaystyle 2i}2i
2i+2{displaystyle 2i+2}2i+2
2i+1{displaystyle 2i+1}2i+1
i{displaystyle i}i
i+2{displaystyle i+2}i+2
i+1{displaystyle i+1}i+1

i{displaystyle i}i
 0
i{displaystyle i}i
2i{displaystyle 2i}2i
 2
i+2{displaystyle i+2}i+2
2i+2{displaystyle 2i+2}2i+2
 1
i+1{displaystyle i+1}i+1
2i+1{displaystyle 2i+1}2i+1

i+1{displaystyle i+1}i+1
 0
i+1{displaystyle i+1}i+1
2i+2{displaystyle 2i+2}2i+2
i+2{displaystyle i+2}i+2
2i{displaystyle 2i}2i
 1
2i+1{displaystyle 2i+1}2i+1
 2
i{displaystyle i}i

i+2{displaystyle i+2}i+2
 0
i+2{displaystyle i+2}i+2
2i+1{displaystyle 2i+1}2i+1
2i+2{displaystyle 2i+2}2i+2
 1
i{displaystyle i}i
i+1{displaystyle i+1}i+1
2i{displaystyle 2i}2i
 2

2i{displaystyle 2i}2i
 0
2i{displaystyle 2i}2i
i{displaystyle i}i
 1
2i+1{displaystyle 2i+1}2i+1
i+1{displaystyle i+1}i+1
 2
2i+2{displaystyle 2i+2}2i+2
i+2{displaystyle i+2}i+2

2i+1{displaystyle 2i+1}2i+1
 0
2i+1{displaystyle 2i+1}2i+1
i+2{displaystyle i+2}i+2
i+1{displaystyle i+1}i+1
 2
2i{displaystyle 2i}2i
2i+2{displaystyle 2i+2}2i+2
i{displaystyle i}i
 1

2i+2{displaystyle 2i+2}2i+2
 0
2i+2{displaystyle 2i+2}2i+2
i+1{displaystyle i+1}i+1
2i+1{displaystyle 2i+1}2i+1
i{displaystyle i}i
 2
i+2{displaystyle i+2}i+2
 1
2i{displaystyle 2i}2i

Можно проверить, что элемент i+1{displaystyle i+1}i+1 имеет порядок 8 и является примитивным. Элемент i{displaystyle i}i не является примитивным, так как i4=1{displaystyle i^{4}=1}i^{4}=1 (другими словами, многочлен x2+1∈F3[x]{displaystyle x^{2}+1in mathbb {F} _{3}[x]}x^{2}+1in mathbb {F} _{3}[x] не является примитивным)[17].



Мультипликативная группа поля из 16 элементов |


Когда поле F16=GF(24){displaystyle mathbb {F} _{16}=mathrm {GF} (2^{4})}mathbb {F} _{16}=mathrm {GF} (2^{4}) строится с помощью неприводимого многочлена x4+x+1{displaystyle x^{4}+x+1}x^{4}+x+1, элементы расширения задаются наборами коэффициентов многочлена, который получается в остатке при делении на x4+x+1{displaystyle x^{4}+x+1}x^{4}+x+1, записанными в порядке возрастания степеней. Мультипликативная группа порождается элементом α=x{displaystyle alpha =x}alpha =x, который записывается как (0, 1, 0, 0)[18].
























































































Многочлен
 Степень α{displaystyle alpha }alpha

1,x,x2,x3{displaystyle 1,x,x^{2},x^{3}}1,x,x^{2},x^{3}
1
α0{displaystyle alpha ^{0}}{displaystyle alpha ^{0}}
 (1, 0, 0, 0)

α{displaystyle alpha }alpha

α{displaystyle alpha }alpha
(0, 1, 0, 0)

α2{displaystyle alpha ^{2}}alpha ^{2}
α2{displaystyle alpha ^{2}}alpha ^{2}
 (0, 0, 1, 0)

α3{displaystyle alpha ^{3}}alpha ^{3}
α3{displaystyle alpha ^{3}}alpha ^{3}
 (0, 0, 0, 1)

1+α{displaystyle 1+alpha }1+alpha

α4{displaystyle alpha ^{4}}alpha ^{4}
 (1, 1, 0, 0)

α+α2{displaystyle alpha +alpha ^{2}}alpha +alpha ^{2}
α5{displaystyle alpha ^{5}}alpha ^{5}
 (0, 1, 1, 0)

α2+α3{displaystyle alpha ^{2}+alpha ^{3}}alpha ^{2}+alpha ^{3}
α6{displaystyle alpha ^{6}}alpha ^{6}
 (0, 0, 1, 1)

α3+α+1=α3+α4{displaystyle alpha ^{3}+alpha +1=alpha ^{3}+alpha ^{4}}alpha ^{3}+alpha +1=alpha ^{3}+alpha ^{4}
α7{displaystyle alpha ^{7}}alpha ^{7}
 (1, 1, 0, 1)

1+α2=α+1+α2+α{displaystyle 1+alpha ^{2}=alpha +1+alpha ^{2}+alpha }1+alpha ^{2}=alpha +1+alpha ^{2}+alpha

α8{displaystyle alpha ^{8}}alpha ^{8}
 (1, 0, 1, 0)

α+α3{displaystyle alpha +alpha ^{3}}alpha +alpha ^{3}
α9{displaystyle alpha ^{9}}alpha ^{9}
 (0, 1, 0, 1)

α2+1+α=α2+α4{displaystyle alpha ^{2}+1+alpha =alpha ^{2}+alpha ^{4}}alpha ^{2}+1+alpha =alpha ^{2}+alpha ^{4}
α10{displaystyle alpha ^{10}}alpha ^{10}
 (1, 1, 1, 0)

α+α2+α3{displaystyle alpha +alpha ^{2}+alpha ^{3}}alpha +alpha ^{2}+alpha ^{3}
α11{displaystyle alpha ^{11}}alpha ^{11}
 (0, 1, 1, 1)

1+α+α2+α3=α2+α3+α4{displaystyle 1+alpha +alpha ^{2}+alpha ^{3}=alpha ^{2}+alpha ^{3}+alpha ^{4}}1+alpha +alpha ^{2}+alpha ^{3}=alpha ^{2}+alpha ^{3}+alpha ^{4}
α12{displaystyle alpha ^{12}}alpha ^{12}
 (1, 1, 1, 1)

1+α2+α3=α+α2+α3+α4{displaystyle 1+alpha ^{2}+alpha ^{3}=alpha +alpha ^{2}+alpha ^{3}+alpha ^{4}}1+alpha ^{2}+alpha ^{3}=alpha +alpha ^{2}+alpha ^{3}+alpha ^{4}
α13{displaystyle alpha ^{13}}alpha ^{13}
 (1, 0, 1, 1)

1+α3=α+α3+α4{displaystyle 1+alpha ^{3}=alpha +alpha ^{3}+alpha ^{4}}1+alpha ^{3}=alpha +alpha ^{3}+alpha ^{4}
α14{displaystyle alpha ^{14}}alpha ^{14}
 (1, 0, 0, 1)

1=α+α4{displaystyle 1=alpha +alpha ^{4}}1=alpha +alpha ^{4}
α15{displaystyle alpha ^{15}}alpha ^{15}
 (1, 0, 0, 0)


История изучения |


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



Вклад Галуа |




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


В 1830 году восемнадцатилетний Эварист Галуа опубликовал работу[20], которая положила основу общей теории конечных полей. В этой работе Галуа (в связи с исследованиями по теории групп перестановок и алгебраических уравнений[21]) вводит воображаемый корень сравнения F(x)≡0(modp){displaystyle F(x)equiv 0{pmod {p}}}F(x)equiv 0{pmod {p}}, где F(x){displaystyle F(x)}F(x) — произвольный многочлен степени ν{displaystyle nu }nu , неприводимый по модулю p. После этого рассматривается общее выражение A=a0+a1i+a2i2+...+aν−1iν−1{displaystyle A=a_{0}+{a_{1}}i+{a_{2}}i^{2}+...+a_{nu -1}i^{nu -1}}A=a_{0}+{a_{1}}i+{a_{2}}i^{2}+...+a_{nu -1}i^{nu -1}, где a0,a1,...,aν−1{displaystyle a_{0},a_{1},...,a_{nu -1}}a_{0},a_{1},...,a_{nu -1} — некие целые числа по модулю p. Если присваивать этим числам всевозможные значения, выражение A{displaystyle A}A будет принимать pν{displaystyle p^{nu }}p^{nu } значений. Далее Галуа показывает, что эти значения образуют поле и мультипликативная группа этого поля является циклической. Таким образом, эта работа является первым камнем в фундаменте общей теории конечных полей. В отличие от его предшественников, рассматривающих только поля Fp{displaystyle mathbb {F} _{p}}mathbb {F} _{p}, Галуа рассматривает уже поля Fpn{displaystyle mathbb {F} _{p^{n}}}mathbb {F} _{p^{n}}, которые начали называть полями Галуа в его честь[22].


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



Дальнейшее развитие |


В 1893 году математик Элиаким Мур доказал теорему о классификации конечных полей, утверждающую, что любое конечное поле является полем Галуа, то есть любое поле из pn{displaystyle p^{n}}p^{n} элементов изоморфно полю классов вычетов многочленов с коэффициентами из Fp{displaystyle mathbb {F} _{p}}mathbb {F} _{p} по модулю неприводимого многочлена степени n{displaystyle n}n[24]. К этому же году относится первая попытка дать аксиоматический подход к теории конечных полей, осуществленная Генрихом Вебером, который пытался объединить в своей работе понятия, возникшие в различных разделах математики, в том числе и понятие конечного поля[25]. Далее в 1905 году Джозеф Веддербёрн доказывает малую теорему Веддербёрна о том, что любое конечное тело коммутативно, то есть является полем. Современное аксиоматическое определение поля (с конечными полями в качестве частного случая) принадлежит Эрнсту Штайницу и изложено в его работе 1910 года[26].



Приложения |



Диофантовы уравнения |


Диофантово уравнение является уравнением с целыми коэффициентами, в котором переменные также принимают целочисленные значения. Большую волну обсуждения таких уравнений вызвал Ферма, сформулировав свои теоремы. Малая теорема Ферма утверждает, что если p{displaystyle p}p — простое число, не являющееся делителем другого числа a{displaystyle a}a, то ap−1≡1(modp){displaystyle a^{p-1}equiv 1{pmod {p}}}a^{p-1}equiv 1{pmod {p}}. В теории конечных полей эта теорема является очевидным следствием теоремы Лагранжа, применённой к мультипликативной подгруппе, порождённой элементом a{displaystyle a}a, так как вся мультипликативная группа поля Fp{displaystyle mathbb {F} _{p}}mathbb {F} _{p} состоит из p−1{displaystyle p-1}p-1 элементов[5].


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


5=12+22,13=22+32,17=12+42,29=22+52,37=12+62,41=42+52.{displaystyle 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}.}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 года, Ферма предлагает решить уравнение a2+b2=p{displaystyle a^{2}+b^{2}=p}a^{2}+b^{2}=p[27].


Юлиус Дедекинд исследовал это уравнение в конечном поле Fp{displaystyle mathbb {F} _{p}}mathbb {F} _{p}, где оно принимает вид a2+b2=0{displaystyle a^{2}+b^{2}=0}a^{2}+b^{2}=0. Если b=0{displaystyle b=0}b=0, то решение тривиально. В противном случае можно разделить обе части на b2{displaystyle b^{2}}b^{2} и, введя замену, получить уравнение вида x2+1=0{displaystyle x^{2}+1=0}x^{2}+1=0. Домножением на x2−1=0{displaystyle x^{2}-1=0}x^{2}-1=0 получается уравнение x4−1=0{displaystyle x^{4}-1=0}x^{4}-1=0. Считая x{displaystyle x}x генератором мультипликативной подгруппы порядка 4, можно получить необходимые и достаточные условия на p, при которых уравнение имеет решение. Дальнейшее доказательство теоремы Ферма — Эйлера, проведённое Дедекиндом, не использует понятия конечных полей и его можно найти в соответствующей статье[28].



Теория корректирующих кодов |


Годом создания теории корректирующих кодов считается 1948 год, в котором была опубликована статья Клода Шеннона, в которой он показывает, что наличие ошибок при передаче информации по какому-либо каналу зависит в том числе от соотношения скорости передачи и пропускной способности канала. Скорость передачи должна быть выше пропускной способности. Шеннон привел доказательства, но они были признаны несостоятельными[29].


Конструктивный подход предложил Ричард Хэмминг, задав тем самым вектор развития многих более поздних статей данной тематики. В своей работе Хэмминг построил простой код, исправляющий ошибки определенным образом. Хэмминг рассматривал корректирующие коды только над полем F2{displaystyle mathbb {F} _{2}}mathbb {F} _{2}[30]. Вскоре подобные коды были построены над произвольными конечными полями Голеем в 1949 году[31]. Однако наибольший вклад в эту теорию принадлежит все же Хэммингу[30].



Криптография |


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


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



Прочее |




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


В 1960 году Р. К. Боуз[en] и Д. К. Рой-Чоудхури[en] опубликовали работу, в которой исследовали семейства многочленов над конечными полями. А. Хоквингем[en] обобщил их теорию, что привело к созданию кода БЧХ, частным случаем которого является широко известный код Рида — Соломона, имеющий очень обширное применение. Он используется при записи и чтении в контроллерах оперативной памяти, при архивировании данных, записи информации на жесткие диски (ECC), записи на CD/DVD диски. Примечательно то, что при повреждении значительного объёма информации, или если испорчено несколько секторов дискового носителя, код Рида — Соломона позволяют восстановить большую часть потерянной информации. Код БЧХ используется также в системе связи некоторых зондов NASA (таких как Voyager)[35].



См. также |



  • Поле

  • Группа

  • Первообразный корень

  • Многочлен над конечным полем

  • Автоморфизм Фробениуса



Примечания |





  1. ↑ 12 Лидл, Нидеррайтер, 1998, с. 68.


  2. ↑ 123 Лидл, Нидеррайтер, 1998, с. 66.


  3. ↑ 1234 Лидл, Нидеррайтер, 1998, с. 5.


  4. ↑ 12 Diffie, Hellman, 1976.


  5. ↑ 123 Ю.И.Журавлев, Ю.А.Флеров, М.Н.Вялый. Дискретный анализ. Основы высшей алгебры. — М.: МЗ Пресс, 2007. — С. 151. — 224 с.


  6. ↑ Лидл, Нидеррайтер, 1998, с. 69-70.


  7. ↑ Лидл, Нидеррайтер, 1998, с. 71.


  8. ↑ Лидл, Нидеррайтер, 1998, с. 119.


  9. ↑ Лидл, Нидеррайтер, 1998, с. 121.


  10. ↑ Лидл, Нидеррайтер, 1998, с. 65.


  11. ↑ Егоров А. А. Сравнения по модулю и арифметика остатков // Квант. — 1970. — № 5. — С. 28—33.


  12. ↑ Винберг, 2011, с. 32.


  13. ↑ Лидл, Нидеррайтер, 1998, с. 67-68.


  14. ↑ Винберг, 2011, с. 409.


  15. ↑ Лидл, Нидеррайтер, 1998, с. 51, 66.


  16. ↑ Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И., Владимиров С. М. Защита информации. Учебное пособие. Версия от 22 ноября 2015 года. — С. 249.


  17. ↑ 12 Mullen, Gary L.; Panario, Daniel. Handbook of Finite Fields. — CRC Press, 2013. — ISBN 978-1-4398-7378-6.


  18. ↑ Ю.И.Журавлев, Ю.А.Флеров, М.Н.Вялый. Дискретный анализ. Основы высшей алгебры. — М.: МЗ Пресс, 2007. — С. 152. — 224 с.


  19. ↑ Лидл, Нидеррайтер, 1998, с. 10.


  20. ↑ Evariste Galois (1830), Sur la théorie des nombres. Bulletin des sciences mathématiques de M. Férussac 13, pp 428—435 (1830)


  21. ↑ Бурбаки Н. Очерки по истории математики / пер. с фр. И. Г. Башмаковой под ред. К. А. Рыбникова. — М.: ИЛ, 1963. — С. 102.


  22. ↑ Israel Kleiner. A History of Abstract Algebra. — Birkhäuser, 2007. — С. 70. — 168 с. — ISBN 978-0-8176-4684-4.


  23. ↑ G. Frei. The Unpublished Section Eight: On the Way to Function Fields over a Finite Field. — Goldstein Schappacher Schwermer, 2007. — С. 159-198.


  24. ↑ Moore, Eliakim Hastings. A doubly-infinite system of simple groups // Chicago Congr. Papers. — 1896. — P. 208-242. Архивировано 19 ноября 2015 года.


  25. ↑ H. Weber, " Die allgemeinen Grundlagen der Galois’schen Gleichungstheorie ", Mathematische Annalen, vol. 43, 1893, p. 521—549


  26. ↑ Ernst Steinitz, " Algebraische Theorie der Körper ", Journal für die reine und angewandte Mathematik, vol. 137, 1910, p. 167—309 (ISSN 0075-4102)


  27. ↑ Ю.И.Журавлев, Ю.А.Флеров, М.Н.Вялый. Дискретный анализ. Основы высшей алгебры. — М.: МЗ Пресс, 2007. — С. 38. — 224 с.


  28. ↑ R. Dedekind, Supplément XI des Leçons en théorie des nombres de Dirichlet, 1894


  29. ↑ Шеннон, К. Математическая теория связи // Работы по теории информации и кибернетике. — М.: Издательство иностранной литературы, 1963. — С. 243—332.


  30. ↑ 12 Хэмминг, К. Коды с обнаружением и исправлением ошибок. — М.: Издательство иностранной литературы, 1956. — С. 7-23.


  31. ↑ Golay M. J. E. Notes on digital coding // Proceedings IRE. 1949. V. 37, P.657.


  32. ↑ О.С Зензин, М.А. Иванов. Стандарт криптографической защиты - AES. Конечные поля.. — КУДИЦ-Образ, 2002. — С. 41 - 78. — 176 с. — ISBN 5-93378-046-4.


  33. ↑ Анатолий Болотов, Сергей Гашков, Александр Фролов, Анатолий Часовских. Элементарное введение в эллиптическую криптографию. Алгебраические и алгоритмические основы. — КомКнига, 2006. — С. 390 — 398. — 527 с. — ISBN 5-484-00443-8.


  34. ↑ M. Rabin, Probabilistic Algorithm for Testing Primality, J. Number Th. 12 (1980), 128—138


  35. ↑ Bose R. C., Ray-Chaudhuri D. K. On a class of error-correcting binary group codes // Inform. Control. — vol. 3. — mars 1960. — p. 68—79.




Литература |



  • Винберг Э. Б.  Курс алгебры. — новое изд., перераб. и доп. — М.: МЦНМО, 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.

  • Steinitz, Ernst.  Algebraische Theorie der Körper (нем.) // Journal für die reine und angewandte Mathematik. — 1910. — Bd. 137. — S. 167-309.

  • Diffie W., Hellman M. E. New Directions in Cryptography // IEEE Trans. Inf. Theory / F. Kschischang — IEEE, 1976. — Vol. 22, Iss. 6. — P. 644–654. — ISSN 0018-9448 — doi:10.1109/TIT.1976.1055638
    <a href="https://wikidata.org/wiki/Track:Q16194641"></a><a href="https://wikidata.org/wiki/Track:Q27178858"></a><a href="https://wikidata.org/wiki/Track:Q127793"></a><a href="https://wikidata.org/wiki/Track:Q476466"></a><a href="https://wikidata.org/wiki/Track:Q462089"></a>

  • Kleiner, Israel.  A History of Abstract Algebra. — Birkhäuser, 2007. — ISBN 978-0-8176-4684-4.




-

Popular posts from this blog

Котор

Image
У этого термина существуют и другие значения, см. Котор (значения). Город Котор черногор. Котор, Kotor Флаг Герб 42°25′29,61″ с. ш. 18°46′10,83″ в. д. H G Я O Страна Черногория   Черногория Мэр Мария Чатович История и география Первое упоминание 168 год до н. э. Прежние названия Акрувиум, Аскруйон, Декатерон, Каттаро Площадь 335 км² Высота центра 16 м Тип климата субтропический Часовой пояс UTC+1, летом UTC+2 Население Население ↗ 13 176 человек ( 2003 ) Национальности черногорцы, сербы Конфессии православные, католики Официальный язык черногорский Цифровые идентификаторы Телефонный код +382 32 Почтовый индекс 85330 Автомобильный код KO opstinakotor.com Котор  Аудио, фото и видео на Викискладе Всемирное наследие ЮНЕСКО, объект № 125 рус. • англ. • фр. Ко́тор (черногор. Котор/Kotor , серб. Котор/Kotor , хорв. Kotor , итал.  Cattaro , лат.  ...
Read more

Потомский, Вадим Владимирович

Image
Вадим Владимирович Потомский 3-й Заместитель Полномочного представителя президента Российской Федерации в Северо-западном федеральном округе с 5 октября 2017 года Президент Владимир Путин Губернатор Орловской области 23 сентября 2014  — 5 октября 2017 Предшественник Александр Козлов Преемник Андрей Клычков Рождение 12 августа 1972 ( 1972-08-12 ) (46 лет) Мары, Туркменская ССР, СССР Партия КПРФ Образование СПбВЗРКУ, СЗАГС Награды  Вадим Владимирович Потомский на Викискладе Вади́м Влади́мирович Пото́мский (род. 12 августа 1972, Мары, Туркменская ССР, СССР) — российский государственный и политический деятель, экономист. Заместитель Полномочного представителя президента Российской Федерации в Центральном федеральном округе (с 5 октября 2017 года) [1] . Бывший губернатор Орловской области (23 сентября 2014 — 5 октября 2017 [2] ). Член Центрального комитета Коммунистической партии Российской Федерации...
Read more

Бедствия войны

Image
Лист 2: По причине или без (Con razon ó sin ella) Франсиско Гойя Бедствия войны . 1810—1820 Los Desastres de la Guerra Гравюра Нью-Йоркский музей современного искусства  Изображения на Викискладе «Бедствия войны» (исп.  Los Desastres de la Guerra ) — серия из 82 гравюр Франсиско Гойи, созданных в период между 1810 и 1820 годами. Историки искусства рассматривают эту серию как протест против жестокости подавления антифранцузского восстания второго мая, последовавшей за ним войны на Пиренейском полуострове и реакционной политики восстановленной династии Бурбонов. Содержание 1 Описание 2 Исторические предпосылки 2.1 Война 2.2 Голод 2.3 Бурбоны и духовенство 3 Примечания 4 Литература 5 Ссылки Описание | Лист 3: Со здравым смыслом или без него? (Lo mismo) . Мужчина готовится отрубить топором голову солдату. Во время войны между Наполеоновской империей и Испанией, Гойя занимал должность первого живопи...
Read more