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

 

Изобретение относится к вычислительной технике и может быть использовано при построении быстродействующих специализированных вычислительных устройств, работающих с модульной арифметикой. Цель изобретения - повышение быстродействия. Существенным признаком изобретения является то, что на одном умножителе независимо от значения очередного разряда показателя степени осуществляется циклическое возведение в квадрат основания степени, а на другом умножителе при единичных значениях показателя степени осуществляется умножение предыдущих результатов вычисления возведения в степень и циклического возведения в квадрат основания степени, причем эта операция совмещается во времени с операцией циклического возведения в квадрат. В связи с этим в устройстве появляются новые элементы и новые связи, обеспечивающие более быстрое формирование результата. 1 з. п. ф-лы, 2 ил., 1 табл.

Изобретение относится к вычислительной технике и может быть использовано при построении быстродействующих специализированных устройств, работающих с модульной арифметикой. Цель изобретения повышение быстродействия. На фиг.1 представлена блок-схема предложенного устройства для возведения чисел в N-ю степень по модулю; на фиг.2 схема подключения быстродействующих блоков деления (блоков приведения по модулю). Устройство содержит регистр 1 хранения промежуточных результатов, регистр 2 основания, регистр 3 модуля, регистр 4 показателя степени, блоки умножения 5₁ и 5₂, блоки 6₁ и 6₂ деления, группы 7₁-7₈ элементов И, группы 8₁-8₄ элементов ИЛИ, входы 9-12, выход 13 устройства, схемы 14 сравнения, узлы деления 15. Регистр 2 в первый момент времени служит для запоминания значения основания степени А, а в последующие моменты времени для хранения промежуточных результатов возведения в степень. На первый вход блока умножения 5₁ в начальный момент времени подается сигнал "единицы", соответствующий одиночному импульсу (ПУСК), в последующие моменты времени содержимое регистра 1, представляющее собой промежуточные результаты возведения в квадрат, а на второй вход блока умножения в начальный момент времени подается содержимое регистра 2, представляющее собой значение основания степени А, в последующие моменты времени содержимое регистра 2, являющееся промежуточным результатом возведения в степень. Организуются эти передачи с помощью групп элементов ИЛИ 8₁, 8₂, 8₃ и групп элементов И 7₃, 7₄. Блок умножения 5₁ осуществляет циклическое возведение в квадрат основания степени А. Результаты, приведенные по модулю Р с помощью блока деления 6₁, помещаются в регистр 1. Блок умножения 5₂ при единичном значении разряда показателя степени N осуществляет перемножение предыдущего результата возведения в квадрат, хранящегося в регистре 1, на промежуточный результат возведения в степень, хранящийся в регистре 2. Результаты умножения, приведенные по модулю Р с помощью узла деления 6, снова помещаются в регистр 2. Организация этих операций осуществляется с помощью групп элементов И 7₁, 7₂ и ИЛИ 8₁, 8₂, 8₃. После обнуления регистра 4 в результате полного сдвига находившейся в нем информации срабатывает группа элементов И 7₅ и содержимое регистра 2, представляющее собой окончательный результат возведения в степень, поступает на выход 13 устройства. Более быстродействующий узел приведения по модулю можно выполнить так, чтобы в случае, если значение результатов умножения П окажется меньше значения модуля Р, не производить длительной операции деления. Для этого в блок деления 6₁ (6₂), кроме непосредственного узла деления 15, вводится схема сравнения 14, выходные сигналы которой с помощью элементов И 7₆ (7₉), 7₇ (7₁₀), 7₈ (7₁₁) и групп элементов ИЛИ 8₄ (8₅) управляют процессом или деления, или непосредственно пересылки результата умножения в регистр 1 (2). Работу предлагаемого устройства можно проиллюстрировать примером. Пусть число N будет восьмиразрядное, его двоичная запись имеет вид N=a₀2₁⁰+a₁2¹+a₂2²+a₃2³+a₄2⁴+a₅2⁵+a₆2⁶+a₇2⁷(1) При N 149 согласно (1) имеют место коэффициенты а₀ а₂ а₄ а₇= 1 и а₁ а₃а₅ а₆ 0, т.е. N 10010101, для некоторого основания А имеем при А¹⁴⁹ А^10010101 А²⁰А²²А²⁴А²⁷ А˙А⁴˙ А¹⁶˙ А¹²²= А¹⁴⁹ (2). Из выражения (2) видно, что для получения результата необходимо перемножить четыре степени числа А, представляющие собой квадраты: А⁴ А² А², А¹⁸ А⁸ А⁸, А¹²⁸А⁶⁴ А⁶⁴. Значит, вычисляя эти квадраты, можно одновременно их перемножить. Совмещение обоих процессов во времени представлено в таблице. Время возведения в N-ю степень по модулю при реализации прототипа будет определяться увеличением его за счет того, что после каждого возведения в квадрат (при единичном значении очередного разряда показателя степени) необходимо умножить полученный квадрат на основание степени. Поэтому, в худшем случае (при всех разрядах показателя степени, равных единице) время возведения будет пропорционально (2n˙1), где n число разрядов числа N. Как видно из таблицы, в предлагаемом устройстве это время пропорционально величине n+1. Таким образом, выигрыш в быстродействии по сравнению с прототипом будет в k раз k 2 при больших n. Кроме того, введение схемы сравнения в узел деления позволяет не осуществлять деление значения произведения n на значение модуля Р, если n < P, что также повышает быстродействие предлагаемого устройства.

Формула изобретения

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

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3