Б. А. Савельев, Г. В. Бобрышева
ВЫЧИСЛЕНИЯ В КОНЕЧНЫХ ПОЛЯХ
МАЛОЙ РАЗМЕРНОСТИ
В статье предложен алгоритм вычисления операций умножения, деления и сложения для конечных полей Галуа. <...> Алгоритм позволяет упростить вычисления для полей небольшой размерности за счет исключения операции логарифмирования. <...> Введение
Процессы вычислений для систем помехоустойчивой и криптографичеm
ской защиты информации осуществляются в конечных полях GF(p ), где m –
степень расширения поля; p – характеристика поля. <...> При этом элементы поля могут быть представлены в полиномиальном или нормальном базисах. <...> Вычислительные устройства (ВУ) элементов в полиномиальном базисе
имеют меньшую сложность [1–3], однако ВУ элементов нормального базиса
имеют более регулярную структуру [3–5]. <...> Процессы оптимизации вычислений продолжают быть актуальными в современной теории помехоустойчивой и криптографической защиты информации. <...> Один из методов упрощения
m
вычислений для полей GF(2 ) анализируется ниже. <...> Алгоритм вычислений в конечных полях
Перемножаемые элементы в нормальном базисе можно представить в
виде полиномов от фиктивной переменной x:
А ( х) =
m −1 <...> Набор базисных элементов позволяет получить все элементы конечного поля в соответствующем базисе. <...> Кроме того, базис позволяет перейти от
одного представления элементов поля к другому. <...> Информатика и вычислительная техника
элементам нормального базиса от полиномиального, можно использовать
выражение
ϕн = ϕ ⋅Тн, <...> (3)
где ϕн – элементы нормального базиса; Тн – базисный набор элементов нормального базиса; ϕ – элементы полиномиального базиса. <...> В теории компьютерных сетей важное значение имеют параметры
сложности и быстродействия основных математических операций [2, 3, 5]. <...> В
полях с малой размерностью поля (m = 8, 16) широкое распространение получили табличные методы расчетов на основе постоянных запоминающих
устройств [6–8].
i
Так, в работе [6] операции умножения и деления элементов полей α и
j
α заменяются <...>