Научный журнал
Современные наукоемкие технологии
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 1,021

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ИНДЕКСА ЭЛЕМЕНТОВ ПОЛЯ ГАЛУА ПО МОДУЛЮ

Калмыков И.А. Кихтенко О.А. Барильская А.В.
Применение арифметики в кольце полиномов является наиболее целесообразным, когда алгоритмы вычислений отмечаются повышенным содержанием мультипликативных арифметических операций при относительно небольшом количестве аддитивных.

Процедура возведения символа (элемента) конечного поля GF(p) в степень трудоёмка и требует больших затрат на решение уравнения

αx ≡ β(mod p),                  (1)

где α, β, x - элементы конечного поля Галуа с характеристикой p.

Для восстановления исходного значения α из получаемого значения β по модулю p используется уравнение:

1.             (2)

Реализовать выражение (1) можно, используя умножитель по модулю p, однако время данной операции будет равно

Tоп = (х - 1) Tум,

где Tум - время выполнения модульного умножения.

Сократить время выполнения операции можно, используя индексы.

В работе [1] показана возможность использования теории индексов для эффективной реализации операций мультипликативного типа (умножение, деление, возведение в степень). Число iA являющееся решением сравнения

f,                    (3)

называется индексом числа A и обозначается f. Первообразный корень g-основание индекса.

В работе [1] доказана теорема, по которой индекс J произведения простых целых чисел А1 , А2 ,..., Аk по модулю р равен сумме индексов сомножителей, взятой по модулю р-1, т.е.

f,                     (4)

где i1 ,i2 ,..., ik- индексы положительных чисел A1 ,A2 ,...,Ak по модулю р при первообразном коде g.

Т.о., очевидна возможность сведения операции умножения двух операндов А и В по модулю р к операции суммирования индексов iA, i B этих операндов при первообразном корне g по модулю р-1.

Аналогично можно доказать, что операцию возведения в степень (1) можно свести к операции индексов по модулю p-1.

Т.о., для нахождения индекса какого-либо числа A по модулю p надо найти первообразный корень числа p и решение сравнения (1) для данного первообразного корня. Эта операция сравнима по сложности с процедурой вычисления дискретного логарифма в конечном поле.

Аналогичная ситуация возникает и в расширенных полях Галуа f. Т. к. все элементы этого поля получаются с помощью порождающего полинома р(z), то в качестве первообразного корня можно выбрать z. Тогда любой элемент A(z) поля f можно представить в виде

f              (5)

Следовательно, справедливо

f.                     (6)

При этом

f            (7)

Т. к. значение показателя γ задано, то для реализации выражения (6) необходимо определить значение индекса iA по модулю p(z) из выражения (5).

Рассмотрим расширенное поле Галуа GF(23). В этом поле определен порождающий полином p(z)=z3+z+1, который задает следующие элементы поля (таблица 1).

Таблица 1

Представление элементов поля Галуа GF(23)

Степенное

Векторное

Полиномиальное

β0

001

1

β1

010

z

β2

100

z2

β3

011

z+1

β4

110

z2+z

β5

111

z2+z+1

β6

101

z2+1

Видно, что показатели степеней элементов поля f крутятся по модулю 7 = 23 -1.

Из таблицы 1 видно, при векторном представлении элементов f, соответствующих нулевому, 3-ему, 5-ому и 6-ому индексу, в нулевом разряде присутствует единица a0 = 1, а в элементах поля с индексами 1, 2, 4 - в данном разряде записан нуль a0 = 0.

Единица в 1-ом разряде a1=1 векторного представления соответствует индексам - 1, 3, 4, 5, в противном случае, при a1=0  индексам 0, 2, 6.

Единица во 2-ом разряде a2=1 векторного представления соответствует индексам - 2, 4, 5, 6, в противном случае, при a2=0 - индексам 0, 1, 3.

Используя логические функции, можно записать следующие соответствие, приведенные в таблице 2.

Следовательно, для реализации устройства вычисления индекса могут быть использованы базовые логические функции. Структура устройства для вычисления индекса элемента поля Галуа по модулю приведена на рисунке 1.

Таблица 2

Индексное представление

Векторное представление

0

f

f

а0

1

f

а1

f

2

а2

f

f

3

f

а1

а0

4

а2

а1

f

5

а2

а1

а0

6

а2

f

а0

Устройство состоит из регистра 1, предназначенного для хранения элементов поля Галуа GF(23), представленного а двоичном коде, блока 2 элементов НЕ, блока 3, состоявшего из 7 трехвходовых элементов И, шифратора 4 и выхода устройства 5. Выходы регистра 1 подключены к входу соответствующего элемента НЕ, входящего в состав блока 2.

Входы 1-го элемента И блока 3 подключены к выходам 2-ого и 3-его элементов НЕ блока 2 и к 1-ому выходу регистра 1. Входы 2-ого элемента И блока 3 подключены к выходам 1-ого и 3-его элементов НЕ блока 2 и ко 2-ому выходу регистра 1. Входы 3 элемента И блока 3 подключены к выходам 1-ого и 2-ого элементов НЕ блока 2 и к 3-ему выходу регистра 1. Входы 4 элемента И блока 3 подключены к выходу 3-его элемента НЕ блока 2 и к 1-ому и 2-ому выходам регистра 1. Входы 5 элемента И блока 3 подключены к выходу 1-ого элемента НЕ блока 2 и ко 2-ому и 3-ему выходам регистра 1. Входы 6 элемента И блока 3 подключены к 1-ому, 2-ому и 3-ему выходам регистра 1. Входы 7 элемента И блока 3 подключены к выходу 2-ого элемента НЕ блока 2 и к 1-ому и 3-ему выходу регистра 1.

1

Рис. 1. Структура устройства

Выходы элементов И блока 3 подключены к входам шифратора 4, который преобразует семиразрядный унитарный код в двоичный трёхразрядный позиционный код. Выход шифратора 4 является выходом устройства 5.

СПИСОК ЛИТЕРАТУРЫ:

  1. Акушский И.Я., Юдицкий Д.М. Машинная арифметика в остаточных классах. - М.: Сов. радио, 1968. - 440 с.

Библиографическая ссылка

Калмыков И.А., Кихтенко О.А., Барильская А.В. УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ИНДЕКСА ЭЛЕМЕНТОВ ПОЛЯ ГАЛУА ПО МОДУЛЮ // Современные наукоемкие технологии. – 2007. – № 11. – С. 91-93;
URL: http://www.top-technologies.ru/ru/article/view?id=25635 (дата обращения: 15.06.2021).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074