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

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

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

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

Свойства [ править ]

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

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

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

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

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

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

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

идентичность

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

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

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

{\ Displaystyle X ^ {p} -X = \ prod _ {a \ in {\ rm {GF}} (p)} (Xa)}

для полиномов над $GF (p)$ . В более общем смысле, каждый элемент в $GF (p n)$ удовлетворяет полиномиальному уравнению $x p n - x = 0$ .

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

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

Существование и уникальность [ править ]

Пусть $q = p n$ - степень простого числа , а $F$ - поле расщепления многочлена

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

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

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

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

Порядок конечного поля - это степень простого числа. Для любой степени

q

простого числа существуют поля порядка

q

, и все они изоморфны. В этих полях каждый элемент удовлетворяет

{\ Displaystyle х ^ {q} = х,}

а многочлен

X q - X

множится как

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

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

Явное построение [ править ]

Непростые поля [ править ]

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

{\ Displaystyle {\ rm {GF}} (q) = {\ rm {GF}} (p) [X] / (P)}

кольца многочленов $GF (p) [X]$ идеалом, порожденным $P,$ является полем порядка $q$ .

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

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

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

которые делают необходимые евклидовы деления очень эффективными. Однако для некоторых полей, обычно в характеристике $2$ , неприводимые полиномы вида $X n + aX + b$ могут не существовать. В характеристике $2$ , если многочлен $X n + X + 1$ приводим, рекомендуется выбирать $X n + X k + 1$ с наименьшим возможным $k,$ что делает многочлен неприводимым. Если все эти трехчлены приводимы, выбираются «пятичлены» $X n + X a + X b + X c + 1$ , поскольку многочлены степени выше $1$ с четным числом членов никогда не являются неприводимыми в характеристике $2$ , имеющей $1$ в качестве корня. ^[3]

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

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

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

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

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

Следовательно, для $GF (4)$ конструкция предыдущего раздела должна включать этот многочлен, и

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

Если обозначить $α$ корнем этого многочлена в $GF (4)$ , то таблицы операций в $GF (4)$ будут следующими. Таблица для вычитания отсутствует, потому что вычитание идентично сложению, как и в случае с каждым полем характеристики 2. В третьей таблице для деления $x$ на $y$ , $x$ должен быть прочитан слева, а $y -$ на поле. верх.

Добавление

Умножение

Разделение

+	$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$	$α$

$х / у$	$0$	$1$	$α$	$1 + α$
$0$	$-$	$0$	$0$	$0$
$1$	$-$	$1$	$1 + α$	$α$
$α$	$-$	$α$	$1$	$1 + α$
$1 + α$	$-$	$1 + α$	$α$	$1$

GF ( p ² ) для нечетного простого числа p [ править ]

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

Более точно, многочлен $X 2 - r$ неприводим над $GF (p)$ тогда и только тогда, когда $r$ - квадратичный невычет по модулю $p$ (это почти определение квадратичного невычета). Есть $п - 1 / 2$ квадратичные невычеты по модулю $p$ . Так , например, $2$ является квадратичным невычетом для $р = 3, 5, 11, 13, ...$ , и $3$ является квадратичным невычетом для $р = 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)$ будут все линейные выражения

{\ displaystyle 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}}

GF (8) и GF (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$

\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}}

GF (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 (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 2, ..., a q -2, a q -1 = 1

.

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

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

Дискретный логарифм [ править ]

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

х = а п

.

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

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

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

a m + a n = a n (a m - n + 1)

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

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

Корни единства [ править ]

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

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

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

Пример: GF (64) [ править ]

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

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

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),

Под действием группы Галуа они разбиваются на 6 орбит из 6 элементов.

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

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

В этом разделе $p$ - простое число, а $q = p n$ - степень $p$ .

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

\varphi :x\mapsto x^{p}

является $GF (р)$ - линейный эндоморфизм и полевой автоморфизм из $GF (д)$ , который фиксирует каждый элемент подполя $GF (р)$ . Он называется автоморфизмом Фробениуса в честь Фердинанда Георга Фробениуса .

Обозначая через $ф К$ в композиции из $ф$ с собой $K$ раз, мы имеем

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

В предыдущем разделе было показано, что $φ n$ является тождественным. При $0 < k < n$ автоморфизм $φ k$ не является тождественным, как в противном случае многочлен

X^{p^{k}}-X

будет иметь более $p k$ корней.

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

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

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

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

Полиномиальная факторизация [ править ]

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

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

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

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

Полином

X^{q}-X

разлагается на линейные множители над полем порядка $q$ . Точнее, этот многочлен является произведением всех монических многочленов первой степени над полем порядка $q$ .

Отсюда следует, что если $q = p n,$ то $X q - X$ является произведением всех монических неприводимых многочленов над $GF (p)$ , степень которых делит $n$ . Фактически, если $P$ - неприводимый фактор над $GF (p)$ в $X q - X$ , его степень делит $n$ , так как его поле расщепления содержится в $GF (p n)$ . Наоборот, если $P$ - неприводимый монический многочлен над $GF (p)$ степени $d,$ делящей $n$ , он определяет расширение поля степени $d$ , которое содержится в $GF (p n)$ , а все корни $P$ принадлежат $GF (p n)$ и являются корнями $X q - X$ ; Таким образом , $Р$ делит $Й д - Х$ . Поскольку $X q - 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)$ равна

N(q,n)\geq {\frac {1}{n}}\left(q^{n}-\sum _{p\mid n,\ p{\text{ prime}}}q^{n/p}\right).

Легко вывести, что для каждого $q$ и любого $n$ существует хотя бы один неприводимый многочлен степени $n$ над $GF (q)$ . Эта нижняя оценка точна при $q = n = 2$ .

Приложения [ править ]

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

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

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

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

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

Расширения [ править ]

Алгебраическое замыкание [ править ]

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

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

не имеет корней в $F$ , так как $F (α) = 1$ для всех $& alpha$ ; в $F$ .

Фиксируем алгебраическое замыкание в . Отображение, переводящее каждый $x$ в $x$ $q$ , называется автоморфизмом Фробениуса $q-$ й степени . Подполе, фиксируемое $n-$ й итерацией, представляет собой набор нулей многочлена $x$ $q$ $n$ $-$ $x$ , который имеет различные корни, поскольку его производная в равна $-1$ , которая никогда не равна нулю. Следовательно, это подполе имеет $q$ $n$ элементов, поэтому это уникальная копия in . Каждое конечное расширение in есть это ${\overline {\mathbb {F} }}_{q}$ $\mathbb {F} _{q}$ $\varphi _{q}\colon {\overline {\mathbb {F} }}_{q}\to {\overline {\mathbb {F} }}_{q}$ ${\overline {\mathbb {F} }}_{q}$ $\varphi _{q}$ $\mathbb {F} _{q}[x]$ $\mathbb {F} _{q^{n}}$ ${\overline {\mathbb {F} }}_{q}$ $\mathbb {F} _{q}$ ${\overline {\mathbb {F} }}_{q}$ $\mathbb {F} _{q^{n}}$ для некоторых $п$ , так что

{\overline {\mathbb {F} }}_{q}=\bigcup _{n\geq 1}\mathbb {F} _{q^{n}}.

Абсолютная группа Галуа из является проконечной группой $\mathbb {F} _{q}$

\operatorname {Gal} ({\overline {\mathbb {F} }}_{q}/\mathbb {F} _{q})\simeq \varprojlim _{n}\operatorname {Gal} ({\overline {\mathbb {F} }}_{q^{n}}/\mathbb {F} _{q})\simeq \varprojlim _{n}(\mathbf {Z} /n\mathbf {Z} )={\widehat {\mathbf {Z} }}.

Как и любая бесконечная группа Галуа, она может быть снабжена топологией Крулля , и тогда только что приведенные изоморфизмы являются изоморфизмами топологических групп . Изображение в группе - это генератор $1$ , поэтому соответствует . Отсюда следует, что имеет бесконечный порядок и порождает плотную подгруппу , а не всю группу, потому что элемент имеет бесконечный порядок и порождает плотную подгруппу. Один говорит, что является топологическим генератором группы . $\operatorname {Gal} ({\overline {\mathbb {F} }}_{q}/\mathbb {F} _{q})$ $\varphi _{q}$ $\operatorname {Gal} ({\overline {\mathbb {F} }}_{q^{n}}/\mathbb {F} _{q})\simeq \mathbf {Z} /n\mathbf {Z}$ $\varphi _{q}$ $1\in {\widehat {\mathbf {Z} }}$ $\varphi _{q}$ $\operatorname {Gal} ({\overline {\mathbb {F} }}_{q}/\mathbb {F} _{q})$ $1\in {\widehat {\mathbf {Z} }}$ $\mathbf {Z} \subsetneqq {\widehat {\mathbf {Z} }}.$ $\varphi _{q}$ $\operatorname {Gal} ({\overline {\mathbb {F} }}_{q}/\mathbb {F} _{q})$

Квазиалгебраическое замыкание [ править ]

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

Маленькая теорема Веддерберна [ править ]

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

См. Также [ править ]

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

Примечания [ править ]

^ a b Мур, Э. Х. (1896 г.), «Бесконечная дважды система простых групп», в Э. Х. Мур; и другие. (ред.), Математические статьи, прочитанные на Международном математическом конгрессе, проводимом в связи с всемирной Колумбийской выставкой , Macmillan & Co., стр. 208–242
^ Это последнее обозначение было введено Э. Х. Муром в выступлении, сделанном в 1893 году на Международном математическом конгрессе в Чикаго Mullen & Panario 2013 , стр. 10.
^ Рекомендуемые эллиптические кривые для государственного использования (PDF) , Национальный институт стандартов и технологий , июль 1999 г., стр. 3
^ Якобсон 2009 , §4.13
^ Это можно проверить, просмотрев информацию на странице, предоставленную браузером.
^ Шпарлинский, Игорь Евгеньевич (2013), «Добавка Комбинаторика над конечными полями: новые результаты и приложения», Конечные поля и их приложения , DE Gruyter, 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
^ Вольф, Дж. (Март 2015 г.). «Конечнополевые модели в арифметической комбинаторике - десять лет спустя» . Конечные поля и их приложения . 32 : 233–274. DOI : 10.1016 / j.ffa.2014.11.003 . ISSN 1071-5797 .
^ Шулт, Эрнест Э. (2011). Точки и линии. Характеризуя классические геометрии . Universitext. Берлин: Springer-Verlag . п. 123. ISBN 978-3-642-15626-7. Zbl 1213.51001 .

Ссылки [ править ]

WH Bussey (1905) «Таблицы поля Галуа для p ⁿ ≤ 169», Бюллетень Американского математического общества 12 (1): 22–38, DOI : 10.1090 / S0002-9904-1905-01284-2
WH Басси (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
Mullen, Gary L .; Маммерт, Карл (2007), Конечные поля и приложения I , Студенческая математическая библиотека (AMS), ISBN 978-0-8218-4418-2
Mullen, Gary L .; Панарио, Даниэль (2013), Справочник по конечным полям , CRC Press, ISBN 978-1-4398-7378-6
Лидл, Рудольф; Нидеррайтер, Харальд (1997), Конечные поля (2-е изд.), Cambridge University Press , ISBN 0-521-39231-4
Скопин, AI (2001) [1994], "Поле Галуа" , Энциклопедия математики , EMS Press

Внешние ссылки [ править ]

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

[moore-1] Мур, Э. Х. (1896 г.), «Бесконечная дважды система простых групп», в Э. Х. Мур; и другие. (ред.), Математические статьи, прочитанные на Международном математическом конгрессе, проводимом в связи с всемирной Колумбийской выставкой , Macmillan & Co., стр. 208–242

[2] Это последнее обозначение было введено Э. Х. Муром в выступлении, сделанном в 1893 году на Международном математическом конгрессе в Чикаго Mullen & Panario 2013 , стр. 10.

[3] Рекомендуемые эллиптические кривые для государственного использования (PDF) , Национальный институт стандартов и технологий , июль 1999 г., стр. 3

[4] Якобсон 2009 , §4.13

[5] Это можно проверить, просмотрев информацию на странице, предоставленную браузером.

[6] Шпарлинский, Игорь Евгеньевич (2013), «Добавка Комбинаторика над конечными полями: новые результаты и приложения», Конечные поля и их приложения , DE Gruyter, 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

[8] Вольф, Дж. (Март 2015 г.). «Конечнополевые модели в арифметической комбинаторике - десять лет спустя» . Конечные поля и их приложения . 32 : 233–274. DOI : 10.1016 / j.ffa.2014.11.003 . ISSN 1071-5797 .

[9] Шулт, Эрнест Э. (2011). Точки и линии. Характеризуя классические геометрии . Universitext. Берлин: Springer-Verlag . п. 123. ISBN 978-3-642-15626-7. Zbl 1213.51001 .

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

Свойства [ править ]

Существование и уникальность [ править ]

Явное построение [ править ]

Непростые поля [ править ]

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

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

GF (8) и GF (27) [ править ]

GF (16) [ править ]

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

Дискретный логарифм [ править ]

Корни единства [ править ]

Пример: GF (64) [ править ]

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

Полиномиальная факторизация [ править ]

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

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

Приложения [ править ]

Расширения [ править ]

Алгебраическое замыкание [ править ]

Квазиалгебраическое замыкание [ править ]

Маленькая теорема Веддерберна [ править ]

См. Также [ править ]

Примечания [ править ]

Ссылки [ править ]

Внешние ссылки [ править ]

GF ( p ² ) для нечетного простого числа p [ править ]