Галуа Ч.2: Кольца и поля. Конечные поля вида GF(p^n) / Хабр

Это вторая часть из серии статей про путь от основ абстрактной алгебры до изоморфизма конечных полей:

Галуа Ч.1: Классы вычетов и группы.
Галуа Ч.2: Кольца и поля. Конечные поля вида .
Галуа Ч.3: Конечные поля вида . Изоморфизм конечных полей.

Структура статьи

Кольца и поля
Конечные поля
Конечное поле
Конечное поле
Конечное поле

Скрытый текст

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

Кольца и поля

Рассмотрим две новые алгебраические структуры - кольца и поля, которые также активно применяются в криптографии.

Кольцом называется множество с заданными на нем операциями сложения и умножения, обладающее следующими свойствами:

множество является абелевой группой по сложению
операция умножения ассоциативна, т.е. для любых трех элементов $x, y, z \in R$ выполняется равенство: $x \cdot (y \cdot z) = (x \cdot y) \cdot z$
операция умножения связана с операцией сложения свойством дистрибутивности: для любых $x, y, z \in R$

$x \cdot (y + z) = x \cdot y + x \cdot z$ $(x + y) \cdot z = x \cdot z + y \cdot z$

Скрытый текст

Из определения видно, что понятие кольца опирается на понятие группы: каждый новый объект абстрактной алгебры строится на основе предыдущих, как из кирпичиков. Поэтому важно последовательно разобраться в особенностях каждой из структур.

Скрытый текст

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

Из свойства дистрибутивности умножения относительно сложения следует, что для любого элемента $x \in R$ :

$x \cdot 0 = 0 = 0 \cdot x$

Скрытый текст

Это может вас несколько запутать, поэтому добавлю небольшое пояснение. Кольцо является абелевой группой по сложению, следовательно . Тогда из свойства дистрибутивности мы получаем $x \cdot 0 = x \cdot (0 + 0) = x \cdot 0 + x \cdot 0$ . Добавяя к этому выражению слева и справа противоположный элемент по сложению $-(x \cdot 0)$ , получим $0 = x \cdot 0$ . И так далее.

Элемент $x \in R$ называется левым делителем нуля, если существует ненулевой элемент $y \in R$ такой, что $x \cdot y = 0$ , и - правым делителем нуля, если $y \cdot x = 0$ . Элемент, который одновременно является и левым, и правым делителем нуля, называется делителем нуля. Ноль называется тривиальным делителем нуля, а остальные делители нуля, если существуют, - нетривиальными.

Кольцо, в котором нет нетривиальных делителей нуля, называется областью целостности.

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

Пусть - кольцо с единицей. Элемент $x \in R$ называется обратимым, если существует элемент $y \in R$ такой, что:

$x \cdot y = 1 = y \cdot x$

Элемент называется обратным по умножению (мультипликативным обратным) к элементу и обозначается $x^{-1}$ . Множество обратимых элементов кольца образует мультипликативную группу кольца и обозначается .

Полем называется коммутативное кольцо с единицей, множество ненулевых элементов которого является абелевой группой по умножению. Эта группа называется мультипликативной группой поля. Т.е. поле - коммутативное кольцо с единицей, все ненулевые элементы которого обратимы. Или, иначе говоря, поле - это множество, образующее абелеву группу по сложению с нейтральный элементом 0, и все ненулевые элементы которого образуют абелеву группу по умножению с нейтральным элементом 1, при этом операции сложения и умножения связаны свойством дистрибутивности.

Скрытый текст

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

Скрытый текст

Пример. Привычные нам множества $\mathbb{Q}$ рациональных и $\mathbb{R}$ вещественных чисел являются полями.

Подмножество поля , замкнутое относительно обеих операций и само являющееся полем, называется подполем поля и обозначается $F \subseteq Q$ .

Поле, состоящее из конечного числа элементов, называется конечным полем (или полем Галуа) и обозначается , где q - порядок поля. Порядком поля называется число его элементов. Порядок поля всегда является степенью простого числа, т.е. , где - простое число, - натуральное. Число называется характеристикой поля.

Характеристика поля - наименьшее натуральное число такое, что для любого элемента $x \in GF(q)$ выполняется равенство:

$\underbrace{x + x + \dots + x}_{n} = n \cdot x = 0$

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

Скрытый текст

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

$n \cdot 1 = (ab) \cdot 1 = (a \cdot 1) (b \cdot 1) = 0$

При этом ни $a \cdot 1$ , ни $b \cdot 1$ не равны нулю вследствие минимальности характеристики. Получаются мы имеем делители нуля, что противоречит определению поля. Следовательно, характеристика поля либо равна нулю, либо является простым числом.

Мультипликативная группа конечного поля порядка обозначается и имеет порядок (так как ноль не является элементом мультипликативной группы поля).

Два поля и называются изоморфными, если существует биекция (взаимно однозначное соответствие) $\varphi: F_1 \rightarrow F_2$ , сохраняющая обе операции, т.е. для любых $x, y \in F_1$ выполняется:

$\varphi(x + y) = \varphi(x) + \varphi(y)$ $\varphi(x \cdot y) = \varphi(x) \cdot \varphi(y)$

Функция $\varphi: F_1 \rightarrow F_2$ и обратная к ней функция $\varphi^{-1}: F_2 \rightarrow F_1$ называются изоморфизмами (таккак функция $\varphi$ - биекция, то обратная к ней функция всегда существует).

Свойства изоморфизма:

$\varphi(0_{F_1}) = 0_{F_2}$ $\varphi(1_{F_1}) = 1_{F_2}$

, где $0_{F_1}, 1_{F_1} \in F_1$ ; $0_{F_2}, 1_{F_2} \in F_2$

$\varphi(x^{n}) = \varphi(x)^n$

, для любого $x \in F_1$

Теорема (О существовании и единственности конечных полей). Существует единственное конечное поле порядка с точностью до изоморфизма.

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

Скрытый текст

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

Пусть - поле. Рассмотрим кольцо, элементами которого являются многочлены вида

$p(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_x x^n + \dots$

с коэффициентами из поля . Такие многочлены называются многочленами над полем .

Скрытый текст

До этого момента многие рассматриваемые объекты еще можно было мысленно ассоциировать с обычными числами. Дальше мы будем работать с многочленами, поэтому интуитивные аналогии начнут уступать место строгим определениям и теоремам.

Максимальное число такое, что коэффициент $a_d \neq 0$ , называется степенью многочлена и обозначается $\deg p(x)$ . Этот коэффициент называется старшим коэффициентом многочлена. Если старший коэффициент многочлена , то многочлен называетсянормированным. Количество ненулевых коэффициентов многочлена будем называть его весом.

Многочлен нулевой степени будем называть константой. Нулевым многочленом будем называть многочлен, все коэффициенты которого равны нулю. Будем считать степень нулевого многочлена неопределенной.

Множество всех возможных многочленов над полем F образует кольцо многочленов над полем F и обозначается .

Операции сложения и умножения в кольце многочленов осуществляются по тем же правилам, по которым мы привыкли складывать или перемножать многочлены в поле действительных чисел.

Пусть $p_1(x) = \sum_{i=0}^{n} a_i x^i$ и $p_2(x) = \sum_{i = 0}^{n} b_i x^i$ - многочлены степени не выше .

Тогда сумма многочленов равна

$p_1(x) + p_2(x) = \sum_{i = 0}^{n} (a_i + b_i) x^i$

Степень суммы многочленов не больше максимальной из их степеней:

$\deg(p_1(x) + p_2(x)) \leq \max(\deg p_1(x), \deg p_2(x))$

Произведение многочленов равно

$p_1(x) \cdot p_2(x) = \sum_{i=0}^{2n} \Big( \sum_{j + k = i} a_j b_k \Big) x^i$

Степень произведения многочленов равна сумме их степеней:

$\deg(p_1(x) \cdot p_2(x)) = \deg p_1(x) + \deg p_2(x)$

Нулем кольца многочленов является нулевой многочлен 0, он является нейтральным элементом по сложению. Единицей кольца многочленов является константа 1, она является нейтральным элементом по умножению.

Кольцо многочленов не является полем, т.к. не для каждого многочлена существует обратный к нему элемент кольца.

Конечные поля

Рассмотрим подробнее структуру конечных полей на примерах. Именно конечные поля активно используются в криптографии.

Как мы уже говорили, порядок конечного поля всегда является степенью простого числа, т.е. , где - простое, - натуральное. Рассмотрим самый простой случай: конечное поле , где p - простое число.

Конечные поля могут быть заданы разными способами. Однако любое конечное поле простого порядка может быть представлено как кольцо классов вычетов (т.е. любое поле изоморфно кольцу классов вычетов $\mathbb{Z}/p\mathbb{Z}$ , иначе говоря, если - простое число, то кольцо классов вычетов $\mathbb{Z}/p\mathbb{Z}$ является полем классов вычетов). Далее мы будем использовать именно такое представление.

Элементами поля являются целые числа из множества $\{ 0, 1, \dots, p - 1 \}$ : наименьшие неотрицательные представители каждого класса вычетов по модулю простого числа . Арифметические операции в этом поле осуществляются с приведением результата по модулю .

Поле , где - простое, - натуральное число, называется расширением поля . Аналогично поле , где - натуральное число, является расширением поля и т.д. Расширение какого-то поля само также является полем.

В криптографии активно используются поля характеристики , так как арифметические операции в таких полях могут быть эффективно реализованы. Рассмотрим структуру конечных полей на примере конечных полей вида $GF((2^n)^m), n, m \in \mathbb{N}$ .

Скрытый текст

Почитать про оптимизацию вычислений в полях характеристики 2 можно в K. M. Greenan, E. L. Miller and T. J. E. Schwarz S.J., "Optimizing Galois Field Arithmetic for Diverse Processor Architectures and Applications,"2008 IEEE International Symposium on Modeling, Analysis and Simulation of Computers and Telecommunication Systems, Baltimore, MD, USA, 2008, pp. 1-10.

Конечное поле GF(2)

- это конечное поле, элементами которого являются два числа $\{ 0, 1 \}$ : наименьшие неотрицательные представители классов вычетов по модулю числа . Сложение и умножение осуществляется с приведением результата по модулю . Порядок поля . Также и характеристика поля :

$\underbrace{1 + 1}_2 = 2 \equiv 0 \: (\textrm{mod} \: 2)$

Так как $1 + 1 \equiv 0 \: (\textrm{mod} \: 2)$ (т.е. $1 \equiv -1 \: (\textrm{mod} \: 2)$ ), то в сложение и вычитание - одна и та же операция.

Правила сложения у умножения для этого конечного поля показаны в таблице 1. Обратим внимание, что сложение соответствует логической операции XOR (исключающее "ИЛИ"), а умножение - логической операции AND ("И").

Правила сложения и умножения в конечном поле : а - таблица сложения; б - таблица умножения.

Конечное поле GF(p^n)

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

$GF(p^n) = \{ a_{n-1} x^{n-1} + \dots + a_1 x + a_0 \: | \: a_i \in GF(p), i = 0, \dots, n-1 \}$

Таких многочленов имеется в точности : коэффициентов, которые могут принимать одно из значений (по формуле числа размещений с повторениями получает ).

Чтобы получить из кольца многочленов конечное поле степени , необходимо взять остатки от деления всех многочленов этого кольца на неприводимый многочлен степени над полем . Полученное таким образом поле обозначают $GF(p)[x] / \langle f(x) \rangle$ . Неприводимый многочлен над полем - это многочлен c коэффициентами в , который не может быть представлены в виде произведения двух и более многочленов положительной степени (не констант). Для любого конечного поля существует хотя бы один неприводимый многочлен степени над этим полем.

Скрытый текст

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

Скрытый текст

Замечание. Строго говоря, конечное поле строится не по модулю неприводимого многочлена, а по модулю главного идеала $\langle f(x) \rangle$ , порожденного многочленом . Однако, чтобы не усложнять изложение, мы сознательно здесь допускаем неточность.

Если многочлен неприводим над полем , то существует расширение поля , в котором этот многочлен имеет корни. Этим расширением является поле $GF(p)[x] / \langle f(x) \rangle$ . Пусть элемент $\alpha \in GF(p)[x] / \langle f(x) \rangle$ является корнем многочлена , т.е. $f(\alpha) = 0$ . Тогда говорят, что поле $GF(p)[x] / \langle f(x) \rangle$ порождается элементом $\alpha$ над полем , поэтому переход от поля к полю $GF(p)[x] / \langle f(x) \rangle$ называется присоединением к полю корня неприводимого многочлена .

Скрытый текст

Если вас начинают пугать обозначения и формулировки, всегда можно провести аналогию с полем классов вычетов по модулю простого числа. Как в поле $\mathbb{Z}/p\mathbb{Z}$ мы считаем, что $p \equiv 0 \: (\textrm{mod} \: p)$ , так и в поле $GF(p)[x] / \langle f(x) \rangle$ мы считаем многочлен $f(x) \equiv 0 \: (\textrm{mod} \: f(x))$ , а значит, в этом поле у многочлена появляются корни.

Скрытый текст

Замечание. Пусть $\alpha = x + \langle f(x) \rangle$ - класс вычетов многочлена по модулю главного идеала $\langle f(x) \rangle$ , то есть множество всех многочленов, которые при деление на многочлен дают остаток . Тогда $f(\alpha) = 0$ , так как $f(x) \equiv 0 \: (\textrm{mod} \: f(x))$ , следовательно $\alpha$ является корнем многочлена . Однако, как и в случае классов вычетов по модулю простого числа, чтобы не перегружать изложение, далее мы будем использовать представителей классов и отождествлять $\alpha$ с .

Так как элементами поля являются многочлены, то сложение и вычитание элементов поля осуществляются по тем же правилам, которые используются в кольце многочленов : эти операции сводятся к соответствующим операциям над коэффициентами многочленов. Для того, чтобы перемножить 2 элемента конечного поля , необходимо сначала перемножить соответствующие им многочлены, а затем взять остаток от деления произведения элементов поля на неприводимый многочлен , с помощью которого было построено поле $GF(p)[x] / \langle f(x) \rangle$ .

Скрытый текст

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

Примитивным элементом конечного поля называется всякий генератор мультипликативной группы поля , т.е. элемент, степени которого генерируют все ненулевые элементы этого поля. Порядок примитивного элемента $\alpha \in GF(q)$ равен .

Минимальный многочлен элемента $\alpha \in GF(p^n)$ - нормированный многочлен минимальной степени в кольце многочленов , корнем которого является $\alpha$ . Любой минимальный многочлен является неприводимым над полем .

Алгебраическим числом над полем называется корень $\alpha$ ненулевого многочлена с коэффициентами в . Степень минимального многочлена элемента $\alpha$ над полем называется степенью алгебраического числа $\alpha$ .

Примитивный многочлен поля - это минимальный многочлен примитивного элемента поля (т.е. минимальный многочлен, корнем которого является примитивный элемент поля).

Конечное поле GF(2^4)

- это конечное поле, его порядок . Прядок конечного поля является степенью простого числа, т.е. . Представим как и рассмотрим конечное поле .

Элементами поля являются многочлены степени не больше 3 с коэффициентами в , т.е. многочлены вида p(x) = , $a_i \in GF(2), i = 0, \dots, 3$ .

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

Скрытый текст

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

Ниже представлен код для поиска примитивного элемента конечного поля:

from sage.all import *

x = var('x') # создаем символическую переменную

# создаем основное поле GF(p)
F = GF(2, name='a')
# получаем кольцо многочленов с коэффициентами в GF(p)
R = F[x]

# выбираем необходимую степень неприводимого многочлена
# (степень расширения)
deg = 4

# функция для поиска примитивного элемента поля
def primitive_poly(R, deg):
    while True:
        poly = R.irreducible_element(deg, 'random')
        if poly.is_primitive():
            return poly

print(primitive_poly(R, deg))

Скрытый текст

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

Неприводимый многочлен в поле характеристики 2 должен иметь нечетное количество ненулевых коэффициентов, так как без свободного члена (константы) многочлен всегда имеет нулевой корень, а многочлен с четным количеством коэффициентов всегда будет иметь 1 в качестве корня. Поэтому будем искать неприводимый многочлен вида или , $a, b, c, d \in GF(2)$ .

Неприводимых многочленов 4 степени над полем существует несколько, найдем некоторые из них. Пусть - многочлен 4 степени над полем , и пусть $f(x) = g(x) \cdot h(x)$ .

Так как $\deg f(x) = 4$ и $\deg f(x) = \deg(g(x) \cdot h(x)) = \deg g(x) + \deg h(x)$ , то возможен один из следующих вариантов:

$\deg g(x) = 1; \deg h(x) = 3$ $\deg g(x) = 2; \deg h(x) = 2$ $\deg g(x) = 3; \deg h(x) = 1$

Заметим, что во всех случаях один из многочленов в разложении будет иметь степень не выше 2, следовательно достаточно проверить делимость на все многочлены степени не выше 2. Выпишем все многочлены степени не выше 2 над полем :

многочлены первой степени: , ;
многочлены второй степени: , , , .

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

Таким образом, ни один из многочленов степени не выше 2 над полем не делят без остатка многочлен . Можно сделать вывод, что многочлен является неприводимым над .

Скрытый текст

Замечание. Деление многочленов можно осуществлять с помощью известного со школы способа - деление "уголком" ("в столбик"), это полезно уметь делать. Однако на практике намного удобнее использовать для этого специализированное программное обеспечение:

from sage.all import *

# определяем символическую переменную
x = var('x') 

# определяем конечное поле GF(2)
F = GF(2)
# определяем кольцо многочленов GF(2)[x]
R = F[x]

# определяем многочлен f(x) как элемент кольца многочленов
f = R(x**4 + x + 1)

# задаем список многочленов, на которые хотим поделить
polys = [x+1, x**2 + 1, x**2 + x + 1]
for poly in polys:
    # получаем частное и остаток
    q, r = f.quo_rem(R(poly))
    print(f'f(x) = ({poly})({q}) + {r}')

Теперь аналогично рассмотрим многочлен . Этот многочлен, как и в предыдущем случае, имеет свободный член. Проверим оставшиеся многочлены:

Следовательно, многочлен также является неприводимым над .

Теперь рассмотрим, в чем отличие при построении поля по модулю и . По определению поля его элементами будет являться множество из 16 многочленов степени не более 3 с коэффициентами в :

$GF(2^4) = \{ 0, 1, x, x + 1, x^2, x^2 + 1, x^2 + x, x^2 + x + 1,$ $x^3, x^3 + 1, x^3 + x, x^3 + x + 1, x^3 + x^2, x^3 + x^2 + 1, x^3 + x^2 + x, x^3 + x^2 + x + 1 \}$

Однако, когда мы задаем поле по модулю :

$x^{-1} = x^3 + 1;\quad (x^2)^{-1} = x^3 + x^2 + 1;\quad (x^3)^{-1} = x^3 + x^2 + x + 1;$ $(x + 1)^{-1} = x^3 + x^2 + x; \quad (x^2 + x)^{-1} = x^2 + x + 1; \quad (x^3 + x^2)^{-1} = x^3 + x;$ $(x^3 + x + 1)^{-1} = x^2 + 1$

А когда мы задаем поле по модулю :

$x^{-1} = x^3 + x^2 + x + 1; \quad (x^2)^{-1} = x^3; \quad (x + 1)^{-1} = x^3 + x;$ $(x^2 + x)^{-1} = x^2 + 1; \quad (x^3 + 1)^{-1} = x^2 + x + 1; \quad (x^3 + x^2)^{-1} = x^3 + x^2 + 1;$ $(x^3 + x + 1)^{-1} = x^3 + x^2 + x$

Таким образом, различные неприводимые многочлены по-разному формируют соотношения между элементами: по-разному создают пары взаимно обратных элементов. Само же "содержимое" конечного поля зависит только от порядка поля.

Скрытый текст

Ниже представлен код для поиска обратных элементов для каждого элемента поля:

from sage.all import *

x = var('x') # определяем символическую переменную

# определяем конечное поле GF(2^4)
F = GF(2**4, name='x', modulus=x**4 + x + 1)

# итерируемся по всем элементам поля
for el in F:
    # пропускаем 0 и 1
    if el == 0 or el == 1:
        continue
    # находим обратный элемент
    print(f'({el})^(-1) = {el**-1}')

Скрытый текст

Замечание. Рассмотрим по модулю . Тогда

$x^{-1} = x^3 + 1 \implies (x^3 + 1)x = x^4 + x = (x^4 + x + 1) - 1 = 1 \: (\textrm{mod} \: f(x))$

т.к. по построению $f(x) \equiv 0 \: (\textrm{mod} \: f(x))$ и в поле характеристики 2 выполняется $-1 \equiv 1 \: (\textrm{mod} \: 2)$ .

Далее рассмотрим подробнее поле по модулю неприводимого многочлена . Пусть $\alpha = x \in GF(2^4)$ - корень неприводимого многочлена , т.е. $f(\alpha) = 0$ . Тогда $GF(2^4) = GF(2)[x] / \langle f(x) \rangle$ порождается элементом $\alpha$ , т.е. поле можно представить как множество многочленов от $\alpha$ степени не более 3. Построим это поле: выразим все элементы через элемент $\alpha$ , при этом заметим, что $-1 \equiv 1 \: (\textrm{mod} \: 2)$ и $f(\alpha) = 0$ , следовательно $\alpha^4 = \alpha + 1$ . Получаем:

$\alpha^0 = 1; \quad \alpha^1 = \alpha; \quad \alpha^2 = \alpha^2; \quad \alpha^3 = \alpha^3; \quad \alpha^4 = \alpha + 1; \quad \alpha^5 = \alpha \cdot \alpha^4 = \alpha (\alpha + 1) = \alpha^2 + \alpha;$ $\alpha^6 = \alpha \cdot \alpha^5 = \alpha (\alpha^2 + \alpha) = \alpha^3 + \alpha^2; \quad \alpha^7 = \alpha \cdot \alpha^6 = \alpha(\alpha^3 + \alpha^2) = \alpha^4 + \alpha^3 = \alpha^3 + \alpha + 1;$ $\alpha^8 = \alpha \cdot \alpha^7 = \alpha(\alpha^3 + \alpha + 1) = \alpha^2 + 2\alpha + 1 = \alpha^2 + 1; \quad \alpha^9 = \alpha(\alpha^2 + 1) = \alpha^3 + \alpha;$ $\alpha^{10} = \alpha(\alpha^3 + \alpha) = \alpha^2 + \alpha + 1; \quad \alpha^{11} = \alpha^3 + \alpha^2 + \alpha; \quad \alpha^{12} = \alpha^3 + \alpha^2 + \alpha + 1;$ $\alpha^{13} = \alpha^3 + \alpha^2 + 1; \quad \alpha^{14} = \alpha^3 + 1; \quad \alpha^{15} = 1$

Заметим, что способ представления элементов поля через многочлены от $\alpha$ отличается от представления через многочлены от только тем, что буква была заменена на $\alpha$ . Однако, такая замена позволяет оперировать в терминах корней многочленов при осуществлении арифметических операций в конечных полях, а это намного удобнее.

Скрытый текст

Ниже представлен код для вычисления всех элементов поля в виде степеней корня неприводимого многочлена:

from sage.all import *

x = var('x') # определяем символическую переменную

# определяем конечное поле GF(2^4)
F = GF(2**4, name='a', modulus=x**4 + x + 1)
# получаем корень неприводимого многочлена
a = F.gen()

# перебираем все степени, дающие уникальные элементы
# порядок "a" равен 2**4 - 1 = 15
for i in range(16):
    print(f'a^{i} = {a**i}')

Элемент $\alpha$ сгенерировал все ненулевые элементы поля, т.е. мультипликативную группу этого поля, следовательно элемент $\alpha$ является примитивным элементом поля. Его порядок равен . А так как $\alpha$ является еще и корнем многочлена и - минимальный многочлен элемента $\alpha$ , то - примитивный многочлен поля . Необходимо отметить, что кроме полученных выше элементов поля, ноль также является элементом конечного поля. В итоге получаем ровно элементов.

Как было показано, любой ненулевой элемент поля может быть получен как степень $\alpha^k, k \in \mathbb{Z}$ . В свою очередь, $\alpha^k = b_3 \alpha^3 + b_2 \alpha^2 + b_1 \alpha + b_0$ , где $b_i \in GF(2), i = 0, \dots, 3$ , следовательно мы можем задать каждый элемент поля в виде двоичного вектора, в котором каждая цифра соответствует коэффициенту . Все элементы поля, записанные с помощью разных способов представления, указаны в таблице 2.

Таблица 2 – Все элементы поля , записанные с помощью разных способов представления.

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

Таблица 3 – Правило сложения в конечном поле .

Чтобы перемножить два элемента $a(x), b(x) \in GF(2^4)$ , необходимо перемножить соответствующие многочлены и взять остаток от деления на неприводимый многочлен : $a(x) \cdot b(x) \: (\textrm{mod} \: f(x))$ .

Скрытый текст

Пример.

$= (x^4 + x + 1)(x^2 + x) + x^3 \equiv x^3 \: (\textrm{mod} \: f(x))$

Однако умножать таким способом элементы поля не всегда удобно и эффективно, поэтому нередко (особенно в случае небольших полей) используется представление элементов поля как степеней $\alpha^k, k \in \mathbb{Z}$ генерирующего элемента - образующего элемента циклической мультипликативной группы. Правило умножения для поля показано в таблице 4:

Таблица 4 – Правило умножения в конечном поле .

Скрытый текст

Пример. Пусть , . Запишем эти элементы как многочлены от $\alpha$ : $a(\alpha) = \alpha^3 + \alpha + 1$ , $b(\alpha) = \alpha^3 + \alpha^2 + \alpha$ . Мы уже вычисляли (см. таблицу 2), что $a(\alpha) = \alpha^7$ , $b(\alpha) = \alpha^{11}$ . Учитывая, что порядок элемента $\alpha$ равен , по свойствам циклической мультипликативной группы получаем:

$\alpha^7 \cdot \alpha^{11} = \alpha^{18} \equiv \alpha^{(18 \: \textrm{mod} \: 15)} = \alpha^3$

Скрытый текст

Ниже предствален код для вычисления таблиц сложения и умножения:

from sage.all import *

x = var('x') # определяем символическую переменную

# определяем конечное поле GF(2^4)
F = GF(2**4, name='a', modulus=x**4 + x + 1)

# функция, которая преобразует элемент в двоичную строку
def element_to_binary(el):
    # получаем коэффициенты многочлена
    coefs = el.polynomial().list()[::-1]
    # добавляем нули до длины 4
    coefs = [0]*(4 - len(coefs)) + coefs
    return ''.join(map(lambda x: str(x), coefs))

# функция, которая выводит таблицу
def print_table(t):
    # получаем ключи для получения исходных элементов
    # в закодированной таблице
    keys = t.column_keys()
    # получаем таблицу в виде двумерного списка
    table = t.table()
    
    # выводим первую строку
    print('    ', end=' ')
    for i in range(len(table)):
        print(element_to_binary(keys[i]), end=' ')
    print()

    for i in range(len(table)):
        print(element_to_binary(keys[i]), end=' ')
        for j in range(len(table)):
            # получаем результат умножения
            el = keys[table[i][j]]
            print(element_to_binary(el), end=' ')
        print()

print("Таблица сложения:")
print_table(F.addition_table())

print("Таблица умножения:")
print_table(F.multiplication_table())

Теперь построим поле по модулю неприводимого многочлена . Пусть $\lambda \in GF(2^4)$ - корень многочлена , т.е. $h(\lambda) = 0$ . Представим элементы поля как многочлены от $\lambda$ . Аналогично предыдущему случаю $-1 \equiv 1 \: (\textrm{mod} \: 2)$ и $h(\lambda) = 0$ , следовательно $\lambda^4 = \lambda^3 + \lambda^2 + \lambda + 1$ . Получаем:

$\lambda^0 = 1; \quad \lambda^1 = \lambda; \quad \lambda^2 = \lambda^2; \quad \lambda^3 = \lambda^3; \quad \lambda^4 = \lambda^3 + \lambda^2 + \lambda + 1;$ $\lambda^5 = \lambda \cdot \lambda^4 = 2\lambda^3 + 2\lambda^2 + 2\lambda + 1 = 1$

Таким образом элемент $\lambda$ порождает не всю мультипликативную группу поля , а только подгруппу из 5 элементов. Следовательно, элемент $\lambda$ не является примитивным элементом поля , а многочлен не является примитивным многочленом.

Скрытый текст

Замечание. Важно отметить, что не любой неприводимый многочлен является примитивным.

Чтобы найти примитивный элемент поля, можно воспользоваться алгоритмом поиска образующего элемента циклической группы, который мы разбирали в первой части серии. Не сложно проверить, что, например, элемент $\lambda + 1$ является примитивным элементом и все ненулевые элементы поля можно представить как степени $(\lambda + 1)^k, k \in \mathbb{Z}$ .

Операции с элементами поля , построенного по модулю многочлена , осуществляются аналогично предыдущему случаю с учетом того, что необходимо использовать в качестве примитивного элемента, например, элемент $\lambda + 1$ . На этом шаге закончим с построением поля .

Теперь-то мы закончили?

Самая сложная часть позади. Но это еще не все.

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

Спасибо за уделённое время! Если тема оказалась вам интересна - следите за выходом следующих статей.