Содержание к диссертации
Введение
Глава 1. След, полуслед и задача решения квадратных уравнений в конечных полях характеристики два 23
1.1. След и вектор следа 23
1.2. Пример расчета вектора следа 30
1.3. Полуслед и расширение конечных полей 33
1.4. Нормальные базисы в конечных полях и решение квадратных уравнений 38
1.5. Решение уравнений на эллиптических кривых 45
Глава 2. Алгоритмы поликвадратичного расширения бинарных полей 50
2.1. Симметричное квадратичное расширение 50
2.2. Общий вид многочленов одного цикла 54
2.3. Операция A 57
2.4. Переход к 3 и 5 степеням корня многочлена 60
2.5. Неприводимые многочлены степени n = pq 62
Глава 3. Задача построения неприводимых многочленов 68
3.1. Многочлены вида Чебышва-Диксона 68
3.2. Неприводимые симметричные многочлены 74
3.3. Построение неприводимых многочленов простого порядка 79
3.4. Построение рекурсий первого порядка 84
Заключение 90
Литература 92
- Полуслед и расширение конечных полей
- Решение уравнений на эллиптических кривых
- Переход к 3 и 5 степеням корня многочлена
- Построение неприводимых многочленов простого порядка
Полуслед и расширение конечных полей
Данная глава посвящена решениям задач в конечных полях характеристики два, изучению их свойств. Рассмотрены понятия следа и вектора следа. Доказаны утверждения, которые дают более четкое представление о быстром и упрощенном нахождении вектора следа неприводимого многочлена.
Во второй части рассмотрена формула полуследа и сформулированы утверждения о ее применении для решения квадратных уравнений в конечных полях GF(2n). Доказана теорема о нормальном базисе в поле GF(22n). Приведено решение квадратного уравнения в поле вида GF(2nk). Нормальность базиса позволяет получить эффективную алгоритмическую реализацию арифметики конечных полей.
След имеет большое значение в кодировании, передаче информации и информационной технике, а также прикладной математике, компьютерной алгебре. Эффективная реализация вычислений, связанных с функцией следа, лежит в основе многих алгоритмов дискретной математики, применяемых к объектам конечных полей.
Известно, что след - единственная операция, отображающая элементы поля F в элементы поля К, обладающая всеми этими свойствами [23].
Для вычисления следа элемента поля необходимо поразрядно сложить соответствующие строки. Для поля Галуа GF(2") номера строк получаются умножением номера предыдущей строки на два и приведением по модулю Т - 1, где п - старшая степень многочлена (так, для многочлена пятой степени это будет модуль 25 - 1 = 31). Получившиеся после сложения числа нужно привести по модулю два, первая цифра (нулевой бит) будет следом для данной строки -элемента поля GF(2W) [24].
Но, оказывается, существует более простой способ вычисления следа [9]. Он заключается в том, что изначально вычисляется так называемый вектор следа для данного многочлена. Значение функции следа для элемента поля GF(2") равно сумме (по модулю 2) элементов вектора, получаемого как поразрядное произведение (конъюнкция) элементов вектора и вектора следа. Элементы ti, i = 0, …, n – 1 вектора следа (t0, …, tn–1) образуются суммированием по модулю два элементов таблицы, расположенных по диагонали (слева направо и сверху вниз) в соседних векторах i, i+1, …, i+n–1 [65]. Строки вычисленного вектора следа и строки в таблице степеней корня многочлена перемножаются скалярно как векторы над полем из двух элементов, поэтому для упрощения и ускорения вычислений следов хотелось бы получить вектор следа вида 1000... 0, в котором только первый бит не равен нулю. Оказывается, это зависит от вида многочлена. Поставим и решим эту задачу для многочленов нечетных степеней [65-66].
Так как п – нечетное число, то количество строк с нулевой по (п – 1)-ю будет нечетным, в клетках по диагонали таблицы будут стоять единицы и их сумма (по модулю два) будет равна единице. При расчете следующих цифр вектора следа количество единиц будет четным, так как единицы будут начинаться только в п-й строке в k-й позиции, а количество столбцов от k до (п – 1) – четное число, соответственно сумма (по модулю два) битов в каждой такой диагонали будет равна нулю. При расчете последней цифры счт начинается с (п – 1)-й строки, где заведомо будет стоять ноль, и заканчивается на строке (2n – 2) (количество строк с n-й по (2n – 2)-ю четное). Единицы появляются начиная с k-го столбца и заканчиваются в (п – 1)-м, количество этих столбцов – число четное, поэтому сумма (по модулю два) будет равна нулю. Во всех последующих клетках по диагонали левее k-го столбца будут стоять нули и сумма (по модулю два) будет равна нулю.
Вычисление неприводимых трехчленов имеет большое значение: к примеру, реализация линейных регистров сдвига в виде кодера-декодера с упрощением операций над используемыми в них трехчленами становится наиболее эффективной, так как используется всего два отвода для обратных связей. Утверждение 1.1. Вектор следа при нечетном п будет иметь вид 1000...0, если и только если все показатели степеней членов неприводимого многочлена нечетные, за исключением нулевой.
Доказательства схожи с теми, что были приведены для леммы. Так как п – нечетное число, то количество строк с нулевой по (n – 1)-ю будет нечетным, в клетках по диагонали таблицы будут стоять единицы и их сумма (по модулю два) будет равна единице. Для наглядности рассмотрим таблицу степеней корня данного многочлена в общем случае (таблица 1.2).
Решение уравнений на эллиптических кривых
В многочленах четных степеней появятся две степени подряд, поэтому при сложении z + z1 некоторые позиции сократятся и не дадут полной формулы, аналогичной для многочленов нечетной степени.
В книге [9] вычисление решения квадратного уравнения в полях GF(2"), где п четное, сводится к системе линейных уравнений, вычисление которой довольно громоздко и требует временных затрат. Нетривиальность задачи поиска формулы решения для четной степени иллюстрирует следующее Утверждение 1.5. При четном п не существует многочлена вида d а , дающего решение квадратного уравнения z1 + z = а. keK Можно ставить задачу как поиск многочлена, корень которого является решением квадратного уравнения z + z в поле GF(2"), где п - четное. Стоит отметить, что в поле характеристики 2 квадратное уравнение будет являться линейным.
Для поиска решения уравнения больших степеней можно использовать идею расширения полей: зная формулу решения квадратного уравнения в полях GF(2"), где п - нечетно, и, зная формулу решения этого уравнения в полях GF(2 ). Идея такого расширения в поле GF(2" ), к = 2\ s = 1, 2, 3, … представлена на рисунке 1.3. Г) GF(28w) ПҐ V GF(24w) GF(28) Ч \f V) GF(22w) GF( 2 4) Л ( l V) GF(2") GF( 2 2) Л GF(2) Рисунок 1.3. Схема расширения конечных полей Еще одним теоретическим аспектом в вопросе решения квадратных уравнений в конечных полях являются линеаризированные и аффинные многочлены [7]. Определение 1.2. Многочлен L(z) над GF(pm) называется линеаризированным, если (--) = ! 4--" [7, с.250]. Определение 1.3. Многочлен A(z) над GF(pm) называется аффинным, если A{z) = L{z) - и, где L{z) - линеаризированный многочлен, аиЄ G(pm) [7, с.251]. В частном случае квадратного уравнения над GF(2ra) можно избежать перехода к системе линейных двоичных уравнений. С помощью соответствующей замены переменных квадратное уравнение общего вида без кратных корней можно привести к виду у2 + у = и. Линеаризированная часть этого многочлена имеет один и тот же вид для всех квадратных уравнений над заданным полем, так что решения всех этих уравнений могут быть найдены и фиксированы в виде соответствующей матрицы.
Уравнение у1 + у = и имеет решение в GF(2ra) тогда и только тогда, когда Тг(и) = 0. Пусть - произвольный элемент поля степени m над GF(2), а J-элемент для которого 7 ( ) = 1. Тогда для г = 0, 1, 2, …, m - 1 можно найти такое У , что
Особенность вычислений в конечном поле состоит в необходимости выбора представления элементов – от него существенно зависит способ реализации, а, следовательно, сложность и глубина логической схемы. Потенциально возможны разные представления, но практически используются в основном два, а именно представления в стандартных базисах, т.е. базисах вида {1, , 2, 3, …, n–1}, и нормальных базисах, т.е. базисе вида {, 2, 4, 8, …, 2n-1 }, где и – корни неприводимого многочлена степени n. Также могут быть использованы производные от них базисы. Наиболее широко используемым является представление в стандартном базисе – элементы поля в нем представляются многочленами, арифметические операции с которыми выполняются по модулю неприводимого многочлена, определяющего этот базис [23]. В работе рассмотрено разложение в нормальном базисе, т.е. базисе вида (Р, р2, Р4, Р8, ..., р2 -1 }. Это необходимо, например, для решения квадратных уравнений в полях чётных степеней, что представляют собой более сложную задачу, чем для нечётных степеней, как показано выше. Задача построения нормальных базисов является нетривиальной, например, требуется, чтобы 7 (Р)=1, поэтому для построения базиса используем операцию симметричного квадратичного расширения.
Пусть а - корень многочлена Дх) степени п. Из нормальности базиса вытекает, что Дх) неприводим. Элемент р является корнем многочлена F{x) степени 2п, связанного с Дх) соотношением F(x) = xnf[x + JT1). Многочлен F(x) = xnf[x + JC"1) является самовозвратным. Исследуем вопрос, когда множество { , 2 , ..., 2" } также будет нормальным базисом, но уже в поле GF(22w). Если F(x) приводим, то все степени элемента лежат в поле GF(2W) и поэтому не могут образовывать требуемый базис. Многочлен F(x) будет неприводимым тогда и только тогда [9], когда след
Переход к 3 и 5 степеням корня многочлена
При умножении элементов разноименные дают 4 слагаемых, а возведение в квадрат - 3 слагаемых и 4 единицы, причем — пар дают удвоенные слагаемые, которые совпадают с одним из элементов орбиты (диагонали), поэтому при дальнейшем умножении на остальные (т - к) элементов квадрат дадут только 2 из 4-х слагаемых. Аналогична ситуация для других — пар, у которых повторится один из элементов произведения, поэтому они дадут 43 единиц. Остальные — пар дадут 44 единицы. з зависит от кратности 3-м числа т, если – целое, то появится цикл длины - (ситуация аналогична для всех ,-), остальные же орбиты будут длиной т и содержать по 3 элемента. Остается рассчитать количество единиц, которые внесут положительный вклад в з, и количество остальных слагаемых, объединив их по т штук, которые внесут вклад отрицательный. Тройки K ax /г дадут квадрат в том случае, если / совпадет с одним из элементов {{h + 1), {h - 1), {h + і), {h - і)}, иначе - 16 слагаемых, которые при циклическом сдвиге на т дадут (–\)т. Аналогично можно найти остальные коэффициенты .
Идея построения простых чисел заключается в биквадратичном расширении. На нижнем слое лежит один и тот же многочлен X2 + X + 2 (см. выше). Операцию всегда можно сделать, независимо от простоты и приводимости, поэтому для многочленов Чебышва-Диксона есть рекурсия. Для искомой операции очевидной рекурсии нет, потому что числа, получаемые таким способом не всегда простые:
К примеру, для чисел, которые вычисляются по формуле р = 4т + 1, где т - натуральное число, получаются следующие неприводимые многочлены; jw = l5p = 5, Gi() = +l; т = 2, р = 9 - не простое, G2() = 2 + + 1 - приводим над GF(3); т = 3,р= 13, G3() = 3 + 2 - 4 +1; т = 4,р= 17, G4() = 4 + 3 - б2 - +1, по mod 3 G4() совпадает с f4(X); т = 5,р = 21 - не простое; т = 6, р = 25 - не простое; т = 7,р = 29, G7() = 7 + 6 - 125 - 74 + 283 + 142 - 9 +1 и т.д. Таким образом, получается процедура последовательного вычисления многочленов степени т, неприводимость которых связана с простотой соответствующего числа/? = 4т + 1.
Проверка простоты числа Ферма р = 22 +1 эквивалентна генерации неприводимых симметричных многочленов, имеющих особое значение в кодировании (теорема Мирончикова [23, 25]) степени п = 2к + 1 и порядка р = 22 +1. Действительно, очевидны следующие наблюдения. Утверждение 3.2. Если представить число Ферма р как порядок симметричного неприводимого многочлена Дх) степени п, то простота р равносильна равенству р порядков всех Дх). Если же р = 1т не простое, то существуют Дх) порядка р, I и т. ord f(x)-\ 22k
Дальнейшая подстановка не дает аналогичного результата (получившиеся числа не простые), других простых чисел Ферма не известно: k = 5, p = 4294967297 = 6416700417, из которых 10 многочленов deg f = 64, ord f = 641; k = 6, p = 18446744073709551617 = 27417767280421310721. Наличие хотя бы одного неприводимого симметричного многочлена степени п = 2 не максимально возможного порядка р = 2 +1 равносильно непростоте числа Ферма/?. Генерация неприводимых многочленов возможна разными способами. В работах [50, 54, 71] рассмотрено поликвадратичное расширение полей посредством применения, так называемой, операции A: F(X) = f{X2+X). Элементы базиса {, 2, 4, …, а2 } являются корнями одного и того же многочлена степени п, это связано с тем, что операция возведения в квадрат является автоморфизмом поля. Для перехода из расширенного поля в расширяемое необходимо выполнить операцию = А–\ Рассмотрим другой способ генерации симметричных неприводимых многочленов посредством переходов к 3 и 5 степеням корня многочлена [32]. Причем для многочленов степени dee f = 32 через = 211 = 2048 шагов цикл замкнется, т.к. 3 и 5 - первообразный корень по модулю 25. Аналогичная задача встречается в книге [13], где требуется доказать, что р = 22 +1 простое тогда и только тогда, когда g = 3 - первообразный корень по mod р. Поиск этих простых чисел является очень важной задачей.
Посредством переходов к 3 и 5 степеням корня многочлена были сгенерированы все симметричные неприводимые многочлены степени deg/= 32. Приведем первые многочлены, полученные с помощью таких переходов:
Построение неприводимых многочленов простого порядка
Числа Ферма тесно связаны с умножением точек эллиптических кривых. Для суперсингулярных кривых [10, с.21] Еи Е2, Еъ - три класса неизоморфных на GF(2") при нечетных п, при четных п имеется 7 классов [42, с.70]. Порядок группы определяется по теореме Хассе-Вейля [9, с.105, теорема 2.3.1], а строение групп - по теореме 2.3.3.[9, с.109]. сложение и удвоение точек дано алгоритмом неприводимых над GF(2) периодических многочленов степени 2к+\ получившихся посредством операции А из неприводимых над GF(2) периодических многочленов степени 2к+\ порядок которых делится на три, а след равен единице; Fr{v) есть произведение всех самовозвратных многочленов, соответствующих этим периодическим многочленам.
Пусть vs может быть выражена для каждого s как функция от v, т.е. vs = vs(v). Тогда vs(vf(v)) = vst(v) = vf(vs(v)), т.е. получается система коммутирующих рациональных функций на конечном поле. Для кривой Еі: если у2 + y = t, Tr(t) = 1, t є GF(2W), то Tr 1 = 7 (0 = 1, Этот подход дает еще одну задачу, эквивалентную задаче проверки простоты чисел Ферма.
Аналогично, если т - простое число, то в поле GF(2ra) нет подполей, кроме простого и поэтому непростота числа 2т - 1 равносильна наличию неприводимого многочлена степени не максимального порядка (см. выше, глава 1). Следовательно, поиск простых чисел Мерсенна q = 2т - 1 эквивалентен генерации примитивных многочленов степени т и порядка 2т - 1:
Утверждение 3.4. Примитивность всех неприводимых многочленов степени т равносильна простоте числа 2т - 1.
Построение неприводимых многочленов простого порядка Актуальность тематики расширения бинарных полей тесно связана с изменением архитектуры в вычислительной технике: переход от битовой архитектуры к байтовой, от 32-х разрядной к 64-х, а в последствии к 1024-х битовой.
Развитие в области информационных технологий увеличивает функционал видеокарт и эффективность работы. За счет распараллеливания операций обеспечивается мультибитовость. Поэтому гибкая аппаратная компоновка видеокарт, благодаря рациональной организации отводов регистров сдвига, может позволить реализовать широкий спектр возможностей, в том числе и взлом шифров.
Еще одной сферой применения многочленов в бинарных полях являются дискретные устройства, период работы которого определяется характеристическим многочленом. Так, к примеру, для программирования конечного автомата цикла ord/ 2w- 1, необходим непримитивный многочлен степени п [23-24].
Для поиска всех неприводимых многочленов данного простого порядка предложен следующий алгоритм.
Пусть р - простое число, и пусть gp–\{x) разлагается в произведение симметричных многочленов степени 2к; тогда имеем gp–\(x) делит g2 , т.е. 2 + 1 0 (mod;?), т.к. р = огё/дляД ), делящего gp–x{x).
Обратно, пусть р - простое число, к - наименьшее такое, что 2 1 (mod/?). Тогда gp–\(x) делит g2 (и такая степень двойки в индексе - наименьшая возможная), отсюда gp–\{x) разлагается в произведение неприводимых симметричных многочленов степеней 2т, где — нечетно, отсюда к = т, т.к. ясно, что если р - простое число и gp–\{x) разлагается в произведение неприводимых многочленов qj(x) (/ 1) одной и той же степени. Пусть deg/=«, ord f = p, f{x) неприводим, тогда х = р в Kf GF(2"), и для любого уФ1,ує х имеем у = х (т.к. р простое число); следовательно, никакой уФ1,ує х не принадлежит собственному подполю поля GF(2") К/ , т.е. у удовлетворяет неприводимому уравнению той же степени п [22-23].
Степень таких неприводимых многочленов определяется как наименьшая натуральная степень п такая, что 2 =l(mod р). Соответственно их количество многочленов s(x) = 2V mod/? и ( ) = $ t(x) = j xl (выбор формулы г=1 г=0 ;=1 зависит от значения следа многочлена qj(x)). Если же таких многочленов qj(x) 2, то задача сложнее, т.к. НОД в таком случае будет произведением всех qj (x) с заданным значением следа Tr(x) = {0, 1} [4]. Итак, получено Утверждение 3.5. Построение неприводимых многочленов степени n простого порядка p над GF(2n) равносильно последовательности вычислений степеней двойки по модулю p и применению алгоритма Евклида.
Для примера рассмотрим многочлены ord f = 73. Степень многочленов такого порядка является решением уравнения 2n 1(mod 73) (табл.3.2): Таблица 3.2. Решение уравнения 2n 1(mod 73) n 0 1 2 3 4 5 6 7 8 9 2n (mod 73) 2 8 32 55 Получаем n = deg/jc) = 9, (73 - 1)/9 = 8, т.е. 8 неприводимых многочленов порядка ord fix) = 73 и степени deg fix) = 9, которые можно представить в виде х9 + гх + 2х7 + 6 + 4X5 + 4 + вх3 + 7х2 + 8 + 9, где ,- = {0, 1}. Произведение таких многочленов/ ) дает сумму всех степеней от 0 до 72 (или от 1 до 73) r(jt) = JV. 2fc 1 (mod 73), поэтому в данном примере 4 пары взаимовозвратных многочлена. 9
На рисунке 3.1 представлен регистр сдвига с линейной связью (РСЛОС, Linear feedback shift register, LFSR), которому соответствует характеристический многочлен х9 + х + 1 с периодом равным 73 тактам, на О подается входная последовательность бит, вход С2 - тактовый. При включении регистра LFSR карты PnP4 запускается протокол с подачей на вход нулевых битов C1 = 0 (автономный режим). Стоит отметить, что возможно использование не только одного регистр сдвига, но и каскада устройств для достижения нужного объема выходных бит, как это происходит в стандарте GSM: 64 бита за счет 3-х регистров – 19, 22, 23 такта соответственно.
Регистр сдвига, по своей сути, – инструмент для генерации псевдослучайной последовательности. Выходная последовательность регистра сдвига является уникальной и может быть использовано в целях аутентификации при передаче информации по каналам связи. Примерами использования можно назвать стандарт мобильной связи GSM, телевизионные системы семейства MAC/packet, системы АТ и С на железнодорожном транспорте (отслеживание положения локомотива, связь диспетчера с машинистом, оформление и проверка проездных документов). Для фиксации размеров этой последовательности при реализации конкретных задач необходимо подобрать неприводимый многочлен фиксированного порядка.