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

Конечное поле - одно из понятий, наиболее широко используемых в теории чисел, теории групп, алгебраической геометрии и криптографии. К введению этого понятия достаточно близко подходили такие видные математики как Жозеф Луи Лагранж, Пьер Ферма, Леонард Эйлер и Адриен Мари Лежандр. Однако наиболее значимым в общую теорию конечных полей по праву считается вклад Галуа. В 1830 году он публикует работу "Замечание о решении численных уравнений" (Sur la theorie des nombres) во французском математическом журнале "Бюллетень наук о математике господина де М.Фруссака", (Bulletin des sciences mathematiques de M. Ferussac) которая впоследствии станет основой общей теории конечных полей.
В "Замечание..." Галуа вводит воображаемый корень сравнения F(x) = 0 mod(p), где F(x) — неприводимый, то есть не имеющий корней, по модулю p многочлен. Рассмотрев после этого выражение А = а0 + a1i + a2i2 + —+ av_1iv—1 , где а0, а0 ... av-1 - некоторые числа по модулю р. Из этого следует, что количество сочетаний с повторениями, которое может принимать A равно N = pv. Далее Галуа сумел доказать, что эти числа образуют поле и группа этого поля по умножению является циклической - что дало основания для введения понятия примитивного элемента поля.
Используя созданный им математический аппарат, Г алуа исследовал проблему решения произвольных уравнений в радикалах и нашёл необходимое и достаточное условие того, чтобы корни уравнения выражались через радикалы.
Теорема Галуа. Решения полиномиального уравнения Р(х) = 0 выражаются в радикалах тогда и только тогда, когда группа Г алуа данного уравнения разрешима.
Данная работа будет посвящена методам решения уравнений, сами
коэффициенты которых (как впрочем и корни) уже являются элементами поля.

Купить

Конечные поля нашли себе широкое применение в теории кодирования. Они используются в кодах исправляющих ошибки, таких например как БЧХ коды (коды Коды Боуза — Чоудхури — Хоквингемакоды) в частности в коде Рида- Соломона, позволяющем исправлять ошибки в блоках данных.
Теория конечных полей была применена при создании блочного шифра «Кузнечик» (ГОСТ Р 34.12-2015} — симметричного алгоритма блочного шифрования с длиной ключа 256 битов и размером блока 128 битов, использующего для генерации раундовых ключей сеть Фейстеля.
Собственно решение квадратных уравнений в конечных полях, которому посвящена данная работа, чаще всего используется в криптографии при построении таблиц подстановок (S-box} и построении эллиптических кривых, которые над неким полем Fq определяются уравнением:
у2 + а4ху + а3у = х3 + а2х2 + а4х + а5,
в котором а4, а2, а3, а4, а5 Е Fq, и для разрешения которого необходимо уметь достаточно быстро решать квадратные уравнения в конечных полях.

Купить