Всеукраїнська науково-практична конференція



Сторінка40/60
Дата конвертації11.05.2018
Розмір3.74 Mb.
1   ...   36   37   38   39   40   41   42   43   ...   60

ДИЧКА І.А., ОНАЙ М.В.


НТУУ “КПІ(Україна)

ОСОБЛИВОСТІ АПАРАТНОЇ РЕАЛІЗАЦІЇ ОПЕРАЦІЇ ВІДНІМАННЯ В КІЛЬЦІ

ЛИШКІВ ЗА МОДУЛЕМ 2m–1



Обґрунтована актуальність виконання операції віднімання в кільці лишків за модулем 2m  1 у завадостійкому кодуванні даних та при виконанні криптографічних перетворень. Проаналізовані особливості алгебраїчних операцій за модулем 2m  1 та запропоновано алгоритм виконання операції за модулем 2m  1 та його схемотехнічна реалізація.
У зв’язку з розвитком завадостійкого кодування та криптографії в наш час активно розвиваються прикладні аспекти теорії скінченних полів [1]. Обчислення в полях Галуа GF(2m) мають свою специфіку, і, завдяки подальшому розвитку зазначених галузей, з’являється потреба в удосконаленні структур обчислювальних засобів, які реалізують арифметику скінченних полів GF(2m).

Існують 3 форми подання [2] елементів поля GF(2m): степеневе (у вигляді степеня примітивного елемента поля), многочленне та числове.

Аналіз операцій в полі GF(2m) показав, що при виконанні операцій множення, знаходження мультиплікативно оберненого елемента, ділення та піднесення до степеня над степеневим поданням ненульових елементів поля GF(2m) необхідно виконувати зведення показника степеня результату за модулем . Тобто виникає необхідність виконувати мікрооперації за модулем .

Розглянемо операцію ділення елементів поля GF(2m). Очевидним є те, що при виконанні операції ділення елементів поля GF(2m) виникає необхідність виконання віднімання величин за модулем : .

Наприклад, :

.

Математично мікрооперацію віднімання за модулем записують так:



(1)

В ЕОМ операцію віднімання двійкових кодів реалізують шляхом перетворення від’ємника у доповняльний код та його додавання до зменшуваного. З врахуванням цього другу рівність з (1) можемо переписати таким чином:



,

а третю, як



.

Доданок не вливає на значущі цифри результату, а впливає лише на значення  , тому (1) перепишемо у вигляді:



(2)

Введемо позначення .

Розглянемо випадок, коли . Тоді:

,

а відповідно до першої рівності з (2) має дорівнювати 0. Отже, при , значення необхідно проінвертувати (знайти ), або додати ‘1’.

Тому (2) можна переписати, як

Сформулюємо алгоритм виконання операції віднімання за модулем :

1. Обчислити ; зафіксувати .

2. Якщо , то ; перейти до п.4.

3. Якщо , то .

4. Видати .

Схемотехнічно даний алгоритм можна реалізувати, як показано на рис. 1.




Рис. 1. Функціональна схема вузла виконання операції віднімання за

модулем 2m – 1



При використанні табличного способу зберігання елементів поля в тій частині таблиці (ПЗП) елементів поля де зберігаються числові подання елементів поля за адресою ‘0 … 0’ та адресою ‘1 … 1’ можна записати однакове значення ‘0 … 1’, оскільки. Тоді інвертування на  можна не виконувати. З врахуванням цього, алгоритм виконання операції віднімання за модулем  набуває вигляду:

1. Обчислити ; зафіксувати значення .

2. Якщо , то .

3. Видати .

Останній алгоритм дозволяє значно пришвидшити виконання операції додавання в кільці лишків за модулем . Подальші дослідження слід зосередити на побудові алгоритмів, що з прийнятною швидкодією реалізують перехід від степеневого подання елементів поля до многочленного і навпаки.
ПЕРЕЛІК ЛІТЕРАТУРИ

1. Vasundara Patel: Aritmetic operations in Multi-Valued logic, International Journal of VLSI design & Communication Systems (VLSICS) Vol. 1, No. 1, March 2010.

2. Lidl R, Niederreiter H. Finite fields. Addison Wesley; 1983.

3. Lejla Batina, Siddika Berna Ors, Bert Preneel, Joos Vandewalle: Hardware architectures for public key cryptography, Elsevier, INTEGRATION, the VLSI journal 34 (2003).



УДК 004.55


Поділіться з Вашими друзьями:
1   ...   36   37   38   39   40   41   42   43   ...   60


База даних захищена авторським правом ©wishenko.org 2017
звернутися до адміністрації

    Головна сторінка