АРИФМЕТИКА В КОНЕЧНЫХ ПОЛЯХ И ЕЁ ПРОГРАММНАЯ РЕАЛИЗАЦИЯ

1. Определения

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

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

Множество с двумя бинарными операциями + (сложение) и ⋅ (умножение) называется полем, если оно образует коммутативную группу по сложению, все его ненулевые элементы образуют коммутативную группу по умножению, и выполняется свойство дистрибутивности.

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

2. Свойства конечных полей

1. Характеристика конечного поля является простым числом p.
2. Число элементов в конечном поле F является степенью его характеристики: |F|=.
3. Для любого простого числа p и натурального числа m существует единственное с точностью до изоморфизма поле из  элементов. Это поле обозначается GF().
4. Мультипликативная группа конечного поля является циклической.

3. Простое конечное поле

Поле GF(), где p-простое число, а m=1, можно назвать простым конечным полем.

Для построения простого конечного поля мы можем воспользоваться модульной арифметикой. Тогда, если наше множество содержит p элементов, то результатом произведения чисел a * b будет является число (a * b) mod p. Сумма чисел определяется как (a + b) mod p.

4. Примеры простых конечных полей

Для примера построим таблицы умножения и сложения для конечного поля,где p=5 (см. Рисунок 1 и Рисунок 2)

Рисунок 1. Таблица сложения простого конечного поля

Рисунок 2. Таблица умножения простого конечного поля

5. Конечные поля вида GF()

Поле GF(q)=GF(),p – простое число, имеет q= элементов, нумеруемых как 0, 1, 2,..., q–1. Путь построения этого поля – оно генерируется корнем неприводимого многочлена степени m с коэффициентами из GF(p). Иными словами, в конечных конструкциях помимо "комплексной" арифметики с двумя образующими (конечного аналога комплексных чисел), существует арифметика для p образующих, оперирующая с  значениями.

В случае,когда m>1,поле может быть построено следующим образом.

Сначала выбирается неприводимый многочлен P в GF(p)[ X ] степени m (такой неприводимый многочлен всегда существует). Тогда фактор-кольцо:

GF(q)= GF(p)[X]/(P)

Элементы GF(q ) являются многочленами над GF (p), степень которых строго меньше m. Сложение и вычитание являются полиномами над GF(p) . Произведение двух элементов является остатком евклидова деления на P произведения в GF(p)[X].

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

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

Приведем пример построения конечного поля GF().

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

,

Поэтому для GF(4):

GF(4)=GF(2)[X]/(.

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

Рисунок 3. Матрицы операций конечного поля GF()

Если p-нечетное простое число, всегда существуют неприводимые многочлены вида , причем r принадлежит GF( p ).

Точнее, многочлен  неприводим над GF (p) тогда и только тогда, когда r-квадратичный невычет по модулю p (это почти определение квадратичного нерасчета). Существуют  квадратичных невычетов по модулю p.

Выбрав квадратичный невычет r, пусть α-символический квадратный корень из r, то есть символ, обладающий свойством = r, точно так же, как комплексное число i является символическим квадратным корнем из -1 . Тогда элементами GF() являются все линейные выражения: a+bα.

6. Программная реализация арифметики конечных полей на языке JavaScript

Прежде всего необходимо реализовать функцию-конструктор FiniteFieldCalculator(p = NaN, m = NaN, irreduciblePolynom = null), которая будет возвращать экземпляр функции вместе с её свойствами (переменными и дочерними функциями). На входе принимаются параметры поля p, mи irreduciblePolynom (неприводимый многочлен над полем GF(). Параметры m и irreduciblePolynom – опциональные.

В конструкторе мы проверяем корректность переданных параметров pи m, и если они некорректные, возвращаем сообщение об этом. В противном случае, создаем и возвращаем созданный объект калькулятора.

Если задается только параметр p, то будет сгенерировано поле GF(p). Если задаются параметры pи m, то сначала будут вычислены неприводимые многочлены над полем с заданными параметрами, которые затем будут предложены пользователю на выбор (если вычисление неприводимых многочленов завершилось неудачно, то пользователю будет возвращено сообщение об этом). После выбора многочлена пользователем, созданный объект будет полностью готов к вычислениям матриц операций.

Многочлены в реализованной программе представлены в виде массивов, где индекс элемента массива это степень x, а элемент массива – коэффициент. Например, многочлену соответствует массив [2, 1, 1, 1].

Далее рассмотрим функцию, возвращающую массив из элементов поля (см. Рисунок 4). Функция принимает один параметр sType(тип поля), далее в зависимости от типа поля мы вызываем функцию либо generateAndGetElementsOfGpField() (см. Рисунок 5), которая создает и возвращает массив из элементов поля GF(p) (0, 1, 2, …, p-1), либо функцию getArrayOfPolynomialsForFiniteField(iMaxPolynomialDegree, aAcceptableCoefficients = [])(см. Рисунок 6), которая возвращает двумерный массив размера , состоящий из всевозможных многочленов для данного поля, представленных в виде массивов, на вход функция принимает два параметра: максимальную допустимую степень полинома и массив допустимых коэффициентов из поляGF(p). В функции getArrayOfPolynomialsForFiniteField используется вспомогательная функция PermutationsWithRepetition(src, len), которая возвращает экземпляр этой функции, содержащий двумерный массив комбинаций из размещения с повторениями  размера .

Рисунок 4. Функция, возвращающая массив элементов поля

Рисунок 5. Функция, возвращающая массив элементов поля из GF(p) от 0 до p-1

Рисунок 6. Функция, возвращающая двумерный массив из многочленов поля GF()

Следующая немаловажная функция – это generateAndGetIrreduciblesPolynomialsForGpm() (см. Рисунок 7 и Рисунок 8). Данная функция вычисляет неприводимые над полем GF() многочлены и возвращает их. Логика данной проста: сначала ищем неприводимые многочлены среди «треугольников» вида , где kлежит в интервале [1,n-1], и добавляем их в возвращаемый массив, если они непроходимы, а затем среди «пятиугольников» вида , где a,b,cлежат в интервале [1,n-1]. Также для полейGF(), где p –  простое нечетное число, написана функция  (см. Рисунок 9) вычисления многочленов вида, где  r является квадратичным невычетом по модулю p. Для того, чтобы проверить сгенерированные неприводимые многочлены на неприводимость была написана функция checkThePolynomialForIrreducibilityWithRespectToTheField(aPolynomForCheck) (см. Рисунок 10), которая работает следующим образом: внутри функции запускается цикл for, в котором мы проходим по всем многочленам конечного поля и делим этим многочлены на сгенерированный неприводимый многочлен, если найдется хотя бы один элемент поля, который поделился нацело, то возвращаем false, если таких элементов не найдено, то возвращаем true.

Рисунок 7. Первая часть функции generateAndGetIrreduciblesPolynomialsForGpm()

Рисунок 8. Вторая часть функции generateAndGetIrreduciblesPolynomialsForGpm()

Рисунок 9. Функция, вычисляющая неприводимые многочлены для полей вида GF()

Рисунок 10. Функция, проверяющая многочлен на неприводимость

Рассмотрим функцию constructAndGetFiniteFieldMatrixForOperation(sOperation), которая генерирует сами матрицы операций для заданного поля. Она принимает на вход один аргумент, который принимает одно из следующих значений: «+», «-», «*», «/», «^», «v», и строит соответствующую матрицу. Для поля GF(p) реализованы следующие операции: сложение, вычитание, умножение, деление, возведение в степень, взятие из-под корня, а для поляGF(): сложение, вычитание, умножение и деление.

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

Функция деления по модулю представлена ниже (см. Рисунок 11). В поле GF(p)для операнда просто вычисляется значение деления по модулю p, а в поле GF( )для операнда сначала вычисляется остаток от деления по модулю на заданный неприводимый многочлен, затем вызываем функцию getDivModuleForCoeffs() (см. Рисунок 12), которая в получившемся многочлене проходится по всем его коэффициентам и приводит их по модулю p.

Рисунок 11. Функция деления по модулю

Рисунок 12. Функция приведения коэффициентов многочлена по модулю p

Функция для подсчета суммы элементов, которая вычисляет сумму элементов, используя вспомогательную функцию (см. Рисунок 13), а затем вычисляет значение деления по модулю p(или по модулю непроходимого многочлена в случае GF()) представлена ниже (см. Рисунок 14).

Рисунок 13. Функция, подсчета суммы элементов

Рисунок 14. Функция подсчета суммы элементов и взятия ее остатка от деления по модулю и функция подсчета суммы

Аналогичную структуру имеет и реализация функции умножения элементов поля (см. Рисунок 15).

Рисунок 15. Функция подсчета произведения элементов и взятия ее остатка от деления по модулю и функция подсчета произведения

Функция подсчета разности имеет следующую логику: сначала ищем противоположный элемент для вычитаемого (такой, что a + b = 0), а затем получаем сумму для найденного противоположного элемента вычитаемого и уменьшаемого (см. Рисунок 16).

Рисунок 16. Функция нахождения противоположного элемента и функция нахождения разности

Функция подсчета частного имеет следующую логику: если делитель равен нулю, то возвращаем NaN, иначе сначала ищем обратный элемент для делителя (такой, что a * b = 1), а затем вычисляем произведение для найденного обратного элемента делителя и делимого (см. Рисунок 17).

Рисунок 17. Функция нахождения обратного элемента и функция нахождения частного

Функция нахождения степени имеет следующую реализацию: получаем два параметра, основание и степень, далее присваиваем результирующей переменной значение основания ,затем проходимся циклом n раз (n равняется значению заданной степени), присваивая результирующей переменной произведение текущего значения переменной назаданное основание, после выполнения цикла возвращаем результирующую переменную. Код функции представлен на Рисунке 18.

Рисунок 18. Функция возведения в степень

Функция вычисления корня реализована следующим образом: получаем два параметра, основание и степень корня, далее проходимся циклом по списку элементов поля и ищем элемент, который при возведении в степень корня даст нам наше основание, если такой элемент найден, то возвращаем его, иначе возвращаем NaN. Код функции представлен на Рисунке 19.

Рисунок 19. Функция вычисления корня

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

1) Существование противоположного элемента

2) Существование обратного элемента для ненулевого элемента

Также используются две вспомогательные функции:

- checkFieldOnUniquenessOfZero(sOperation) (см. Рисунок 21)

- checkFieldOnUniquenessOfOne(sOperation)(см. Рисунок 22)

Функция checkFieldOnUniquenessOfZero(sOperation)проверяет, может ли существовать несколько противоположных элементов ( sOperation = «+»), и может ли возникнуть ситуация, что a * b = 0, где a != 0 и b != 0 (sOperation = «*»).

Функция checkFieldOnUniquenessOfOne(sOperation)проверяет существование и единственность обратного элемента (sOperation = «*»).

Если все условия соблюдены, то функция возвращает «success».

Рисунок 20. Функция проверки поля на аксиомы

Рисунок 21. Функция проверки существования и единственности противоположного элемента

Рисунок 22. Функция проверки существования и единственности обратного элемента

7. Заключение

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

Рабочая версия калькулятора доступна по ссылке: http://galois-calculator.ru.

Исходный код калькулятора доступен на GitHub по ссылке: https://github.com/ArturIBAS/FiniteFieldCalculatorJS.

Список литературы:

1. Wikipedia [Электронный ресурс]: Finitefield — режим доступа: https://en.wikipedia.org/wiki/Finite_field (дата обращения 03.05.2020)
2. Научная Библиотека [Электронный ресурс]: Конечные поля — режим доступа: http://scask.ru/a_book_tec.php?id=79 (дата обращения 05.05.2020)
3. Научная математическая сеть имени Леонарда Эйлера [Электронный ресурс]: Поля Галуа — режим доступа: http://www.mathscinet.ru/catalogue/galois/ (дата обращения 03.05.2020)