УМНОЖИТЕЛЬ НА ДВА ПО МОДУЛЮ
DOUBLER BY MODULE

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах, а также в устройствах для формирования элементов конечных полей и в криптографических приложениях.
Известен умножитель на два по модулю, содержащий сумматор и мультиплексор (см. патент РФ №2015537, кл. G06F 7/49, 30.06.1994).
Недостатком данного устройства являются его ограниченные функциональные возможности, а именно ограниченный диапазон значений входных чисел x (0<x≤p-1, где p - значение модуля, по которому производится вычисление).
Наиболее близким по технической сущности к заявляемому изобретению является умножитель на два по модулю, содержащий n сумматоров, n инверторов, (n-1) умножителей и мультиплексор (см. патент РФ №2299460, кл. G06F 7/72, 20.05.2007).
Недостатком данного устройства является ограниченный диапазон значений входных чисел х (0<x≤{n/2)p-1, где p - модуль, n - размер умножителя, определяемый количеством сумматоров).
Цель изобретения - увеличение диапазона значений входных чисел.
Для достижения поставленной цели в умножитель на два по модулю, состоящий из n сумматоров, n инверторов, n-1 умножителей, и первого мультиплексора, имеющего n+1 информационных и n управляющих входов, причем вход записи двоичного кода числа, подключен к первому информационному входу первого мультиплексора и первым входам всех n сумматоров, выход переноса i-го сумматора подключен к i-му управляющему входу первого мультиплексора, информационный выход i-го сумматора подключен к (i+1)-му информационному входу первого мультиплексора, где i=1, …, n, вход записи двоичного кода модуля подключен к входу первого инвертора и к входу каждого умножителя, j-й умножитель производит умножение значения на своем входе на величину (j+1), где j=1, …, n-1, выход 7-го умножителя подключен к входу (j+1)-го инвертора, выход i-го инвертора подключен ко второму входу i-го сумматора, к входу переноса каждого сумматора подключен вход записи логической единицы, дополнительно введены (n+1)-й сумматор, (n+1)-й инвертор и второй мультиплексор, имеющий два информационных и один управляющий вход, причем выход первого мультиплексора, сдвинутый на один разряд в сторону старшего, подключен к первому информационному входу (n+1)-го сумматора и первому информационному входу второго мультиплексора, вход записи двоичного кода модуля подключен к входу (n+1)-го инвертора, выход которого подключен ко второму информационному входу (n+1)-го сумматора, на вход переноса которого подана логическая единица, выход переноса (n+1)-го сумматора соединен с управляющим входом второго мультиплексора, второй информационный вход которого соединен с информационным выходом сумматора, выход второго мультиплексора является выходом умножителя.
Сущность изобретения заключается в реализации следующего способа умножения на два по модулю.
Пусть требуется умножить число х на два и сформировать остаток r получившегося выражения по модулю p.
1
2
i
N
i
Число х лежит в пределах 0<х≤np-1. Перед умножением на два формируется остаток r1 по модулю р двоичного числа х. Для этого х одновременно сравнивается со значениями p, 2p, …, ip, …, np путем вычитания из х этих значений. Таким образом получаются разности х=х-р, x=x-2p,.… x=x-ip, …, х=х-nр. То значение x,, где i=1, …, n, которое окажется больше 0 и меньше р, и будет результатом формирования остатка r1 по модулю p двоичного числа х. Получившееся значение r1 умножается на два и снова приводится по модулю p тем же способом.
На чертеже представлена схема умножителя на два по модулю.
Умножитель на два по модулю содержит n+1 сумматоров 1, n+1 инверторов 2, n-1 умножителей 3, 1 мультиплексор 4.1, имеющий n управляющих и (n+1) информационных входов и 1 мультиплексор 4.2, имеющий 1 управляющий и 2 информационных входа. Вход 5 служит для подачи двоичного кода числа х, вход 6 служит для подачи двоичного кода модуля р. Выходы переноса первых n сумматоров 1 подключены к управляющим входам мультиплексора 4.1, а их информационные выходы подключены к информационным входам мультиплексора 4.1. Информационный выход мультиплексора 4.1 подключен к информационному входу (n+1)-го сумматора 1 и информационному входу мультиплексора 4.2. Выход переноса (n+1)-го сумматора 1 подключен к управляющему входу мультиплексора 4.2, информационный выход (n+1)-го сумматора 1 подключен к информационному входу мультиплексора 4.2. Выход мультиплексора 4.2 подключен к выходу 7 и является выходом устройства.
Умножитель на два по модулю работает следующим образом.
На вход 5 подается код числа из диапазона 0<x≤np-1, где х - умножаемое число, p - модуль, n - размер умножителя, определяемый количеством сумматоров 1. Данный код поступает на первые входы первых n сумматоров 1 и на первый информационный вход мультиплексора 4.1. Со входа 6 код модуля (подается на входы умножителей 3, на вход первого и (n+1)-го инвертора 2, причем значение модуля в k-м умножителе умножается на значение i=(k+1), где k=1,.…, n-1. С выхода k-го умножителя 3 код произведения ixp поступает на вход (k+1)-го инвертора 2. В j-м инверторе 2 поступающий на его вход код переводится в инверсный код, который подается на второй вход j-го сумматора 1, где j,.…, n+1. Таким образом, на второй вход каждого сумматора 1 поступает инверсный код значения i×p, где i=1,.…, n - номер сумматора. На вход переноса каждого сумматора 1 поступает код числа «1», служащий для перевода инверсного кода модуля в дополнительный код.
В общем виде n сумматоров 1 осуществляют операцию, описываемую выражением: где с - результат суммирования, х - число, i - номер сумматора, p - модуль. Старший разряд сформированного значения с поступает на выход переноса сумматора 1, остальные разряды представляют разность х - i×p и поступают на информационный выход сумматора 1. (n+1)-ый сумматор 1 осуществляют операцию, описываемую выражением: где m - результат суммирования, х - число, p - модуль. Старший разряд сформированного значения m поступает на выход переноса сумматора 1, остальные разряды представляют разность х-p и поступают на информационный выход сумматора 1.
До тех пор, пока значение х превышает значение i×p, на выходе переноса i-го сумматора 1 будет формироваться «1», которая будет поступать на i-й управляющий вход мультиплексора 4.1. При превышении значением i×p значения х на выходе переноса i-го сумматора 1 сформируется «0». При поступлении на i-й управляющий вход мультиплексора 4.1 символа «0» с выхода переноса i-го сумматора 1 мультиплексор 4.1 переключит на вход (n+1)-го сумматора 1 и на первый вход мультиплексора 4.2, со сдвигом разрядов на один в сторону старшего разряда, информационный вход, на который подается значение с информационного выхода (i-1)-го сумматора 1. Мультиплексор 4.2 переключит на выход 7 информационный вход с мультиплексора 4.1, если 2 с<p, или информационный вход с сумматора 1, если 2 с≥p. В последнем случае на выходе мультиплексора 4.2 будет значение m=2 с - p. Данное значение будет представлять результат умножения числа х на два по модулю ρ.
Рассмотрим работу умножителя на примере.
Пусть  Как показано выше, i-й сумматор 1 формирует значение  поэтому для второго сумматора  для третьего сумматора  для четвертого сумматора
1
2
2
2
2
2
2
2
3
2
2
2
4
2
2
2
Тогда первый сумматор 1 сформирует значение c=01111+11011+1=101011, второй c=01111+10111+1=100111, третий - с=01111+10011+1=100011, четвертый - c=01111+01111+1=011111.
2
10
Как видно из примера, на выходах переноса первых трех сумматоров 1 сформировано значение «1», на выходе же четвертого сумматора 1 сформировано значение «0», поэтому на выход мультиплексора 4.1 поступит значение с информационного выхода третьего сумматора 1, равное 00011=3.
2
2
10
Полученное значение умножается на 2, путем сдвига разрядов на один в сторону старшего. На первый информационный вход мультиплексора 4.2 и на первый информационных вход сумматора 1 поступает значение 0110. (n+1)-ый сумматор 1 формирует значение  Т.к. на выходе переноса сумматора 1 сформировано значение «1», поэтому на выход мультиплексора 4.2 поступит значение с информационного выхода сумматора 1, равное 0010=2. Так как (15)(mod 4)=3, (3×2)(mod 4)=2, то правильность работы устройства очевидна.