Галуа Ч.3: Конечные поля вида GF((p^n)^m). Изоморфизм конечных полей / Хабр

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

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

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

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

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

Расширение поля , где - простое, $n, m \in \mathbb{N}$ , строится аналогично расширению поля . Назовем для удобства поле, над которым строится расширение, базовым поле, т.е. для расширения базовым полем является , а для расширения базовым является .

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

Поле замкнуто относительно своих операций и, очевидно, удовлетворяет всем свойствам поля. Арифметические операции в таком поле осуществляются аналогично случаю . Рассмотрим далее структуру поля на примере.

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

Построим конечное поле . Его порядок , так же как и в случае конечного поля . Сначала кратко опишем поле . Так как мы уже описали поле во второй части серии, то я не буду подробно останавливаться на деталях.

В качестве неприводимого многочлена возьмем многочлен . Пусть $\beta \in GF( 2^ 2)$ - корень многочлена . Следовательно, $\beta^2 = \beta + 1$ . Представим элементы поля как многочлены от $\beta$ :

$\beta^0 = 1; \quad \beta^1 = \beta; \quad \beta^2 = \beta + 1; \quad \beta^3 = \beta(\beta + 1) = 2\beta + 1 = 1$

Элемент $\beta$ сгенерировал мультипликативную группу этого поля, следовательно $\beta$ является примитивным элементом этого поля, а - примитивным многочленом.

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

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

Правило сложения в поле показано в таблице 2:

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

Правило умножения для поля показано в таблице 3:

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

На этом закончим с описание поля и перейдем к полю . Поле может быть представлено как множество всех многочленов неотрицательной степени не более 1 с коэффициентами в поле , т.е. $GF((2^2)^2) = \{ a_1 x + a_0 | a_i \in GF(2^2), i=0, 1 \}$ .

В качестве неприводимого многочлена возьмем многочлен $h(x) = x^2 + x + \beta$ , где $\beta$ - корень многочлена , по модулю которого было построено поле . Пусть $\gamma \in GF((2^2)^2)$ - корень многочлена . Следовательно, $\gamma^2 = \gamma + \beta$ . Представим элементы поля как многочлены от $\gamma$ . Элемент поля может быть представлен как двоичная строка длины 4, которую разбили на 2 последовательных подстроки длины 2, где каждая двоичная строка длины 2 соответствует коэффициенту из базового поля , т.е. элемент $\gamma^k = a_1 \gamma + a_0, k \in \mathbb{Z}$ будем представлять как двоичный вектор , где $a_0, a_1 \in GF(2^2)$ . Все элементы поля, записанные с помощью разных способов представления, указаны в таблице 4:

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

GF((2^2)^2) — Таблица 4 - Все элементы поля , записанные с помощью разных способов представления.

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

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

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

from sage.all import *

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

g = var('g') # определяем символическую переменную
# получаем кольцо многочленов с коэффициентами в F
R = F[g]

# определяем неприводимый многочлен x^2 + x + b
# как элемент R
irreducible_poly = R([b, 1, 1])
g = R(g) # определяем g как элемент R

# получаем все ненулевые элементы
for i in range(16):
    print(f'g^{i} = {g**i % irreducible_poly}')

Элемент $\gamma$ сгенерировал мультипликативную группу этого поля, следовательно $\gamma$ является примитивным элементом этого поля, а - примитивным многочленом.

Арифметические операции в поле осуществляются аналогично предыдущим случаям с тем только отличием, что коэффициенты элементов поля являются элементами поля , т.е. операции над ними осуществляются в соответствии с таблицами 2 и 3.

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

Пример. Пусть $a = (\beta + 1)\gamma + \beta = \gamma^3$ и $b = \beta \gamma + 1 = \gamma^{13}$ (см. таблицу 4), $a, b \in GF((2^2)^2)$ . Тогда

$a + b = (\beta + 1) \gamma + \beta + \beta \gamma + 1 = (2\beta + 1) \gamma + \beta + 1 = \gamma + \beta + 1$ $a \cdot b = \gamma^3 \cdot \gamma^{13} = \gamma^{16 \: \textrm{mod} \: 15} = \gamma$

Правило сложения в поле показано в таблице 5:

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

Правило умножения для поля показано в таблице 6:

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

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

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

from sage.all import *

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

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

g = var('g') # определяем символическую переменную
# получаем кольцо многочленов с коэффициентами в F
R = F[g]

# определяем неприводимый многочлен x^2 + x + b
# как элемент R
irr_poly = R([b, 1, 1])
g = R(g) # определяем g как элемент R

# получаем все ненулевые элементы
elements = [g**i % irr_poly for i in range(15)]
elements.insert(0, R(0)) # добавляем ноль

# функция, которая преобразует элемент в двоичную строку
def element_to_binary(el):
    # добавляем нули до длины 2
    coefs = el.coefficients(sparse=False)
    coefs = (coefs + [0] * (2 - len(coefs)))[::-1]
    
    result = []
    for coef in coefs:
        if coef == 0: # ноль не является многочленом
            cfs = [coef]
        else:
            cfs = coef.polynomial().coefficients(sparse=False)
        # добавляем нули до длины 2
        cfs = (cfs + [0] * (2 - len(cfs)))[::-1]
        
        result.extend(cfs)
    return ''.join(map(lambda x: str(x), result))

# сортируем элементы в лексикографическом порядке,
# представляя каждый элемент как бинарную строку
elements.sort(key=lambda x: element_to_binary(x))

# функция, которая выводит таблицу
def print_table(els, op):    
    # выводим первую строку
    print('    ', end=' ')
    for i in range(len(els)):
        print(element_to_binary(els[i]), end=' ')
    print()

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

def elements_sum(el1, el2):
    return (el1 + el2) % irr_poly

def elements_mul(el1, el2):
    return (el1 * el2) % irr_poly


print("Таблица сложения:")
print_table(elements, elements_sum)

print("Таблица умножения:")
print_table(elements, elements_mul)

Изоморфизм конечных полей

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

Пусть , - конечные поля одинакового порядка, - примитивным многочлен степени над , $\alpha$ - примитивный элемент поля , $\beta$ - примитивный элемент поля . Тогда из теории конечных полей известно, что существует такой элемент $\beta^k, k \in \mathbb{Z}$ , что $f(\beta^k) = 0$ , т.е. $\beta^k$ является примитивным элементом. Поле есть множество многочленов от $\alpha$ степени не более , поле - множество многочленов от $\beta$ степени не более . Следовательно, взаимно однозначное соответствие $\varphi: \alpha \rightarrow \beta^k$ задает изоморфизм полей и . Пусть $\alpha^c = \alpha^a + \alpha^b$ , где $a, b, c \in \mathbb{Z}$ . Из определения и свойств изоморфизма получаем, что должны выполняться следующие условия:

$(\beta^k)^c = \varphi(\alpha)^c = \varphi(\alpha^c) = \varphi(\alpha^a + \alpha^b) = \varphi(\alpha^a) + \varphi(\alpha^b) = \varphi(\alpha)^a + \varphi(\alpha)^b = (\beta^k)^a + (\beta^k)^b$ $\varphi(\alpha^{a+b}) = \varphi(\alpha^a \cdot \alpha^b) = \varphi(\alpha^a) \cdot \varphi(\alpha^b) = (\beta^k)^a \cdot (\beta^k)^b = (\beta^k)^{a + b}$

Рассмотрим конечные поля и . Пусть эти поля построены так, как было описано ранее, т.е. $\alpha$ примитивный элемент поля , - примитивный многочлен этого поля, $\gamma$ - примитивный элемент поля . Необходимо найти $\gamma^k, k \in Z$ такие, что $f(\gamma^k) = (\gamma^k)^4 + \gamma^k + 1 = 0$ , т.е. $(\gamma^k)^4 = \gamma^k + 1$ .

Легко видеть по таблице 4, что подходит значение , т.е. $\gamma$ (также подходят сопряженные элементы $\gamma^2$ , $\gamma^4$ , $\gamma^8$ ). Получаем, что $\varphi: \alpha \rightarrow \gamma$ задает изоморфизм между полями и .

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

Про сопряженные элементы можно почитать в Сагалович Ю.Л. Введение в алгебраические коды: учебное пособие / Ю. Л. Сагалович. М-во обра- зования и науки Российской Федерации, Учреждение Российской акад. наук Ин-т проблем передачи информ. им. А. А. Харкевича РАН. - 3-е изд., перераб. и доп. - Москва: ИППИ РАН, 2014. - 310 с.

Проверим, что свойства изоморфизма выполняются. Рассмотрим два произвольных элемента $\alpha^2, \alpha^6 \in GF(2^4)$ (см. вторую статью из серии), из таблицы 3 второй статьи получаем $\alpha^2 + \alpha^6 = \alpha^3$ . По таблице 5 можно проверить, что $\gamma^3 = \varphi(\alpha^2 + \alpha^6) = \varphi(\alpha)^2 + \varphi(\alpha)^6 = \gamma^2 + \gamma^6$ . Выполнение второго условия очевидно: $\varphi(\alpha^8) = \varphi(\alpha^2 \cdot \alpha^6) = \varphi(\alpha)^2 \cdot \varphi(\alpha)^6 = \gamma^2 \cdot \gamma^6 = \gamma^8$ . Аналогично можно проверить выполнения условий для всех остальных элементов этих полей. Таким образом, взаимно однозначное соответствие $\varphi: \alpha \rightarrow \gamma$ корректно задает изоморфизм между полями и .

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

Мы рассмотрели один из способов задания изоморфизма конечных полей через соответствие примитивных элементов. Однако на практике часто удобнее работать не со степенями примитивных элементов, а с координатными векторами, представляющими элементы поля относительно выбранного базиса. Поскольку конечное поле является -мерным векторным пространством над , в каждом из рассматриваемых полей можно выбрать базис и представлять элементы их координатами в этом базисе. Тогда изоморфизм между полями будет задаваться линейным преобразованием и может быть реализован с помощью матрицы перехода между соответствующими базисами. Подробнее этот подход рассматривается в работе Satoh, A., Takano, K. A Scalable Dual-Field Elliptic Curve Cryptographic Processor, IEEE Transactions on Computers, vol. 52, no. 4, pp. 449–460, April 2003.

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

Мы рассмотрели структуру полей вида в общем виде. Однако до этого мы приводили примеры только полей характеристики 2. В результате этого у читателя может сформироваться неправильное видение структуры конечных полей в результате привыкания к особенным свойствам полей характеристики 2. Далее мы кратко рассмотрим поле .

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

$\underbrace{1 + 1 + 1}_3 = 3 \equiv 0 \: (\textrm{mod} \: 3)$

В отличие от полей характеристики 2, в полях характеристики 3 сложение и вычитание - это разные операции ( $-1 \equiv 2 \: (\textrm{mod} \: 3)$ , т.е. для любых $a, b \in GF(3)$ имеем $a - b \equiv a + 2b \: (\textrm{mod} \: 3)$ ). Правила сложения, вычитания и умножения для этого конечного поля показаны в таблице 7:

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

Перейдем к описанию поля . Его элементами являются многочлены степени не более 1 с коэффициентами в поле . В качестве неприводимого многочлена возьмем многочлен (так как характеристика этого поля 3, а не 2, ненулевых коэффициентов может быть четное количество). Пусть $\alpha \in GF(3^2)$ - корень многочлена . Следовательно, $\alpha^2 = -1 \equiv 2 \: (\textrm{mod} \: 3)$ . Представим элементы поля как многочлены от $\alpha$ :

$\alpha^0 = 1; \quad \alpha^1 = \alpha; \quad \alpha^2 = 2; \quad \alpha^3 = 2\alpha; \quad \alpha^4 = 2\alpha^2 = 4 \equiv 1 \: (\textrm{mod} \: 3)$

Элемент $\alpha$ сгенерировал подгруппу мультипликативной группы порядка 4, следовательно $\alpha$ не является примитивным элементом этого поля. Рассмотрим в качестве примитивного элемента $\alpha + 1$ . Представим элементы поля как многочлены от $\alpha + 1$ :

$(\alpha+1)^0 = 1; \quad (\alpha+1)^1 = \alpha + 1; \quad (\alpha+1)^2 = 2\alpha; \quad (\alpha+1)^3 = 2\alpha + 1; \quad (\alpha+1)^4 = 2$ $(\alpha+1)^5 = 2\alpha + 2; \quad (\alpha + 1)^6 = \alpha; \quad (\alpha + 1)^7 = \alpha + 2; \quad (\alpha + 1)^8 = 1$

Элемент $\alpha + 1$ сгенерировал все ненулевые элементы поля , т.е. мультипликативную группу поля, его порядок равен . Таким образом, элемент $\alpha + 1$ является примитивным элементом поля по модулю многочлена , при этом многочлен не является примитивным многочленом.

Элементы поля можно представит в виде векторов, однако теперь эти вектора будут не двоичными, их координаты будут принимать значения из множества $\{ 0, 1, 2 \}$ . Все элементы поля, записанные с помощью разных способов представления, указаны в таблице 8:

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

Сложение элементов осуществляется покоординатно по модулю 3. Правило сложения в поле показано в таблице 9:

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

Умножение элементов, так же как и в поле характеристики 2, осуществляется через умножение многочленов и вычисление остатка от деления на неприводимый многочлен . Также, можно использовать представление элементов в виде степеней $(\alpha + 1)^k, k \in \mathbb{Z}$ примитивного элемента поля. Правило умножения для поля показано в таблице 10:

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

Ну вот и все

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

Когда я учился в университете, я мечтал построить карьеру в сфере криптографии. Увы, эта мечта разбилась о скалы рынка труда. Если эти статьи помогут кому-то в учебе или работе, значит, всё было не зря, а мне будет плюсик в карму (и тут я не про Хабр).

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

Спасибо за уделённое время! Если вам было интересно читать мои статьи, подписывайтесь и следите за новыми публикациями.