Арифметический алгоритм решения квадратных уравнений в конечных полях характеристики два Текст научной статьи по специальности «Математика»

Аннотация научной статьи по математике, автор научной работы — Глуско Кристина Леонидовна, Титов Сергей Сергеевич

Рассмотрены арифметические задачи в конечных полях характеристики два , которые могут иметь криптографические приложения. На основе построения нормальных базисов с помощью симметричного квадратичного расширения предложен алгоритм решения квадратных уравнений через обобщённую формулу полуследа. Рассмотрены примеры

Похожие темы научных работ по математике , автор научной работы — Глуско Кристина Леонидовна, Титов Сергей Сергеевич

Arithmetic algorithm for solving quadratic equations in finite fields of characteristic two

The paper considers the problem of arithmetic in finite fields of characteristic two, which may have cryptographic applications. Based on the construction of normal bases by using a symmetric quadratic extension of an algorithm for solving quadratic equations by the generalized formula semitrace. Examples considered.

Текст научной работы на тему «Арифметический алгоритм решения квадратных уравнений в конечных полях характеристики два»

УДК 512.624: 003.26 Кр.Л. Глуско, С.С. Титов

Арифметический алгоритм решения квадратных уравнений в конечных полях характеристики два

Рассмотрены арифметические задачи в конечных полях характеристики два, которые могут иметь криптографические приложения. На основе построения нормальных базисов с помощью симметричного квадратичного расширения предложен алгоритм решения квадратных уравнений через обобщённую формулу полуследа. Рассмотрены примеры.

Ключевые слова: конечное поле характеристики два, нормальный базис, формула полуследа квадратное уравнение.

Задача решения квадратных уравнений в конечных полях

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

В теории конечных полей одним из актуальных вопросов является решение квадратных уравнений, что нашло применение и в других областях дискретной математики. В эллиптической криптографии, к примеру, это позволяет в два раза уменьшить количество бит для хранения точек эллиптической кривой [1, 2] при реализации криптографических примитивов.

Имеется отличие в задачах решения квадратных уравнений в полях различной характеристики. Решение квадратных уравнений в простых полях нечётной характеристики приводит к задаче вычисления символа Лежандра [2]. Решение же квадратных уравнений в полях характеристики два имеет свою специфику, поскольку решаемое уравнение в стандартном виде оказывается линейным.

Рассмотрим алгоритм решения квадратных уравнений в конечных полях характеристики два. Для полноты изложения дальнейших рассуждений напомним некоторые теоретические понятия.

След - линейная операция ТгР/К, отображающая элементы поля Р в элементы поля К, обладающая свойствами идемпотентности, коммутативности, ассоциативности и дистрибутивности [3]. Различают понятия абсолютного и относительного следа элемента поля. В поле бр(д), где q = рп, фор-

мула абсолютного следа элемента поля имеет следующий вид: Тг(2) = 2 + 2 + 2р +. + 2р Є ОР^) и может принимать значения .

Если поле Р = ОР^т) является расширением поля К = ОР^), то речь уже идет о вычислении относительного следа ТгР/К(2) элемента поля ОР^т). Значение следа элемента часто является определяющим для выполнения тех или иных условий.

Любое квадратное уравнение в поле характеристики два приводится к стандартному виду х2 + х = = 2, где г - данный элемент этого поля; х - искомый корень [1, 2]. В книге [2, с. 80] представлен пример такого приведения для несуперсингулярных эллиптических кривых: уравнение вида У2 + хУ + +Дх) = 0 при подстановке У = хТ принимает вид + х12 + Дх) = 0, и при х Ф 0 оно эквивалентно

уравнению Т + Т + о = 0, где о = Дх)/х

Для решения такого квадратного уравнения при Тг(2) = 0 в конечных полях ОР(2п) при нечетном

п используется так называемая формула полуследа: Бг(2) = х = 2 + 2+ 2 + . + г ; причём 2 =

Утверждение 1. Формула полуследа дает решение квадратного уравнения с нулевым следом в поле ОР(2п), где п нечетное.

В книге [1] решение квадратного уравнения в полях ОР(2п), где п четное, сводится к системе линейных уравнений, вычисление которой довольно громоздко и требует временных затрат. Трудность задачи поиска формулы решения для четной степени иллюстрирует следующее

Утверждение 2. При четном п не существует линеаризированного многочлена вида 2 = ^ а

(Б - подмножество в ), дающего решение квадратного уравнения 22 + 2 = а.

Можно ставить задачу и как поиск многочлена, корень которого является решением квадратного уравнения

2 = а в поле ОР(2п) [5, 6], где п четное, при этом стоит еще раз отметить, что в бинарных полях квадратное уравнение является линейным.

Для поиска решения уравнения больших степеней можно использовать идею расширения полей: зная формулу решения квадратного уравнения в полях ОР(2п), где п нечетно, и, зная формулу решения этого уравнения в полях ОР(2*), мы можем найти формулу решения в поле ОР(2пк), к = 2Г, г = 1, 2, 3, . .

Построение нормальных базисов с помощью квадратичного симметричного расширения

Решение уравнения может быть представлено в стандартном базисе, т.е. базисе вида , но мы воспользуемся разложением в нормальном базисе, т.е. базисе вида , где X и а - корни неприводимого многочлена степени п. Задача построения нормальных базисов является нетривиальной, например, требуется, чтобы Тг (в) = 1, поэтому для построения ба-

зиса используем операцию симметричного квадратичного расширения, формула которого такова: а = в + в- , где а является элементом поля Р, в является элементом поля К, а поле К является расширением поля Р.

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

Возьмем нормальный базис , а Є ОР(2п), примем в Є ОР(2 п) как результат

симметричного квадратичного расширения поля ОР(2п), то есть а = в + в-1; таким образом, в -

корень квадратного уравнения в2 + в + 1 = 0. Пусть - корень многочлена Д(х) степени п. Из

нормальности базиса вытекает, что Дх) неприводим. Элемент в является корнем многочлена Р(х)

степени 2п, связанного с Дх) соотношением Р(х) = хДх + х-1). Многочлен Р(х) = хпД(х + х-1) является

самовозвратным. Исследуем вопрос: когда множество также будет нормальным

базисом, но уже в поле ОР(22п)? Если Р(х) приводим, то все степени элемента в лежат в поле ОР(2п)

и поэтому не могут образовывать требуемый базис. Многочлен Р(х) будет неприводимым тогда и

только тогда [7], когда след а равен единице; в этом случае справедливо равенство в = в .

В таком случае потребуем от а равенства единице её антиследа, то есть следа а-1: Тг( а-1) = а-1 + . +

+ а = 1 ф 0. Это требование является существенным.

Из определения нормальности базиса следует: а + . + а ф 0, т.е. (абсолютный) след элемента равен единице, более того, нормальность исходного базиса равносильна тому, что для

любого подмножества