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

7Г Изобретение относится к вь числЯ тельной технике и может быть исполы зовано в устройствах, работающих в системе остаточных классов. Известны устройства умножения, с помощью которых можно осуществить операцию возведения чисел в произвольную степень по модулю Р. Эти уст ройства содержат входные регистры, дешифраторы, элементы И и ИЛИ и т.д. 1 . Недостаток этих устройств - низкие функциональные возможности. Наиболее близким по технической сущности к изобретению является уст ройство, содержащее входной и выходной регистры, дешифратор, шифратор, группу Р -1/2 элементрв ИЛИ, причем входы операнда устройства соединены с входами входного регистра, выходы которого соединены с входами дешифра тора, выходы которого соединены попарно с входами соответствующих элементов ИЛИ, выходы выходного регистра соединены с выходами устройства, выходы элементов ИЛИ соединены соответственно с входами шифратора 2 . Недостаток прототипа - ограниченная область применения из-за того, что данное устройство не позволяет осуществлять операцию возведения чисел в нечетную () степень по модулю Р . Цель изобретения - расширение области применения путем возведения ка; в четную, так и нечетную степень Поставленная цель достигается тем чтЬ в устройство, содержащее входной и выходной регистры, дешифратор, шиф ратор, группу Р -1/2 элементов ИЛИ, причем входы операнда устройства сое динены с входами входного регистра, выходы которого соединены с входами дешифратора, выходы которого соедине ны с входами дешифратора, выхода которого соединены, попарно с входами соответствующих элементов ИЛИ, выходы выходного регистра соединены с вы ходами устройства, выходы элементов ИЛИ соединены соответственно с входа ми шифратора, введены первая и вторая группы элементов И, сумматор по модулю Р, группа элементов ИЛИ, причем выходы шифратора соединены с пер выми входами элементов И первой и второй групп, вторые входы которых соединены соответственно с входом управления четной и входом управления нечетной степеней устройства, вы ходы элементрв И первой группы соеди нены с первыми входами элементов ИЛИ группы, вторые входы которых соедине ны с выходами сумматора по модулю Р, информационные входы которого соединены с выходами элементов И второйгруппы, вход знака сумматора по моду лю Р соединен с входом знака модуля Р устройства. Известно, что А (modP)(P -А ) mod Р , где А - входной операнд устройства; Р - модуль,К 1,2,... Это обусловлено /тем, что в разложении (р-д) с;, Р ... при четном показателе степени (), значение А входит с положительным.знаком, и поэтому IP -A)l(iP-их, rfleA kp + oc. При нечетном значении показателя степени(п 2К-1-1) (Р-А) , PA-ь... -А, т.е. значение А входит в разложение (Р -А) с отрицательным знаком, и поэтому (Р - А) К2 n-ctf т.е. при 2k.+l, А (modP) {P-A)modP . Таким образом, при п 2k-i-l и А kP-b ОС очевидно следующее равенство: (P-f fmodP P-o6. Это и является основным алгоритмом определения результата операции tmod Р )В изобретении. I На чертеже представлена структурная сх;ема предлагаемого устройства. Устройство содержит вход 1 операнда устройства, входной регистр 2, дешифратор 3, группу Р -1/2 элементов ИЛИ 4, шифратор 5, первую и вторую группы элементов И 6 и 7, вход 8 управления четной степени устройства, вход 9 управления нечетной степени устройства, сумматор 10 по модулю Р, входы 11 знака сумматора 10 , по модулю Р , элемент ИЛИ 12, выходной регистр 13, выход 14 устройства. Дешифратор 3 служит для преобразования чисел из двоичного кода в десятичный . Пары выходных шин дешифратора 3 объединяются таким образом, что сумма присвоенных значений каждой пары равна модулю Р.. Шифратор 5 служит для преобразования чисел из десятичного кода в двоичный. Количество входных шин шифратора 5 равно количеству элементов ИЛИ 4 и равно Р -1/2. Количество выходных шин шифратора 5 зависит от значений Р и п. Выходным шинам шифратора 5 присвоены значения А (mod Р ) для Oi AiP -1/2. В табл. 2 приведены значения, присвоенные выходным шинам шифратора для значений Р 7, 1 2 (1) ,р 7, (т Р 7,м 4(ш). Для заданного значения модуля Р при произвольных И схемы шифраторов 5 различны и могут выполняться в виде съемных матричных ПЗУ. Сумматор 10 по модулю Р служит для инвертирования по модулю Р при п 2k-fl значение остатка oi , т.е. на выходе сумматора 10 по модулю Р получаем результат операции Р-об. . Устройство работает следующим образом. По входу 1 во входной регистр 2 в двоичном коле заносится операнд А

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