Пристрій для ділення елементів скінченних полів gf(2n)

Пристрій для ділення елементів скінченних полів GF(2n), який містить блок формування часткових добутків, який складається з n груп по n елементів І кожний, (n-1) блоків матричного перетворення та блок додавання, виходи якого з'єднані з виходом результату пристрою, вхід 1-го розряду першого (I=1, ..., n) співмножника якого з'єднаний із згрупованими першими входами елементів І і-ої групи блока формування часткових добутків, входи поточної суми j-гo блока матричного перетворення (j=2, ..., n-l) з'єднані з виходами поточної суми (j-l)-го блока матричного перетворення, який відрізняється тим, що в нього введено блок ділення, а кожний блок матричного перетворення містить першу і другу групи із n та (n-1) суматорів по модулю два, першу і другу групи з (n-2) та n елементів І та елемент АБО, причому входи блока ділення з'єднані з відповідними входами коефіцієнтів утворюючого полінома пристрою і входами коефіцієнтів утворюючого полінома кожного з (n-1) блоків матричного перетворення, а виходи зі входами коефіцієнтів розширення k-го блока матричного перетворення (k=1, ..., n-2), виходи поточної U 2 40145 1 3 40145 4 вання часткових добутків, блок матричного перепершої по (n-1) групу якого з'єднані відповідно з творення, блок додавання, дешифратор, n елемевходами часткових добутків з першого по (n-1) нтів И та елемент АБО та блок результату приблок матричного перетворення, вхід і-го розряду строю. другого співмножника пристрою з'єднаний з групоНедоліком даного пристрою є обмеженість ваними другими входами і-их елементів И в кожній функціональних можливостей при виконанні опегрупі блоку формування часткових добутків, при рації ділення, за рахунок чого зростають часові цьому в кожному блоці матричного перетворення витрати при обробці інформації. перші входи суматорів по модулю два першої груЗадачею корисної моделі є удосконалення пи з'єднані з входами поточної суми блоку, входи пристрою для ділення елементів скінченних полів часткових добутків якого з'єднані з другими входашляхом видалення дешифратора та введення ми суматорів по модулю два першої групи, виходи блоку ділення. яких, починаючи з другого, з'єднані відповідно з Це дозволяє забезпечити безпосередньо випершими входами суматорів по модулю два другої конувати операції ділення та множення елементів групи, другі входи яких з'єднані з виходами з перрізноманітних скінчених полів GF(2 n), тобто має шого по (n-1)-ий елемент И другої групи, виходи широкі функціональні можливості застосування їх суматорів по модулю два та вихід (n-2)-го елеменв процедурах кодування та декодування циклічних ту И другої групи з'єднані з відповідними виходами поліноміальних кодів. поточної суми блоку, виходи суматорів по модулю Поставлена задача вирішується тим, що в два з першого по (n-2)-ий першої групи з'єднані пристрої для ділення елементів скінченних полів відповідно з першими входами елементів И перGF(2n), який містить блок формування часткових шої групи, другі входи яких з'єднані з відповідними добутків, який складається з n груп по n елементів входами коефіцієнтів розширення блоку, а виходи И кожній, (n-1) блоків матричного перетворення та з входами елемента АБО, вихід якого з'єднаний з блок додавання, виходи якого з'єднані з виходом групованими першими входами елемента И другої результату пристрою, вхід 1-го розряду першого групи, другі входи яких з'єднані з відповідними (I=1, ..., n) співмножника якого з'єднаний з згруповходами коефіцієнтів утворюючого поліному блованими першими входами елементів И і-ої групи ку. блоку формування часткових добутків, входи поДілення, наприклад, одного елементу точної суми j-гo блоку матричного перетворення aÎGF(pm) на другий елемент bÎGF(pm) відповідає (j=2, ..., n-1) з'єднані з виходами поточної суми (jмноження багаточлену a(х) на багаточлен с(х), що 1)-го блоку матричного перетворення, а також, відповідає елементу cÎGF(pm), зворотному m згідно з винаходом, введено блок ділення, а кожbÎGF(p ), де багаточлен с(х) повинен відповідати ний блок матричного перетворення містить першу умові b(х)*с(х)≡1mod p(x). Відомо [2], що множення і другу групи із п та (n-1) суматорів по модулю два, багаточлена с(х) на багаточлен a(х) виконується у першу і другу групи з (n-2) та п елементів И та відповідності с виразом: с(х)=a(х) b(х) + r(х), яке у елемент АБО, причому входи блоку ділення з'єдвідповідності до того, що операції над багаточленані з відповідними входами коефіцієнтів утворюнами виконуються в полі GF(2n), то вираз можна ючого поліному пристрою і входами коефіцієнтів записати у вигляді с(х)=a(х) Ä b(х) Å r(х)=е(х) Å утворюючого поліному кожного з (n-1) блоків матr(х), де: ричного перетворення, а виходи зі входами коефіa(x)=am-1xm-1 + am-2xm-2 + ...+ a1x + a0; цієнтів розширення k-го блоку матричного переb(x)=bm-1xm-1 + bm-2xm-2 + ...+ b1x + b0; творення (k=1, ..., n-2), виходи поточної суми (n-1)r(х)=rm-1xm-1 + rm-2xm-2 + ...+ r1 x + r0; го блоку матричного перетворення з'єднані з перai, bj, rs Î GF(2); шими входами блоку додавання, другі входи якого з'єднані з виходами відповідних елементів И з (m-1)+ (n -1) (n -1) (m -1) (n - 2) (m -1) e (x ) = ei x i = e (m -1)+ к x (m -1)+ к + e1x1 = e m +k x m + k + e1x1 å i= 0 å k =1 Ділення елементів скінченних полів GF(2 n) виконується як множення багаточленів та зводиться до обчислення суми часткових добутків з приведенням її по модулю утворюючого поліному, що забезпечує множення елементів скінченних полів GF(2n) (2≤m≤n), створених різними утворюючими поліномами. В результаті це дозволяє забезпечити безпосередньо виконувати операції ділення та множення елементів різноманітних скінчених полів GF(2n), і як наслідок, розширення функціональних можливостей побудови комбінаційних схем. На креслені 1 зображена структурна схема пристрою для множення елементів скінчених полів GF(2n). На кресленні 2 - структурна схема блоку матричного перетворення. На кресленні 3 - структурна схема блоку ділення. На кресленні 4 - комбінаційна схема множення скінченного поля GF(2 n). å l= 0 å k =0 å l =0 На кресленні 5 - приклад виконання операції ділення багаточлену над полем GF(2n). Пристрій для ділення елементів скінчених полів містить входи 1 коефіцієнтів утворюючого поліному, входи 2 першого співмножника, входи 3 другого співмножника, блок 4 формування часткових добутків, (n-1) блоків 5 матричного перетворення, блок 6 додавання, блоку ділення 7 та виходи 8 результату. Блок 5 матричного перетворення містить входи 9 поточної суми, входи 10 часткових добутків, входи 11 поточного коефіцієнту розширення, входи 12 коефіцієнтів утворюючого поліному, першу групу з n суматорів 13 по модулю два, першу групу з (n-2) елементів И 14, (n-2) - вхідних елементів АБО 15, другу групу з n елементів И 16, другу гру 5 40145 6 пу з (n-1) суматорів 17 по модулю два та виходи Блоки 5 матричного перетворення обчислюпоточної суми. ють поточну суму часткових добутків та приведенБлок ділення 7 містить входи 19 коефіцієнтів ня її по модулю утворюючого поліному gm(x). Обутворюючого поліному, групу з (n-3) інверторів 20, числення поточної суми a (x ) * biÅ Pn -1(x ) , де a (x ) групу з (n-3) елементів И 21 та виходи 22 поточнокоефіцієнти першого співмножника, bi - і-тий коего коефіцієнту розширення. фіцієнт другого співмножника, який відповідає ноНа кресленні 5 зображено приклад схеми дімеру і-го поточного блоку 5 матричного перетволення багаточлену над полем GF(2n), де n=1. рення, Pn-1(x ) - коефіцієнти поточної суми (і-1)-го Пристрій для ділення елементів скінчених полів GF(2n) працює в такий спосіб. попереднього блоку 5 матричного перетворення, Перед початком ділення на входи 1 утворююÅ сума по модулю два, яка виконується першою чого поліному пристрою поступають значення когрупою суматорів 13 по модулю два. Приведення ефіцієнтів утворюючого поліному gm(x), що припо модулю два утворюючого поліному gm(x) викозводить до формування на відповідному виході нується за умови якщо, сума по модулю два блоку ділення 7 коефіцієнта розширення m. При aк * b1ÅP(i -1) = 1 / aк та P(i-1) відповідно к-ті коефіцієнподанні на входи 2 та 3 пристрою відповідно перти першого співмножника та поточної суми попешого a (x ) та другого b(x ) співмножників на вихореднього блоку 5 матричного перетворення співдах блоку 4 формування часткових добутків утвопадає зі значенням коефіцієнта розширення поля рюються часткові добутки a (x ) * bi , які подаються ("1"), то з суми a (x ) * biÅ Pn -1(x ) вираховується знана входи 10 часткових добутків відповідних і-тих чення коефіцієнтів gm(x) утворюючого поліному, блоків 5 матричного перетворення, входи 9 поточщо являється результуючою поточною сумою цьоної суми кожного з яких з'єднані з однойменними го блоку. Якщо немає співпадіння aк * b1ÅP(i -1)к зі входами 18 попереднього (і-1)-го блоку 5 матричзначенням коефіцієнта розширення ("0"), то відніного перетворення. На виходах 18 кожного і-го блоку 5 матричного перетворення формується і-а мання не виконується, та сума a (x ) * biÅ Pn -1(x ) пепоточна сума як приведена по модулю утворюючоредається на вихід блоку. Перша група елементів го поліному сума і-го часткового добутку та (і-1)-ої И 14 застосовується для порівняння коефіцієнта поточної суми, a (x ) * biÅ Pn -1(x ) modgm (x ) . Таким розширення зі знаком aк * b1ÅP(i -1)к , а друга 16 чином, на виходах 19 (n-1)-го блоку 5 матричного для управління відніманням, а (n-3) - входовий елемент АБО 15 призначений для мультиплексуперетворення формується поточна сума Pn-1(x ) як вання коефіцієнтів розширення. Блок 6 сумування, сума a (x ) * biÅ Pn -2 (x )mod gm (x ) . Остаточний реякий складається з (n-1) суматорів по модулю два, призначений для формування коефіцієнтів результат ділення елементів скінчених полів формузультуючого добутку, які визначаються як сума ється на виходах 8 блоку 6 підсумовування. Блок 4 формування часткових добутків, який a (x ) * biÅ Pn -1(x ) . Ділення елементів скінченних повміщує в себе n груп по n елементів И в кожній, лів GF(2n) виконується як множення багаточленів слугує для отримання послідовності часткових та призводить до обчислення суми часткових додобутків виду ai (x ) * bк , ai - множина коефіцієнтів бутків с приведенням їх по модулю утворюючого першого співмножника, bк - коефіцієнт другого поліному. співмножника. На виходах елементів И перші груТаким чином, ефективність запропонованого пи формують часткові добутки а(n-1) * b(n-1), а(n-2) * пристрою визначається його багатофункціональb(n-1), а(n-3) * b(n-1), ..., а1 * b(n-1), а0 * b(n-1), на виходах ними можливостями (діапазон степені розширення другої групи елементів И - а(n-1) * b(n-2), а(n-2) * b(n-2), полю), регулярністю структури та можливістю реаа(n-3) * b(n-2), ..., а1 * b(n-2), а0 * b(n-2), на виходах n-ої лізації у вигляді ВІС або ПЛІС. групи елементів И - а(n-1) * b0, а(n-2) * b0, а(n-3) * b0, ..., Джерела інформації а1 * b0, а0 * b0. 1. Патент Російської Федерації №2058040, кл. Блок ділення 7 призначений для визначення G06F7/49, 1996. коефіцієнта розширення поля. Так, як ступінь роз2. Патент України №25491, кл. G06F7/49, 2007. ширення поля визначається старшим коефіцієнm том перетворюючого поліному g (x), то поява сигналу "1" в старшому коефіцієнті утворюючого поліному трактується на виходах блоку ділення як поточний коефіцієнт розширення. При цьому на всі інші входи надходить сигнал "0", та вони блокуються. 7 40145 8 9 40145 10 11 40145 12 13 40145 14 15 Комп’ютерна верстка В. Мацело 40145 Підписне 16 Тираж 28 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601