Введение 3
1. Цель работы 5
2. Используемые сведения о конечных полях 6
3. Теоретические оценки времени работы различных алгоритмов извлечения
квадратного корня 18
4. Создание приложения для подсчёта времени работы различных
алгоритмов извлечения квадратного корня 33
5. Оценка среднего времени поиска корней уравнений восьмой и девятой
степени в поле Галуа 38
Заключение 40
Литература 41
Приложение42
Конечное поле - одно из понятий, наиболее широко используемых в теории чисел, теории групп, алгебраической геометрии и криптографии. К введению этого понятия достаточно близко подходили такие видные математики как Жозеф Луи Лагранж, Пьер Ферма, Леонард Эйлер и Адриен Мари Лежандр. Однако наиболее значимым в общую теорию конечных полей по праву считается вклад Галуа. В 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, и для разрешения которого необходимо уметь достаточно быстро решать квадратные уравнения в конечных полях.
