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

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

 

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

Известно устройство для умножения чисел по модулю, содержащее два входных регистра, два дешифратора, три группы элементов ИЛИ, четыре группы элементов И, табличный вычислитель значений вида α'β'(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) остаток ri суммируется по модулю р с остатками, сформированными на других шагах вычислений, в соответствии с коэффициентом при (i-1)-й степени двоичной формы числа b. Если bi=1, остаток на i-м шаге вычислений суммируется с остальными, если bi=0 - не суммируется. Результатом суммирования по модулю р полученных частичных остатков является остаток от произведения (а×b)mod p.

Пример.

Пусть a=1010=10102, b=1110=10112, p=1310=11012, тогда (a×b)mod p=(11010)mod 1310=610.

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

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

r1=a=10102=1010.

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

r2=(r1×2) mod p=(101002) mod 11012=01112=710;

r3=(r2×2) mod p=(011102) mod 11012=00012=110;

r4=(r3×2) mod p=(000102) mod 11012=00102=210.

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

r=(r1+r2+r4) mod р=(1010+710+210) mod 1310=610.

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

Устройство для умножения чисел по произвольному модулю содержит (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=1010=10102, p=1310=11012, , то есть для случая а<р, на выходе сумматора 1 сформируется результат вычисления . На выход переноса сумматора 1 поступит символ «0». Если же а≥р, например а=1410=11102, р=1310=11012, , то на выходе сумматора 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. То есть на входе первого ключа сформируется частичный остаток r1=а, на входе i-го ключа (i=2, ..., m) сформируется частичный остаток ri. Управление ключами осуществляется коэффициентами при соответствующих степенях двоичного представления числа b, поступающими со входа 7 устройства. На k-й ключ 5 поступает k-й коэффициент (k=1, ..., m) двоичного представления числа b. Для вышеописанного примера, где b=1110=10112, на первый ключ 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)-го сумматора, выход последнего мультиплексора подключен ко входу последнего ключа, выходы ключей подключены ко входам сумматора по модулю, выход которого является выходом устройства.



 

Похожие патенты:

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

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

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

Изобретение относится к вычислительной технике и, в частности, к модулярным нейрокомпьютерным средствам и предназначено для определения ошибок в кодовых конструкциях непозиционного кода полиномиальной системы классов вычетов (ПСКВ), представленных в расширенных полях Галуа GF (2V).

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

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

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

Изобретение относится к вычислительной технике и предназначено для использования в вычислительных устройствах, функционирующих в системе остаточных классов (СОК), а также технике связи для передачи информации кодами СОК.

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

Изобретение относится к вычислительной техники и, в частности, к модулярным нейрокомпьютерным средствам и предназначено для выполнения операций округления и масштабирования над числами, представленными в системе остаточных классах (СОК).

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

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

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

Изобретение относится к автоматике и вычислительной технике и предназначено для построения линейных и плоскостных однородных структур, реализующих булевы формулы, системы булевых формул, включая булевы формулы, представленные в виде полиномов Жегалкина из классов бесповторных упорядоченных и неупорядоченных формул, заданных в базисе И, ИЛИ, НЕ при равной доступности прямых и инверсных выходов источников информации.

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

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

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

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

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

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