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

 

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

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

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

РЕСПУБЛИН (19) (11), 3(59 G 06 F 7/49

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

К ABTOPCKOMV СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3569037/18-24 (22) 29.03.83 (46) 30.05.84 Бюл. Р 20 (72) В.A.Êðàñíîáàåâ, Е.И.Бороденко и В.И.Стеценко (53) 681.325(088.8) (56) i. Акушский И.Я. и др. Машинная арифметика в остаточных классах. М., "Советское радио", 1968, с. 327-334.

2. Авторское свидетельство СССР по заявке Р 3569037/24 кл. G 06 F 7/72, 1983 (прототип). (54)(57) УСТРОЙСТВО ДЛЯ ВОЗВЕДЕНИЯ

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

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

1095172

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

Известны устройства умножения, с помощью которых можно осуществить 5 операцию возведения чисел в произвольную степень по модулю Р . Эти устройства содержат входные регистры, дешифраторы, элементы И и ИЛИ и т.д. A) . 10

Недостаток этих устройств - низкие функциональные возможности.

Наиболее близким по технической сущности к изобретению является устройство, содержащее входной и выходной регистры, дешифратор,.шиФратор, группу р --1/2 элементрв ИЛИ, причем входы операнда устройства соединены с входами входного регистра, выходы которого соединены с входами дешифра- 20 тора, выходы которого соединены попарно с входами соответствующих эле- ментов ИЛИ, выходы выходного регистра соединены с выходами устройства, выходы элементов ИЛИ соединены соответственно с входами шифратора f2) .

Недостаток прототипа — ограниченная область применения из-за того, что данное устройство не позволяет осуществлять операцию возведения чисел в нечетную (и =2К+1) степень но модулю Р .

Цель изобретения — расширение области применения путем возведения Ç5 как в четную, так и нечетную степень.

Поставленная цель достигается тем, что в устройство, содержащее входной и выходной регистры, дешифратор, шифратор, группу P -1/2 элементов ИЛИ, 40 причем входы операнда устройства соединены с входами входного регистра, выходы которого соединены с входами дешифратора, выходы которого соединены с входами дешифратора, выхода которого соединены попарно с входами соответствующих элементов ИЛИ, выходы выходного регистра соединены с вы1 ходами устройства, выходы элементов

ИЛИ соединены соответственно с входами шифратора, введены первая и вторая группы элементов И, сумматор по модулю Р, группа элементов ИЛИ, причем выходы шифратора соединены с первыми входами элементов И первой и второй групп, вторые входы которых соединены соответственно с входом управления четной и входом управления нечетной степеней устройства, выходы элементов И первой группы соединены с первыми входами элементов ИЛИ 60 группы, вторые входы которых соединены с выходами сумматора по модулю Р, информационные входы которого соединены с выходами элементов И второй" группы, вход знака сумматора по моду 5 лю Р соединен с входом знака модуля

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

Известно, что А (шооР)=(Р - A )

mod P, где A — входной операнд устройства; P — модуль, К = 1,2,... Это обусловлено тем, что в разложении (Р -А)" =Р"- C „Ð " À +... + А" при четном показателе степени (=2 k), значение

А" входит с положительным знаком, и поэтому (Р— А) =М,Р + к, где А"=КР+В,.

При нечетном значении показателя степени(и =2К+1)(Р -4)"= P"-С,, Г""А+. °л

-4", т.е. значение А входйт в разложение (P -A)" с отрицательным знаком, и поэтому (Р— А)" =К П-g,, т.е. при ь =2k.+1, А" (modP)=(Р-А)modP.

Таким образом, при и =2k+1 и A" =

1Р+ К очевидно следующее равенство: (P -A ) modP =Р-о .

Это и является основным алгоритмом определения результата операции (шод. Р ) в изобретении.

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

Устройство содержит вход 1 операнда устройства, входной регистр 2, дешифратор 3., группу Р -1/2 элементов ИЛИ 4, шифратор 5, первую и вторую группы элементов И б и 7, вход

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

Дешифратор 3 служит для преобразования чисел из двоичного кода в десятичный. Пары выходных шин дешифратора 3 объединяются таким образом, что сумма присвоенных значений каждой пары равна модулю Р . Шифратор 5 служит для преобразования чисел из десятичного кода в двоичный. Количество входных шин шифратора 5 равно количеству элементов ИЛИ 4 и равно Р -1/2. Количество выходных шин шифратора 5 зависит от значений Р и n . .Выходным шинам шифратора 5 присвоены значения A" (mod Р ) для

0 «(Д с Р -1/2

В табл. 2 приведены значения, присвоенные выходным шинам шифратора для значений Р =7, и =2 (I),P =7, п=3 (H3 Р =7,п =4(й). Для заданного значения модуля Р при произвольных схемы шифраторов 5 различны и могут выполняться в виде съемных матричных ПЗУ. Сумматор 10 по модулю

P служит для инвертирования по модулю Р при п -2k+1 значение остатка 6, т.е. на выходе сумматора 10 по модулю P получаем результат операции

Р- .

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

tIo входу 1 во входной регистр 2 в двоичном коле заносится операнд А

1095172

Значение, присвоенное паре выходных шин дешифратора

Пара шин,в

1,6

2,5

3,4

Таблица2

3 преобразует операнд A в десятичный

35 код. Сигнал, соответствующий значению.пять, через второй элемент ИЛИ 4 группы (2+5=7, табл. 1) поступает на второй вход шифратора 5, с выхода которого значения (p -А) mod 7=2 40

2 (mod 7) (табл. 2, I) поступают на первые входы элементов И 6, 7. Так как =2 (четное), то управляющий сигнал присутствует на входе 8, и значение 2 (mod 7)=4 через открытый элемент И 6, элемент ИЛИ 12 поступает на вход выходнрго регистра 13.

ПровеРка (табл. 2): 52(mod 7) =4 °

Пусть необходимо определить результат операции 5 (шоа 7) . 50

В этом случае с выхода шифратора

5 значение (p — A) mod 7 = 2 (mod 7) =1 (табл. 2, П) поступает на первые входы элементов И 6, 7. Так как и =3 (нечетное), то управляющий сигнал 55 присутствует на входе 9, и значение

Составитель Л.М

Редактор М.Товтин Техред С.Легеза

A(mod 7) A (mod 7)A)mod 7) о

I Й

I М

4 едведева

Корректор С.Шекмар

Заказ 3599/31 Тираж 699 Подписное

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

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

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

Дешифратор 3 преобразует операнд А в десятичный код. Сигнал, .соответствующий значению входного операнда А, через соответствующий элемент 4 или группы поступает на вход шифратора 5, с выхода которого значение А"(modP (если 0 A - P 1/2 или (Р -А)" тойР (если Р +1/2 - А6Р-1), поступает на первые входы элементов И 6 и 7. Если

m=2k (четное), то управляющий сигнал присутствует на первом входе 8. В 10 этом случае элемент И 6 открыт и значение А" (modP) или (Р - Ц" mod Р через элемент ИЛИ 12 поступает на вход выходного регистра 13. Если 8 =2k+1 (не. четное), то управляющий сигнал при- 5 сутствует на входе 9. В этом случае элемент, H 7 открыт и значением (modP или (P -4) mod Р поступает на вход сумматора 10 по модулю Р, на вход знака, которого по входу 11 поступает значение.модуля Р . С выхода сумматора 10 по модулю Р .значение Р- A " (mod P) или P -(P -А) mpd P — через элемент 12 ИЛИ поступает на вход выход" ного регистра 13. 25

Примеры конкретного выполнения

1операции An(modf для р =7. В табл . 1 даны значения, присвоенные выходным шинам дешифратора 3.

В табл. 2 даны значения А (mod 7) для и =2, 3, 4.

Пусть необходимо определить результат операции 5 (mod 7).

По входу 1 во входной регистр 2 заносится операнд А =101. Дешифратор

"единица" через открытый элемент

И 7 поступает на вход сумматора 10 по модулю Р, на вход знака которого поступает значение P =111. С выхода сумматора 10 по модулю Р значение .Г-001 110 через элемент 12 ИЛИ посту

)пает на вход выходного региетра 13 ° Проверка (табл. 2):5 (mod 7)=6.

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

Экономический эффект заключается в уменьшении оборудования за счет совмещения s одном устройстве выпол. нения операции возведения чисел в

11-ную степень по модулю P для любых натуральных значений показателя и

Т а б л и ц а T