Устройство для формирования элементов мультипликативных групп полей Галуа @ Советский патент 1986 года по МПК G06F7/49 

Изобретение относится к вычислительной -технике и может быть использовано в цифровых вычислительных устройствах для вычисления элементов полей Галуа GF(P) и формирования кодовых рекуррентных последовательностей, построение которых основывается на теории полей Галуа GF(F) ,

Целью изобретения является расширение функциональных возможностей устройства за счет формирования элементов мультипликативных групп полей Галуа GF(P) для произвольного моду ля Р.

На чертеже показана функциональная схема устройства формирования элементов мультипликативных групп полей Галуа GF(P) .

Устройство содержит блок 1 дифференцирования, первый элемент ИЛИ 2, элемент ШШ-НЕ 3, группу элементов ИСЮВОЧАОДЕЕ ИЛИ 4-1 4-К, регистр 5, счетчик 6, сумматор 7, формирователь 8 импульсов, элемент И 9, групгде AJ а;,, 0 9 (mod Р); и т.д.

Формирования остаточных классов по произвольному модулю происходит путем вычитания из числа А q раз вьг

5 бранный модуль Р; до тех пор, пока

не будет выполняться условие

А, ajj : Р; . Равенство остатка а модулю Р; означает тождественное равенство нулю числа А, т.е. А

10 (ач - Р; ) E0(mod Р).

Устройство работает следующим образом.

Перед началом работы на вход 22 поступает импульс, который обнуляет

15 регистр множимого блока 5 и счетчик 6, на вход 20 поступает импульс, обнуляющий регистр 5 и регистр множителя блока 15, на вход 23 подается код модуля Р и записывается в регистр 5 и

20 в сумматор 7, в регистр множителя блока is с входа 19 поступает двоичный код числа первообразного элемента 9; в регистр множимого блока 15 записывается единичный элемент. При

элементов И lO-l-lCbK, первый эле- 5 подаче импупъса на вход 21 устройстпу

мент 11 задержки, второй элемент 12 задержки, второй элемент ИЛИ 13, сум матор 1А, блок 15 умножения, элемент ИСКПЮЧАЩЕЕ ИЛИ 6, третий элемент ИЛИ 17, четвертый элемент ИЛИ 18, вход 19 записи первообразного элемента, первый управляющий вход 20 записи единицы, вход 21 сигнала начала работы устройства, второй управляюприй аход 22 обнуления множимого, вход 23 записи значения приводящего модуля, тактовый вход 24.

По.строение и функционирование устройства основано на алгоритме формирования элементов мультипликативных групп полей Галуа GF(P), представлен ном в виде

а; ° б (-mod Р) при i 0,1 ,., «,Р-1 .

Вычисление aj складывается из операций вычисхГения значения S и приве- дения 9 по модулю Р в полях GF(P) , Работа устройства для каждого значения Р описывается следукяцей последовательностью:

а А,(mod Р), где А, s О; а г 5 Р),

во начинает выполнять операцию умножения. Блок 15 умножения умножает единицу на в; и записывает в пара,т- лельном коде результат умножения «

30 сумматор 14, который является вычита- Ю1ЩНМ. в результате на выходе сумматора 14 образуется код числа А, 0; 1 который поступает на входы элемента ИЛИ 13, образуя на его выходе единич-

35 ный потенциал, который открывает эле

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

множимого вход блока 15 умножения и через элемент ИЛИ 2 на обнуляющий вход счетчика 6, в результате чего счетчик 6 и регистр множимого , блока 15 умножения обнуляются. Через откры тый элемент И 9 тактовые импульсы с входа 24 поступают на вход второг 5 слагаемого сумматора 14 и на мационный вход счетчика 6. Последний осуществляет суммирование поступив-

50 шего на его вход количества тактовых ш тульсов. Суммирование осуществляет- ся до тех пор, пока на выходах сч«т- чика 6 не образуется число в двои(|ном коде, численно равное модулю Р и по.

53 ступающее на вторые входы группы элементов ИСКЛЮЧАЩЕЕ ИЛИ 4-1 - 4-К, на первые входы которых с выходов рех ист ра 5 поступает .двоичный код выбра -

i

а, S - 9 (mod Р) ; ,. .;

А; (mod Р),

,

1236497

где AJ а;,, 0 9 (mod Р); и т.д.

Формирования остаточных классов по произвольному модулю происходит путем вычитания из числа А q раз вьг

5 бранный модуль Р; до тех пор, пока

не будет выполняться условие

А, qP| ajj : Р; . Равенство остатка а модулю Р; означает тождественное равенство нулю числа А, т.е. А

(ач - Р; ) E0(mod Р).

Устройство работает следующим образом.

Перед началом работы на вход 22 поступает импульс, который обнуляет

регистр множимого блока 5 и счетчик 6, на вход 20 поступает импульс, обнуляющий регистр 5 и регистр множителя блока 15, на вход 23 подается код модуля Р и записывается в регистр 5 и

в сумматор 7, в регистр множителя блока is с входа 19 поступает двоичный код числа первообразного элемента 9; в регистр множимого блока 15 записывается единичный элемент. При

во начинает выполнять операцию умножения. Блок 15 умножения умножает единицу на в; и записывает в пара,т- лельном коде результат умножения «

сумматор 14, который является вычита- Ю1ЩНМ. в результате на выходе сумматора 14 образуется код числа А, 0; 1 который поступает на входы элемента ИЛИ 13, образуя на его выходе единич-

ный потенциал, который открывает эле

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

множимого вход блока 15 умножения и через элемент ИЛИ 2 на обнуляющий вход счетчика 6, в результате чего счетчик 6 и регистр множимого , блока 15 умножения обнуляются. Через открытый элемент И 9 тактовые импульсы с входа 24 поступают на вход второг 5 слагаемого сумматора 14 и на мационный вход счетчика 6. Последний осуществляет суммирование поступив-

шего на его вход количества тактовых ш тульсов. Суммирование осуществляет- ся до тех пор, пока на выходах сч«т- чика 6 не образуется число в двои(|ном коде, численно равное модулю Р и по.

ступающее на вторые входы группы элементов ИСКЛЮЧАЩЕЕ ИЛИ 4-1 - 4-К, на первые входы которых с выходов рех ист- ра 5 поступает .двоичный код выбра -

31236497

ного модуля р. в результате на выходе каждого элемента 4-1 - 4-К окажутся нулевые сигналы, которые поступают на входы элемента ИЛИ-НЕ 3, на выходе последнего образуется единичный сигнал, который через элемент Ш1И 2 поступает на вход установки в О счетчика 6, и подсчет тактовых импульсов начнется заново.

Таким образом, на вторые входы группы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 4-1 4-К поступают двоичные коды чисел от 1 до Р. В течение этого времени хотя бы на одном из выходов элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 4-1 - 4-К будет единичный сигнал, вследствие чего на выходе элемента ИЛИ-НЕ 3 будет нулевой сигнал. Как только счетчик 6 сосчитает количество тактовых импульсов, равныхвыбранному модулю, опять, произойдет его обнуление. Данная операция будет происходить до тех пор, пока не обнулится сумматор 14. Обнуление последнего произойдет в том случае, когда количество поступивших на его вход второго слагаемого тактовых импульсов будет численно равно

t5

20

25

с:д пе по оп чи а

те

зу

О са хо ко в ма

хо по

а . а ,

до жа чи сл лы ли по ки ЩЕ 12 11 пр ок чи

числу А,, записанному на сумматоре 14. В результате этого с выхода элемента ИЛИ 13 поступает нулевой сиг- нал, элемент И 9 закроется и тактовая последовательность перестанет поступать на входы сумматора 14 счетчика (5. Поэтому на выходах счетчика 6 останется остаток а, числа А, по вы- бранному модулю Р. Под воздействием среза единичного импульса, поступившего с выхода элемента ИЛИ 13, формирователь 8 сформирует импульс, рый откроет элементы И 10--i - 1О-К, на первые входы которых поступает остаток а числа А, с выхода счетчика 6. Тем самым обеспечивается считьша- ние остатка а, от числа А, по модулю Р на выходы устройства и его запись на регистр множимого блока 15, Импульс с выхода формирователя 8 импульсов поступит через элемент PiJIH 17 на вычитающий вход второго слагаемо го сумматора 7 и через элемент 11 за-50 держки на первый вход элемента ИСКШЬ ЧАКЩЕЕ ИЛИ 16. Элемент 11 задержки рассчит на задержку импульсов на один такт. За это время остаток а, от числа А, по модулю Р запишется в 5 регистр множимого блока 15. Так как на второй вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 16 поступает нулевой сигнал.

45

с:динимнъ1Й сиг нал, иО - гупкишиГ: ил гмс первый нход, окажется ил ныхо/ie и поступит на вход н.ачлла ньтсччирния операции умножения блока 15, .i6(i(-- чивая умножением множимого чиглл а, Л, (mod Р) на , . Се-

Л . л , I, S

J л- тем повторяется цикл операций, они-зультат умножения - число

9. записывается в сумм.-пчтр 14

санных раньше для чнсла А, и ил ходных шинах устройства появляется код остатка U2 Aj(mod Р), который в блоке 15 умножается на ; ив cyt-r маторе 14 записывается результат А,

и т.д. Таким образом на выходных шинах устройства появляется последовательность кодой остатков

а . г б:. (mod Р), а н с (mod Р) , . . ., а , 6; (mod Р) и т.д.

Процесс формирования данной последовательности кодов остатков продолжается до тех пор, пока сумматор 7 числа элементов, на вход второго слагаемого которого поступают сигналы с выхода формирователя 8, не обнулится и не выдаст сигнал o6Hyj eHHH, поступающий через элемент 12 задержки на второй вход элемента ИСКПЮЧАКН ЩЕЕ ИЛИ 16. Время задержки элемента 12 равно времени задержки элемента 11. В результате блок 15 умножения прекратит свою работу и устройство окажется готовым к новому циклу вычисления остатков а;.

Записывая в устройство коды первообразных элементов б; , можно сформировать любые последовательности элементов мультипликативной группы поля GF(P), а изменяя модуль Р, с целью формирования остатков по иному модулю Р; можно сформировать последовательности элементов мультипликативных групп и других полей Галуа GF(Pj ) ,

Формула изобретения

Устройство для формирования элементов мультипликативных групп полей Галуа GF(P), содержащее первый элемент ИЛИ, блок умножения, группу из К элементов И, где К - разрядность мультипликативных групп, первый и второй элементы задержки, первый сумматор, входы значения первообразного элемента устройства подключены к входам множителя блока умножения, первый установочный вход устройства подключен к входу установки в нулевое состояние

регистра множителя, второй установочный вход устройства подключен к входу установки в нулевое состояние регистра множимого и к первому входу пе.рво го элемента ШТИ, входы значения приводящего модуля устройства подключены к входам первого слагаемого первого сумматора, выходы элементов И группы ггодключены к входам множимого блока умножения и к выходам результата устройства, выход первого сумматора подключен к входу второго элемента задержки, отличающееся тем, что, с целью расширения функцио- напьных возможностей устройства за счет формирования элементов мультипликативных групп полей Галуа FG(P) при любом модуле Р, в него введены элементы ИЛИ с второго по четвертый, эле- мент ИЛИ-НЕ, элемент И, второй сумматор, одновибратор, блок дифференцирования, счетчик, регистр, группа из К элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, входы значения приводящего модуля устройства подключены к информационным входам регистра, вход установки в нулевое состояние которого подключен к первому установочному входу устройства i-й (i 1, 2, . . .,К) выход регистра подключен к первому входу i-ro элемента ИСКПЮЧАКШЩЕ ИЛИ группы, к второму входу которого подключены i-и выход счетчика и второй вход i-го элемента И группы, выходы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ группы

подключены к входам элемента 1ШИ-НЕ, выход которого подключен к второму входу первого элемента ИЛИ, третий вход которого подключен к выходу блока дифференцирования, выходы блока умножения подключены к входам первого слагаемого второго сумматора, вход второго слагаемого второго сумматора подключен к выходу элемента И и к информационному входу счетчика, вход установки в нулевое состояние которого подключен к выходу первого элемента ИЛИ, выходы второго сумматора подключены к входам второго элемента ИЛИ, выход которого подклю чен к входам блока дифференцирования, одновибратора и к первому входу элемента И, второй вход которого подклю чен к синхровходу устройства, выход одновибратора подключен к первым входам элементов И группы, первому входу третьего элемента ИЛИ и к входу первого элемента задержки, второй вход третьего элемента ИЛИ подключен к входу запуска устройства и к первому входу четвертого элемента ИЛИ, второй вход которого подключен к выходу элемента ИСКЛЮЧАЩЕЕ ИЛИ, первый и второй входы которого подключены соответственно к выходам первого и второго элементов задержки, выход четвертого элемента ИЛИ подююг чен к синхровходу блока умножения,выход третьего элемента ИЛИ подключен к входу ВТОРОГО слагаемого первого сумматора.

212022

Изобретение относится к вычисли- тельной технике и может быть использовано в цифровых вычислительных устройствах для вычисления элементов полей Галуа GF(P) и формирования кодовых рекуррентных последовательностей. построение которых основы1зается на теории полей Галуа GF(P). Цель изобретения - расширение функциональных возможностей устройства за счет формирования элементов мультипликативных групп полей Галуа GF(Р) при любом модуле Р. Устройство содержит блок умножения, элементы И, ИЛИ, ИЛИ-НЕ, ИСКЛЮЧАЮЩЕЕ ИЛИ, первый и второй сумматоры, первый и второй элементы задержки, регистр, счетчик, формирователь импульсов, дифференциальную цепочку. В основу работы устройства положен алгоритм последовательного определения а; 9 (mod р), для i 0, 1, ...,Р-1 . Устройство позволяет формировать элементы мультипликативных групп полей Галуа GF(P) при любом модуле Р. 1 нл. ю СЛ