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

(19) (11),(511 С Об У 7/ ИСАНИЕ ИЗОБРЕТЕНИЯ ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ К АВТОРСКОМУ СВИДЕТЕЛЬСТВ(56) 1. Акушский И.Я. и др. Машинная арифметика в остаточных классах. М., "Советское радио", 1968, с, 327-334,2. Авторское свидетельство СССР по заявке 9 3569037/24кл, 0 Об Р 7/72, 1983 (прототип). (54)(57) УСТРОЙСТВО ДЛЯ ВОЗВЕДЕНИЯ ЧИСЕЛ В СТЕПЕНЬ ПО МОДУЛЮ р, содержащее входной и выходной регистры, дешифратор, шифратор, группу-1/2 элементов ИЛИ, причем входы операнда устройства соединены с входами входного, регистра, выходы которого соединены с входами дешифратора, выходы которого соединены попарно с входами соответствующих элементов ИЛИ, выходы выходного регистра соединены с выходами устройства, выходы элемен.тов ИЛИ соединены соответственно с входами шифратора, о т л и ч а ю - щ е е с я тем, что, с целью расширения области применения путем возведения как в четную, так и в нечетную степень, в него введены первая и вторая группы элементов И, сумматор по модулю Р, группа элементов ИЛИ, причем выходы шифратора соединены с первыми входами элементов И первой и второй групп, вторые входы которых соединены соответственно с входом управления четной и входом уп. равления нечетной степеней устрбйства, выходы элементов И первой группы соединены с первыми входами элемен- Щ тов ИЛИ группы, вторые входы которых соединены с выходами сумматора по модулю Ринформационные входы которо. . го соединены с выходами элементов И % второй группы, вход знака сумматора по модулю Р соединен с входом знака ф модуля Р устройства.Изобретение относится к вычислятельной технике и может быть испольчзовано в устройствах, работающих всистеме остаточных классов,Известны устройства умножения,с помощью которых можно осуществить 5операцию возведения чисел в произвольную степень по модулю Р . Эти устройства содержат входные регистры,дешифраторы, элементы И и ИЛИ ит.д, 11, 10Недостаток этих устройств - низкие функциональнъе возможности.Наиболее близким по техническойсущности к изобретению является устройство, содержащее входной и выходной регистры, дешифратор, шифратор,группу Р -1/2 элементрв ИЛИ, причемвходы операнда устройства соединеныс входами входного регистра, выходыкоторого соединены с входами дешифратора, выходы которого соединены по-,парно с входами соответствующих эле-ментов ИЛИ, выходы выходного регистра соединены с выходами устройства,выходы элементов ИЛИ соединены соответственно с входами шифратора 2 .Недостаток прототипа - ограниченная область применения из-за того, что данное устройство не позволяет осуществлять операцию возведения чисел в нечетную (о =2 К+1) степеньо модулю Р .Цель изобретения - расширение области применения путем возведения 35 как в четную, так и нечетную степень.,Поставленная цель достигается тем, что в устройство, содержащее входной и выходной регистры, дешифратор, шифратор, группу Р -1/2 элементов ИЛИ 40 причем входы операнда устройства сое. динены с входами входного регистра, выходы которого соединены с входами дешифратора, выходы которого соединены с входами дешифратора, выхода которого соединены попарно с входами соответствующих элементов ИЛИ, выходы выходного регистра соединены с выходами устройства, выходы элементов ИЛИ соединены соответственно с входами шифратора, введены первая и вторая группы элементов И, сумматор по модулю Р, группа элементов ИЛИ, причем выходы шифратора соединены с первыми входами элементов И первой и второй групп, вторые входы которых соединены соответственно с входом управления четной и входом управления нечетной степеней устройства, вы. ходы элементов И первой группы соединены с первыми входами элементов ИЛИ 60 группы, вторые входы которых соединены с выходами сумматора по модулю Р, информационные входы которого соединены с выходами элементов И второй" группы, вход знака сумматора по моду 5 лю Р соединен с входом знака модуляР устройства,Известно, что А (шоаР)=(Р - А )шод. Р, где А - входной операнд устройства; Р - модуль, К = 1,2, Этообусловлено тем, что в разложении(Р -А)" =Р"- СР "Я А" при четномпоказателе степени (о=2 К), значениеА" входит с положительным знаком, ипоэтому ( Р - А) =М,Р + к, где А"=КР+В,.При нечетном значении показателястепении =2 К+1)(Р -4)"= Р"-С РА+л(Р -А ) тоаР =Р-о.Это и является основным алгоритмом определения результата операции(щоа Р ) в изобрЕтении.На чертеже представлена структурная схема предлагаемого устройства.Устройство содержит вход 1 операнда устройства, входной регистр 2,дешиФратор 3, группу Р -1/2 элементов ИЛИ 4, шифратор 5, первую и вторую группы элементов И б и 7, вход8 управления четной степени устройства, вход 9 управления нечетной степени устройства, сумматор 10 по модулю Р, входы 11 знака сумматора 10по модулю Р, элемент ИЛИ 12, выходной регистр 13, выход 14 устройства.Дешифратор 3 служит для преобразования чисел из двоичного кода в десятичный. Пары выходных шин дешифратора 3 объединяются таким образом,что сумма присвоенных значений каждой пары равна модулю Р . ШиФратор 5служит для преобразования чисел издесятичного кода в двоичный. Количество входных шин шифратора 5 равно количеству элементов ИЛИ 4 и равно Р -1/2. Количество выходных шиншифратора 5 зависит от значений Ри и . Выходным шинам шифратора 5 присвоены значения А" (воа Р ) для0 А Р -1/2.В табл. 2 приведены значения, присвоенные выходным шинам шифраторадля значений Р =7, и =2 (,1) Р =7й=3 (и) Р =7,й =4(й). Для заданногозначения модуля Р при произвольныхй схемы шифраторов 5 различны и могут выполняться в виде съемных матричных ПЗУ. Сумматор 10 по модулюР служит для инвертирования по модулю Р при о =21+1 значение остатка Ж,т.е. на выходе сумматора 10 по модулю Р получаем результат операцииР -о.Устройство работает следующим образомПо входу 1 во входной регистр 2в двоичном коле заносится операнд АЗначение, присвоенное паревыходных шин дешифратора Парашин,М 1,6 3,4 Таблица 2 3 преобразует операнд А в десятичный35 код. Сигнал, соответствующий значению.пять, через второй элемент ИЛИ 4 группы (2+5=7, табл. 1) поступает на второй вход шифратора 5, с выхода которого значения (Р -А) щоа 7=2 40 (шоа 7) (табл. 2, 1) поступают на первые входы элементов И б, 7. Так как =2 (четное), то управляющий сигнал присутствует на входе 8, и значение 2 (шоа 7)=4 через открытый элемент И б, элемент ИЛИ 12 поступает на вход выходнрго регистра 13.Проверка ( табл. 2): 5(щоа 7) =4Пусть необходимо определить результат операции 5(щоа 7) . 50В этом случае с выхода шифратора 5 значение (Р - А)щоа 7 = 2(щоа 7) =1(,табл. 2, П) поступает на первые входы элементов И б, 7. Так как и =3(нечетное), то управляющий сигнал 55присутствует на входе 9, и значениеСоставитель Л.МРедактор М.Товтин Техред С.Легезаедведева Корректор С,Шекмар Заказ 3599/31 Тираж 699 ПодписноеВНИИПИ Государственного комитетаСССРпо делам изобретений и открытий113035, Москва, Ж, Раушская наб., д. 4/5 В Ь щ МШШфилиал ППП "Патент", г.ужгород, ул,Проектная, 4 Дешифратор 3 преобразует операнд Ав десятичный код, Сигнал, .соответствующий значению входного операнда А,через соответствующий элемент 4 илигруппы поступает на вход шифратора 5,с выхода которого значение А"(щоаР),если 0- А- Р/2 или Р-А)" щоаР (если Р +1/2 й А ( Р -1), поступает на первые входы элементов И б и 7. Еслиа=21 (четное), то управляющий сигналприсутствует на первом входе 8. В 10этом случае элемент И б открыт и значение Аф (щоаР) или (Р - А)" шоа Р черезэлемент ИЛИ 12 поступает на вход выходного регистра 13. Если и =21+1 (нечетное), то управляющий сигнал присутствует на входе 9. В этом случаеэлемент, И 7 открыт и значением (щоаРили (Р -4) щоа Р поступает на входсумматора 10 по модулю Р, на входзнака, которого по входу 11 поступает значение.модуля Р . С выхода сумматора 10 по модулю Р .значение Р- А "(вод Р) или Р -(Р -А) вой Р - через элемент 12 ИЛИ поступает на вход выход"ного регистра 13. 25Примеры конкретного выполнения1 операции Аф(шоаР) для Р =7. В табл. 1даны значения, присвоенные выходнымшинам дешифратора 3.В табл. 2 даны значения А (щоа 7)для и =2, 3, 4.Пусть необходимо определить результат операции 5 (щоа 7),гПо входу 1 во входной регистр 2заносится операнд А =101. Дешифратор"единица" через открытый элемент И 7 поступает на вход сумматора 10 по модулю Р, на вход знака которого поступает значение Р =111. С выхода сумматора 10 по модулю Р значение .Г110 через элемент 2 ИЛИ посту пает на вход выходного региетра 13Проверка (табл. 2):51(шоа 7)=6,Техническое преимущество иэобрете. ния состоит,в расширении области применения за счет полученной возможнос. ти возведения чисел по модулю для любых натуральных значений показате" ля степени и.Экономический эффект закаечаетоя в уменьшении оборудования за счет совмещения и одном устройстве выпол нения операции возведения чисел в 11-ную степень по модулю Р для любых натуральных значений показателя йТ а б л и ц а 1