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

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

Иллюстрации

Показать все

Реферат

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

Известно устройство для умножения чисел по модулю, содержащее два входных регистра, два дешифратора, три группы элементов ИЛИ, четыре группы элементов И, табличный вычислитель значений вида α'β'(mod р/2)+р/2, пять элементов ИЛИ, два элемента И и шифратор (см. АС СССР №1187161, кл. G06F 7/49, 23.10.1985).

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

Наиболее близким по технической сущности к заявляемому изобретению является умножитель на два по модулю, содержащий сумматор и мультиплексор (см. патент РФ №2015537, кл. G06F 7/49, 30.06.1994).

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

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

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

Пусть a, b, p (где а и b - множители, от произведения которых требуется сформировать остаток по произвольному модулю, р - модуль) - простые целые числа, представленные в двоичном виде, причем а<р и b<р.

Двоичная форма множителей имеет следующий вид:

Для формирования остатка от произведения (a×b)mod p необходимо сформировать частичный остаток по модулю р от числа а, умножить на два полученный результат и от полученного значения вновь вычислить частичный остаток. Данная операция повторяется m раз (где m - количество разрядов в двоичном коде числа b). Так как а<р, то частичным остатком на первом шаге вычислений будет являться само число а. То есть правило формирования частичных остатков от числа а имеет вид:

Операция же умножения на два для двоичной системы счисления заключается в сдвиге кодовой комбинации на один разряд в сторону увеличения с записью нуля в младший разряд. Полученный на i-м шаге вычислений (i=1....m+1) остаток r_i суммируется по модулю р с остатками, сформированными на других шагах вычислений, в соответствии с коэффициентом при (i-1)-й степени двоичной формы числа b. Если b_i=1, остаток на i-м шаге вычислений суммируется с остальными, если b_i=0 - не суммируется. Результатом суммирования по модулю р полученных частичных остатков является остаток от произведения (а×b)mod p.

Пример.

Пусть a=10₁₀=1010₂, b=11₁₀=1011₂, p=13₁₀=1101₂, тогда (a×b)mod p=(110₁₀)mod 13₁₀=6₁₀.

Согласно вышеизложенному алгоритму, для вычисления искомого остатка от произведения (а×b) mod p необходимо m раз (m - количество разрядов в двоичной форме числа b, в данном случае m=3) вычислить частичные остатки от числа а, которые затем необходимо просуммировать в соответствии с коэффициентами при соответствующих степенях числа b.

На первом шаге вычислений частичным остатком r₁ будет являться само число а:

r₁=a=1010₂=10₁₀.

Остальные частичные остатки формируются следующим образом:

r₂=(r₁×2) mod p=(10100₂) mod 1101₂=0111₂=7₁₀;

r₃=(r₂×2) mod p=(01110₂) mod 1101₂=0001₂=1₁₀;

r₄=(r₃×2) mod p=(00010₂) mod 1101₂=0010₂=2₁₀.

Так как число b=11₁₀=1011₂, необходимо просуммировать по модулю р частичные остатки с индексами, соответствующими номерам позиций ненулевых коэффициентов в двоичном коде числа b начиная с младшего разряда (в данном случае, первый, второй и четвертый частичные остатки). То есть

r=(r₁+r₂+r₄) mod р=(10₁₀+7₁₀+2₁₀) mod 13₁₀=6₁₀.

На чертеже представлена схема устройства для умножения чисел по произвольному модулю.

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

Входы 7 и 10 служат для подачи двоичных кодов умножаемых чисел а и b соответственно. Вход 8 служит для записи символа «1», служащего кодом начала операции. Вход 9 служит для записи кода модуля р. Выход 11 является выходом устройства.

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

Код числа а поступает на первый вход первого сумматора 1, первый информационный вход первого мультиплексора 2, а также на первый ключ 5, код модуля р поступает на вход инвертора 4, с выхода которого инверсный код модуля р подается на второй вход каждого сумматора 1. На третий вход каждого сумматора 1 подается символ «1», служащий для перевода инверсного кода модуля в дополнительный.

В общем виде i-й сумматор 2 (i=1...m-1) осуществляет операцию, описываемую выражением: , где с - результат суммирования, а - число, поступающее на вход сумматора, - инверсный код модуля. При сложении чисел, состоящих из l разрядов (где l - количество разрядов в двоичном представлении модуля р), (l+1)-й разряд сформированного значения с поступает на выход переноса сумматора 1, который подключен к управляющему входу i-го мультиплексора 2. Остальные разряды поступают на информационный выход сумматора 1, который подключен ко второму информационному входу i-го мультиплексора 2. Для вышеописанного примера, где a=10₁₀=1010₂, p=13₁₀=1101₂, , то есть для случая а<р, на выходе сумматора 1 сформируется результат вычисления . На выход переноса сумматора 1 поступит символ «0». Если же а≥р, например а=14₁₀=1110₂, р=13₁₀=1101₂, , то на выходе сумматора 1 сформируется результат вычисления . На выход переноса сумматора поступит символ «1». Остальные же разряды представляют разность (а-р).

Мультиплексор 2 при поступлении на управляющий вход символа «0» подключает на выход свой первый информационный вход, при поступлении символа «1» - второй информационный вход.

Таким образом, формирование значения на выходе связки «сумматор - мультиплексор» можно описать следующими выражениями:

В данных формулах i=2, ..., m.

С выхода j-го мультиплексора 2 (j=1, ..., m-2) сформированный частичный остаток поступает на вход j-го блока 3 сдвига (который, путем переноса всех разрядов входного числа на один разряд в сторону увеличения, осуществляет операцию умножения входного числа на два), а также на вход (j+1)-го ключа 5. Сдвинутый на один разряд код числа с выхода j-го блока 3 сдвига подается на первый информационный вход (j+1)-го мультиплексора и на первый вход (j+1)-го сумматора 1. С выхода последнего мультиплексора 2 выходное значение поступает только на вход последнего ключа 5. То есть на входе первого ключа сформируется частичный остаток r₁=а, на входе i-го ключа (i=2, ..., m) сформируется частичный остаток r_i. Управление ключами осуществляется коэффициентами при соответствующих степенях двоичного представления числа b, поступающими со входа 7 устройства. На k-й ключ 5 поступает k-й коэффициент (k=1, ..., m) двоичного представления числа b. Для вышеописанного примера, где b=11₁₀=1011₂, на первый ключ 5 поступит символ «1», на второй - «1», на третий - «0», на четвертый - «1». Ключ пропускает информацию на выход в случае наличия на управляющем входе символа «1».

С выходов ключей значения частичных остатков поступают на вход сумматора 6 по модулю. Результатом суммирования по модулю р частичных остатков, формируемым на выходе сумматора 6 по модулю, будет являться искомое значение (а×b)mod р.

Устройство для умножения чисел по произвольному модулю, содержащее (m-1) сумматоров, (m-1) мультиплексоров, отличающееся тем, что в него введены (m-2) блоков сдвига, m ключей и сумматор по модулю, причем вход записи двоичного кода первого из умножаемых чисел подключен к первому входу первого сумматора, первому информационному входу первого мультиплексора, а также к первому ключу, вход записи двоичного кода второго умножаемого числа поразрядно подключен к управляющему входу каждого ключа, вход записи символа «1» подключен к третьему входу каждого сумматора, вход записи двоичного кода модуля подключен ко входу инвертора, выход которого подключен ко второму входу каждого сумматора, причем выход переноса i-го сумматора подключен к управляющему входу i-го мультиплексора (i=1...m-1), информационный выход 1-го сумматора подключен ко второму информационному входу i-го мультиплексора, выход j-го мультиплексора (j=1...m-2) подключен ко входу j-го блока сдвига и ко входу (j+1)-го ключа, выход j-го блока сдвига подключен к первому информационному входу (j+1)-го мультиплексора и первому входу (j+1)-го сумматора, выход последнего мультиплексора подключен ко входу последнего ключа, выходы ключей подключены ко входам сумматора по модулю, выход которого является выходом устройства.