Нормальные базисы в конечных полях и их приложения

• Автор: Геут, Кристина Леонидовна
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2015
• Место защиты: Екатеринбург
• Количество страниц: 111 с. : ил.

ОГЛАВЛЕНИЕ
Введение
Глава 1. След, полуслед и задача решения квадратных уравнений в конечных полях характеристики два

§1.1. След и вектор следа

§ 1.2. Пример расчета вектора следа

§ 1.3. Полуслед и расширение конечных полей

§ 1.4. Нормальные базисы в конечных полях и решение квадратных

уравнений

§ 1.5. Решение уравнений на эллиптических кривых

Глава 2. Алгоритмы поликвадратичного расширения бинарных полей

§ 2.1. Симметричное квадратичное расширение
§ 2.2. Общий вид многочленов одного цикла
§ 2.3. Операция А
§ 2.4. Переход к 3 и 5 степеням корня многочлена
§ 2.5. Неприводимые многочлены степени п = р’ц.,
Глава 3. Задача построения неприводимых многочленов
§3.1. Многочлены вида Чебышёва-Диксона
§ 3.2. Неприводимые симметричные многочлены
§ 3.3. Построение неприводимых многочленов простого порядка
§ 3.4. Построение рекурсий первого порядка
Заключение
Литература
Приложение А
Приложение Б

Введение
Работа посвящена исследованию объектов конечных полей, алгоритмам поликвадратичного расширения полей и построения нормальных базисов, постановке и решению задач последовательной генерации неприводимых многочленов, а также эквивалентных задач построения неприводимых многочленов и проверки простоты чисел.
Актуальность темы исследования. Теория конечных полей была построена в работах Ферма, Эйлера, Лежандра, Гаусса, Галуа, Диксона и других выдающих ученых [11, 12], и до последней четверти 20-го века развивалась как область чистой математики, но в связи с потребностями кодирования и криптографии в настоящее время активно развиваются прикладные аспекты теории. Вопросам эффективной реализации арифметики в конечных полях посвящено много работ и специальных книг, отечественных и зарубежных авторов [3, 5-7, 12-13, 15, 20, 22-23, 34, 38-43].
Неприводимые многочлены, корни которых образуют базис для представления элементов конечных полей, аналогичны простым числам [13, 46-47]. Они нашли свое применение в различных областях математики, информационной техники и защите информации. Использование свойств неприводимых многочленов [21, 25-26, 44-46] позволяет максимизировать эффективность компьютерной реализации арифметики в конечных полях, что имеет особое значение для криптографии и теории кодирования. Таковы, например, реализация электронной цифровой подписи на эллиптических кривых [9-10, 20, 34-35, 38, 40-43]; коды Рида-Маллера, Рида-Соломона и другие [2, 6, 18, 24]; программирование дискретных устройств [19, 23, 29-30, 36, 39]; современные стандарты шифрования [28]. Для нахождения таких многочленов нет определенного (детерминированного) алгоритма, так что их построение производится подбором, т.е. вероятностными алгоритмами, что требует временных затрат и объемных вычислений. Коэффициенты многочленов, как
элементы конечных полей характеристики два, можно интерпретировать в многобитовые последовательности для передачи по современным каналам связи [27]. Поэтому важной задачей становится использование неприводимых многочленов больших степеней, задающих эти поля.
При организации транспортного производства используется более двух десятков видов связи. Все шире внедряются беспроводные технологии, такие как GSM-R, TETRA, CDMA и др. При этом важно отметить, что именно беспроводные технологии наиболее уязвимы с точки зрения информационной безопасности. Перехват информации в беспроводных системах не требует физического контакта с линией связи, что существенно упрощает задачу несанкционированного доступа к информации [27, 29].
В устройствах связи ОАО «РЖД» предполагается применение системы GSM-R, как основной системы технологической радиосвязи на участках высокоскоростного и скоростного движения, а также на основных транспортных магистралях. В системах GSM, GSM-R в качестве алгоритмов шифрования используются шифры семейства А5 [39]. Стандарт шифрования А5/1, используемый в GSM-R, можно считать примером кодирующего аппарата с обратной связью и без памяти.
Одним из таких кодирующих аппаратов является регистр сдвига с линейной связью (PCДОС, Linear feedback shift register, LFSR). Он состоит из двух частей: собственно регистра сдвига и функции обратной связи. Регистр состоит из битов, его длина - количество этих бит. Новый крайний слева бит определяется функцией остальных битов. На выходе регистра оказывается один, обычно младший, значащий бит. Период регистра сдвига - длина выходной последовательности до начала её повторения.
Для оптимизации работы конечного автомата в качестве характеристического многочлена используют «малочлены» (идеальный случай -трехчлены), и лучше - примитивные (т.е. максимального порядка). С точки зрения кибернетики минимизация обратных связей существенно повышает работу этих дискретных устройств.

2 n S
Если же r,s е GF(2' ), то абсолютный след Тг элемента равен а = — в поле

GF(2") вычитается уже по формуле 7>(-^-)= Тг(а) =а + а2 + а +

+ а +а +а , и поэтому если а е GF(2"), то а = а и след его в GF(2") равен нулю Тг(а) = 0 в поле GF(2"), то решение уравнения х + гх + 5 = О существует.
Рассмотрим решение квадратного уравнения вида: х2 + х = z
Выразим х через z:

— , 4 , 16 , 64 , ,
х = г + г +г +г + ... + г
Тогда х2 будет равен:
2_2, 8, 32, , 2п
х — г + ... + 2 .
Так как г1" = г, сумма х + х2 = г + г* + г]6 + + ... + г2 + г2 + г8 +
+ г12 + ... + г2 = Тг(г) + г.
Тг(г) = 0 —»х2 + х — г —* х = г+ г4 + г16 + ... + г2 = 8г(г).
Любое квадратного уравнение в поле характеристики два приводится к стандартному виду х2 + х = г, где г - данный элемент этого поля, х - искомый корень [9, 23]. В книге [9, с.80] представлен пример такого приведения: уравнение вида У2 + хУ + Дх) =0 при подстановке У = х2 принимает вид 12х2 +
+ ^2 + Дх) =0, и при х Ф 0 оно эквивалентно уравнению У2 + У + о = 0, где
о =Дх)х2.
Рассмотрим применение формулы полуследа для решения квадратного
уравнения наглядно (рис. 1.1-1.2). Представим х = , где 5 = 0, 1, 2, ..., п - 1. В
поле ОР(2") для нечетной степени п получаем следующие значения 5:
0¥(2")->з = {0,2, 4, 1}
5 + 1 = {1, 3, 5, ..., п}