М В Ногаль - Додавання і множення в полях галуа - страница 1

Страницы:
1  2 

УДК 004.382 М.В. Ногаль

Національний університет "Львівська політехніка" кафедра електронних обчислювальних машин

ДОДАВАННЯ І МНОЖЕННЯ В ПОЛЯХ ГАЛУА

© Ногаль М.В., 2007

Розглянуто алгоритми додавання і множення в полях Галуа, описано основні принципи побудови суматора і перемножувача згідно з наведеними алгоритмами. Наве­дено функціональні схеми пристроїв, показано доцільність їх описання мовою описання апаратних засобів для подальшої реалізації на ПЛІС.

The algorithms of addition and multiplication are considered in the fields of Galua, basic principles of construction of adder and multiplier are described in obedience to the resulted algorithms. The functional diagrams of devices are resulted.

Вступ. Еліптичні криві над скінченними полями - один з найперспективніших інструментів для побудови криптографічних алгоритмів. Сьогодні для цілей криптографії використовуються зазвичай еліптичні криві над простим полем і над полем характеристики 2. У скінченних полях (або полях Галуа, як їх ще називають) основними операціями є операції підсумовування і множення.

Постановка задачі. Розглянути принципи побудови суматорів і перемножувачів в полях Галуа, реалізувати їх у вигляді моделей мовою описання апаратних засобів.

Поля Галуа. Полем називають множину елементів, на якій визначено дві операції. Одна з них називається додаванням і позначається a+b, а інша - множенням і позначається а-b, навіть якщо ці операції не є звичайними операціями додавання і множення чисел. Для того, щоб множина елементів, на якій задані операції додавання і множення, була полем, необхідно, щоб для кожної з цих операцій виконувалися всі групові аксіоми, а саме комутативність (а+Ь = bі аЬ = Ьа), асоціативність (а+(Ь+с) = (a+b)+c і а(Ьс) = (ab)c), а також виконувався дистрибутивний закон, тобто для трьох будь-яких елементів поля а, b, с була справедлива рівність а(Ь+с) = аЬ+ас і (Ь+с)а = Ьа+са.

Варто відмітити, що групові властивості для операції множення справедливі для всіх ненульових елементів поля.

Поля з скінченним числом елементів q називають полями Галуа на ім'я їх першого дослідника Еваріста Галуа і позначають GF(q)[1].

Число елементів поля q називають порядком поля. Скінченні поля використовуються для побудови більшості відомих кодів і їх декодування.

Найменше число елементів, які утворюють поле, дорівнює 2. Таке поле повинне містити 2 оди­ничних елементи: 0 щодо операції додавання і 1 щодо операції множення. Це поле GF(2), або двійкове.

Залежно від значення q розрізняють прості або розширені поля. Поле називають простим, якщо q - просте число. Для позначення простих чисел використовуватимемо символ р. Просте поле утворюють числа за модулем p: 0, 1, 2., p-1, а операції додавання і множення виконуються за модулем р. Якщо ж поле утворене з qm елементів, то таке поле називають розширенням поля степеня m над GF(p) або розширеним полем. Воно містить pm елементів і позначається GF(pm). Надалі будемо розглядати поля GF(2m). Будь-яке скінченне поле GF(2m) є m-вимірним вектором над полем GF(2). Многочлен f(t) степеня m над полем GF(2) є многочлен вигляду

f(t) = tm+fm-1tm-1+ ...  + fo,

де коефіцієнти многочлена f належать GF(2). Операції над такими многочленами виконуються як операції над звичайними многочленами, тільки операції над коефіцієнтами виконуються в полі GF(2).

Многочлен f(t) ненульового степеня називається незвідним над полем GF(2m), якщо він ділиться без залишку над цим полем на самого себе і на многочлени нульового степеня [2]. Елемент x скінченного поля GF(2m) називається коренем многочлена f(t), якщо f(x)=0. Якщо x - корінь незвідного многочлена p(x) степеня m, то елементи (xm-1, 1) утворюють базис скінченного поля GF(2m) як векторного простору над полем GF(2). Такий базис називається поліноміальним. Многочлен, коренем якого є примітивний елемент, називається примітивним многочленом. Якщо як P(x) вибрати примітивний многочлен степеня m, незвідний над полем GF(2),то отримаємо поле GF(2m) зі всіх 2m двійкових послідовностей довжини m. Поліноміальний базис задається при­мітивним многочленом.

Елементи скінченного поля в поліноміальному базисі зображаються многочленами степеня не більше m-1 або, що еквівалентно, двійковими рядками довжини m, що складаються з коефіцієнтів таких многочленів. Операції додавання і множення у скінченному полі в такому разі - це операції над многочленами степеня не більше m-1 зі зведенням результату за потреби за модулем примітивного многочлена.

Додавання двох елементів виконується як додавання відповідних многочленів або як додавання за модулем 2 відповідних до цих многочленів двійкових рядків. Множення двох елементів виконується як множення відповідних многочленів з подальшим зведенням результатів за модулем примітивного многочлена.

Нормальним базисом поля GF(2 ) є множина

B = \е,Є2,Є2\..,Є2П1~1} (1) Елементи множини можна подати у вигляді двійкових рядків (a0 a1 a2 ... am-1)

2 22 2m-1

а0в + alG + a2G   +... + am _lG (2) Залежно від параметра Т розрізняють типи нормального базису і нормальні поліноми:

_ _ m      m-1 2

При T=1: p(x) = t + t   + ... + t + t + 1;

при T=2: p0(t) = 1,p1(t) = t + 1,p+1(t) = tp(t) + piA(t), i = 1, m.

Виконання операцій додавання і множення в простих скінченних полях GF(q)

Суматор за модулем обчислює суму Z=(X+Y)q, де число Z дорівнює залишку від ділення суми X+Y на число q. Числа Z, X, Y, і q зображають в двійковій формі і мають розрядність n. Необхідно синтезувати суматор за модулем q для будь-якого значення n.

Розглянемо суму

S = (X + Y) + (2n _ q), (3)

де S має n+1 двійкових розрядів. Очевидно, що сума S може приймати значення S<2n і S>=2n залежно від значень X і Y. Якщо сума S<2n, то (n+1) розряд числа S дорівнює 0 і з співвідношення (1) отримуємо, що X+Y<q, а отже, Z=X+Y.

Якщо ж сума S>=2n, то (n+1) розряд числа S дорівнює 1 і з співвідношеня (3) випливає, що X+Y>=q, а отже, Z=X+Y-q.Таким чином існує співвідношення

IX + Y, якщо X + Y < q Z = (X + Y)q =j        '   Щ (4) IX + Y _ q, якщо X + Y > q

На основі співвідношення (4) може бути побудована схема суматора за модулем, де q - будь-яке просте число. На рис.1 показана схема суматора для n-розрядного числа q. Суматор D1 виконує обчислення суми чисел X і Y, суматор D2 віднімає від суми X+Y значення q, оскільки 2n-q -доповнення числа q до 222і. Мультиплексор подає на вихід суму Z=(X+Y)q залежно від розряду sn+1 (а ним буде розряд переповнення одного з суматорів).


 

SM

Co

A

 

 

 

 

S

B

 

 

Ci

D1

 

4

 

SM

Co

A

 

 

 

 

S

B

 

 

Ci

D2

 

n

Й 0

MUX

=>Z

Рис. 1. n-розрядний суматор за модулем

Такий суматор можна описати однією з мов описання апаратних засобів для подальшого синтезу на ПЛІС. Було описано 1024-х розрядний суматор на VHDL.

У структурних схемах для суматорів за модулем q будемо використовувати умовне позначення, яке зображено на рис. 2а.

 

 

(X+Y)q

X

(A+B)q

 

 

 

 

 

и

 

 

а

 

(2*A)q

l(2*X)q

б

Рис. 2. Умовне графічне позначення суматора за модулем q і перемножувача за модулем

Для добутку чисел X*Y існує співвідношення

X *Y yp *X *2p-1 , (5)

p=1

де yp=0 або 1. З цього випливає, що для побудови пермножувача за модулем q необхідно синтезувати типову схему, яка виконує операцію (2*X)q - перемноження на 2 за модулем q. Дійсно, оскільки (X*21+1)q=(2*(X*21)q)q, значення (X*2p'1)q можуть бути отримані послідовним використанням перемно­жувачів на 2 за модулем Правило побудови схеми такого перемножувача отримуємо з співвідношень (3) і (4), якщо візьмемо X=Y і S=2*X+(2n-q). На рис. 2б показано умовне позначення перемножувача на 2 за модулем. На рис. 3 показано схема перемножувача на 2 за модулем для n-розрядного q. Перемно­ження числа X на 2 досягається зсувом розрядів числа X на один розряд відносно входів суматора, а тому потрібний лише один суматор. На виході мультиплексора отримуємо величину Z=(2*X)q.

Xn-1_

 

 

 

SM

Co

2*Xr-У

 

A

 

 

 

 

 

 

S

— П/

q >=^

 

B

 

 

 

 

Ci

 

 

n

MUX

Рис. 3. n-розрядний перемножувач на 2 за модулем

1

n

q

X

На рис. 4 показана структурна схема перемножувача за модулем, яка обчислює величину

Z = (X*Y)q = (±yp *X*2p-1)q, (6)

p=1

тут q і Z -n-розрядні двійкові числа. Тут числа q і X являють собою n-розрядні дані, а вузол & - сукупність логічних елементів І для порозрядного логічного перемноження числа X на розряди Ур, де p=1, 2, n.

X

&

(A+B)q

 

 

(A+B)q

 

_

 

 

&&

(2*A)q

Y1

H (2*A)q

Y2

(2*A)q -

Y3

1

(A+B)q

& I

(X*Y)q

Yn

Рис. 4. n-розрядний перемножувач за модулем

Виконання операцій додавання і множення в поліноміальному базисі скінченного поля GF(2n)

Додавання двох елементів виконується як додавання відповідних многочленів або як додавання за модулем 2 відповідних до цих многочленів двійкових рядків.

Тобто, додавання реалізується як порозрядне додавання за модулем 2 двох n-розрядних двійкових рядків.

Страницы:
1  2 


Похожие статьи

М В Ногаль - Додавання і множення в полях галуа