Устройство для формирования остатка по произвольному модулю

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах, а также в устройствах для формирования элементов конечных полей и в криптографических приложениях. Техническим результатом является повышение быстродействия. Устройство содержит блок формирователей частичных остатков по модулю, блок умножителей по модулю и блок сумматоров по модулю. 3 н.п. ф-лы, 3 ил.

 

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах, а также в устройствах для формирования элементов конечных полей и в криптографических приложениях.

Известно устройство для формирования остатка по произвольному модулю от числа, содержащее регистры, элементы ИЛИ, вычислитель, схемы сравнения, мультиплексор, элемент задержки, сумматор, группу блоков элементов И и блок постоянной памяти со связями (см. авт. св. СССР №1633495, кл. H03M 7/18, 1991).

Недостатком известного устройства является низкая надежность, так как для его реализации требуется большой объем оборудования.

Наиболее близким по технической сущности к заявляемому изобретению является комбинационный рекуррентный формирователь остатков, содержащий комбинационный формирователь частичных остатков, блок ключей и блок сумматоров по модулю (см. патент РФ №2029435, кл. 6 H03M 7/18, 20.02.1995, бюл. №5).

Недостатком данного устройства является низкое быстродействие.

Целью изобретения является повышение быстродействия.

Сущность изобретения заключается в реализации следующего способа формирования остатка по произвольному модулю.

Пусть требуется сформировать остаток r от числа А по модулю р.

Число А может быть представлено в позиционной системе счисления в виде

где a_i, - коэффициенты, принимающие значения 0 или 1, n - количество разрядов в представлении числа А. Это выражение может быть представлено в следующем виде:

где , если n четное, и , если n нечетное, [] - целая часть от деления.

Из теории чисел известно, что операция приведения по модулю инвариантна к сложению и умножению, т.е. величина остатка не зависит от того, вычислен он от суммы (произведения) или от каждого слагаемого (сомножителя), а затем соответствующие частичные остатки просуммированы (перемножены) и от результата вычислен остаток по модулю.

В таком виде значительно облегчается задача нахождения остатка r от числа A.

Для вычисления остатка от числа А по модулю р достаточно в выражении (2) просуммировать частичные остатки по модулю р от чисел 2²ⁱ(a_2i+12+a_2i), где - при n четном и при n нечетном. Частичные остатки получаются в результате умножения частичного остатка от 2²ⁱ по модулю р на число

(a_2i+12+a_2i). Способ вычисления частичных остатков от 2²ⁱ по модулю р состоит в следующем. Вычисление частичного остатка от 2²ⁱ заключается в умножении на четыре частичного остатка от 2^2(i-1) и приведение результата по модулю р. Операция умножения на четыре может быть реализована сдвигом всех разрядов числа на два разряда влево. Операция приведения по модулю реализуется следующим образом. Если число не превышает величину р, то оно остается без изменения. Если оно лежит в интервале от р до 2р-1, то из него вычитается модуль р. Если число лежит в интервале от 2р до 3р-1, то из него вычитается удвоенный модуль р. Если число лежит в интервале от 3р до 4р-1, то из него вычитается утроенный модуль р. Способ умножения частичного остатка от 2²ⁱ по модулю p на число (a_2i+12+a_2i) состоит в следующем. Частичный остаток от 2²ⁱ по модулю р, умноженный на a_2i+12, складывается с частичным остатком от 2²ⁱ по модулю р, умноженный на a_2i. Если полученный результат не превышает величину р, то оно остается без изменения. Если оно лежит в интервале от p до 2р-1, то из него вычитается модуль р. Если число лежит в интервале от 2р до 3p-1, то из него вычитается удвоенный модуль р. Суммирование по модулю р частичных остатков происходит последовательно.

На фиг.1 представлена схема устройства для формирования остатка по произвольному модулю от числа; на фиг.2 - формирователя частичных остатков; на фиг.3 - умножителя по модулю.

Устройство формирования остатка по произвольному модулю от числа (фиг.1) содержит блок 1 формирователей частичных остатков, блок 2 умножителей по модулю и блок 3 сумматоров по модулю. Входы 4 служат для подачи двоичного кода числа А. Выход 5 является выходом остатка устройства формирования остатка по произвольному модулю от числа.

Блок 1 формирователей частичных остатков (фиг.1) содержит n/2 формирователей частичных остатков 6, соединенных последовательно, причем на вход первого формирователя частичных остатков 6 подан код единицы, разряд которого сдвинут на два разряда влево. Выходы разрядов предыдущего формирователя частичных остатков 6 подаются на входы последующего формирователя частичных остатков 6 со сдвигом на два в сторону старших. Выходы каждого формирователя частичных остатков 6 являются информационными выходами формирователя. Блок 2 умножителей по модулю (фиг.1) содержит n/2 умножителей по модулю 7, на информационные входы которых подаются коды с выходов формирователей частичных остатков 6. Блок 3 сумматоров по модулю (фиг.1) содержит n/2 сумматоров по модулю 8, на информационные входы которых подаются коды с выходов умножителей по модулю 7 и с выходов предыдущего сумматора по модулю 8, причем на первый сумматор по модулю 8 подаются два младших разряда кода числа А.

Каждый формирователь частичных остатков (фиг.2) содержит три сумматора 12 и мультиплексор 13. На входы переносов трех сумматоров 12 подается код единицы. На первые информационные входы трех сумматоров 12 подается код с выхода формирователя частичных остатков 6. Вход 9 служит для подачи инверсного кода модуля, вход 10 - для подачи инверсного кода удвоенного кода модуля, вход 11 - для подачи инверсного кода утроенного кода модуля.

Каждый умножитель 7 по модулю (фиг.3) содержит два ключа 16, которые управляются разрядами кода числа А, три сумматора 17 и мультиплексор 18. Вход 14 служит для подачи инверсного кода модуля, вход 15 - для подачи инверсного кода удвоенного кода модуля.

Устройство для формирования остатка по произвольному модулю от числа работает следующим образом.

На вход первого формирователя частичных остатков 6 подается код единицы, сдвинутый на два разряда в сторону старших, выходы разрядов предыдущего формирователя частичных остатков 6 подключены к входам последующего формирователя частичных остатков 6 со сдвигом на два разряда в сторону старших. Таким образом на выходах блока формирования частичных остатков 1 формируются частичные остатки по модулю р от числа 2²ⁱ, где при n четном и при n нечетном.

Код числа А через входы 4 поступает на управляющие входы умножителя 7 по модулю. Умножитель 7 по модулю умножает частичный остаток по модулю р от числа 2²ⁱ на число (a_2i+12+a_2i), где a_i коэффициенты двоичного кода числа А, и вычисляет частичный остаток по модулю р от полученного результата. Блок сумматоров 3 по модулю суммирует по модулю р частичные остатки и число (а₁2+а₀). Результат суммирования выдается на информационные выходы 5 устройства для формирования остатка по произвольному модулю от числа.

Формирователь частичных остатков работает следующим образом. На первые информационные входы трех сумматоров 12 и на первый информационных вход мультиплексора 13 подается частичный остаток t_i-1 по модулю р от числа 2^2(i-l), сдвинутый на два разряда в сторону старших. На входы переносов трех сумматоров 12 подается код единицы. На второй вход первого сумматора 12 подается инверсный код модуля р. На второй вход второго сумматора 12 подается инверсный код удвоенного модуля р. На второй вход третьего сумматора 12 подается инверсный код утроенного модуля р. Первый сумматор 12 выполняет операцию . Сигнал со старшего (k+1)-го разряда полученного значения, где k - количество разрядов инверсного двоичного кода модуля р, поступает на выход переноса первого сумматора 12. Остальные разряды представляют собой разность (t_i-1-р). Второй сумматор выполняет операцию . Сигнал со старшего (k+1)-го разряда полученного значения, где k - количество разрядов инверсного двоичного кода удвоенного модуля р, поступает на выход переноса второго сумматора 12. Остальные разряды представляют собой разность (t_i-1-2р). Третий сумматор выполняет операцию . Сигнал со старшего (k+1)-го разряда полученного значения, где k - количество разрядов инверсного двоичного кода утроенного модуля р, поступает на выход переноса третьего сумматора 12. Остальные разряды представляют собой разность (t_i-1-3р). Если на выходе переноса третьего сумматора 12 сигнал равен "1", то на выходе формирователя частичных остатков будет разность (t_i-1-3р). Если на выходе переноса третьего сумматора 12 сигнал равен "0", а на выходе переноса второго сумматора 12 сигнал равен "1", то на выходе формирователя частичных остатков будет разность (t_i-1-2р). Если на выходе переноса третьего сумматора 12 сигнал равен "0" и на выходе переноса второго сумматора 12 сигнал равен "0", а на выходе переноса первого сумматора 12 сигнал равен "1", то на выходе формирователя частичных остатков будет разность (t_i-1-р). Если на выходе переноса третьего сумматора 12 сигнал равен "0", на выходе переноса второго сумматора 12 сигнал равен "0" и на выходе переноса первого сумматора 12 сигнал равен "0", то на выходе формирователя частичных остатков будет число t_i-1.

Умножитель по модулю работает следующим образом. Коэффициенты a_i+1 и a_i, через входы 4 поступают на управляющие входы двух ключей 16. На информационные входы двух ключей подается частичный остаток t_i по модулю р от числа 2^2t. В зависимости от того, на управляющий вход какого из ключей 16 поступает логическая "1", тот из ключей 16 оказывается открытым и коммутирует на свои выходы значения с информационных входов, которые поступают на входы первого сумматора 17. Причем на первый вход первого сумматора 17 поступает значение, сдвинутое на один разряд влево. На выходе первого сумматора оказывается результат умножения частичного остатка t₁, по модулю р от числа 2²ⁱ на число (a_2i+12+a_2i,). Результат вычисления поступает на первые входы второго и третьего сумматоров 17. На входы переносов второго и третьего сумматоров 17 подается код единицы. На второй вход второго сумматора 17 подается инверсный код модуля р. На второй вход третьего сумматора 17 подается инверсный код удвоенного модуля р. Второй сумматор 17 выполняет операцию . Сигнал со старшего (k+1)-го разряда полученного значения, где k - количество разрядов инверсного двоичного кода модуля р, поступает на выход переноса второго сумматора 17. Остальные разряды представляют собой разность (t_i-р). Третий сумматор выполняет операцию Сигнал со старшего (k+1)-го разряда полученного значения, где k - количество разрядов инверсного двоичного кода удвоенного модуля р, поступает на выход переноса третьего сумматора 17. Остальные разряды представляют собой разность (t_i-2р). Если на выходе переноса третьего сумматора 17 сигнал равен "1", то на выходе умножителя по модулю будет разность (t_i-2p). Если на выходе переноса третьего сумматора 17 сигнал равен "0", а на выходе переноса второго сумматора 17 сигнал равен "1", то на выходе умножителя по модулю будет разность (t_i-р). Если на выходе переноса третьего сумматора 17 сигнал равен "0" и на выходе переноса второго сумматора 17 сигнал равен "0", то на выходе умножителя по модулю будет число t_i.

Рассмотрим работу устройства формирования остатка по произвольному модулю от числа на примере.

Пусть A=49₁₀=110001₂, p=9₁₀=001001₂. Первый формирователь частичных остатков формирует значение частичного остатка от 2² по модулю р, который равен 000100₂. Второй формирователь частичных остатков формирует частичный остаток от 2⁴ по модулю р, который равен 000111₂. Первый умножитель по модулю производит умножение частичного остатка, полученного на первом формирователе частичных остатков, и коэффициентов а₂=0 и а₃=0. В результате получается значение, равное 0. Первый сумматор по модулю выполняет операцию сложения полученного значения и коэффициентов а₀=1 и 2а₁=00 и находит остаток по модулю р. В результате получается значение, равное 1. Второй умножитель по модулю производит умножение частичного остатка, полученного на втором формирователе частичных остатков, и коэффициентов а₄=1 и a₅=1. В результате получается значение, равное 000011. Второй сумматор по модулю выполняет операцию сложения полученного значения и результата с первого сумматора по модулю и находит остаток по модулю р. В результате получается значение, равное 100₂=4₁₀.

49=9·3+4

1. Устройство для формирования остатка по произвольному модулю, содержащее блок формирователей частичных остатков и блок сумматоров по модулю, причем на первый формирователь частичных остатков блока формирователей частичных остатков подается код единицы, выход каждого формирователя частичных остатков соединен с входом последующего формирователя частичных остатков и является соответствующим информационным выходом блока формирователей частичных остатков, второй вход каждого сумматора по модулю блока сумматоров по модулю соединен с выходом предыдущего сумматора по модулю, выход последнего сумматора по модулю является выходом устройства для формирования остатков по произвольному модулю, отличающееся тем, что в него введен блок умножителей по модулю, содержащий t умножителей по модулю, где , если n четное, и , если n нечетное, n - разрядность входного числа, управляющие входы которых соединены с входами двоичного кода числа, причем два младших разряда числа подаются на второй вход первого сумматора по модулю, блок формирователей частичных остатков содержит t формирователей частичных остатков, блок сумматоров по модулю содержит t сумматоров по модулю, t выходов блока формирователей частичных остатков соединены соответственно с информационными входами умножителей по модулю блока умножителей по модулю, t выходов которого соединены соответственно с информационными входами блока сумматоров по модулю, являющихся первыми входами сумматоров по модулю.

2. Формирователь частичных остатков, содержащий три сумматора и мультиплексор, причем первые входы сумматоров и мультиплексора соединены с входом формирователя частичных остатков, второй вход первого сумматора соединен с входом инверсного кода модуля, второй вход второго сумматора соединен с входом инверсного кода удвоенного модуля, второй вход третьего сумматора соединен с входом инверсного кода утроенного модуля, на входы переносов всех сумматоров подается код единицы, входы мультиплексора соединены с информационными выходами и выходами переноса всех сумматоров, выход мультиплексора соединен с выходом формирователя частичных остатков.

3. Умножитель по модулю, содержащий мультиплексор, три сумматора, два ключа, информационные входы которых соединены с входом умножителя по модулю, на управляющие входы ключей подаются разряды кода числа, а выходы соединены с входами первого сумматора, выход которого соединен с первыми входами второго и третьего сумматоров, второй вход второго сумматора соединен с входом инверсного кода модуля, второй вход третьего сумматора соединен с входом инверсного кода двойного модуля, на входы переносов второго и третьего сумматоров подается код единицы, информационные выходы всех сумматоров и выходы переноса второго и третьего сумматоров соединены с входами мультиплексора, выход которого соединен с выходом умножителя по модулю.