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

Алгебраическая структура

В математике конечное поле или поле Галуа (названное так в честь Эвариста Галуа ) — это поле , содержащее конечное число элементов . Как и любое поле, конечное поле — это множество, на котором определены операции умножения, сложения, вычитания и деления и которые удовлетворяют определенным основным правилам. Наиболее распространенными примерами конечных полей являются целые числа по модулю p , когда p — простое число .

Порядок конечного поля — это количество его элементов, которое является либо простым числом, либо простой степенью . Для каждого простого числа p и любого ^{натурального} числа k существуют поля порядка pk , все из которых изоморфны .

Конечные поля являются фундаментальными в ряде областей математики и информатики , включая теорию чисел , алгебраическую геометрию , теорию Галуа , конечную геометрию , криптографию и теорию кодирования .

Характеристики

Конечное поле — это конечное множество, являющееся полем ; это означает, что умножение, сложение, вычитание и деление (за исключением деления на ноль) определены и удовлетворяют правилам арифметики, известным как аксиомы поля .

Число элементов конечного поля называется его порядком или иногда размером . Конечное поле порядка q существует тогда и только тогда, когда q — степень простого числа p ^k (где p — простое число, а k — целое положительное число). В поле порядка p ^k добавление p копий любого элемента всегда приводит к нулю; то есть характеристика поля равна p .

Если q = p ^k , все поля порядка q изоморфны (см. § Существование и единственность ниже). ^[1] Более того, поле не может содержать два разных конечных подполя одного и того же порядка. Таким образом, можно идентифицировать все конечные поля одного и того же порядка, и они однозначно обозначаются F q _или GF ( q ) , где буквы GF обозначают «поле Галуа». ^[2] ${\displaystyle \mathbb {F} _{q}}$

В конечном поле порядка q многочлен X ^q − X имеет все q элементов конечного поля как корни . Ненулевые элементы конечного поля образуют мультипликативную группу . Эта группа является циклической , поэтому все ненулевые элементы могут быть выражены как степени одного элемента, называемого примитивным элементом поля. (Обычно для данного поля будет несколько примитивных элементов.)

Простейшими примерами конечных полей являются поля простого порядка: для каждого простого числа p простое поле порядка p может быть построено как целые числа по модулю p , . ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$

Элементы простого поля порядка p могут быть представлены целыми числами в диапазоне 0, ..., p − 1 . Сумма, разность и произведение представляют собой остаток от деления на p результата соответствующей целочисленной операции. Мультипликативный обратный элемент можно вычислить с помощью расширенного алгоритма Евклида (см. Расширенный алгоритм Евклида § Модульные целые числа ).

Пусть F — конечное поле. Для любого элемента x в F и любого целого числа n обозначим через n ⋅ x сумму n копий x . Наименьшее положительное n такое, что n ⋅ 1 = 0, является характеристикой p поля. Это позволяет определить умножение ( k , x ) ↦ k ⋅ x элемента k из GF( p ) на элемент x из F путем выбора целочисленного представителя для k . Это умножение превращает F в GF( p ) -векторное пространство . Отсюда следует, что число элементов F равно p ⁿ для некоторого целого числа n .

Личность​

$${\displaystyle (x+y)^{p}=x^{p}+y^{p}}$$

сном первокурсникаpбиномиальной теоремыбиномиальный коэффициент( x + y ) ^pp

По малой теореме Ферма , если p — простое число и x находится в поле GF( p ) , то x ^p = x . Отсюда следует равенство

$${\displaystyle X^{p}-X=\prod _{a\in \mathrm {GF} (p)}(X-a)}$$

GF( p )GF( p ⁿ )x ^{p n} − x = 0

Любое конечное расширение конечного поля сепарабельно и просто. То есть, если E — конечное поле, а F — подполе E , то E получается из F путем присоединения одного элемента, минимальный многочлен которого является отделимым . Если использовать жаргонизм, то конечные поля идеальны .

Более общая алгебраическая структура, удовлетворяющая всем остальным аксиомам поля, но умножение которой не обязательно должно быть коммутативным, называется телом ( или иногда телом ). По малой теореме Веддерберна любое конечное тело коммутативно и, следовательно, является конечным полем.

Существование и уникальность

Пусть q = pn ^— степень простого числа , а F — поле разложения многочлена

$${\displaystyle P=X^{q}-X}$$

GF( p )FPqформальная производнаяP ′ = −1gcd( P , P ′ ) = 1 ,сепарабельным расширениемPPP. PqF

Таким образом, из единственности с точностью до изоморфизма полей расщепления следует, что все поля порядка q изоморфны. Кроме того, если поле F имеет поле порядка q = p ^k в качестве подполя, его элементами являются q корни X ^q − X , и F не может содержать другое подполе порядка q .

Таким образом, мы имеем следующую классификационную теорему, впервые доказанную в 1893 году Э. Х. Муром : ^[1]

Порядок конечного поля — это степень простого числа. Для каждой простой степени q существуют поля порядка q , и все они изоморфны. В этих полях каждый элемент удовлетворяет

$${\displaystyle x^{q}=x,}$$

и многочлен X ^q − X факторизуется как

$${\displaystyle X^{q}-X=\prod _{a\in F}(X-a).}$$

Отсюда следует, что GF( pn ) содержит подполе, изоморфное GF( pm ^{) ,} тогда и только тогда, когда m является делителем n ; в этом случае это подполе уникально. Фактически, многочлен X ^{p m} − X делит X ^{p n} − X тогда и только тогда, когда m является делителем n .

Явная конструкция

Непростые поля

Учитывая степень простого числа q = p ⁿ с p prime и n > 1 , поле GF( q ) можно явно построить следующим образом. Сначала выбирают неприводимый многочлен P в GF( p )[ X ] степени n (такой неприводимый многочлен всегда существует). Тогда факторкольцо

$${\displaystyle \mathrm {GF} (q)=\mathrm {GF} (p)[X]/(P)}$$

GF( p )[ X ]Pq

Более явно, элементы GF( q ) являются полиномами над GF( p ) , степень которых строго меньше n . Сложение и вычитание относятся к полиномам над GF( p ) . Произведение двух элементов является остатком евклидова деления на P произведения в GF( p )[ X ] . Мультипликативный обратный ненулевому элементу можно вычислить с помощью расширенного алгоритма Евклида; см. Расширенный алгоритм Евклида § Простые расширения алгебраических полей .

Однако при таком представлении элементы GF( q ) может быть трудно отличить от соответствующих полиномов. Поэтому принято давать имя, обычно α , элементу GF( q ) , который соответствует многочлену X. Итак, элементы GF( q ) становятся полиномами от α , где P ( α ) = 0 , и когда кто-то встречает полином от α степени, большей или равной n (например, после умножения), можно знать, что один должен использовать соотношение P ( α ) = 0, чтобы уменьшить свою степень (это то, что делает евклидово деление).

За исключением конструкции GF(4) существует несколько возможных вариантов выбора P , которые дают изоморфные результаты. Чтобы упростить евклидово деление, в качестве P обычно выбирают многочлен вида

$${\displaystyle X^{n}+aX+b,}$$

2X ⁿ + aX + b2X ⁿ + X + 1X ⁿ + X ^k + 1kтрехчленыX ⁿ + X ^a + X ^b + X ^c + 1121^[3]

Возможный выбор такого полинома дается полиномами Конвея . Они обеспечивают определенную совместимость между представлением поля и представлениями его подполей.

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

Поле с четырьмя элементами

Наименьшее непростое поле — это поле с четырьмя элементами, которое обычно обозначается GF(4) или оно состоит из четырех элементов 0, 1, α , 1 + α таких, что α ² = 1 + α , 1 ⋅ α = α ⋅ 1 = α , x + x = 0 и x ⋅ 0 = 0 ⋅ x = 0 , для каждого x ∈ GF(4) результаты остальных операций легко выводятся из закона распределения . Ниже приведены полные рабочие таблицы. ${\displaystyle \mathbb {F} _{4}.}$

Это можно вывести следующим образом из результатов предыдущего раздела.

Над GF(2) существует только один неприводимый полином степени 2 :

$${\displaystyle X^{2}+X+1}$$

GF(4)

$${\displaystyle \mathrm {GF} (4)=\mathrm {GF} (2)[X]/(X^{2}+X+1).}$$

Пусть α обозначает корень этого многочлена в GF(4) . Это подразумевает, что

α ² = 1 + α ,

и что α и 1 + α являются элементами GF(4) , которых нет в GF(2) . В результате этого получены таблицы операций в GF(4) :

Таблица для вычитания не приведена, поскольку вычитание идентично сложению, как и для каждого поля признака 2. В третьей таблице для деления x на y значения x необходимо читать в левом столбце. и значения y в верхней строке. (Поскольку 0 ⋅ z = 0 для каждого z в каждом кольце деление на 0 должно оставаться неопределенным.) Из таблиц видно, что аддитивная структура GF(4) изоморфна четырехгруппе Клейна , а ненулевая мультипликативная структура изоморфна группе Z ₃ .

Карта

$${\displaystyle \varphi :x\mapsto x^{2}}$$

α1 + αX ² + X + 1

GF( p 2 ) для нечетного простого числа p

Для применения приведенной выше общей конструкции конечных полей в случае GF( p2 ) необходимо найти неприводимый полином степени 2. Для ^p = 2 это было сделано в предыдущем разделе. Если p — нечетное простое число, всегда существуют неприводимые многочлены формы X ² − r с r в GF( p ) .

Точнее, многочлен X ² − r неприводим над GF( p ) тогда и только тогда, когда r является квадратичным невычетом по модулю p (это почти определение квадратичного невычета). Естьп - 1/2квадратичные невычеты по модулю p . Например, 2 является квадратичным невычетом для p = 3, 5, 11, 13, ... , а 3 является квадратичным невычетом для p = 5, 7, 17, ... . Если p ≡ 3 mod 4 , то есть p = 3, 7, 11, 19, ... , можно выбрать −1 ≡ p − 1 в качестве квадратичного невычета, что позволяет нам иметь очень простой неприводимый многочлен X ² + 1 .

Выбрав квадратичный невычет r , пусть α будет символическим квадратным корнем из r , то есть символом, который обладает свойством α ² = r , точно так же, как комплексное число i является символическим квадратным корнем из −1. . Тогда элементами GF( p ² ) являются все линейные выражения

$${\displaystyle a+b\alpha ,}$$

abGF( p )GF( p2 )GF( p ) , представленными латинскими буквами ^,GF( p )

$${\displaystyle {\begin{aligned}-(a+b\alpha )&=-a+(-b)\alpha \\(a+b\alpha )+(c+d\alpha )&=(a+c)+(b+d)\alpha \\(a+b\alpha )(c+d\alpha )&=(ac+rbd)+(ad+bc)\alpha \\(a+b\alpha )^{-1}&=a(a^{2}-rb^{2})^{-1}+(-b)(a^{2}-rb^{2})^{-1}\alpha \end{aligned}}}$$

ГФ(8) и ГФ(27)

Полином

$${\displaystyle X^{3}-X-1}$$

GF(2)GF(3)23GF(2)GF(3)GF(8)GF(27)выражениями

$${\displaystyle a+b\alpha +c\alpha ^{2},}$$

a , b , cGF(2)GF(3)α

$${\displaystyle \alpha ^{3}=\alpha +1.}$$

Таким образом, сложение, аддитивное обратное и умножение GF(8) и GF(27) можно определить следующим образом; в следующих формулах операции между элементами GF(2) или GF(3) , представленными латинскими буквами, являются операциями в GF(2) или GF(3) соответственно:

$${\displaystyle {\begin{aligned}-(a+b\alpha +c\alpha ^{2})&=-a+(-b)\alpha +(-c)\alpha ^{2}\qquad {\text{(for }}\mathrm {GF} (8),{\text{this operation is the identity)}}\\(a+b\alpha +c\alpha ^{2})+(d+e\alpha +f\alpha ^{2})&=(a+d)+(b+e)\alpha +(c+f)\alpha ^{2}\\(a+b\alpha +c\alpha ^{2})(d+e\alpha +f\alpha ^{2})&=(ad+bf+ce)+(ae+bd+bf+ce+cf)\alpha +(af+be+cd+cf)\alpha ^{2}\end{aligned}}}$$

ГФ(16)

Полином

$${\displaystyle X^{4}+X+1}$$

GF(2)2GF(16)выражениями

$${\displaystyle a+b\alpha +c\alpha ^{2}+d\alpha ^{3},}$$

a , b , c , d01GF(2)α

$${\displaystyle \alpha ^{4}=\alpha +1}$$

αGF(2)2GF(16)GF(16)GF(2)GF(2)

$${\displaystyle {\begin{aligned}(a+b\alpha +c\alpha ^{2}+d\alpha ^{3})+(e+f\alpha +g\alpha ^{2}+h\alpha ^{3})&=(a+e)+(b+f)\alpha +(c+g)\alpha ^{2}+(d+h)\alpha ^{3}\\(a+b\alpha +c\alpha ^{2}+d\alpha ^{3})(e+f\alpha +g\alpha ^{2}+h\alpha ^{3})&=(ae+bh+cg+df)+(af+be+bh+cg+df+ch+dg)\alpha \;+\\&\quad \;(ag+bf+ce+ch+dg+dh)\alpha ^{2}+(ah+bg+cf+de+dh)\alpha ^{3}\end{aligned}}}$$

Поле GF(16) имеет восемь примитивных элементов (элементов, у которых все ненулевые элементы GF(16) имеют целочисленную степень). Этими элементами являются четыре корня X ⁴ + X + 1 и их мультипликативные обратные . В частности, α является примитивным элементом, а примитивными элементами являются α ^m с m меньше и взаимно простыми с 15 (то есть 1, 2, 4, 7, 8, 11, 13, 14).

Мультипликативная структура

Множество ненулевых элементов в GF( q ) является абелевой группой при умножении порядка q – 1 . По теореме Лагранжа существует делитель k числа q – 1 такой, что x ^k = 1 для каждого ненулевого x в GF( q ) . Поскольку уравнение x ^k = 1 имеет не более k решений в любом поле, q – 1 является наименьшим возможным значением k . Структурная теорема конечных абелевых групп подразумевает, что эта мультипликативная группа является циклической , то есть все ненулевые элементы являются степенями одного элемента. В итоге:

Мультипликативная группа ненулевых элементов в GF( q ) является циклической, т. е. существует элемент a такой, что q – 1 ненулевых элементов GF( q ) являются a , a ² , ..., а ^{q -2} , а ^{q -1} знак равно 1 .

Такой элемент a называется примитивным элементом GF ( q ) . Если q = 2, 3 , примитивный элемент не уникален. Число примитивных элементов равно φ ( q − 1), где φ — функция Эйлера .

Из приведенного выше результата следует, что x ^q = x для каждого x в GF( q ) . Частный случай, когда q является простым, — это малая теорема Ферма .

Дискретный логарифм

Если a является примитивным элементом в GF( q ) , то для любого ненулевого элемента x в F существует уникальное целое число n с 0 ≤ n ≤ q − 2 такое, что

Икс знак равно а ^п .

Это целое число n называется дискретным логарифмом x по основанию a .

Хотя n можно вычислить очень быстро, например, с помощью ^{возведения} в степень возведением в квадрат , не существует известного эффективного алгоритма вычисления обратной операции — дискретного логарифма. Это использовалось в различных криптографических протоколах , подробности см. в разделе «Дискретный логарифм» .

Когда ненулевые элементы GF( q ) представлены своими дискретными логарифмами, умножение и деление выполняются легко, поскольку они сводятся к сложению и вычитанию по модулю q – 1 . ^{Однако сложение} сводится к вычислению дискретного логарифма a ^m + an . Личность

а ^м + а ^п = а ^п ( а ^{м - п} + 1)

позволяет решить эту проблему, построив таблицу дискретных логарифмов a ⁿ + 1 , называемую логарифмами Зеха , для n = 0, ..., q − 2 (дискретный логарифм нуля удобно определить как — ∞ ).

Логарифмы Зеха полезны для больших вычислений, таких как линейная алгебра над полями среднего размера, то есть полей, которые достаточно велики, чтобы сделать естественные алгоритмы неэффективными, но не слишком большими, поскольку необходимо предварительно вычислить таблицу того же размера. как порядок поля.

Корни единства

Каждый ненулевой элемент конечного поля является корнем из единицы , поскольку x ^{q −1} = 1 для каждого ненулевого элемента GF( q ) .

Если n — целое положительное число, примитивный корень n- й степени из единицы является решением уравнения x ⁿ = 1 , которое не является решением уравнения x ^m = 1 для любого положительного целого числа m < n . Если a является примитивным корнем n-й степени из единицы в поле F , то F содержит все n корней из единицы, то есть 1, a , a ² , ..., a ^{n −1} .

Поле GF( q ) содержит примитивный корень n- й степени из единицы тогда и только тогда, когда n является делителем q − 1 ; если n является делителем q − 1 , то число примитивных корней n -й степени из единицы в GF( q ) равно φ ( n ) ( функция Эйлера ). Число корней n -й степени из единицы в GF( q ) равно gcd( n , q − 1) .

В поле характеристики p каждый корень ( np ) -й степени из единицы является также корнем n- й степени из единицы. Отсюда следует, что примитивные ( np ) -ые корни из единицы никогда не существуют в поле характеристики p .

С другой стороны, если n взаимно просто с p , корни n -го кругового многочлена различны в каждом поле характеристики p , поскольку этот многочлен является делителем X ⁿ - 1 , дискриминант которого n ⁿ не равен нулю по модулю p . Отсюда следует, что n- й круговой многочлен разлагается над GF( p ) на различные неприводимые многочлены, которые имеют одну и ту же степень, скажем, d , и что GF( p ^d ) является наименьшим полем характеристики p , которое содержит n- е примитивные корни единство.

Пример: GF(64)

Поле GF(64) обладает несколькими интересными свойствами, которых нет у полей меньшего размера: оно имеет два подполя, ни одно из которых не содержится в другом; не все генераторы (элементы с минимальным полиномом 6- й степени над GF(2) ) являются примитивными элементами; и не все примитивные элементы сопряжены относительно группы Галуа .

Порядок этого поля равен 2 ⁶ , а делители 6 равны 1, 2, 3, 6 , подполя GF(64) — GF(2) , GF(2 ² ) = GF(4) , GF(2 ³ ) = GF(8) и сам GF(64) . Поскольку 2 и 3 взаимно просты , пересечение GF(4) и GF(8) в GF(64) является простым полем GF(2) .

Таким образом, объединение GF(4) и GF(8) содержит 10 элементов. Остальные 54 элемента GF(64) порождают GF(64) в том смысле, что никакое другое подполе не содержит ни одного из них. Отсюда следует, что они являются корнями неприводимых многочленов степени 6 над GF(2) . Это означает, что над GF(2) существует ровно 9 =54/6неприводимые монические полиномы 6-й степени . Это можно проверить, разложив X ⁶⁴ − X по GF(2) .

Элементы GF(64) являются примитивными корнями n- й степени из единицы для некоторого n , делящего 63 . Поскольку 3-й и 7-й корни из единицы принадлежат GF(4) и GF(8) соответственно, 54 генератора являются примитивными корнями n-й степени из единицы для некоторого n в {9, 21, 63} . Функция тотента Эйлера показывает, что существует 6 примитивных корней 9- й степени из единицы, 12 примитивных корней 21 -й степени из единицы и 36 примитивных корней 63 -й степени из единицы. Суммируя эти числа, снова получаем 54 элемента.

Факторизируя круговые полиномы по GF(2) , можно обнаружить, что:

• Шесть первоначальных девятых корней единицы являются корнями
  $${\displaystyle X^{6}+X^{3}+1,}$$
  и все сопряжены под действием группы Галуа.
• Двенадцать первоначальных 21 -х корней единства являются корнями
  $${\displaystyle (X^{6}+X^{4}+X^{2}+X+1)(X^{6}+X^{5}+X^{4}+X^{2}+1).}$$
  Под действием группы Галуа они образуют две орбиты. Поскольку эти два фактора взаимно обратны друг другу, корень и его (мультипликативный) обратный не принадлежат одной и той же орбите.
• 36 примитивных элементов GF (64) являются корнями
  $${\displaystyle (X^{6}+X^{4}+X^{3}+X+1)(X^{6}+X+1)(X^{6}+X^{5}+1)(X^{6}+X^{5}+X^{3}+X^{2}+1)(X^{6}+X^{5}+X^{2}+X+1)(X^{6}+X^{5}+X^{4}+X+1).}$$
  Они разделились на шесть орбит по шесть элементов каждая под действием группы Галуа.

Это показывает, что лучший выбор для построения GF(64) — это определить его как GF(2)[ X ] / ( X ⁶ + X + 1) . Фактически, этот генератор является примитивным элементом, а этот многочлен — неприводимым многочленом, который производит простейшее евклидово деление.

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

В этом разделе p — простое число, а q = pn ^— степень p .

В GF( q ) тождество ( x + y ) ^p = x ^p + y ^p подразумевает, что отображение

$${\displaystyle \varphi :x\mapsto x^{p}}$$

GF( p )линейным эндоморфизмомполевым автоморфизмом( q )GF( p )автоморфизмом ФробениусаФердинанда Георга Фробениуса

Обозначая через φ k ^{композицию} φ с самим собой k раз , имеем

$${\displaystyle \varphi ^{k}:x\mapsto x^{p^{k}}.}$$

φ ⁿ0 < k < nφ ^k

$${\displaystyle X^{p^{k}}-X}$$

p ^k

Других GF( p ) -автоморфизмов GF( q ) не существует . Другими словами, GF( pn ) имеет ровно n GF( p ) ^{-автоморфизмов} , которые являются

$${\displaystyle \mathrm {Id} =\varphi ^{0},\varphi ,\varphi ^{2},\ldots ,\varphi ^{n-1}.}$$

С точки зрения теории Галуа это означает, что GF( p ⁿ ) является расширением Галуа GF( p ) , которое имеет циклическую группу Галуа.

Тот факт, что отображение Фробениуса сюръективно, означает, что каждое конечное поле совершенно .

Полиномиальная факторизация

Если F — конечное поле, непостоянный монический многочлен с коэффициентами из F неприводим над F , если он не является продуктом двух непостоянных монических многочленов с коэффициентами из F.

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

Существуют эффективные алгоритмы проверки полиномиальной неприводимости и факторизации полиномов по конечному полю. Они являются ключевым шагом для факторизации многочленов по целым или рациональным числам . По крайней мере по этой причине каждая система компьютерной алгебры имеет функции для факторизации многочленов по конечным полям или, по крайней мере, по конечным простым полям.

Неприводимые многочлены заданной степени

Полином

$${\displaystyle X^{q}-X}$$

qq

Это означает, что если q = p ⁿ , то X ^q − X является произведением всех монических неприводимых многочленов над GF( p ) , степень которых делит n . Фактически, если P является неприводимым фактором над GF ( p ) X ^q − X , его степень делит n , поскольку его поле расщепления содержится в GF( p ⁿ ) . И наоборот, если P — неприводимый монический полином над GF( p ) степени d , делящий n , он определяет расширение поля степени d , которое содержится в GF( pn ⁾ , и все корни P принадлежат GF( pn ⁾ ) и являются корнями X ^q − X ; таким образом, P делит X ^q − X . Поскольку X ^q - X не имеет кратного множителя, он, таким образом, является произведением всех неприводимых монических полиномов, которые его делят.

Это свойство используется для вычисления произведения неприводимых множителей каждой степени полиномов над GF( p ) ; см. факторизацию различных степеней .

Число унитарных неприводимых многочленов заданной степени над конечным полем

Число N ( q , n ) монических неприводимых полиномов степени n над GF( q ) определяется выражением ^[4]

$${\displaystyle N(q,n)={\frac {1}{n}}\sum _{d\mid n}\mu (d)q^{n/d},}$$

цфункция МёбиусаX ^q − Xформулы обращения Мёбиуса

По приведенной выше формуле количество неприводимых (не обязательно монических) многочленов степени n над GF( q ) равно ( q − 1) N ( q , n ) .

Из точной формулы следует неравенство

$${\displaystyle N(q,n)\geq {\frac {1}{n}}\left(q^{n}-\sum _{\ell \mid n,\ \ell {\text{ prime}}}q^{n/\ell }\right);}$$

nqnnGF( q )

Приложения

В криптографии сложность задачи дискретного логарифмирования в конечных полях или эллиптических кривых лежит в основе нескольких широко используемых протоколов, таких как протокол Диффи-Хеллмана . Например, в 2014 году безопасное интернет-соединение с Википедией использовало протокол Диффи-Хеллмана на основе эллиптических кривых ( ECDHE ) в большом конечном поле. ^[5] В теории кодирования многие коды строятся как подпространства векторных пространств над конечными полями.

Конечные поля используются многими кодами исправления ошибок , такими как код исправления ошибок Рида-Соломона или код BCH . Конечное поле почти всегда имеет характеристику 2 , поскольку компьютерные данные хранятся в двоичном формате. Например, байт данных можно интерпретировать как элемент GF(2 ⁸ ) . Единственным исключением является штрих-код PDF417 , то есть GF(929) . Некоторые процессоры имеют специальные инструкции, которые могут быть полезны для конечных полей характеристики 2 , обычно это вариации продукта без переноса .

Конечные поля широко используются в теории чисел , так как многие задачи над целыми числами можно решить, сокращая их по модулю одного или нескольких простых чисел . Например, самые быстрые известные алгоритмы факторизации полиномов и линейной алгебры над полем рациональных чисел основаны на сокращении по модулю одного или нескольких простых чисел, а затем восстановлении решения с использованием китайской теоремы об остатках , подъема Гензеля или алгоритма LLL .

Точно так же многие теоретические проблемы теории чисел можно решить, рассматривая их сокращение по модулю некоторых или всех простых чисел. См., например, принцип Хассе . Многие недавние разработки алгебраической геометрии были мотивированы необходимостью расширить возможности этих модульных методов. Доказательство Уайлса Великой теоремы Ферма является примером глубокого результата, в котором задействовано множество математических инструментов, включая конечные поля.

Гипотезы Вейля касаются количества точек на алгебраических многообразиях над конечными полями, и теория имеет множество приложений, включая экспоненциальные оценки и оценки суммы характеров .

Конечные поля имеют широкое применение в комбинаторике , двумя хорошо известными примерами являются определение графов Пэли и связанная с ними конструкция матриц Адамара . В арифметической комбинаторике широко используются конечные поля ^[6] и модели конечных полей ^{[7] [8]} , например, в теореме Семереди об арифметических прогрессиях.

Расширения

Маленькая теорема Веддерберна

Тело — это обобщение поля. Тела не считаются коммутативными. Некоммутативных конечных тел не существует: маленькая теорема Веддерберна утверждает, что все конечные тела коммутативны и, следовательно, являются конечными полями. Этот результат справедлив, даже если мы ослабим аксиому ассоциативности до альтернативности , то есть все конечные альтернативные тела являются конечными полями по теореме Артина – Цорна . ^[9]

Алгебраическое замыкание

Конечное поле F не является алгебраически замкнутым: полином

$${\displaystyle f(T)=1+\prod _{\alpha \in F}(T-\alpha ),}$$

Ff  ( α ) = 1αF.

Пусть p является алгебраическим замыканием простого числа . Оно не только уникально с точностью до изоморфизма, как и все алгебраические замыкания, но, в отличие от общего случая, все его подполя фиксируются всеми его автоморфизмами, и это также алгебраическое замыкание всех конечных полей одной характеристики p . ${\displaystyle {\overline {\mathbb {F} }}_{p}}$ ${\displaystyle \mathbb {F} _{p}.}$

Это свойство возникает главным образом из-за того, что элементы являются в точности корнями и это определяет включение для Эти включения позволяют писать неформально ${\displaystyle \mathbb {F} _{p^{n}}}$ ${\displaystyle x^{p^{n}}-x,}$ ${\displaystyle \mathbb {\mathbb {F} } _{p^{n}}\subset \mathbb {F} _{p^{nm}}}$ ${\displaystyle m>1.}$

$${\displaystyle {\overline {\mathbb {F} }}_{p}=\bigcup _{n\geq 1}\mathbb {F} _{p^{n}}.}$$

направленный наборпрямым пределом ${\displaystyle {\overline {\mathbb {F} }}_{p},}$

Примитивные элементы в алгебраическом замыкании

Дан примитивный элемент then является примитивным элементом ${\displaystyle g_{mn}}$ ${\displaystyle \mathbb {F} _{q^{mn}},}$ ${\displaystyle g_{mn}^{m}}$ ${\displaystyle \mathbb {F} _{q^{n}}.}$

Для явных вычислений может быть полезно иметь последовательный выбор примитивных элементов для всех конечных полей; то есть выбрать примитивный элемент для того, чтобы всякий раз, когда есть примитивный элемент, уже выбранный для ${\displaystyle g_{n}}$ ${\displaystyle \mathbb {F} _{q^{n}}}$ ${\displaystyle n=mh,}$ ${\displaystyle g_{m}=g_{n}^{h},}$ ${\displaystyle g_{m}}$ ${\displaystyle \mathbb {F} _{q^{m}}.}$

Такая конструкция может быть получена с помощью полиномов Конвея .

Квазиалгебраическое замыкание

Хотя конечные поля не являются алгебраически замкнутыми, они квазиалгебраически замкнуты , что означает, что каждый однородный многочлен над конечным полем имеет нетривиальный нуль, компоненты которого находятся в поле, если число его переменных больше его степени. Это была гипотеза Артина и Диксона, доказанная Шевалле (см. теорему Шевалле – Предупреждения ).

Смотрите также

• Квазиконечное поле
• Поле с одним элементом
• Арифметика конечных полей
• Конечное кольцо
• Конечная группа
• Элементарная абелева группа
• Пространство Хэмминга

Примечания

1. Moore, EH (1896), «Дважды бесконечная система простых групп», в EH Moore; и другие. (ред.), Математические статьи, прочитанные на Международном математическом конгрессе, состоявшемся в связи со Всемирной Колумбийской выставкой , Macmillan & Co., стр. 208–242.
2. Это последнее обозначение было введено Э. Х. Муром в выступлении, сделанном в 1893 году на Международном математическом конгрессе, проходившем в Чикаго Mullen & Panario 2013, p. 10.
3. Рекомендуемые эллиптические кривые для государственного использования (PDF) , Национальный институт стандартов и технологий , июль 1999 г., стр. 3, заархивировано (PDF) из оригинала 19 июля 2008 г.
4. Джейкобсон 2009, §4.13
5. В этом можно убедиться, посмотрев информацию на странице, предоставленную браузером.
6. Шпарлинский, Игорь Э. (2013), «Аддитивная комбинаторика над конечными полями: новые результаты и приложения», Конечные поля и их приложения , DE GRUYTER, стр. 233–272, doi : 10.1515/9783110283600.233, ISBN 9783110283600
7. Грин, Бен (2005), «Модели конечного поля в аддитивной комбинаторике», Surveys in Combinatorics 2005 , Cambridge University Press, стр. 1–28, arXiv : math/0409420 , doi : 10.1017/cbo9780511734885.002, ISBN 9780511734885, S2CID  28297089
8. Вольф, Дж. (март 2015 г.). «Модели конечных полей в арифметической комбинаторике – десять лет спустя». Конечные поля и их приложения . 32 : 233–274. дои : 10.1016/j.ffa.2014.11.003 . hdl : 1983/d340f853-0584-49c8-a463-ea16ee51ce0f . ISSN  1071-5797.
9. Шульт, Эрнест Э. (2011). Точки и линии. Характеристика классической геометрии . Университеттекст. Берлин: Springer-Verlag . п. 123. ИСБН 978-3-642-15626-7. Збл  1213.51001.

Рекомендации

• WH Bussey (1905) «Таблицы полей Галуа для p ⁿ ≤ 169 », Бюллетень Американского математического общества 12 (1): 22–38, doi : 10.1090/S0002-9904-1905-01284-2
• WH Bussey (1910) «Таблицы полей Галуа порядка <1000», Бюллетень Американского математического общества 16 (4): 188–206, doi : 10.1090/S0002-9904-1910-01888-7
• Джейкобсон, Натан (2009) [1985], Основная алгебра I (второе изд.), Dover Publications, ISBN 978-0-486-47189-1
• Маллен, Гэри Л.; Муммерт, Карл (2007), Конечные поля и приложения I , Студенческая математическая библиотека (AMS), ISBN 978-0-8218-4418-2
• Маллен, Гэри Л.; Панарио, Дэниел (2013), Справочник по конечным полям , CRC Press, ISBN 978-1-4398-7378-6
• Лидл, Рудольф; Нидеррайтер, Харальд (1997), Конечные поля (2-е изд.), Cambridge University Press , ISBN 0-521-39231-4
• Скопин, А.И. (2001) [1994], «Поле Галуа», Математическая энциклопедия , EMS Press

Внешние ссылки

• Конечные поля в исследовании Wolfram.