On the solution of quadratic equations in binary fields.pdf Передача информации в современных каналах связи основана на использованиимногобитовых последовательностей, которые можно интерпретировать как элементыконечных полей. Поэтому решение задач в бинарных полях больших степеней и пред-ставление этих решений в виде битовых строк является важной проблемой. Решениеквадратных уравнений в конечных полях используется в разных областях математи-ки и защиты информации. В эллиптической криптографии, к примеру, это позволяетв два раза уменьшить количество бит для хранения точек эллиптической кривой приреализации криптографических примитивов [1, 2].След - линейная операция Tr^/к, отображающая элементы поля F в элементы по-ля K, обладающая свойствами идемпотентности, коммутативности, ассоциативностии дистрибутивности [3].Различают понятия абсолютного и относительного следа элемента поля. В по-ле GF(q), где q = pn, Tr(z) . GF(q) и может принимать значения 0, 1, ..., p - 1,формула абсолютного следа элемента поля имеет видTr(z) = z + zp + zp2 + . . . + zp n - 1.Значение следа элемента часто является определяющим для выполнения тех илииных условий. Любое квадратное уравнение в поле характеристики два приводитсяк стандартному виду x2 + x = z, где z - элемент данного поля, x - искомый корень [1].Для решения такого квадратного уравнения при Tr(z) = 0 в конечных полях GF(2n)при нечётном n используется так называемая формула полуследа:Sr(z) = x = z + z4 + z16 + . . . + z2 n - 1.Утверждение 1. Формула полуследа дает решение квадратного уравнения с ну-левым следом в поле GF(2n), где n нечётное.Утверждение 2 [1, 4]. При чётном n не существует линеаризированного много-члена вида z = a2 (S - подмножество в { 0 , 1 , . . . , n - 1}), дающего решение квад-ses 2 ратного уравнения z2 + z = a.Решение квадратного уравнения может быть представлено в стандартном базисе,т. е. в базисе вида {1, А, А2, А3 ,... , An - 1 } , но мы воспользуемся разложением в нормаль-ном базисе, т. е. в базисе вида { в , в2, в4, в 8 , . . . , в2" }, где А и в - корни неприводимыхмногочленов степени n [2]. Отметим, что построение нормальных базисов является за-дачей нетривиальной.Для построения базиса {в, в2, в4, в 8 , . . . , в2" 1} используем операцию симметрич-ного квадратичного расширения а = в + в - 1 , где а является элементом поля F, в -элементом поля K, а поле K - расширением поля F [5].Теорема 1. Если множество {а, а 2 , . . . , а2" 1} является нормальным базисомв поле GF(2n), след а - 1 равен единице и а = в + в - 1 в поле GF(22"), то множество{в, в 2 , . . . , в22" 1} также является нормальным базисом в поле GF(22") [4].Разложим квадратное уравнение х2 + х = а в нормальном базисе {а, а 2 , . . . , а2к 1}:I 2 | 4 | I 2k-1 х = ах0 + а х1 + а х2 + . . . + а хк - 1,2 4 2^-1а = аа0 + а а1 + а а2 + . . . + а ак - 1,х2 = а2 х0 + а4х1 + а8х2 + . . . + а2к х к - 1 .Просуммируем эти уравнения и с учётом необходимого условия равенства нулюмножителей при степенях а получимхо + ао + х к - 1 = 0,х1 + а1 + xQ = 0,Х2 + а2 + х1 = 0,х х к - 1 + а к - 1 + Х к - 2 =Решив систему, получим формулу для х0:Хо = (Sr(Sr(Sr(... (Sr(bo)))))),где b0 = xQk + х0 и число операций Sr равно к.Аналогично находим остальные элементы корней.Описанный метод дает возможность быстро найти корни квадратных уравненийх2 + х = а в полях GF(2m) при любых m и представить эти решения в виде битовыхстрок.

Скачать электронную версию публикации