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

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

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

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

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

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

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

Число элементов конечного поля называется его порядком или, иногда, его размером . Конечное поле порядка 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 .

Тождество (иногда называемое мечтой первокурсника ) истинно в поле характеристики p . Это следует из биномиальной теоремы , поскольку каждый биномиальный коэффициент разложения ( x + y ) ^p , за исключением первого и последнего, кратен p . $${\displaystyle (x+y)^{p}=x^{p}+y^{p}}$$

По малой теореме Ферма , если p — простое число и x принадлежит полю GF( p ), то x ^p = x . Это подразумевает равенство для многочленов над GF( p ) . В более общем смысле, каждый элемент в GF( p ⁿ ) удовлетворяет полиномиальному уравнению x ^{p n} − x = 0 . $${\displaystyle X^{p}-X=\prod _{a\in \mathrm {GF} (p)}(X-a)}$$

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

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

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

Пусть q = p ⁿ — степень простого числа , а F — поле расщепления многочлена над простым полем GF( p ) . Это означает, что F — конечное поле наименьшего порядка, в котором P имеет q различных корней ( формальная производная P равна P ′ = −1 , что подразумевает, что gcd( P , P ′ ) = 1 , что в общем случае означает, что поле расщепления является сепарабельным расширением исходного). Вышеприведенное тождество показывает, что сумма и произведение двух корней P являются корнями P , а также мультипликативным обратным корнем P . Другими словами, корни P образуют поле порядка q , которое равно F в силу минимальности поля расщепления. $${\displaystyle P=X^{q}-X}$$

Единственность с точностью до изоморфизма полей расщепления подразумевает, таким образом, что все поля порядка 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( p ⁿ ) содержит подполе, изоморфное GF( p ^m ) , тогда и только тогда, когда m является делителем n ; в этом случае это подполе уникально. Фактически, многочлен X ^{p m} − X делит X ^{p n} − X тогда и только тогда, когда m является делителем n .

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

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

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

Более конкретно, элементы 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 многочлен вида , который делает необходимые евклидовы деления очень эффективными. Однако для некоторых полей, обычно в характеристике 2 , неприводимые многочлены вида X ⁿ + aX + b могут не существовать. В характеристике 2 , если многочлен X ⁿ + X + 1 приводим, рекомендуется выбрать X ⁿ + X ^k + 1 с наименьшим возможным k , которое делает многочлен неприводимым. Если все эти трехчлены приводимы, выбирают «пентаномиалы» X ⁿ + X ^a + X ^b + X ^c + 1 , поскольку многочлены степени больше 1 , с четным числом членов, никогда не являются неприводимыми в характеристике 2 , имея 1 в качестве корня. ^[3] $${\displaystyle X^{n}+aX+b,}$$

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

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

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

Наименьшее не простое поле — это поле с четырьмя элементами, которое обычно обозначается 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 : Поэтому для GF(4) конструкция предыдущего раздела должна включать этот многочлен, и $${\displaystyle X^{2}+X+1}$$ $${\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 ₃ .

Отображение представляет собой нетривиальный автоморфизм поля, называемый автоморфизмом Фробениуса, который переводит α во второй корень 1 + α вышеупомянутого неприводимого многочлена X ² + X + 1 . $${\displaystyle \varphi :x\mapsto x^{2}}$$

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

Для применения вышеприведенной общей конструкции конечных полей в случае GF( p ² ) нужно найти неприводимый многочлен степени 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 ² ) являются всеми линейными выражениями с a и b в GF( p ) . Операции над GF( p ² ) определяются следующим образом (операции между элементами GF( p ), представленными латинскими буквами, являются операциями в GF( p ) ): $${\displaystyle a+b\alpha ,}$$ $${\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)

Многочлен неприводим над GF(2) и GF(3) , то есть он неприводим по модулю 2 и 3 (чтобы показать это, достаточно показать, что он не имеет корня ни в GF(2) , ни в GF(3) ). Отсюда следует, что элементы GF(8) и GF(27) могут быть представлены выражениями , где a , b , c являются элементами GF(2) или GF(3) (соответственно), а α является символом таким, что $${\displaystyle X^{3}-X-1}$$ $${\displaystyle a+b\alpha +c\alpha ^{2},}$$ $${\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)

Многочлен неприводим над GF(2) , то есть он неприводим по модулю 2 . Отсюда следует, что элементы GF(16) могут быть представлены выражениями , где a , b , c , d равны либо 0 , либо 1 (элементы GF(2) ), а α — символ такой, что (то есть α определяется как корень данного неприводимого многочлена). Поскольку характеристика GF(2) равна 2 , каждый элемент является его аддитивным обратным в GF(16) . Сложение и умножение в GF(16) могут быть определены следующим образом; в следующих формулах операции между элементами GF(2) , представленные латинскими буквами, являются операциями в GF(2) . $${\displaystyle X^{4}+X+1}$$ $${\displaystyle a+b\alpha +c\alpha ^{2}+d\alpha ^{3},}$$ $${\displaystyle \alpha ^{4}=\alpha +1}$$ $${\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 ² , ..., a ^{q −2} , a ^{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 + a ⁿ . Тождество

а ^м + н = н ( а ^{м − н} + ^{1 )}

позволяет решить эту задачу, построив таблицу дискретных логарифмов числа n ⁺ 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 , a2 ^, ..., an ^{− 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 -е примитивные корни из единицы.

Пример: ГФ(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) , находим, что:

• Шесть примитивных корней 9- й степени из единицы являются корнями и все сопряжены под действием группы Галуа. $${\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 = p ⁿ — степень числа p .

В GF( q ) тождество ( x + y ) ^p = x ^p + y ^p подразумевает, что отображение является GF( p ) - линейным эндоморфизмом и полевым автоморфизмом GF ( q ) , который фиксирует каждый элемент подполя GF( p ) . Это называется автоморфизмом Фробениуса в честь Фердинанда Георга Фробениуса . $${\displaystyle \varphi :x\mapsto x^{p}}$$

Обозначая через φ ^k композицию φ с самим собой k раз , имеем В предыдущем разделе было показано, что φ ⁿ является тождеством. При 0 < k < n автоморфизм φ ^k не является тождеством, так как в противном случае многочлен имел бы более p ^k корней . $${\displaystyle \varphi ^{k}:x\mapsto x^{p^{k}}.}$$ $${\displaystyle X^{p^{k}}-X}$$

Других GF( p ) -автоморфизмов GF( q ) нет . Другими словами, GF( p ⁿ ) имеет ровно n GF( p ) -автоморфизмов, которые являются $${\displaystyle \mathrm {Id} =\varphi ^{0},\varphi ,\varphi ^{2},\ldots ,\varphi ^{n-1}.}$$

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

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

Факторизация полинома

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

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

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

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

Многочлен раскладывается на линейные множители над полем порядка q . Точнее, этот многочлен является произведением всех монических многочленов первой степени над полем порядка q . $${\displaystyle X^{q}-X}$$

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

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

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

Число N ( q , n ) монических неприводимых многочленов степени n над GF( q ) определяется выражением ^[4], где μ — функция Мёбиуса . Эта формула является непосредственным следствием свойства X ^q − X выше и формулы обращения Мёбиуса . $${\displaystyle N(q,n)={\frac {1}{n}}\sum _{d\mid n}\mu (d)q^{n/d},}$$

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

Точная формула подразумевает, что неравенство является точным тогда и только тогда, когда n является степенью некоторого простого числа. Для каждого q и каждого n правая часть положительна, поэтому существует по крайней мере один неприводимый многочлен степени n над GF( q ) . $${\displaystyle N(q,n)\geq {\frac {1}{n}}\left(q^{n}-\sum _{\ell \mid n,\ \ell {\text{ prime}}}q^{n/\ell }\right);}$$

Приложения

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

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

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

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

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

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

Расширения

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

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

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

Конечное поле F не является алгебраически замкнутым: многочлен не имеет корней в F , поскольку f  ( α ) = 1 для всех α из F . $${\displaystyle f(T)=1+\prod _{\alpha \in F}(T-\alpha ),}$$

Пусть задано простое число 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},}$

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

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