УМНОЖИТЕЛЬ ЧИСЕЛ ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ Российский патент 2025 года по МПК G06F7/72 

Область техники, к которой относится изобретение

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

Уровень техники

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

Известно устройство для умножения чисел по произвольному модулю, содержащее сумматоры, мультиплексоры, ключи, блоки сдвига, инвертор и сумматор по модулю [2]. Недостатком данного устройства является большой объем оборудования.

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

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

Раскрытие сущности изобретения

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

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

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

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

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

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

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

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

A = a_m-1·2^m-1+…+a₁·2+a₀, (2)

B = b_n-1·2^n-1+…+b₁·2+b₀, (3)

P = p_n-1·2^n-1+…+p₁·2¹+p₀, (4)

R = r_n-1·2^n-1+…+r₁·2¹+r₀, (5)

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

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

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

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

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

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

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

A·B = (a_m-1·2^m-1+…+ a₁·2+ a₀)·B. (6)

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

A·B = (a_m-1·2^m-1·B +…+ a₁·2·B + a₀·B), (7)

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

(A·B) mod P ≡ (a_m-1·2^m-1·B +…+ a₁·2·B + a₀·B) (mod P). (8)

В выражении (8) можно множитель 2 вынести несколько раз за скобки следующим образом:

(A·B) mod P ≡ (a_m-1·2^m-1·B + a_m-2·2^m-2·B +…+ a₁·2·B + a₀·B) (mod P) =

= (2(a_m-1·2^m-2·B + a_m-2 2^m-3·B +…+ a₁·B) + a₀·B) (mod P) =

= (2(2(… (a_m-1·2·B + a_m-2·B) + a_m-3·B) + … + a₁·B) + a₀·B) (mod P). (9)

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

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

(A⋅B) mod P ≡ (2(2(… (a_m-1·2·B + a_m-2·B) (mod P) + a_m-3·B) (mod P) +

… + a₁·B) (mod P) + a₀·B) (mod P). (10)

В соответствии с (10) вычисление произведения (A⋅B) по модулю P может быть выполнено за m этапов. На каждом этапе выполняется последовательное умножение коэффициентов a_i на величину B с последующим приведением результата по модулю P. Затем производится вынесение двойки за скобки, что позволяет представить выражение в виде накапливающей суммы, где каждый промежуточный результат умножается на 2 по модулю P. Этот процесс продолжается до тех пор, пока все коэффициенты a_i не будут учтены. Умножение на 2 при двоичном представлении чисел осуществляется сдвигом разрядов кода умножаемого числа на один в сторону старших. Если результат умножения попадает в диапазон [0; P-1], приведение по модулю не требуется, если же в диапазон [P; 2P-2], то приведение по модулю P осуществляется путем вычитания из результата умножения модуля P, а если в диапазон [2P; 3P-3], то приведение по модулю P осуществляется путем вычитания из результата умножения модуля 2P.

Краткое описание чертежей

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

Умножитель чисел по произвольному модулю содержит регистр сдвига 1 разрядностью m, где m - разрядность множимого, ключ 2, первый 3 и второй 4 трехвходовые сумматоры разрядностью (n+2) и (n+1) соответственно, двухвходовый сумматор 5, трехвходовый мультиплексор 6, параллельный регистр 7 разрядностью n, где n - разрядность множителя, модуля и произведения, первые информационные входы устройства 11, на которые подается код множимого, вторые информационные входы устройства 10, на которые подается код множителя, третьи информационные входы устройства 9, на которые подается инверсный код модуля и четвертые информационные входы устройства 8, на которые подается инверсный код удвоенного модуля, вход установки устройства в исходное состояние 12, который соединен со входом записи регистра сдвига 1 и со входом сброса параллельного регистра 7, тактовый вход устройства 13, который соединен с тактовыми входами регистра сдвига 1 и параллельного регистра 7, информационные выходы устройства 14, с которых снимается код произведения. Первые информационные входы устройства соединены 11 с информационными входами регистра сдвига 1, вторые информационные входы устройства соединены с информационными входами ключа 2, третьи информационные входы устройства 9 соединены с третьими информационными входами второго трехвходового сумматора 4, четвертые информационные входы устройства 8 соединены с третьими информационными входами первого трехвходового сумматора 3, старший разряд информационных выходов регистра сдвига 1 соединен с управляющим входом ключа 2, информационные выходы которого соединены со вторыми информационными входами двухвходового сумматора 5, первого 3 и второго 4 трехвходовых сумматоров, информационные выходы двухвходового сумматора 5 соединены с первыми информационными входами трехвходового мультиплексора 6, младшие n разрядов информационных выходов первого трехвходового сумматора 3 соединены с третьими информационными входами трехвходового мультиплексора 6, а выход переноса соединен со вторым управляющим входом трехвходового мультиплексора 6, младшие n разрядов информационных выходов второго трехвходового сумматора 4 соединены со вторыми информационными входами трехвходового мультиплексора 6, а выход переноса соединен с первым управляющим входом трехвходового мультиплексора 6, информационные выходы которого соединены с информационными входами параллельного регистра 7, информационный выход которого соединен с информационными выходами 14 устройства и со сдвигом на один разряд в сторону старших с первыми информационными входами двухвходового сумматора 5, первого 3 и второго 4 трехвходовых сумматоров, на входы переноса первого 3 и второго 4 трехвходовых сумматоров подается сигнал логической единицы.

Осуществление изобретения

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

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

На первые информационные входы 11 устройства подается m-разрядный двоичный код множимого A. На вторые информационные входы 10 устройства подается n-разрядный двоичный код множителя B. На третьи информационные входы 9 устройства подается (n+1)-разрядный инверсный двоичный код модуля P. На четвертые информационные входы устройства подается (n+2)-разрядный инверсный двоичный код удвоенного модуля P.

Для установки устройства в исходное состояние на вход 12 устройства подается сигнал установки в исходное состояние устройства, который, поступая на вход записи регистра сдвига 1, осуществляет запись кода множимого A, поступившего с информационных входов 11 устройства в регистр сдвига 1, а также поступая на вход сброса параллельного регистра 7 устанавливает его в нулевое состояние.

На первом такте со вторых информационных входов устройства 10 код множителя B поступает на информационные входы ключа 2, на управляющий вход которого с информационного выхода регистра сдвига 1 поступает значение старшего разряда a_m-1 кода множимого A в соответствии с (2). На информационном выходе ключа 2 образуется значение 0, если a_m-1=0 или значение B, если a_m-1=1, которое поступает на первые информационные входы двухвходового сумматора 5, первого 3 и второго 4 трехвходовых сумматоров.

На первые информационные входы всех сумматоров 3, 4 и 5 с информационных выходов параллельного регистра 7 поступают нулевые сигналы. На третьи информационные входы первого сумматора 3 поступает инверсный код удвоенного значения модуля, а на третьи информационные входы второго сумматора 4 поступает инверсный код модуля. С учетом этого, а также с учетом того, что на входы переноса первого 3 и второго 4 сумматоров подается сигнал логической единицы, эти сумматоры фактически будут вычислять разность между суммой чисел, поступающих на их первые и вторые информационные входы и числом, поступающим на их третьи информационные входы. В случае, если сумма чисел на их первых и вторых информационных входах будет превышать значение числа на их третьих информационных входах, то на выходе переноса образуется сигнал переноса.

Логика работы трехвходового мультиплексора 6 заключается в том, что при отсутствии сигналов переноса на его управляющих входах, с его информационными выходами будут скоммутированы его первые информационные входы. При наличии сигнала переноса на его втором управляющем входе, независимо от значения сигнала переноса на его первом управляющим входе, с его информационными выходами будут скоммутированы его третьи информационные входы. При отсутствии сигнала переноса на его втором управляющем входе и наличии сигнала на его первом управляющем входе с его информационными выходами будут скоммутированы его вторые информационные входы. Так как на первом такте на первых информационных входах первого 3 и второго 4 сумматоров присутствуют нулевые сигналы, а множитель B по определению меньше модуля P, то сигналов переноса в этом случае на выходах указанных сумматоров генерироваться не будет. В результате на информационные выходы трехвходового мультиплексора 6 на первом такте будет скоммутировано значение с его первых информационных входов. Под воздействием первого тактового импульса это значение и будет записано в параллельной регистр 7.

Так как информационные выходы параллельного регистра 7 соединены со сдвигом на один разряд в сторону старших с первыми информационными входами двухвходового сумматора 5, первого 3 и второго 4 сумматоров, то на этих входах образуется значение 2⋅(a_m-1⋅B).

На втором такте, после сдвига кода множимого в регистре сдвига 1 на один разряд в сторону младших, на информационных выходах ключа 2 образуется значение a_m-2⋅B, которое поступает на вторые информационные входы двухвходового сумматора 5, первого 3 и второго 4 трехвходовых сумматоров. Двухвходовый сумматор 5 осуществляет суммирование значений (2⋅a_m-1⋅B) и a_m-2⋅B. Второй трехвходовый сумматор 4 осуществляет сложение и вычитание (2⋅a_m-1·B + a_m-2⋅B)-P, так как на его третий информационный вход с третьих информационных входов устройства 9 подается инверсный код модуля P, а на вход переноса сигнал логической единицы. Аналогично первый трехвходовый сумматор 3 совершает сложение и вычитание (2·a_m-1·B + a_m-2·B)-2P, так как на третьи информационные входы подается инверсный код удвоенного модуля 2P.

Если значение (2·a_m-1·B + a_m-2·B) окажется в диапазоне [2P; 3P-3], то сигнал переноса появится на выходе переноса первого трехвходового сумматора 3 и, поступая далее на второй управляющий вход трехвходового мультиплексора 6, скоммутирует с его информационными выходами его третьи информационные входы.

Если значение (2·a_m-1·B + a_m-2·B) окажется в диапазоне [P; 2P-2], то сигнал переноса появится на выходе переноса второго трехвходового сумматора 4 и, поступая далее на первый управляющий вход трехвходового мультиплексора 6, скоммутирует с его информационными выходами его вторые информационные входы.

Если значение (2·a_m-1⋅B + a_m-2⋅B) окажется в диапазоне [0; P-1], то сигналы переноса на выходах переноса первого 3 и второго 4 трехвходовых сумматоров будут отсутствовать и с информационными выходами трехвходового мультиплексора 6 будут скоммутированы его первые информационные входы.

В результате на информационных выходах трехвходового мультиплексора окажется значение (2·a_m-1⋅B + a_m-2⋅B) modP. Под воздействием второго тактового импульса это значение и будет записано в параллельной регистр 7.

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

В результате на m-ом такте, в соответствии с (10) на информационных выходах 14 устройства получим произведение чисел A и B по модулю P. Перед началом следующих вычислений устройство будет установлено в исходное состояние.

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

Источники информации

1. Петренко В.И., Чипига А.Ф. Умножитель на два по модулю // Патент РФ №2015537. Опубл. 30.06.1994.

2. Петренко В.И., Кузьминов Ю.В. Устройство для умножения чисел по произвольному модулю // Патент РФ №2316042. Опубл. 27.01.2008. Бюл. №3.

3. Петренко В.И., Умножитель по модулю // Патент РФ №2751802. Опубл. 19.07.2021. Бюл. №20.

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

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