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

(51)5 8 И ЕЛЬСТВ тся к автоматике и е и может быть исельных машинах и рующих в системе ения со ервый провес ияАВ тавим Яп2 1) + 1стоит в операнд, ти опера(тор в), число В и+ +Тогда прощение устройВ =,равно "0 ибо "1" ю- ии ту по моналоге,ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ИСАНИЕ ИЗО К АВТОРСКОМУ С(56) Авторское свидетельство СССРМ 1617439, кл, 6 06 Р 702, 1988,Авторское свидетельство СССРВ 1259255, кл. 6 06 Р 7 П 2, 1985,(54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛ ПО МОДУЛЮ(57) Изобретение относится к автоматике ивычислительной. технике и может быть исИзобретение относвычислительной техникпользовано в вычислитустройствах, функционостаточных классов,Цель изобретения -ства.На чертеже представлена схема устройства для умножения чисел по модулю.Устройство содержит вход 1 первого сомножителя, вход 2 второго сомножителя, группу блоков 3 элементов И, группу блоков 4 умножения на константу по модулю, первый кольцевой. регистр 5 сдвига, выход 6 устройства, тактовый вход 7 устройства, блок элементов ИЛИ 8, счетчик 9, элемент ИЛИ 10, первый элемент И 11, элемент НЕ 12, второй и третий элементы И 13 и 14, блок элементов И 15, второй кольцевой регистр 16 сдвига, шифратор 17.Блоки 4 умножения на констан дулю группы реализованы как в а пользовано в вычислительных машинах и устройствах, функционирующих в системе остаточных классов. Целью изобретения является упрощение устройства, Устройство для умножения чисел по модулю содержит группу блоков 3 элементов И, группу блоков 4 умножения на константу по модулю, коль. цевые регистры 5 и 16 сдвига, блок 8 элементов ИЛИ, счетчик 9, элемент ИЛИ 10, элементы И 11, 13 и 14, элемент НЕ 12, блок 15 элементов И и шифратор 17 с соответствующими связями, 1 ил. Сущность изобрет следующем: пусть А - и В - второй и необходимо цию модульного умножен где гп - модуль. П р ед с в виде В = 31 2"+ + Яо 2 (и= о 92 (ат.е. соответствует значению У щего разряда в двоичном и н числа В). Произведение вида А 2 (проб в) можно получить при помощи блока умножения на константу, Следовательно, для получения результата операции А В (гпоб т) необходимо произвести последовательное слажение чисел вида А 2 (аоб (и) длятех разрядов двоичного представления, числа В, Я которых равны единице,Рассмотрим работу устройства. Первый кольцевой регистр 5 сдвига состоит из и двоичных разрядов (с 0-го по и-й). Второй20 25 30 35 40 50 55 кольцевой регистр 16 сдвига состоит из гп двоичных разрядов (с 0-го по п-й), В исходном состоянии в нулевые разряды регистров 5 и 16 записаны единицы, а в остальные разряды - нули по входу начальной установки устройства (на чертеже не показан). Первый сомножитель А поступает на входы блоков 4 умножения на константу по модулю, а также на первый вход последнего блока 3 элементов И группы, на входах блоков 4 умножения на константу по модулю группы получаем произведения вида (а 2) гпоб п ( = и- 1), а на третьем входе последнего блока 3 элементов И имеем (А 2 О) пагод в = А. Второй сомножитель В в двоичном коде поступает на соответствук)- щие вторые входы блоков 3 элементов И группы. На первые входы блоков 3 элементов И группы поступает сигнал с выходов разрядов первого кольцевого регистра 5 сдвига, Первоначально в нулевом разряде регистра 5 записана единица, В соответствующий и-й разряд операнда В тоже записывается единица, Тогда через соответствующий блок элементов И 3 и через блок элементов ИЛИ 8 число (А 2" ) гпо п поступает на импульсный вход установки числа счетчика 9, Сигнал с элемента ИЛИ 10 открывает элемент И 11, и импульсы с входа 7 устройства поступают на вход разрешения сдвига разрядов регистра 16 и вычитающий вход счетчика 9. Через (А 2" ) тоба импульсов единица из нулевого разряда регистра 16 переходит в (А 2" ) вод т-й разряд, а содержимое счетчика 9 становится равно нулю, Тогда сигнал поступает через элемент НЕ 12 на элемент И 13. С входа 7 устройства один импульс поступает на вход разрешения сдвига разрядов регистра 5, передвинув единицу из нулевого разряда в первый. Если в и-м двоичном разряде операнда В имеется нуль, сигнал с элемента 12 поступает на элемент И 13, и единица из первого разряда регистра 5 переходит во второй. Процесс продолжается до тех пор, пока единица в регистре 5 не перейдет в и-й разряд. В этом случае, если соответствующий (нулевой) разряд операнда В равен нулю, на выходе элемента НЕ 12 оказывается сигнал, который поступает с элемента И 14 на первый вход блока элементов И 15, и результат операции модульного умножения, полученный в унитарном коде на выходах разрядов регистра 16, поступает через шифратор 17, который преобразует его в двоичное представление, на выход 6 устройства, Если нулевой двоичный разряд операнда В равен единице, сигнал с элемента И 14 поступает только тогда, когда содержимое счетчика 9 становится равно нулю,т.е. после последнего сложения. формула изобретения Устройство для умножения чисел по модулю, содержащее группу блоков элементов И, первый и второй кольцевые регистры сдвига, блок элементов ИЛИ,счетчик, элемент НЕ, с первого по третий элементы И и блок элементов И, причем выходы разрядов первого кольцевого регистра сдвига соединены с первыми входами соответствующих блоков элементов И группы, выходы которых соединены с соответствующими входами блока элементов ИЛИ, тактовый вход устройства соединен с первыми входами первого и второго элементов И, выход элемента НЕ соединен со вторым входом второго элемента И, выход третьего элемента И соединен с первым входом блока элементов И, отл и ча ю щее с я тем, что, с целью упрощения устройства, оно содержит группу блоков умножения на константу по модулю, элемент ИЛИ и шифратор, причем вход первого сомножителя устоойства соединен со входами блоков умножения на константу по модулю группы, входы разрядов входа второго сомножителя устройства соединены со вторыми входами соответствующих блоков элементов И группы, выходы блоков умножения на константу по модулю группы соединены соответственно с третьими входами блоков элементов И, кроме последнего, группы, вход первого сомножителя устройства соединен с третьим входом последнего блока элементов И группы, выход блока элементов ИЛИ соединен с установочным входом счетчика, выходы разрядов которого соединены с соответствующими входами элемента ИЛИ, выход которого соединен со входом элемента НЕ и со вторым входом первого элемента И, выход которого соединен с вычитающим входом счетчика и со входом разрешения сдвига второго кольцевого регистра сдвига, выходы разрядов которого соединены с соответствующими входами шифратора, выход которого соединен со вторым входом блока элементов И. выход которого является выходом устройства, выход последнего разряда первого коль.%4цевого регистра сдвига и выход элемента НЕ соединены соответственно с первым и вторым входами третьего элемента И, выход второго элемента И соединен со входом разрешения сдвига первого кольцевого регистра сдвига.Производственно-издательский комбинат "Патент", г, Ужгород, у рина, 101 Заказ 4307 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., 4/5