Устройство для сложения и вычитания чисел по модулю @

 

Изобретение относится к области автоматики и вычислительной техники. Цель изобретения - расширение функциональных возможностей за счет получения результата операции модульного умножения. Это достигается за счет использования свойства следующего равенства: АВ (А - В)- (А - ЪГ1/, Изобретение целесообразно использовать в системах и устройствах, функционирующих в системе остаточных классов. 2 ил. К) О1 ;о iNd ел СП

СОЮЗ СОВЕТСНИХ

ОЛ °

РЕСПУБЛИК (5D4 G06 F 7 72 ф

jig

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

И ASTOPCHQMY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3852110/24-24 (22) 05.02.85 (46) 23.09.86. Бкл. У 35 (72) В.А.Краснобаев (53) 681.325.5(088.8) (56) Авторское свидетельство СССР

Р 446056, кл. С 06 F 7/72, 1971.

Авторское свидетельство СССР

В 1168934, кл. G 06 У,7/72, 1983. б (54) УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ И ВЫЧИТАНИЯ ЧИСЕЛ ПО ИОДУЛЮ P!

„„SU„„1259255 А 1 (57) Изобретение относится к области автоматики и вычислительной техники.

Цель изобретения — расширение функциональных воэможностей эа счет получения результата операции модульного умножения. Это достигается за счет использования свойства следующего равенства: АВ = ((А + В) - (А + В) 1/А.

Изобретение целесообразно испольэовать в системах и устройствах, функционирующих в системе остаточных классов. 2 ил.

1 12592

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

Цель изобретения — расширение функциональных возможностей за счет обеспечения возможности получения результата операции умножения чисел по модулю P.

На фиг.1 и 2 предетавлена структурная схема предлагаемого устройства. устройство содержит первый информационный вход 1, первый входной регистр 2, дешифратор 3, группу ключевых элементов 4, первую группу элементов И 5, первый кольцевой сдвигающий регистр 6 (KCP), первый элемент ИЛИ 7, выход 8 результата сложения — значение операции (А+В) mod P, второй информационный вход 9 устройства, второй входной регистр 10, вход 11 запуска устройства, генератор 12 импульсов, первый и второй элементы И 13 и 14, умножитель 15 частоты, суммирующий счетчик 16, схему

17 сравнения, третий и четвертый элементы И 18 и 19, вход 20 установки в исходное состояние устройства (вход установки кольцевого сдвигающего регистра в исходное состояние), второй и третий элементы ИЛИ 21 и 22, пятый и шестой элементы И 23 и 24, вход 25 разрешения операции сложения — приз- 35 нак операции (А + В) mod P вход 26 разрешения операции вычитания — признак операции (А " B)mod P, второй кольцевой сдвигающий регистр 27, вход

28 разрешения операции умножения — 40 признак операции AB(mod P), вторую группу элементов И 29, четвертый элемент ИЛИ 30, выход 31 результата вычитания - значение операции (А— — B)mod Р, первый и второй квадрато- 45 ры 32 и 33, вычитатель 34, группу сумматоров 35, шины 36 констант KP (К = 0-3), пятый элемент ИЛИ 37, делитель 38 и выход 39 результата умножения — значение операции AB(mod Р) . 5О

Умножитель 15 частоты в и

=(1о8 (р — 1Ц + 1 раз увеличивает 2 количество выходных импульсов генератора 12.

Количество разрядов КСР 6 и 27 55 равно количеству возможных остатков по исходному модулю P. Каждый разряд

КСР 6 и 27 состоит из и двоичных.паз

2 рядов. Первый КСР в разряд осуществляет сдвиг содержимого разрядов в положительном (против часовой стрелки) направлении, а второй КСР 27 осуществляет сдвиг в отрицательном (по часовой стрелке) направлении.

Первый 32 и второй 33 квадраторы осуществляют соответственно операции с „= ((А — B)mod P) mod Р и оС =((А +

+ B)mod P) mod P.

Вычитатель 34 определяет результат операции с = 4 A B(mod P) =(о -о()mod Р, ъ 2

Количество сумматоров 35 равно количеству шин 36 и равно четырем. На первые входы сумматора 35 подается значение d. на вторые входы — соответствующие значения k P(k =0-3). С выхода того сумматора 35, для которого значение + kP = 4m, т.е. з кратное четырем, сигнал через эле-. мент ИЛИ 37 поступает на вход делителя 38.

Делитель 38 производит операцию деления значения 4m на четыре, т.е. полученное частное m = AB(mod P) и будет результатом модульного умножения двух операндов.

Работу .устройства удобно рассматривать в трех режимах.

Режим определения (А + B)mod P присутствует сигнал шины 25. Первый операнд А в двоичном коде по шине 1 через регистр 2 поступает на вход дешифратора 3, с выхода которого операнд А в унитарном коде поступает на первый вход соответствующего ключевого элемента 4. Второй операнд В в двоичном коде по шине 9 поступает во второй регистр 10. Сигнал шины 11 запускает генератор 12, с выхода ко-. торого импульсы через открытые элементы И 13 и 14 поступают на входы соответственно умножителя 15 частоты и счетчика 16. С выхода умножителя

;15 через открытый элемент И 23 импульсы сдвигают содержимое регистра

6 на В .и двоичных разрядов влево.

Одновременно при совпадении содержимого регистра 10 и счетчика 16 схема

17 сравнения выдает сигнал, который закрывает элементы И 13 и 14, открывает ключевые элементы 4 и элемент И

18, выходной сигнал которого открывает соответствующий (А+ 1)-й-элемент

И 5, через который содержимое (А +

+ 1)-ro разряда регистра 6 через эле1259255

О

5 мент ИЛИ 7 поступает на выход 8 устройства.

Режим определения (А-В)mod Р, присутствует сигнал шины 26. С выхода умножителя 15 через открытый элемент

И 24 импульсы сдвигают содержимое регистра 27 на В и двоичных разрядов вправо. Сигнал с выхода элемента И t9 открывает (А+1)-й элемент

И 29, через который содержимое (А +

+ 1)-го разряда регистра 27 через элемент ИЛИ 30 поступает на выход

31 устройства.

Режим определения AB(mod P) присутствует сигнал шины 28. В этом случае одновременно открыты (А+1)-вые элементы И 5 и 29. Таким образом, на входы квадраторов 32 и 33 поступают сигналы, соответствующие значениям (A-B)mod P и (A+B)mod Р. Вычитатель 34 определяет результат операции

oL = {((А+В)шос1 Р) mod P — ((Aз

2. — B)mod Р1 mod Р) mod P.

Сумматоры 35 производят операцию

Ф

d- + k P для соответствующих кон3 стант О, Р, 2Р, ЗР, поступающих по шинам 36. С выхода того сумматора

35, для которого d. + KP = 4m (сум- 30 ма кратна четырем), сигнал, соответствующий значению 4AB(mod P) через элемент ИЛИ 37 поступает на вход делителя 38 на четыре, с выхода которого значение AB(mod P) поступает: З5 на выход 39 устройства.

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

Устройство для сложения и вычита- 40 ния чисел по модулю Р, содержащее первый н второй входные регистры, дешифратор, группу ключевых элемен-. тов, первую группу элементов И, первый кольцевой сдвигающий регистр, первый и второй элементы И, генератор импульсов, схему сравнения, умножитель частоты, суммирующий счетчик, причем информационный вход первого входного регистра является первым .у информационным входом устройства, выход первого входного регистра соединен с информационным входом дешифратора, выходы которого подключены к информационным .входам соответ- ствующих ключевых элементов группы, выходы которых подключены к первым входам соответствующих элементов И первой группы, выходы которых соединены с соответсгвующими входами элемента ИЛИ, второй информационный вход устройства подключен к входу второго входного регистра, управляющий вход генератора импульсов соединен с входом запуска устройства, а выход соединен с первыми входами первого и второго элементов И, выход второго элемента И соединен с информационным входом*умножителя частоты, выход первого элемента И соединен с информационным входом суммирующего счетчика, выход которого соединен с первым входом схемы сравнения, вы- . ход которого соединен с вторыми входами первого элемента И, второго элемента И и управляющими входами ключевых элементов группы, выходы разрядов первого кольцевого сдвигающего. регистра соединены с вторыми входами элементов И первой группы, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет обеспечения возможности получения результата оператчи умножения чисел по модулю Р, в устройство введены третий, четвертый, пятый и шестой элементы И, второй, третий, четвертый и пятый элементы ИЛИ, вторая группа элементов

И, второй кольцевой сдвигающий регистр, первый и второй квадраторы по модулю Р, вычитатель, делитель и группа сумматоров, причем выход второго входного регистра подключен к второму входу схемы сравнения, выход которой соединен с первыми входами третьего и четвертого элементов И, к вторым входам. которых подключены выходы соответственно второго и третьего элементов ИЛИ, выход умножителя частоты подключен к первым входам пятого н шестого элементов И, вход разрешения операции сложения устройства соединен с первым входом второго элемента ИЛИ и с вторым входом пятого элемента И, выход которого подключен к управляющему входу первого кольцевого сдвигающего регистра, вход разрешения операции вычитания устройства соединен с первым входом третьего элемента ИЛИ и с вторым входом шестого элемента И, выход которого подключен к управляющему входу второго кольцевого сдвигающего регистра, вход разрешения операции умножения устройства подS 1259255 ф ключен вторым входам второго и сложения устройства, выходы первого третьего элементов ИЛИ, выходы клю- и второго квадраторов подключены чевых элементов группы подключены к соответственно к первому и второму первым входам соответствующих эле- информационным входам вычитателя, выментов И второй группы, к вторым ход которого подключен к первым вховходам которых подключен выход чет- дам сумматоров группы, к вторым вховертого элемента И, а к третьим дам которых подключены соответствуювходам — соответствующие разряды вто- щие входы констант устройства, выхорого кольцевого сдвигающего регис- ды сумматоров группы через пятый тра, выход третьего элемента H >oÀ 10 элемент ИЛИ подключены к входу деключен к третьим входам элементов И лителя, установочные входы нерпервой группы, выходы элементов И вого и второго кольцевых сдвивторой группы через четвертый эле- гающих регистров соединены межмев"1 ИЛИ подключены к входу первого ду собой и являются входом квадратора и выходу результата вычи- 1 установки и исходное состояние тания устройства, выход первого эле- устройства, выход делителя являетмента ИЛИ подключен к входу второго ся выходом результата умножения квадратора и к выходу результата устройства.

1259255 б

В

Составитель М.Есенина

Редактор О.Юрковецкая Техред И.Попович Корректор E.Ðîøêî

Заказ 5122/46 Тирам 671 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, r.узгород, ул.Проектная, 4