Устройство для возведения чисел в степень по модулю Р Советский патент 1985 года по МПК G06F7/49 

со со 1 Изобретение относится к вычислительной технике и может быть использовано в системах и устройствах, работающих в системе остаточных клас сов. По основному авт.св. № 1095172 известно устройство, содержащее входной и выходной регистры, дешифра тор, шифратор, первую группу -J--элементов ИЛИ (Р - модуль, по которому работает устройство), перву и вторую группы элементов И, сумматор по модулю Р и вторую группу элементов ИЛИ . Однако устройство позволяет осуществлять операцию, возведения чисел А в натуральную степень при п. 2К + 1. СК. О, 1, 2,...) по модулю Р только для чисел, лежащих вдиапазоне - -- Л Р - 1, т.е. имеет огра ниченные функциональные возможности Цель изобретения - расширение функциональных возможностей путем возведения чисел в нечетную степень для полного диапазона изменения чисел о, Р - 1 (где Р - модуль ус ройства) . Поставленная цель достигается тем, что в устройство дополнительно введены первый, второй и эле менты ИЛИ, а также первый и второй элементы И, при этом первая (1 + Р- 1) групи вторая П / «i «J 1 VJtVti J. л пы выходов дешифратора подключены к входам соответственно первого и второго элементов. ИЛИ, выходы котор подключены к первым входам соответственно первого и второго элементов И, к вторым бходам которых подключен вход управления нечетной степени устройства, выход -первого элемента И подключен к первому входу третьего элемента ИЛИ, к второму входу которого подключен вход .уп равления четной степени устройства, выходы третьего элемента ИЛИ и втор го элемента И подключены соответственно к вторым входам первой и второй групп элементов И. На чертеже представлена структурная схема предлагаемого устройства. Устройство содержит вход 1, входной регистр 2, дешифратор 3, первую Р - 1 груп; 2- элементов ИЛИ 4, шиф72ратор 5, первую и вторую группы эле ментов И 6 и 7, сумматор 8 по модулю Р, вход 9 знака модуля Р (шина подачи значения модуля Р в двоичном коде), вторую группу элементов ИЛИ 10, выходной регистр 11, выходы 12, первый и второй элементы ИЛИ 13 и 14, первый и второй элементы И 15 и 16, вход 17 управления вычислением значения нечетной степенью, третий элемент ИЛИ 18 и вход 19 управления вычислением значения четной степенью. Дешифратор 3 служит для преобразования входных операндов А Из двоичного кода в десятичный. В.табл. 1 приведены значения, присвоенные паре вькодных шин дешифратора при Р 7. Шифратор 5 служит для преобразования чисел из десятичного кода в двоичный. Количество входных шин шифратора 3 равно количеству элеменР - 1 трв ИЛИ 42- Количество выходных шин шифратора 5 зависит от значения модуля Р и величины степени п. Выходным шинам шифратора 5 присвоены знлчения А (mod Р) для 1 $ А В табл. 2 приведены значения, присвоенные выходным шинам шифратора 5 для значений Р 7, п 2, Р 7, п 3 и Р 7, п 4. Для заданного значения модуля Р, при пр.оизвольных п,. схемы шифраторов 5 различны и могут выполняться в виде съемных ПЗУ. Сумматор 8 по мрдулю Р служит для инвертирования по модулю Р при п 2К + 1 и 4 А4 SP - 1 остатка о( А (mod Р), т.е. на выходе сумматора 8 получаем результат операции Р - о( . Таблица 1 Значение, присвоенное паре выходных шин (Р 7)

Таблица 2

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

1

1

4 2 2 4 1

2

3 4

5 6 Отметим, что в табл. 1 и 2 нуль не кодируем, так как в этом случае операция возведения чисел в степень по модулю Р вьтолняется быстрее . простым анализом входного операнда, при А О, А (mod Р) 0 Устройство работает следующим образом. С входа 1 устройства в регистр 2 в двоичном коде зайосится операнд А. Дешифратор 3 преобразует операнд А в десятичный код. Сигнал, соответ ствующий значению входного операн да А, через соответствующий элемен ИЛИ 4 поступает на вход шифратора 5, с выхода которого значение А (mod Р), если 1 s А4 --, или (Р - A)mod Р, если А $ Р - 1, поступает на первые входы первой и второй групп элементов И 6 и Пусть п 2К + 1. В этом случае сигнал с входа 17 открывает элемент И 15 и 16. Если 1 $ А$ сигнал с выхода дешифратора 3 через элемент ИЛИ. 13, элемент И 15. и элемент ИЛИ 18 открывает элементы И 6. Р + 1 Если -2- А Р - 1, то сигнал

1 2 4 4 2 1

1 1 6 1 6 6 с выхода дешифратора 3 через элемент ИЛИ 14 и элемент И 16 открывает элемент И 7. Пусть п 2К. В этом случае сигнал с входа 19 через элемент ИЛИ 18 открывает элементы И 6. Если элементы И 6 открыты, то значение А (mod Р) или ,(Р - А) mod Р через элементы ИЛИ 10 поступает на вход регистра 11. Если элементы И 7 открыты, то значение А (mod Р) или (Р - А) mod Р поступает на первый вход сумматора 8, на второй вход которого с входа 9 поступает значение модуля Р в двоичном коде. С выхода сумматора 8 значение Р - А(mod Р) или Р - (Р - А) mod Р через элементы ИЛИ 10 поступает на вход регистра 11. Техническое преимущество изобретения состоит в расширении функцио нальных возможностей устройства за счет вьшол-нения операции возведения чисел по модулю Р для любых натуральных значений показателя степени п. При этом для п 2К +1 числовой диапазон возможных значений операн ГР + ов А увеличивается с1-тГ 1 , Р - 1J, т.е. вдвое.

fM

f f

13

1

f

17

16 -o

15

W -o