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

 

УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛ ПО МОДУЛЮ, содержащее два входных регистра, два дешифратора, три группы элементов ИЛИ,четыре группы элементов И,табличный вычислитель значений вида а . (mod Р/2)+Р/2 пять элементов ИЛИ, два элемента И и шифратор, причем входы первого и второго операндов устройства соединены соответственно с входами первого и второго входных регистров, выходы которых соединены соответственно с входам первого и второго дешифраторов, первые группы выходов которых соединены соответственно с первыми входами элементов ШШ первой и второй групп и входами первого и второго элементов ИЛИ, а вторые группы выходов - с вторыми входами элементов ИЛИ первой и второй групп и входами третьего и четвертого элементов ИЛИ соответственно, выходы первого и четвертого элементов ИЛИ соединены соответственно с первым и вторым входами первого элемента И, выход которого соединен с первым входом пятого элемента ИЛИ,второй вход которого соединен с выходом второго элемента И, первый и второй входы которого соединены соответственно с выходами второго и третьего элементов ИЛИ, выходы элементов ИЛИ первой и второй групп соединены соответственно с первыми входами элементов И первой и второй , групп, вторые входы которых соединены с входом управления устройства, а выходы - соответственно с пер (Л вой и второй группами входов табличного вычислителя значений вида (mod Р/2)+Р/2, выходы которого соединены соответственно с первыми входами элементов И третьей и четвертой групп, вторые входыкоторых соединены с выходом пятого элемента ИЛИ, а выходы - с первыми и вторыми входами элементов ИЛИ третьей группы, отличающееся ON тем, что, с целью упрощения, в него введен выходной регистр, информационные входы которого соединены с выходами элементов ИЛИ третьей группы, а выходы - с входами шифратора, выход которого соединен с выходом устройства.

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

СОЦИАЛИСТИЧЕСНИХ

PECflVBJlHH (19) (11) (51)4G 06 F 7 49

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3742043/24-24 (22) 16.05.84 (46) 23.10.85. Бюл. 9 39 (72) О.Н. Фоменко, В.А. Краснобаев, В.Н. Уваров и В.А. Каревский (53) 681.325 (088.8) (56) Авторское свидетельство СССР

Ф 981990, кл. G 06 F 7/49, 1981.

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

В 1030799, кл. G 06 F 7/49, 1982. (54) (57) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ

ЧИСЕЛ ПО МОДУЛЮ, содержащее два входных регистра, два дешифратора, три группы элементов ИЛИ,четыре груп- пы элементов И,табличный вычислитель значений вида a / . (mod P/2)+P/2> пять элементов ИЛИ, два элемента И и шифратор, причем входы первого и второго операндов устройства соединены соответственно с входами первого и второго входных регистров, выходы которых соединены соответственно с входами, первого и второго дешифраторов, первые группы выходов которых соединены соответственно с первыми входами элементов ИЛИ первой и второй групп и входами первого и второго элементов ИЛИ, а вторые группы выходов — с вторыми входами элементов ИЛИ первой и второй групп и входами третьего и четвертого элементов ИЛИ соответственно, выходы первого и четвертого элементов ИЛИ соединены соответственно с первым и вторым входами первого элемента И, выход которого соединен с первым входом пятого элемента ИЛИ,второй вход которого соединен с выходом второго элемента И, первый и второй входы которого соединены соответственно с выходами второго и третьего элементов ИЛИ, выходы элементов ИЛИ первой и второй групп соединены соответственно с первыми входами элементов И первой и второй, групп, вторые входы которых соединены с входом управления устройства, а выходы — соответственно с первой и второй группами входов табличного вычислителя значений вида а f3 (mod Р/2)+Р/2, выходы которого соединены соответственно с первыми входами элементов И третьей и четвертой групп, вторые входы которых соединены с выходом пятого элемента ИЛИ, а выходы — с первыми и вторыми входами элементов ИЛИ третьей группы, о т л и ч а ю щ е е с я тем, что, с целью упрощения, в него введен выходной регистр, информационные входы которого соединены с выходами элементов ИЛИ третьей группы, а выходы — с входами шифратора, выход которого соединен с выходом устройства.

1187161

6 0 6 -1 13 1

1 6

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

Цель изобретения — упрощение устройства.

На чертеже представлена структурная схема устройства для умножения чисел по модулю. 10

Устройство содержит первый 1 и второй 2 входы устройства, первый 3 и второй 4 входные регистры, первый 5 и второй 6 дешифраторы, три группы элементов ИЛИ 7-9, четыре . 15 группы элементов И 10-13, вход 14 управления устройства, пять элементов ИЛИ 15-19, два элемента И 20 и 21, табличный вычислитель 22 значений вида à P (mod Р/2)+Р/2, выход- 20 ной регистр 23, шифратор 24, выход 25 устройства.

Шифратор 24 служит для преобразования операндов унитарного кода 25 в двоичный.

Табличный вычислитель 22 представляет собой двухвходовое ПЗУ.

Количество элементов И в узлах табличного вычислителя 22 равно

P-2 2 () где P — - модуль умножения.

Входные операнды устройства лежат в интервале 1 6 А, В « Р-1 таблич(/ ного вычислителя, а входные операн- 35 ды табличного вычислителя 22

Р-г

1 а Я (—.

Известно, что для операндов, представленных в искусственной форме

A = А + P/2, В = В + P/2, резуль-. тат операции модульного умножения представляется в виде (А В) = А В

/ или (А В) = А В +Р/2. В предлагаемом устройстве табличному вычислителю 22 присваиваются значения а Р (mod P/2)+Р/2, представленные в табл.1.

Такое кодирование позволяет не- 50 посредственно установить взаимно однозначное соответствие между кодами чисел в искусственной форме и кодами чисел в обычном представлении.

В табл.1 знаком (+) отмечены случаи, 55 когда (а 3) = а /3 (mod P).

B табл.2 представлены операнды в искусственной форме для P = 14.

Т а б л л ц а 1 (Р=14)1

1 13 8 9 10 11 12 13

2 12 9 11 13 8+ 10+ 12+

3 11 10 13 9+ 12+ 8 11

4 10 11 8+ 12+ 9 13 10+

5 9 12 10+ 8 13 11+ 9

6 8 13 12+ 11 10+ 9 8+

Таблица 2 (Р=14) ((((А fA а А А gA а А

1 0 1 -6 8 1 6 1

2 0 2 -5 9 1 5 2

3 0 3 -4 10 1 4 3

4 0 4 -3 11 1 3 4

5 0 5 -2 12 1 2 5

Таким образом, при реализации операции модульного умножения в предлагаемом изобретении происходит самокоррекция результата операции за счет внутренней структуры таблицы вычислителя 22 (таблица 1). Количество входных шин в каждой группе

P-2 входов вычислителя 22 равно, а выходных шин - (Р-1) .

Дешифраторы 5 и 6 имеют две группы выходов, каждая из которых включает в себя соответственно

P-2 Р+2 (1 — — ) и (— — Р-1) выходов.

2 2

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

По входам 1 и 2 входные операнды А и В в двоичном коде постуI лают на соответствующие входные регистры 3 и 4, с выходов которых поступают на соответствующие дешифраторы 5 и 6. С выходов дешифраторов 5 и 6 операнды А и В в деся/

3 1 тичном коде поступают на соответстствующие элементы ИЛИ 7 и 8, с выходов которых операнды а и /3 (А =

=(gА, а ), В = (, P )) через элементы И 10 и 11 групп, которые одновременно открываются сигналом 14, поступают на входы табличного вычислителя 22. Выходной сигнал табличного вычислителя 22, соответствующий значению а P (mod Р/2)+P/2, поступает на первые входы К-го элемента И 12 группы и К-го элемента И 13 группы (К = 1,2,...,Р-1).

Если = 4 то элементы И 20 и 21 закрыты и выходной сигнал элемента ИЛИ 19 отсутствует. Элементы И 12 группы открыты, а элементы И 13 группы закрыты (на первый запрещающий вход элемента И 12 группы сигнал с выхода элемента ИЛИ 19

187161 4 не поступает). В этом случае сигнал с выхода К-го элемента И 12 группы поступает на вход К-ro элемента ИЛИ

9 группы, с выхода которого сигнал поступает на вход регистра 23 и далее поступает на шифратор 24, с выхода которого результат операции модульного умножения в двоичном коде поступает на выход 25 устрой1р ства.

I I

Если gA 4 fs,òî сигнал с выхода элемента ИЛИ 19 присутствует. Этот сигнал закрывает элементы И 12 группы и разрешает прохождению сигнала с выхода табличного вычислителя 22 через элементы И 13 группы. В этОм случае сигнал с выхода К-го элемента И 14 поступает на вход (P-К)-ro элемента ИЛИ 9 группы.

Филиал ППП Патаитг, г. Улгорол, ул.Проаатиаа,4

ВИИИПИ Заказ 6551/54 Тираж 709

Подписное