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

2024-09-18 в 10:15, admin, рубрики: дискретное логарифмирование, конечные поля, поля галуа, порождающий полином

Вступление

В качестве КДПВ представлен математик Эварист Галуа, имя которого увековечено в обозначении конечных полей: GF (Galois field).

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

Я не профессиональный математик, поэтому в статье не будет никаких "зубодробительных" формул, по крайней мере очень мало.

Для начала пробежимся по теории.

Теоретическая часть

В данном разделе рассмотрим поближе что такое: группа, поле, нейтральный элемент и т.п. Ничего нового, кто знаком, можно смело пропускать.

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

Группа — множество, на котором определена ассоциативная бинарная операция, причём для этой операции имеется нейтральный элемент, и каждый элемент множества имеет обратный.

— бинарная операция. Стоит отметить, что знакомое программистам слово "бинарный" в данном контексте означает, что в операции участвует два операнда. Для тех кто удивился, как и я когда-то, скажу что есть например, тернарная операция - в которой участвует три операнда. Опять знакомое программистам понятие )

Ассоциативность или сочетательность: .

— нейтральный элемент. Элемент, который оставляет любой другой элемент неизменным при применении бинарной операции .

Обратный элемент — термин, обобщающий понятия обратного числа ( $a^{-1}$ , для умножения) и противоположного числа (, для сложения).

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

Математики считают что операция вычитания это частный случай сложения, сравните: и .

Конечное поле — поле, состоящее из конечного числа элементов, обозначается , — количество элементов поля, называется порядком поля.

, где — простое число, а — любое натуральное число. При этом будет являться характеристикой этого поля.

Еще известно другое обозначение конечных полей: $mathbb{F}_q$ , которое было известно до Галуа.

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

Мне ближе обозначение $mathrm{GF}(p^n)$ , при необходимости можно указать так: $mathrm{GF}(p^1)$ или просто .

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

Если сейчас не очень понятно - не страшно, главное на текущий момент запомнить, что — характеристика конечного поля.

Рассмотрим конечное поле из двух элементов (вики)

Как сгенерировать порождающие полиномы для конечных полей - 23

Видим две таблицы: для сложения и умножения, в которых складываются и умножаются элементы множества

Важное свойство конечных полей: в каждой строке/столбце таблиц должны быть уникальные значения, кроме 0-й строки/столбца в таблице умножения.

Может возникнуть вопрос, почему:

Для характеристика поля = 2

, так как число 2 не входит в множество элементов, то приводим результат по модулю 2:

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

0 - нейтральный элемент для группы по сложению ;
1 - нейтральный элемент для группы по умножению .

Рассмотрим конечное поле из трех элементов (вики)

Как сгенерировать порождающие полиномы для конечных полей - 33

Характеристика поля = 3

Рассмотрим конечное поле из четырех элементов

Как сгенерировать порождающие полиномы для конечных полей - 39

Что такое, почему в столбце со значением 2, не уникальные значения?

Потому что — должно быть простым числом!

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

А вот 4 можно представить как

Поэтому рассмотрим другое конечное поле из 4-х элементов $mathrm{GF}(2^2)$ (вики)

До этого примера, в качестве элементов множества мы использовали обычные числа

Для конечных полей типа $mathrm{GF}(p^n)$ , при , надо использовать полиномы или ..., об этом позже.

Множество для $mathrm{GF}(2^2)$ выглядит так:

Во-первых, между элементами множества должен быть определенный шаг, у нас есть обязательные элементы: 0 и 1, поэтому шаг = 1.

Во-вторых, "мнимая" переменная , мнимая - потому что нельзя просто так, заменить на определенное значение, но для определения множества можно установить: .

Множество получается: - шаг сохранен.

Неважно как вы будете обозначать переменную, хоть , или , или как-нибудь еще.

Как сгенерировать порождающие полиномы для конечных полей - 56 — $mathrm{GF}(2^2)$

Кстати, сокращать по модулю характеристики можно не только , но и любой другой элемент, например

Желательно даже запомнить: , где - характеристика, - элемент.

С таблицей умножения будет посложнее, рассмотрим в следующем разделе.

Получение остатка от деления полиномов

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

Для $mathrm{GF}(2^2)$ порождающий полином:

Заметим что степень порождающего полинома всегда равна степени порядка поля .

Итак: почему?

Конкретно этот пример можно решить как в выше указанной ссылке на вики:

Данный вариант имеет право на жизнь, но не всегда удобен и его трудно запрограммировать.

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

Разделим уголком (или столбиком) на порождающий полином

И последнее: , удалили по модулю p

Идем дальше, переведем полиномы в бинарный вид.

Для тех кто забыл, как перевести полином в бинарный вид.

Остаток 11 переводим в полиномиальный вид: , результат тот же что и при делении полиномов.

А если полиномы разной длины? Например, нужно найти остаток от деления на

Результат тот же.

Результат деления нам не нужен, важен только остаток от деления. Оставляем только последовательное применение XOR до получения остатка.

Данную функцию назвал XORO (XOR+Остаток).

Под таблицей умножения детализация расчетов с использованием XORO.

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

CRC (Циклический избыточный код) также базируется на конечных полях.

Скриншоты таблиц конечных полей сделаны из сервиса, ссылка будет в конце статьи.

Выходим за пределы характеристики 2

Большая часть статей посвященных конечным полям описывают такие поля как: $mathrm{GF}(2^n)$ (т.е. с характеристикой 2) или совсем простые .

Что касается криптографии, то используются именно $mathrm{GF}(2^n)$ (других пока не видел), в частности шифр "Кузнечик" основан на поле $mathrm{GF}(2^8)$ .

Мы будем расширять знания, т.е. исследуем конечные поля $mathrm{GF}(p^n)$ , при .

Рассмотрим конечное поле из 9-и элементов $mathrm{GF}(3^2)$ , описанное в вики.

Обратите внимание, используется переменная , т.е. есть отношение к комплексным числам.

Для построения таблицы умножения используется соотношение , откуда оно взялось?

Взялось оно так: . Вспоминаем модульную арифметику, она нам понадобится и позже.

У меня сходу не получилось экстраполировать данный опыт даже на поле $mathrm{GF}(3^3)$ , возможно просто не хватает знаний в комплексных числах.

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

Рассмотрим, немного другое конечное поле из 9-и элементов $mathrm{GF}(3^2)$ .

Множество элементов будет таким: , в полиномиальном виде: (обратите внимание, совпадает с множеством, описанным в вики первого варианта $mathrm{GF}(3^2)$ ).

Для генерации множества использовали: .

Порождающий полином: .

Есть проблема: функция XORO создана на основе XOR, которая складывает по модулю 2, а нужно 3.

Создана новая функция: XORI - работает с любым модулем.

Использование XORI в поле $mathrm{GF}(3^2)$

XORI работает по модульной арифметике, например:

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

Предустановки в сервисе, выделены использующие XORI.

Таблица степеней

Таблица степеней помогает определить примитивный элемент конечного поля.

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

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

Примеры определения примитивного элемента.

Для полей типа $mathrm{GF}(p^n)$ , где , примитивный элемент равен .

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

Примитивный элемент может не определиться, например, при непростом .

Примитивный элемент помогает в расчетах. Возьмем для примера поле $mathrm{GF}(2^3)$ , таблица степеней для данного поля представлена выше.

Берем числа:

Найдем произведение , сначала через полиномы и xoro:

Теперь найдем произведение через степени:

$5 cdot 6=2^6 cdot 2^4=2^{(10 mod 7)}=2^3=3$ , модуль

Результат тот же, вычислений меньше.

Теперь рассмотрим деление $frac65$ :

Сначала посмотрим результат деления по таблице умножения:

Как сгенерировать порождающие полиномы для конечных полей - 129 — $frac65=7$

При помощи степеней:

$frac65=frac{2^4}{2^6}=2^{(4-6)}=2^{(-2)}=2^{((-2)mod 7)}=2^5=7$

Результат совпадает.

Таблица логарифмов

Строится данная таблица на основе дискретного логарифмирования.

Рассмотрим для начала таблицы логарифмов для полей типа: , в частности .

Найдем все примитивные элементы для поля:

Найдена пара примитивных элементов: {2, 3}, второй обозначим - .

Обратим внимание - слева от 1 установлен обратный примитивный элемент.

Похоже что примитивные элементы всегда идут парами:

Найденные пары: {2, 3}, {3, 5}, {2, 6}, {7, 8}, {2, 7}, {6, 11} очень похожи на взаимно простые числа, но не все, это наверное база для другой теории - не отвлекаемся.

Построим таблицу логарифмов, в качестве основного примитивного элемента, возьмем .

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

В теле таблицы видим целые числа () в виде спирали.

Эту таблицу логарифмов можно представить в виде "болта со спиралью", предвосхищаю смешки). На головке болта по кругу представим элементы множества конечного поля (то что в шапке таблицы). А в качестве спирали представим бумажную ленту с целыми числами (то что в теле таблицы), оборачиваем ленту вокруг стержня болта.

А где собственно сами дискретные логарифмы?

Поиск в сравнении $a^x equiv b{pmod m}$ называется дискретным логарифмированием.

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

Давайте проверим. Начнем с положительных чисел, по порядку:

и новый цикл:
и т.д.

Теперь отрицательные числа, но сначала немного теории.

Чему равно $2^{-1}$ по модулю? Надо найти обратное по модулю число.

Для этого умножаем 2 последовательно, пока не получим 1:

найдено!

Обратное число равно 3, а это ни что иное как , помните таблицу степеней (см. выше).

Получается формула $alpha^{-k}=alpha’^k$

Продолжим проверку:

$2^{-1}=3^1$
$2^{-2}=3^2 equiv 4 pmod 5$
$2^{-3}=3^3 equiv 2 pmod 5$
и новый цикл:
$2^{-4}=3^4 equiv 1 pmod 5$
$2^{-5}=3^5 equiv 3 pmod 5$
$2^{-6}=3^6 equiv 4 pmod 5$
$2^{-7}=3^7 equiv 2 pmod 5$
и т.д.

А если создать таблицу логарифмов на основе ?

Таблица дискретных логарифмов для на основе

и т.д.
$3^{-1}=2^1$
$3^{-2}=2^2 equiv 4 pmod 5$
$3^{-3}=2^3 equiv 3 pmod 5$
и т.д.

Результат аналогичен.

Теперь посмотрим таблицы логарифмов для полей типа: $mathrm{GF}(p^n)$ .

Обратите внимание на порождающий полином - 111, понадобится ниже.

и т.д.
$2^{-1}=3^1=3$
$2^{-2}=3^2=?$

Что делать с последним выражением? На помощь придет бином Ньютона.

удалили по модулю

Дальше понадобится "трином" Ньютона, потом - мультином Ньютона, кто не верит можете проверить, я верю - проверять не буду ).

И зачем нам все это надо? Чтобы умножать и делить элементы конечного поля, поехали.

Для примера возьмем конечное поле побольше $mathrm{GF}(2^3)$ .

Таблица степеней для , выделен — Таблица степеней для $mathrm{GF}(2^3)$ , выделен

Умножим: , по таблице умножения знаем что должно получиться 7.

Решить произведение: $log_{2}4 cdot log_{2}3$
По таблице логарифмов находим соответствие для 4 и 3, это 2 и 3
Далее решаем: $2^2 cdot 2^3=2^{2+3}=2^5=7$

находим по таблице степеней, хотя тоже самое и в таблице логарифмов.

Используем отрицательные значения, решим: , должно получиться 2.

$2^3 cdot 2^{-2}=2^{3-2}=2^1=2$ , для 7 выбрали не 5 а (-2).

$2^3 cdot 2^5=2^{3+5}=2^{(8 mod 7)}=2^1$ , c 5 тоже получится, сокращение по модулю мы уже использовали в разделе "Таблица степеней", модуль .

Число 7 можно представить как размер цикла спирали.

Разделим 6 на 5, должно получиться 7.

$frac65=frac{2^4}{2^6}=2^{(4-6)}=2^{(-2)}=2^{((-2)mod 7)}=2^5=7$

Отрицательные значения можно удалить из таблицы логарифмов, т.е. в теле останется только одна строка, а всю таблицу можно хранить в каком-нибудь key-value хранилище или в одномерном массиве.

Тело таблицы можно представить как индекс массива.

Внимательный читатель, может спросить: зачем "городить огород" с дискретными логарифмами, если умножать и делить можно при помощи только таблицы степеней?

Чем собственно таблица логарифмов лучше таблицы степеней? Тем более что таблица логарифмов просто перевернутая таблица степеней.

Я не смог дать себе ответ на данный вопрос, поэтому в сервисе нет реализации таблицы логарифмов.

Арифметика конечных полей

В конечных полях (см. теоретическую часть) должны быть определены операции:

Умножение;
Деление;
Сложение;
Вычитание;
Определение обратного элемента для умножения и сложения.

Умножение и деление описаны в разделе "Таблица степеней".

Для сложения и вычитания используется знакомая операция XOR.

Рассмотрим пару примеров:

1 пример:

2 пример:

И определим обратные элементы для умножения и сложения.

Для сложения данный элемент называют противоположным числом , а для умножения - обратным $w^{-1}$ .

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

Противоположные числа:

Обратные числа (для деления используем таблицу степеней):

$1^{-1}=1 / 1=1$
$2^{-1}=1 / 2=2^4 / 2^1=2^3=3$
$3^{-1}=1 / 3=2^4 / 2^3=2^1=2$
$4^{-1}=1 / 4=2^4 / 2^2=2^2=4$

Множество элементов и система счисления

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

Обратите внимание, иногда для расчета необходимо сначала перевести элемент из бинарного вида в полиномиальный.

.Для можно обойтись получением результата по mod.

Что касается систем счисления:

Двоичная система счисления используется для конечных полей типа: $mathrm{GF}(2^n)$ и

Третичная система счисления используется для полей типа: $mathrm{GF}(3^n)$

Четвертичная система счисления используется для полей типа: $mathrm{GF}(4^n)$ - не-не-не, такого не может быть.

Пятеричная система счисления используется для полей типа: $mathrm{GF}(5^n)$ и т.д.

Десятичная система счисления используется для конечных полей типа:

В некоторых примерах явно видна связь системы счисления с характеристикой поля.

Порождающий полином для конечных полей

Порождающий полином (англ. generator polynomial). Информация в сети по данному понятию несколько размыта, в англ. вики есть статья: Polynomial code.

Не следует путать порождающий полином для конечных полей, например с порождающим полиномом для Кодов Рида — Соломона, хотя последние тоже имеют отношение к конечным полям.

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

Так что такое порождающий полином? На мой взгляд лучшее определение: "Порождающий полином неприводим и примитивен".

Из выше представленной ссылки на вики: "Неприводимый многочлен — нетривиальный (то есть не константа) многочлен, неразложимый в произведение нетривиальных многочленов."

Или проще: Многочлен называется неприводимым, если он не может быть разложен в произведение многочленов меньших степеней.

Примитивный полином, по аналогии с примитивным элементом, является порождающим для всех элементов множества конечного поля, кроме 0.

Поскольку примитивные полиномы должны быть неприводимыми, коэффициент старшего порядка должен быть равен единице (1…), а постоянный коэффициент должен быть отличен от нуля (…1, …2), например 101, 102 и т.д.

Перейдем к конкретному примеру, на основании сгенерируем множество элементов, и определим кандидатов в порождающие полиномы.

Так как характеристика поля = 2, то множество будет на основе двоичной системы счисления: .

Для одного конечного поля может быть несколько порождающих полиномов.

Количество примитивных полиномов определяется функцией Эйлера (totient):

К сожалению функцию Эйлера можно использовать только для дополнительной проверки, конкретные полиномы при помощи данной функции не найдешь.

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

В общем смысле алгоритм следующий, "возьмем скалу и отсекаем все лишнее":

Определим необходимую длину порождающего полинома;
Найдем все возможные перестановки заданной длины;
Уберем лишнее по правилу: коэффициент старшего порядка должен быть равен единице (1…), а постоянный коэффициент должен быть отличен от нуля (…1, …2), например 101, 102 и т.д.;
Рассчитаем: $x^{(p^n)-1} xori$ с каждым кандидатом в порождающие полиномы, результат должен быть равен 1, остальное удаляем;
Протестируем каждый оставшийся полином на примитивность;
Прошедшие проверку являются кандидатами в порождающие полиномы.

Подробнее по порядку, напоминаю, на основе :

1 шаг. Определим необходимую длину полинома.

Так-как значит порождающий полином будет 2 степени, типа: . Значит длина полинома равна 3.

2 шаг. Найдем все возможные перестановки длиной 3, получилось 8 значений:

000

001

010

011

100

101

110

111

3 шаг. Уберем лишнее по правилу: коэффициент старшего порядка должен быть равен единице (1…), а постоянный коэффициент должен быть отличен от нуля (…1, …2), осталось два значения: 101, 111.

4 шаг. Рассчитаем: $x^{(p^n)-1} xori$ с каждым кандидатом в порождающие полиномы, результат должен быть равен 1, удаляем остальное.

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

Рассчитаем: с каждым кандидатом в порождающие полиномы. — Рассчитаем: $x^{(p^n)-1} xori$ с каждым кандидатом в порождающие полиномы.

Остался один кандидат в порождающие полиномы: 111.

5 шаг. Протестируем каждый оставшийся полином на примитивность.

Сравниваем базовое множество элементов с полученным:

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

Обратите внимание результат (один кандидат в порождающие полиномы) совпал с результатом функции Эйлера:

Скрин сервиса определения порождающих полиномов для

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

Посмотрите примеры определения других порождающих полиномов:

Определение порождающих полиномов для (все не поместилось).

Вот и порождающий полином для "Кузнечика".

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

Рассмотрим две мультипликативные группы (таблицы умножения) с разными порождающими полиномами, но для одного конечного поля:

Подобные мультипликативные группы для $mathrm{GF}(2^3)$

Подобность в математике называется изоморфизм.

Заключение

Порождающий полином напоминает простое число (делится без остатка на 1 и на самого себя), а их поиск - такое же долгое занятие как и поиск простых чисел.

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

Немножко про историю создания этого сервиса

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

Хотелось все ~~потрогать~~ проверить самому. Сначала все расчеты делал на бумаге. Если элементов до десятка, то еще можно все сделать вручную.

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

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

Ссылка на сервис. Для определения порождающего полинома перейдите по кнопке Generation.

Сервис, (вернее две веб-страницы) реализован на vue, никаких математических библиотек не подключал, все реализовано на js, сервис будет работать у вас в браузере.

У меня на компе тормозит уже на , а это таблица 256 на 256 элементов.

Канвас на больших таблицах тоже может тормозить. Есть опция "Короткий отчет".

Содержимое канваса можно двигать мышкой.

Не советую использовать сервис в производственных целях, в общем: AS IS

Следовало бы писать конечно на каком-нибудь go или rust, и распараллелить, например тестирование кандидатов на порождающий полином. Но тогда мой сервер на дешевом vds повесится, в прямом и переносном смыслах.

А существуют ли другие сервисы для определения порождающих полиномов? Я не нашел, если кому известно - сообщите.

В заключение представляю ссылки на ресурсы, которые помогли мне в работе:

Автор: mvladlin

Источник

Информация

Обсуждаемое

Рекомендуем

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

Вступление

Теоретическая часть

Получение остатка от деления полиномов

Выходим за пределы характеристики 2

Таблица степеней

Таблица логарифмов

Арифметика конечных полей

Множество элементов и система счисления

Порождающий полином для конечных полей

Заключение

Архив

Информация

Обсуждаемое

Рекомендуем

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

Вступление

Теоретическая часть

Получение остатка от деления полиномов

Выходим за пределы характеристики 2

Таблица степеней

Таблица логарифмов

Арифметика конечных полей

Множество элементов и система счисления

Порождающий полином для конечных полей

Заключение

Рекомендованный контент

Новости

Актуальные темы

Архив