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

 

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

CNhll

РЕСПУБЛИК

0Ю 01)

3QD G 06 F 7 72

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (61) 1034036 (21) 3521412/18-24 (22) 15. 12. 82 (46) 07.06.84. Бюл. В -21 (72) В.А.Краснобаев, А.Ю.Семенов, Е.И.Бороденко, В.И.Стеценко и В.В.Панарин (53) 681.325(088.8) (56) 1. Авторское свидетельство СССР

М 1034036, кл. С 06 F 7/72, 1982 (прототип). (54) (57) УСТРОЙСТВО ДЛЯ ВОЗВЕДЕНИЯ

ЧИСЕЛ В КВАДРАТ ПО МОДУЛЮ P по авт. св. У 1034036, о т л и ч а ю ш е е— с я тем, что, с целью расширения области применения за счет вычисления как в полошительном, так и в отрицательном диапазоне чисел, в него .введены группа элементов запрета, группа элементов И, сумматор по модулю

P вторая группа элементов ИЛИ, причем выходы регистра выхода соединены соответственно с первыми входами элементов И группы, вторые входы которых объединены и подключены к шине задания диапазона вычисления устройства, выходы элементов И группы соединены соответственно с группой входов сумматора по модулю Р, вход константы которого соединен с шиной задания значения- Р/2, выходы сумматора по модулю P соединены соответственно с первыми входами элементов ИЛИ второй группы, вторые входы которых соединены соответственно с выходами элеФ ментов запрета группы, первые входы Е которых соединены соответственно с выходами регистра выхода, вторые входы элементов запрета группы объединены и соединены с шиной задания диапазона .вычисления устройства. g

1096641

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

По основному авт.св. У !034036 известно устройство для возведения чисел в квадрат по модулю Р, содержащее регистр входа, регистр выхода, P — 1

10 дешифратор, группу 2 элементов

ИЛИ, шифратор, причем вход устройства соединен с входом регистра входа, выход которого соединен попарио с входами соответствующих элементов

ИЛИ, выход регистра выхода соединен

1с выходом устройства, выходы элементов ИЛИ соединены соответственно с входами шифратора, выход которого ч 20 соединен с входом регистра выхода (1 .

Недостаток прототипа — невозможность работы в отрицательном диапазоне чисел.

Цель изобретения — расширение об25 ласти применения за счет вычисления как в положительном, так и в отрицательном диапазоне чисел, Поставленная цель достигается тем, что в устройство введены группа элементов запрета, группа элементов

И, сумматор по модулю Р, вторая группа элементов ИЛИ, причем выходы регистра выхода соединены соответственно с первыми входами элементов И 35 группы, вторые входы которых объединены и подключены к шине задания диапазона вычисления устройства, выходы элементов И группы соединены соответственно с группой входов сум- 40 матора по модулю Р, вход константы которого соединен с шиной задания значения P/2, выходы сумматора по модулю P соединены соответственно с первыми входами элементов. ИЛИ второй группы, вторь!е входы которых соединены соответственно с выходами элементов запрета группы, первые входы которых соединены соответственно с выходами регистра выхода, вторые вхо- 50 ды элементов запрета группы объединены и соединены с шиной задания диапазона вычисления устройства.

Известен алгоритм выполнения операции возведения чисел в квадрат по модулю P для операндов, лежащих только в положительном числовом диапазоне (О «< А с P) В = A (mod Р) =cC, т е. A„=

K Р + g (О - d„ c Р) .

Для определения результатов операции возведения в квадрат по модулю

Р как в положительном, так и в отрицательном числовом диапазоне рассмотрим выражение

А „(ао,1 P/2) = (A — P/2) ê хюо<1Р/2 = j(A )г — A Р + Р /4) од P/2 = K (— P/2 < А „о с P/2), т. е. А (mop P/2) = А (rno3P) = — (A ) mod Р где А = А = А + Р/2 — искусствен1 о ная форма представления операндов (входной операнд устройства).

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

В = А,p (

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

В = j(A ) щам Р + Р/ ") pd Р.

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

Схема содержит вход 1 устройства, регистр 2 входа, дешифратор 3, первую группу элементов ИЛИ 4, шифратор 5, регистр 6 выхода, группу элементов 7 запрета, группу элементов И 8, шину

9 задания диапазона вычисления устройства, сумматор 10 по модулю P шину 11 залания значения P/2, вторую группу элементов ИЛИ 12, выход 13 устройства.

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

По входу 1 в регистр 2 заносится значение операнда А0(А ) в двоичном коде. Дешифратор 3 йреобразует двоичный код в унитарный (десятичный).

Сигнал, соответствующий значению входного операнда А (А ), через соответствующий элемент ИЛИ 4 поступает на вход шифратора 5, с выхода которого значение А „- "(mod P), ((А )

«шо Р) поступает на вход регистра 6.

Пусть необходимо определить результат операции для операндов, лежащих только в положительном числовом диапазоне. В этом случае сигнал по шине 9 отсутствует: элементы 7 запрета открыты, а элементы И 8 закрыты. С выхо! 096641

ВНИИБИ Зажав 3826/36 Тираж: 699 Подписное

Филиал ППП "Патент", r.Óxrîðîä, ул.Проектная, 4 да регистра 6 сигнал, соответствующий значению А „ (m()3 P), через открытые элементы 7 запрета и элементы

ИЛИ 12 поступает на выход 13 устройства. 5

Пусть необходимо определить результат операции для операндов, лежащих либо в положительной, либо в отрицательном числовых диапазонах. В этом случае сигнал шины 9 присутству-10 ет: элементы 7 запрета закрыты, а элементы И 8 открыты. С выхода регистра 6 сигнал, соответствующий значению (А ) ad P, через открытые элементы И 8 поступает на первый вход сумматора 10, на второй вход которого по шине 11 поступает значение

P/2. Сумматор 10 производит операцию модульного сложения

В - ((А ) под Р + P/2) щоS Р, а выходной сигнал сумматора 10, соответствующий этому значению, через элементы ИЛИ 12 поступает на выход

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

Таким образом, данное устройство позволяет производить операцию возведения чисел в квадрат. по модулю P для операндов, находящихся как в положительном, так и в отрицательном числовом диапазоне. !