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

 

УСТРОЙСТВО Д)1Я ВОЗВЕДЕНИЯ ЧИСЕЛ В СТЕПЕНЬ ПО МОДУЛЮ Р по авт. св. № 1095172, отличающеес я тем, что, с целью расширения функциональных возможностей путем возведения чисел в нечетную степень для полного диапазона изменения чисел .0, Р - 1 (где Р - модуль устройства)j в него введены первый. второй и третий элементы ИЛИ, первый и второй элементы И, при этом первая и вторая группы выходов дешифратора подключены к входам соответственно первого и второго элементов ИЛИ, выходы которых подключены к первым входам соответственно первого и второго элементов И, к вторым входам которых подключен вход управления нечетной степени устройства, выход первого элемента И подключен к первому входу третьего элемента ИЛИ, к второму входу которого подключен вход управления четной степени устр ойства, выходы третьего элемента ИЛИ и второго элемента И подключены соответственно к вторым вхо (Л дам первой и. второй групп элементов И.

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

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

РЕСПУБЛИК

4(51) G 06 F 7/49

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (61) 1095172 (21) 3670860/24-24 .(22) 02.12.83 (46) 07.06.85. Бюл. N- 21 (72) В.А.Краснобаев и А.Ю.Семенов (53) 681..325(088.8) (56) 1. Авторское свидетельство СССР

М 1095172, кл. G 06,F 7/49, 29.03.83 (прототип).

:(54) (57) УСТРОЙСТВО ДЛЯ ВОЗВЕДЕНИЯ

ЧИСЕЛ В СТЕПЕНЬ ПО МОДУЛЮ Р по авт. св. Р 1095172 отличающее— с я тем, что, с целью расширения функциональных возможностей путем возведения чисел в нечетную степень для полного диапазона изменения чисел 0, P — t) (где P — модуль устройства), в него введены первый, „„я0,„, д оящ87. А второй и третий элементы ИЛИ, первый и второй элементы И, при этом первая и вторая группы выходов дешифратора подключены к входам соответственно первого и второго элементов

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

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

»60397

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

По основному авт.св..У 1095172 известно устройство, содержащее входной и выходной регистры, дешифратор, шифратор, первую группу

Р 1 1О элементов ИЛИ (Р— модуль, по е которому работает устройство), первую и вторую группы элементов И, сумматор по модулю Р и вторую группу элементов ИЛИ 11. 1$

Однако устройство позволяет осуществлять операцию возведения чисел

А в натуральную степень при n =

2K+ 1 (К = О, 1, 2,...) по модулю

P только для чисел, лежащих в диапазоР + 1

2- — < A < P — 1, т.е. имеет ограг ниченные функциональные возможности.

Цель изобретения — расширение функциональных возможностей путем возведения чисел в нечетную степень для полного диапазона изменения чисел (U, Р - 1) (где Р— модуль устройства). ! !

Поставленная цель достигается тем, что в устройство дополнительно введены первый, второй и третий элементы ИЛИ, а также первый и второй элементы И, при этом первая (1

Р 1 Р+ 1

) и вторая (+ Р-1) груп- . 3

2 пы выходов дешифратора подключены к входам соответственно первого и второго элементов ИЛИ, выходы которых подключены к первым входам соответ40 ственно первого и второго элементов И, к вторым входам которых подключен вход управления нечетной степени устройства, выход первого элемента И подключен к первому вхо45 ду третьего элемента ИЛИ, к второму входу которого подключен вход .управления четной степени устройства, выходы третьего элемента ИЛИ и второго элемента И подключены соответстЮ венно к вторым входам первой и второй групп элементов И.

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

Устройство содержит вход 1, входной регистр 2, дешифратор 3, первую

Р— 1 группу элементов ИЛИ 4, шифстепенью.

Дешифратор 3 служит для преобразования входных операндов А из двоичного кода в десятичный.

В.табл. 1 приведены значения, при своенные паре выходных шин пешифратора при P = 7.

Шифратор 5 служит для преобразоьания чисел из десятичного кода в двоичный. Количество входных шин шифратора 5 равно количеству элеменР-1

ToB ИЛИ 4 2 ° Количество BblxopHhlx шин.шифратора 5 зависит от значения модуля Р и величины степени п. Выходным шинам шифратора 5 присвоены знаи <Р-1 чения А (mod Р) для 1 < А <

2.

В табл. 2 приведены значения, присвоенные выходным шинам шифратора 5 для значений P = 7, n = 2, Р 7, и = 3 и Р = 7, и = 4.

Для заданного значения модуля P при произвольных п, схемы шифраторов

5 различны и могут выполняться в виде съемных ПЗУ. Сумматор 8 по модулю P служит для инвертирования по модулю P npu n — 2К + 1 и < А4

Р + Р— 1 остатка о(А" (mod P), т.е. на выходе сумматора 8 получаем результат операции P — 4

Таблица 1.

Номер пары шин

Значение, присвоенное паре выходных шин (Р = 7) 1,6

2;5

3,4 ратор 5, первую и вторую группы эле ментов И 6 и 7, сумматор 8 по модулю Р, вход 9 знака модуля P (шина подачи значения модуля P в двоичном коде), вторую группу элементов

ИЛИ 10, выходной регистр 11, выходы

12, первый и второй элементы ИЛИ 13 и 14, первый и второй элементы

И 15 и 16, вход 17 управления вычислением значения нечетной степенью, третий элемент ИЛИ 18 и вход 19 управления вычислением значения четной.ieO397

Таблица 2

А (mod 7) А (шой 7) A (mod 7) Выход ц 2 о

25 (P — А) mod Р, если — < А (P—

+- 1

2 AO

1, поступает на первые входы первой и второй групп элементов И б и 7.

Пусть п = 2К + 1. В этом случае сигнал с входа 17 открывает элементы

И 15 и 16. Если 1(А (го

2 сигнал с выхода дешифратора 3 через элемент ИЛИ. 13, элемент И 15 и элемент ИЛИ 18 открывает элементы И 6.

Р+1

Если 2 (А с, P — 1, то сигнал

Отметим, что в табл. 1 и 2 нуль не кодируем, так как в этом случае операция возведения чисел в степень по модулю P выполняется быстрее простым анализом входного операнда, при А = О, А (mod P) = О.

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

С входа 1 устройства в регистр

2 в двоичном коде заносится операнд

А. Дешифратор 3 преобразует операнд

А в десятичный код. Сигнал, соответствующий значению входного операнда А, через соответствующий элемент

ИЛИ 4 поступает на вход шифратора

5, с выхода которого значение

А" (mod P), если 1 @ А C или

2 с выхода дешифратора 3 .через элемент

ИЛИ 14 и элемент И 16 открывает элемент И 7.

Пусть n = 2K. В этом случае сигнал с входа 19 через элемент ИЛИ 18 открывает элементы И 6.

Если элементы И б открыты, то значение А" (mod Р) или (P — А) mod P через элементы ИЛИ 10 поступает на вход регистра 11. Если элементы И 7 открыты, то значение А" (mod P) или (P - А)" mod P поступает иа первый вход сумматора 8, на второй вход которого с входа 9 поступает значение модуля P в двоичном коде. С выхода сумматора 8 значение P— — А"(mod P) или P — (P — А)" mod P через элементы ИЛИ 10 поступает на вход регистра 11.

Техническое преимущество изобретения состоит в расширении.функциональных возможностей устройства за счет выполнения операции возведения чисел по модулю P для любых натуральных значений показателя степени и. При этом для п 2К + 1 числовой диапазон возможных значений операндов А увеличивается с,p - 1

ГР+ 1

2 до О, P — - 1, т.е. вдвое, 1160397

Составитель А.Жижин

Техред Л.Микеш Корректор Л.Пилипенко

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

Тираж 710 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открЫтий

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

Заказ 3779/46

Филиал ППП "Патент", r. Ужгород, ул. Проектная, 4