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

Изобретение относится к области вычислительной техники. Техническим результатом является обеспечение устройства для умножения чисел по произвольному модулю с меньшим объемом оборудования. Устройство содержит три регистра, ключ, три сумматора, два мультиплексора, элемент ИЛИ и блок элементов ИЛИ. Предлагаемое устройство позволяет достичь указанный результат при вычислении произведения чисел A и B по модулю P путем последовательной реализации выражения: (A·B) ≡ (a_n-1(2^n-1·B) mod P +…+(a₁(2·B) mod P +a₀·B) mod P…) mod P, где n - количество разрядов входного числа A; a_i, - коэффициенты в двоичном представлении числа A. 1 ил., 8 табл.

 

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

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

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

Известен умножитель на два по модулю, содержащий сумматор и мультиплексор (см. патент РФ №2015537, кл. G 06 F 7/49, опубл. 30.06.1994).

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

Наиболее близким по технической сущности к заявляемому изобретению является устройство для умножения чисел по произвольному модулю, содержащее сумматоры, мультиплексоры, ключи, блоки сдвига, инвертор и сумматор по модулю (см. патент РФ № 2316042, МПК G06F 7/523 (2006.01), G06F 7/72 (2006.01), опубл. 27.01.2008. Бюл. № 3). Недостатком данного устройства большой объем оборудования.

Техническим результатом изобретения является сокращение объема оборудования.

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

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

(A·B) ≡ R (mod P), (1)

где A - целое положительное число, являющееся множимым;

B - целое положительное число, являющееся множителем, причем B<P;

P - целое положительное число, называемое модулем;

R - целое положительное число, являющееся остатком от произведения чисел A и B по модулю P.

При этом пусть

A = a_n-1·2^n-1+. . . +a₁·2+a₀, (2)

B = b_m-1·2^m-1+ . . . + b₁·2+b₀, (3)

P = p_m-1·2^m-1+ . . . +p₁·2¹+p₀, (4)

R = r_m-1·2^m-1+ . . . +r₁·2¹+r₀, (5)

где a_i, - коэффициенты, принимающие значение 0 или 1 в зависимости от значения числа A;

n - количество разрядов в представлении множимого;

b_i, - коэффициенты, принимающие значение 0 или 1 в зависимости от значения числа B;

p_i, - коэффициенты, принимающие значение 0 или 1 в зависимости от значения модуля P;

r_i, - коэффициенты, принимающие значение 0 или 1 в зависимости от значения остатка R;

m - количество разрядов в представлении множителя B, модуля P и остатка R.

Представим произведение чисел A и B следующим образом:

A·B = (a_n-1·2^n-1+ . . . + a₁·2+a₀)·B. (6)

Перепишем выражение (6) следующим образом:

A·B = (a_n-1·2^n-1·B + . . . + a₁·2·B +a₀·B), (7)

Тогда произведение (1) чисел A и B по модулю P запишем в виде

(A·B) ≡(a_n-1·2^n-1·B + . . . + a₁·2·B +a₀·B) (mod P). (8)

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

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

(A·B) ≡ (a_n-1·2^n-1·B) mod P +… +(a₁·2·B) mod P +(a₀·B)mod P. (9)

Выражение (9) с учетом того, что слагаемое (a₀·B) по определению всегда меньше P и коэффициенты a_i, принимают значения 0 или 1 может быть записано в следующем виде:

(A·B) ≡ a_n-1(2^n-1·B) mod P +... +a₁(2·B) mod P +a₀·B. (10)

Тогда, изменяя в (10) порядок скобок, получим:

(A·B) ≡ (a_n-1(2^n-1·B) mod P +... +(a₁(2·B) mod P +a₀·B)mod P…)mod P(11)

В соответствии с (11) вычисление произведения (A·B) по модулю P может быть выполнено за n этапов последовательным умножением коэффициентов a_i на величину 2ⁱ·B, где , приведением этого значения по модулю P и последовательным накапливающим суммированием результатов умножения по модулю P. По определению величина множителя B лежит в диапазоне 0≤B≤P-1. Величины 2ⁱ·B могут быть получены последовательным умножением множителя B на 2 и приведением результата умножения по модулю P. Умножение на 2 при двоичном представлении чисел осуществляется сдвигом разрядов кода умножаемого числа на один в сторону старших. Результат умножения может попасть в диапазон [0, P-1], в этом случае приведение по модулю не требуется, или в диапазон [P, 2P-2], в этом случае приведение по модулю P осуществляется путем вычитания из результата умножения модуля P.

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

Устройство для умножения чисел по произвольному модулю содержит первый 1, второй 11 и третий 7 регистры, ключ 2, первый 3, второй 9 и третий 8 сумматоры, первый 4 и второй 10 мультиплексоры, элемент ИЛИ 6, блок элементов ИЛИ 5, вход кода множителя 12, вход кода множимого 13, вход инверсного кода модуля 14, вход установки в исходное состояние 15, тактовый вход 16, выход кода произведения 17. Первый регистр 1 является регистром сдвига, а второй 11 и третий 7 регистры являются накопительными. На первые информационные входы первого 3 и второго 9 сумматоров подается инверсный код модуля, а на входы переноса подается сигнал логической единицы. Информационный выход первого 3 сумматора соединен с первым информационным входом первого мультиплексора 4, выход переноса соединен с управляющим входом первого мультиплексора 4. Информационный выход второго сумматора 9 соединен с первым информационным входом второго мультиплексора 10, выход переноса соединен с управляющим входом второго мультиплексора 10. Информационный вход первого регистра 1 является входом кода множимого 13 устройства, вход сигнала параллельной записи является входом установки в исходное состояние 15 устройства, вход сдвига соединен с тактовым входом 16 устройства, информационный выход младшего разряда соединен с управляющим входом ключа 2, информационный выход которого соединен с первым информационным входом третьего сумматора 8, информационный выход которого соединен со вторым информационным входом второго сумматора 9 и вторым информационным входом второго мультиплексора 10, информационный выход которого соединен с информационным входом второго регистра 11, вход записи которого соединен с тактовым входом 16 устройства, а выход является выходом кода произведения 17 устройства и соединен со вторым информационным входом третьего сумматора 8. Вход кодов множителя 12 устройства соединен с первым информационным входом блока элементов ИЛИ 5, второй информационный вход которого соединен с информационным выходом первого мультиплексора 4, а выход соединен с информационным входом третьего регистра 7, вход записи которого соединен с выходом элемента ИЛИ 6, первый вход которого соединен со входом установки в начальное состояние 15 устройства, а второй вход соединен с тактовым входом 16 устройства. Выход третьего регистра 7 соединен информационным входом ключа 2 и со сдвигом на один разряд в сторону старшего со вторыми информационными входами первого сумматора 3 и первого мультиплексора 4.

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

В начальном состоянии первый 1, второй 11 и третий 7 регистры находятся в нулевом состоянии.

На вход 12 устройства подается m - разрядный двоичный код множителя B. На вход 13 устройства подается n - разрядный двоичный код множимого A. На вход 14 устройства подается m - разрядный инверсный двоичный код модуля P.

Для установки устройства в исходное состояние на вход 15 устройства подается сигнал установки в исходное состояние устройства, который, поступая на вход записи первого регистра 1, осуществляет запись кода множимого A со входа 13 устройства в первый регистр 1. Также сигнал установки в исходное состояние устройства, проходя со входа 15 устройства через элемент ИЛИ 6 на вход записи третьего регистра 7, осуществляет запись кода множителя B со входа кода множителя 12 устройства в третий регистр 7. После того, как запись информации в первый регистр 1 и третий регистр 7 осуществлена, на вход 12 устройства подаются нулевые сигналы.

С выхода третьего регистра 7 код множителя B поступает на информационный вход ключа 2, на управляющий вход которого поступает значение младшего разряда a₀ кода множимого A в соответствии с (2). На информационном выходе ключа 2 образуется значение 0, если a₀=0 или значение B, если a₀=1, которое поступает на первый информационный вход третьего сумматора 8, на второй информационный вход которого поступает нулевое значение с выхода второго регистра 11. В результате на информационном выходе третьего сумматора 8 окажется код значения a₀·B, который поступает на вторые информационные входы второго сумматора 9 и второго мультиплексора 10. Так как на первый информационный вход второго сумматора 9 подается инверсный код модуля, а на вход переноса подается логическая единица, то он осуществляет вычитание a₀·B-P. По определению значение a₀·B < P, поэтому сигнал на выходе переноса второго сумматора 9, осуществляющего вычитание a₀·B-P, будет равен нулю и информационный выход второго мультиплексора 10 окажется скоммутированным с его вторым информационным входом. В результате на информационном входе второго регистра 11 окажется значение a₀·B. Одновременно с выхода третьего регистра 7 значение множителя B со сдвигом на один разряд в сторону старших (т.е. 2·B) поступает на вторые информационные входы первого сумматора 3 и первого мультиплексора 4. Первый сумматор 3 осуществляет вычитание 2·B-P, так как на его первый информационный вход подается инверсный код модуля P, а на вход переноса сигнал логической единицы. Если значение 2·B окажется больше или равно P, то на выходе переноса первого сумматора 3 появится сигнал переноса, который скоммутирует первый информационный вход первого мультиплексора 4 с его информационным выходом. Если же значение 2·B окажется меньше модуля P, то сигнал переноса не появится и с информационным выходом первого мультиплексора 4 окажется скоммутирован его второй информационный вход. В результате на информационный вход третьего регистра 7 с информационного выхода первого мультиплексора 4 через блок элементов ИЛИ 5 поступит значение (2·B) mod P.

Таким образом перед началом вычислений устройство будет установлено в исходное состояние, при этом в первый регистр 1 будет записан код множимого A, а в третий регистр 7 будет записан код множителя B.

Первым тактовым сигналом со входа 16 устройства в третий регистр 7 будет записано значение (2·B) mod P, а во второй регистр 11 будет записано значение a₀·B.

Вторым тактовым сигналом со входа 16 устройства в третий регистр 7 будет записано значение (2²·B) mod P, а во второй регистр 11 будет записано значение (a₁·2·B +a₀·B) (mod P).

В результате через n-1 тактов, в соответствии с (11), на входе второго регистра 11 получим произведение чисел A и B по модулю P, код которого
n-ым тактовым сигналом будет записан во второй регистр 11 и поступит на выход 17 устройства.

Рассмотрим работу устройства по модулю на примере.

Пусть множимое A=243₁₀=11110011₂, множитель B=31₁₀=00011111₂ модуль P=41₁₀=00101001₂, разрядность n=8, разрядность m=8.

В таблице 1 представлены состояния на входах и выходах элементов устройства после установки его в исходное состояние. В таблице 1 и далее приняты следующие обозначения:

«инф. вход 1» - информационный вход первого 1, второго 11 и третьего 7 регистров, ключа 2, а также первый информационный вход первого 3, второго 9 и третьего 8 сумматоров, первого 4 и второго 10 мультиплексоров, блока элементов ИЛИ 5;

«инф. вход 2» - второй информационный вход первого 3, второго 9 и третьего 8 сумматоров, первого 4 и второго 10 мультиплексоров, блока элементов ИЛИ 5;

«упр. вход» - управляющий вход ключа 2, первого 4 и второго 10 мультиплексоров, а также вход переноса первого 3 и второго 9 сумматоров;

«инф. выход» - информационный выход ключа 2, первого 3, второго 9 и третьего 8 сумматоров, первого 4 и второго 10 мультиплексоров, блока элементов ИЛИ 5, второго 11 и третьего 7 регистров, а также выход младшего разряда первого регистра 1;

«выход переноса» - выход переноса первого 3 и второго 9 сумматоров.

Таблица 1.

	инф. вход 1	инф. вход 2	упр. вход	инф. выход	выход переноса
Регистр 1	11110011	-	-	1	-
Ключ 2	00011111	-	1	00011111	-
Сумматор 3	11010110	00111110	1	00010101	1
Мультиплексор 4	00010101	00111110	1	00010101	-
Блок ИЛИ 5	00011111	00000000	-	00011111	-
Регистр 7	00010101	-	-	00011111	-
Сумматор 8	00011111	00000000	-	00011111	-
Сумматор 9	11010110	00011111	1	11110110	0
Мультиплексор 10	11110110	00011111	0	00011111	-
Регистр 11	00011111	-	-	0	-

В таблицах 2 - 8 представлены состояния на входах и выходах элементов устройства на первом - седьмом тактах соответственно.

Таблица 2.

	инф. вход 1	инф. вход 2	упр. вход	инф. выход	выход переноса
Регистр 1	11110011	-	-	1	-
Ключ 2	00010101	-	1	00010101	-
Сумматор 3	11010110	00101010	1	00000001	1
Мультиплексор 4	00000001	00101010	1	00000001	-
Блок ИЛИ 5	00000000	00000001	-	00000001	-
Регистр 7	00000001	-	-	00010101	-
Сумматор 8	00010101	00011111	-	00110100	-
Сумматор 9	11010110	00110100	1	00001011	1
Мультиплексор 10	00001011	00110100	1	00001011	-
Регистр 11	00001011	-	-	00011111	-

Таблица 3.

	инф. вход 1	инф. вход 2	упр. вход	инф. выход	выход переноса
Регистр 1	11110011	-	-	0	-
Ключ 2	00000001	-	0	0	-
Сумматор 3	11010110	00000010	1	11011001	0
Мультиплексор 4	11011001	00000010	0	00000010	-
Блок ИЛИ 5	00000000	00000010	-	00000010	-
Регистр 7	00000010	-	-	00000001	-
Сумматор 8	00000000	00001011	-	00001011	-
Сумматор 9	11010110	00001011	1	11100010	0
Мультиплексор 10	11100010	00001011	0	00001011	-
Регистр 11	00001011	-	-	00001011	-

Таблица 4.

	инф. вход 1	инф. вход 2	упр. вход	инф. выход	выход переноса
Регистр 1	11110011	-	-	0	-
Ключ 2	00000010	-	0	0	-
Сумматор 3	11010110	00000100	1	11011011	0
Мультиплексор 4	11011011	00000100	0	00000100	-
Блок ИЛИ 5	00000000	00000100	-	00000100	-
Регистр 7	00000100	-	-	00000010	-
Сумматор 8	00000000	00001011	-	00001011	-
Сумматор 9	11010110	00001011	1	11100010	0
Мультиплексор 10	11100010	00001011	0	00001011	-
Регистр 11	00001011	-	-	00001011	-

Таблица 5.

	инф. вход 1	инф. вход 2	упр. вход	инф. выход	выход переноса
Регистр 1	11110011	-	-	1	-
Ключ 2	00000100	-	1	00000100	-
Сумматор 3	11010110	00001000	1	11011111	0
Мультиплексор 4	11011111	00001000	0	00001000	-
Блок ИЛИ 5	00000000	00001000	-	00001000	-
Регистр 7	00001000	-	-	00000100	-
Сумматор 8	00000100	00001011	-	00001111	-
Сумматор 9	11010110	00001111	1	11100110	0
Мультиплексор 10	11100110	00001111	0	00001111	-
Регистр 11	00001111	-	-	00001011	-

Таблица 6.

	инф. вход 1	инф. вход 2	упр. вход	инф. выход	выход переноса
Регистр 1	11110011	-	-	1	-
Ключ 2	00001000	-	1	00001000	-
Сумматор 3	11010110	00010000	1	11100111	0
Мультиплексор 4	11100111	00010000	0	00010000	-
Блок ИЛИ 5	00000000	00010000	-	00010000	-
Регистр 7	00010000	-	-	00001000	-
Сумматор 8	00001000	00001111	-	00010111	-
Сумматор 9	11010110	00010111	1	11101110	0
Мультиплексор 10	11101110	00010111	0	00010111	-
Регистр 11	00010111	-	-	00001111	-

Таблица 7.

	инф. вход 1	инф. вход 2	упр. вход	инф. выход	выход переноса
Регистр 1	11110011	-	-	1	-
Ключ 2	00010000	-	1	00010000	-
Сумматор 3	11010110	00100000	1	11110111	0
Мультиплексор 4	11110111	00100000	0	00100000	-
Блок ИЛИ 5	00000000	00100000	-	00100000	-
Регистр 7	00100000	-	-	00010000	-
Сумматор 8	00010000	00010111	-	00100111	-
Сумматор 9	11010110	00100111	1	11111110	0
Мультиплексор 10	11111110	00100111	0	00100111	-
Регистр 11	00100111	-	-	00010111	-

Таблица 8.

	инф. вход 1	инф. вход 2	упр. вход	инф. выход	выход переноса
Регистр 1	11110011	-	-	1	-
Ключ 2	00100000	-	1	00100000	-
Сумматор 3	11010110	01000000	1	00010111	1
Мультиплексор 4	00010111	01000000	1	00010111	-
Блок ИЛИ 5	00000000	00010111	-	00010111	-
Регистр 7	00010111	-	-	00100000	-
Сумматор 8	00100000	00100111	-	001000111	-
Сумматор 9	11010110	01000111	1	00011110	1
Мультиплексор 10	00011110	01000111	1	00011110	-
Регистр 11	00011110	-	-	00100111	-

На седьмом такте на информационном входе регистра 11 окажется код числа 30₁₀=00011110₂, который восьмым тактовым импульсом запишется во второй регистр 11 и окажется на выходах устройства. Непосредственной проверкой устанавливаем, что (243·31) mod 41 = 30, что подтверждает правильность работы устройства.

Устройство прототип содержит m - ключей, (m-1) - сумматоров, (m-1) - мультиплексоров, m - входовый сумматор по модулю, который в свою очередь может содержать минимум 2m сумматоров и m мультиплексоров.

Предлагаемое устройство содержит ключ, 3 сумматора, 2 мультиплексора, 3 регистра, элемент ИЛИ и блок элементов ИЛИ. Очевидно, что объем оборудования в предлагаемом устройстве практически в m - раз меньше, чем в устройстве прототипе.

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