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

 

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

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

СОЦИАЛИСТИЧЕСНИХ . РЕСПУБЛИН (5д 4 G 06 F 7/72 7/552

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

К ABTOPCHOMY CBMQETEAbCTB Y

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (61) 1168934 (21) 4264761/24-24 (22) 19.06.87 (46) 15.01.89. Бюл. В 2 (72) О.Н.Фоменко, В.А.Краснобаев, Е.Ф.Глазин, Г.М.Чигасов, В.M.Ïàíêîâ, А.А.Журавлев и А.А,Леваков (53) 681.3 (088 ° 8) (56) Авторское свидетельство СССР

И 1168934, кл. С 06 F 7/72, 1983. (54) УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ И ВЫЧИ

ТАНИЯ ЧИСЕЛ ПО МОДУЛЮ m

„„SU.„1451691 A 2 (57) Изобретение относится к области автоматики и вычислительной техники, может быть использовано в системах и устройствах, функционирующих в системах остаточных классов, и является усовершенствованием устройства по авт. св. СССР Ф 1168934. Цель изобретения — расширение функциональных возможностей за счет реализации операции возведения чисел в квадрат .по модулю m. Поставленная цель достигается путем введения шифратора 5, второй группы элементов И 15, группы элементов ИЛИ 17. 1 ил.

1451691

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

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

-выполнения операции возведения чисел в квадрат по модулю m.

На чертеже представлена структурная схема устройства, На схеме обозначены первый информационный вход 1, первый входной регистр 2, дешифратор 3, группа ключевых элементов 4, шифратор 5, первая группа элементов И 6, первый элемент

ИЛИ 7, выходной регистр 8, выход 9 устройства, первый управляющий вход

10 устройства, первый 11 и второй 12 элементы И, умножитель 13 частоты, кольцевой регистр 14 сдвига (KPC) вторая группа 15 элементов И, второй информационный вход 16 устройства, группа 17 элементов ИЛИ, второй вход- . ной регистр 18, сумматор 19 по модулю m, шина 20 подачи значения модуля

m третий 21 и четвертый 22 элементы И,. второй элемент ИЛИ 23, прием30 ный регистр 24, схема 25 сравнения, счетчик 26 импульсов, второй 27, третий 28 и четвертый 29 управляющие управляющие входы устройства и генератор 30 импульсов. 35

Выходы дешифратора подключены к соответствующим входам шифратора таким образом, что на выходе этого шифратора присутствует двоичный код, соответствующий значению операнда, 40 равному количеству сдвигов KPC. При этом в режиме возведения числа А в квадрат по модулю ш операнд указывает номер разряда КРС, с которого результат операции А )mod m(поступает 45 в выходной регистр, а выходной код шифратора .определяет количество сдвигов разрядов KPC. В таблице приведен алгоритм получения результата операции А (mod.m 1 для m=5 50

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

Для сложения (присутствует сигнал с входа 27) и вычитания (присутствует сигнал с входа 28) алгоритм работы предлагаемого устройства аналогичен алгоритму работы известного.

Рассмотрим алгоритм работы предлагаемого устройства при определении реФ зультата операции возведения числа

A в квадрат по модулю m, т.е.

А f mod mf. В этом случае одновременно присутствует сигнал входов 27 и 29 управления. Входной операнд А в двоичном коде по входу f поступает во входной регистр 2 и далее на вход дешифратора 3, с выхода которого сигнал, соответствующий значению А в унитарном коде, поступает на первый вход соответствующего ключевого элемента 4 и на соответствующий вход шифратора 5, с выхода которого двоичный код, соответствующий количеству необходимых сдвигов разрядов KPC

14, через открытые элементы И группы 15 и первые входы элементов ИЛИ группы f7 поступает на вход регистра 18 и далее через открытый элемент

И 21 и элемент ИЛИ 23 в приемный регистр 24 ° Сигнал с входа 10 запускает генератор 30 импульсов, с выхода которого импульсы через открытые элементы И 11 и 12 поступают соответственно на умножитель 13 частоты и на вход счетчика 26. С выхода умйожителя

13 частоты импульсы, увеличенные в

n(logz(m-f)) раз, поступают на управляющие входы KPC 14, сдвигая в поло" жительном направлении (против часовой стрелки) содержимое разрядов КРС 14.

При совпадении содержимого счетчика

26 и регистра 24 схема 25 сравнения выдает сигнал, который закрывает элементы И 11 и 12 и открывает соответствующий ключевой элемент 4 и соответствующий элемент И 6, через который содержимое соответствующего разряда КРС 14 (через первый элемент

ИЛИ 7) поступает на вход регист-. ра 8.

Пример. Пусть m=5, A=100.

Необходимо определить А j mod m(.

Значение А=100 поступает на вход дешифратора 3, с выхода которого сигнал по четвертому (A=100) выходу поступает на первый вход четвертого ключевого элемента 4 и на второй вход шифратора 5 (см, таблицу), значение

010 через элементы И группы 15 и элементы ИЛИ группы 17 поступает во входной регистр 18, с выхода которого двоичный код 010 через открытый элемент И 21 и элемент ИЛИ 23 поступает в регистр 24. Сигнал с входа 1О запускает генератор 30,с. выхода которого импульсы через открытые элементы И 11 и 12 поступают на вход ум000 — 001 — 010 — 01 — 100

Устройство для сложения и вычита ния чисел по модулю m по авт св, 9 1168934 отличающееся тем, что, с целью расширения функциональных возможностей за счет реализации операции возведения чисел в квадрат по модулю m, в него введены шифратор, группа элементов ИЛИ, вторая группа элементов И, причем выходы дешифратора подключены к соответствующим входам шифратора, выходы которого подключены к первым входам элементов И второй группы, вторые входы элементов И которой подключены к четвертому управляющему входу устройства, а выходы — к первым входам элементов ИЛИ группы, вторые входы и выходы элементов ИЛИ которой соединены соответственно с вторым информационным входом устройства и входом второго входного регистра. содержимое разрядов KPC 14 сдвигается на два (010) разряда KPC (nx2 3х2=6 двоичных разряда) в положительном направлении, т.е. содержимое разрядов KPC 14 представляется в виде

-"010 — 011 — 100 — 000 — 001

В этом случае содержимое счетчика 26 совпадает с содержимым регистра 24 и выходной сигнал счетчика 25 закрывает элементы И 11 и 12 и открывает четвертый ключевой элемент 4 и четвертый элемент И 6, через который содержи мое 001 четвертого разряда KPC 14 через элемент ИЛИ 7 поступает в регистр 8.

Проверка: 4 =1 mod 51 .

Выход шиф",Колиратора 5 чество А 1 mod 5) сдвигов

KPC 14

Вход шифратора 5

А Выход дешифратора 3

000

000

000

001

000

001

100

010

010

001

100

011

2 001

010

100

Составитель О.Фоменко

Редактор А.Orap Техред А.Кравчук Корректор С.Черни

Заказ 7081/47 Тираж 667 Подписное

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

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

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

1451691

4 ножителя 13 и счетчика 26. При исход- Ф о р м у л а и з о б р е т е н и я ном состоянии разрядов КРС 14.