Устройство для сложения и вычитания чисел по модулю @ Советский патент 1986 года по МПК G06F7/72 

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

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

На фиг.1 и 2 предЕтавлена структурная схема предлагаемого устройства.

стройство содержит первый информационный вход 1, первый входной регистр 2, дешифратор 3 группу ключевых элементов 4, первую группу элементов И 5, первый кольцевой сдви- га,ющий регистр 6 (КСР), первый элемент ИЛИ 7, выход 8 результата сложения - значение операции (А+В)mod Р, второй информационный вход 9 устройства, второй входной регистр 10, вход 11 запуска устройства, генератор 12 импульсов, первый и второй элементы И 13 и 14, умножитель 15 частоты, суммирующий- Счетчик 16, схему 1 7 сравнения, третий и четвертый элементы И 18 и 19, вход 20 установки в исходное состояние устройства (бход установки кольцевого сдвигающего регистра в исходное состояние), второй и третий элементы ИЛИ 21 и 22, пятый и шестой элементы И 23 и 24, вход 25 разрешения операции сложения - признак операции (А + В) mod Р, вход 26 разрешения операции вычитания - признак операции (А - В)mod Р, второй кольцевой сдвигающий регистр 27, вхо 28 разрешения операции умножения - признак операции AB(mod Р), вторую группу элементов И 29, четвертый элемент ИЛИ 30, выход 31 результата вычитания - значение операции (А - - B)inod Р, первый и второй квадраторы 32 и 33, вычитатель 34, группу сумматоров 35, шины 36 констант КР (К 0-3), пятый элемент ИЛИ 37, делитель 38 и вькод 39 результата умножения - значение операции AB(mod Р) .

Умножитель 15 частоты в п log (р - 1)3 + 1 раз увеличивает количество выходных импульсов генератора 12.

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

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

осуществляет сдвиг в отрицательном (по часовой стрелке) направлении.

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

н- B)mod P.

Вычитатель 34 определяет результат операции

oS.,, 4.A-B(mod P) (o(.-oi)mod Р.

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

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

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

Режим определения (А + В)mod Р, присутствует сигнал шины 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)-го разряда регистра 6 через эле

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

Режим определения (A-B)mod Р, присутствует сигнал шины 26 С выхода умножителя 15 через открытый элемент И 24 импульсы сдвигают содержимое регистра 27 на В п двоичных разрядов вправо. Сигнал с выхода элемента И 19 открывает (А+1)-й элемент И 29, через который содержимое (А + + 1)-го разряда регистра 27 через элемент ИЛИ 30 поступает на выход 31 устройства.

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

c, {(A+B)mod Р - (А 5 л 2 - B)niod Р mod Р mod Р.

Сумматоры 35 производят операцию с. + k Р для соответствующих констант О, Р, 2Р, ЗР, поступающих по шинам 36. С выхода того сумматора 35, для которого d.+ КР 4in (сумма кратна четьфем), сигнал, соответ- ствукнций значению 4AB(mod Р) , через элемент ИЛИ 37 поступает на вход делителя 38 на четыре, с выхода которого значение АВ(mod Р) поступает на вькод 39 устройства.

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

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

10

5

20

5

0

5

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

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

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

установки и исходное состояние устройства, выход делителя является выходом результата умножения устройства.

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

Редактор О.Юрковецкая

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

Техред И.Попович Корректор Е.Рошко

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

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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