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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Порядок конечного поля — это степень простого числа. Для каждой простой степени $q$ существуют поля порядка $q$ , и все они изоморфны. В этих полях каждый элемент удовлетворяет
$x^{q}=x,$ и многочлен $X д - X$ -факторы как
$X^{q}-X=\prod _{a\in F}(X-a).$

Отсюда следует, что $GF(p н)$ содержит подполе, изоморфное $GF(p м)$ тогда и только тогда, когда $m$ является делителем $n$ ; в этом случае это подполе уникально. В самом деле, полином $X п м - X$ делит $X п н - X$ тогда и только тогда, когда $m$ является делителем $n$ .

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

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

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

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

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

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

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

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

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

Над $GF(2)$ существует только один неприводимый полином степени $2$ : $X^{2}+X+1$ Следовательно, для $GF(4)$ конструкция предыдущего раздела должна включать этот полином, и $\mathrm {GF} (4)=\mathrm {GF} (2)[X]/(X^{2}+X+1).$

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

а 2 = 1 + а

,

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

Сложение

x + y

Умножение

х \cdot у

Отдел

х / у

$и$ $х$	$0$	$1$	$а$	$1 + а$
$0$	$0$	$1$	$а$	$1 + а$
$1$	$1$	$0$	$1 + а$	$а$
$а$	$а$	$1 + а$	$0$	$1$
$1 + а$	$1 + а$	$а$	$1$	$0$

$и$ $х$	$0$	$1$	$а$	$1 + а$
$0$	$0$	$0$	$0$	$0$
$1$	$0$	$1$	$а$	$1 + а$
$а$	$0$	$а$	$1 + а$	$1$
$1 + а$	$0$	$1 + а$	$1$	$а$

$и$ $х$	$1$	$а$	$1 + а$
$0$	$0$	$0$	$0$
$1$	$1$	$1 + а$	$а$
$а$	$а$	$1$	$1 + а$
$1 + а$	$1 + а$	$а$	$1$

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

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

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

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

Точнее, полином $X 2 - r$ неприводим над $GF(p)$ тогда и только тогда, когда $r$ является квадратичным невычетом по модулю $p$ (это почти определение квадратичного невычета). Есть $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠ p - 1/2 модулю ⁠$ квадратичные невычеты по $p$ . Например, $2$ является квадратичным невычетом для $p = 3, 5, 11, 13, ...$ , а $3$ является квадратичным невычетом для $p = 5, 7, 17, ...$ . Если $p \equiv 3 mod 4$ , то есть $p = 3, 7, 11, 19, ...$ , можно выбрать $-1 \equiv p - 1$ в качестве квадратичного невычета, что позволяет нам иметь очень простой неприводимый многочлен $X 2 + 1$ .

Выбрав квадратичный невычет $r$ , пусть $α$ — символический квадратный корень из $r$ , то есть символ, обладающий свойством $α 2 = r$ , точно так же, как комплексное число $i$ является символьным квадратным корнем из $-1$ . Тогда элементы $GF(p 2)$ — все линейные выражения $a+b\alpha ,$ с $a$ и $b$ в $GF(p)$ . Операции над $GF(p 2)$ определяются следующим образом (операции между элементами $GF(p),$ представленными латинскими буквами, являются операциями в $GF(p)$ ): ${\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)

Полином $X^{3}-X-1$ неприводима над $GF(2)$ и $GF(3)$ , т. е. неприводима по модулю $2$ и $3$ (чтобы показать это, достаточно показать, что она не имеет корня ни в $GF(2)$ , ни в $GF(3)$ ). Отсюда следует, что элементы $GF(8)$ и $GF(27)$ можно представить выражениями $a+b\alpha +c\alpha ^{2},$ где $a, b, c$ — элементы $GF(2)$ или $GF(3)$ (соответственно), а $α$ — такой символ, что $\alpha ^{3}=\alpha +1.$

Таким образом , сложение, аддитивное обратное и умножение $GF(8)$ и $GF(27)$ можно определить следующим образом; в следующих формулах операции между элементами $GF(2)$ или $GF(3)$ , представленными латинскими буквами, являются операциями в $GF(2)$ или $GF(3)$ соответственно: ${\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)

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

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

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

Мультипликативная группа ненулевых элементов в

GF(q)

является циклической, т.е. существует элемент

a

q такой, что

- 1

ненулевых элементов

GF(q)

являются

a, a 2, ..., а q -2, а q -1 = 1

.

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

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

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

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

х = а н

.

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

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

Когда ненулевые элементы $GF(q)$ представлены своими дискретными логарифмами, умножение и деление выполняются легко, поскольку они сводятся к сложению и вычитанию по модулю $q - 1$ . Однако сложение сводится к вычислению дискретного логарифма $числа. м + а н$ . Личность

а м + а н = а н (а м - п + 1)

позволяет решить эту задачу путем построения таблицы дискретных $логарифмов н + 1$ , называемые логарифмами Зеха , для $n = 0, ..., q - 2$ (удобно определить дискретный логарифм нуля как $-\infty$ ).

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

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

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

Если $n$ — целое положительное число, $примитивный корень n-$ й степени из единицы является решением уравнения $x н = 1,$ что не является решением уравнения $x м = 1$ для любого положительного целого числа $m < n$ . Если $a$ — $примитивный корень n-й$ степени из единицы в поле $F$ , то $F$ содержит все $n$ корней из единицы, то есть $1, a, a. 2, ..., а п -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 д)$ — наименьшее поле характеристики $p$ , содержащее $n$ -ные примитивные корни из единицы.

Пример: GF(64)

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

Порядок этого поля равен $26$ , а делители числа $6$ равны $1, 2, 3, 6$ , подполями $GF(64)$ являются $GF(2)$ , $GF(2 2) = GF(4)$ , $GF(2 3) = 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 64 - 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)$ , можно обнаружить, что:

Шесть первоначальных $девятых$ корней единицы являются корнями $X^{6}+X^{3}+1,$ и все сопряжены под действием группы Галуа.
Двенадцать первоначальных $21$ -х корней единства являются корнями $(X^{6}+X^{4}+X^{2}+X+1)(X^{6}+X^{5}+X^{4}+X^{2}+1).$ Под действием группы Галуа они образуют две орбиты. Поскольку эти два фактора взаимно обратны друг другу, корень и его (мультипликативный) обратный не принадлежат одной и той же орбите.
36 $GF$ примитивных элементов $(64)$ являются корнями $(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 6 + Х + 1)$ . Фактически, этот генератор является примитивным элементом, а этот многочлен — неприводимым многочленом, который производит простейшее евклидово деление.

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

В этом разделе $p$ — простое число, а $q = p н$ является степенью $p$ .

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

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

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

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

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

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

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

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

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

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

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

Это означает, что если $q = p н$ тогда $Х д - X$ — произведение всех монических неприводимых многочленов над $GF(p)$ , степень которых делит $n$ . В самом деле, если $P$ — неприводимый фактор над $GF(p)$ группы $X д - X$ , его степень делит $n$ , поскольку его поле расщепления содержится в $GF(p н)$ . И наоборот, если $P$ — неприводимый монический полином над $GF(p)$ степени $d,$ делящий $n$ , он определяет расширение поля степени $d$ , которое содержится в $GF(p н)$ , и все корни $P$ принадлежат $GF(p н)$ , и являются корнями $X д - Х$ ; таким образом, $P$ делит $X д - Х.$ Как $Х д - X$ не имеет кратного множителя, поэтому он является произведением всех неприводимых монических многочленов, которые его делят.

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

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

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

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

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

Приложения

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

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

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

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

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

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

Расширения

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

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

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

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

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

Это свойство обусловлено главным образом тем, что элементы $\mathbb {F} _{p^{n}}$ это именно корни $x^{p^{n}}-x,$ и это определяет включение $\mathbb {\mathbb {F} } _{p^{n}}\subset \mathbb {F} _{p^{nm}}$ для $m>1.$ Эти включения позволяют писать неформально. ${\overline {\mathbb {F} }}_{p}=\bigcup _{n\geq 1}\mathbb {F} _{p^{n}}.$ Формальная проверка этих обозначений обусловлена тем, что указанные выше включения полей образуют направленный набор полей; Его прямой предел ${\overline {\mathbb {F} }}_{p},$ что, таким образом, можно рассматривать как «направленный союз».

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

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

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

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

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

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

См. также

Примечания

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

Ссылки

WH Bussey (1905) «Таблицы поля Галуа для p ^н ≤ 169 », Бюллетень Американского математического общества 12(1): 22–38, два : 10.1090/S0002-9904-1905-01284-2
WH Bussey (1910) «Таблицы полей Галуа порядка <1000», Бюллетень Американского математического общества 16 (4): 188–206, два : 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.

[moore-1] Jump up to: ^а ^б Мур, Э.Х. (1896), «Дважды бесконечная система простых групп», у Э.Х. Мура; и др. (ред.), Математические статьи, прочитанные на Международном математическом конгрессе, состоявшемся в связи со Всемирной Колумбийской выставкой , 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 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]