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

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

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

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

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

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

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

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

Наиболее близким по технической сущности к заявляемому изобретению является умножитель по модулю, содержащий ключи, сумматоры и мультиплексоры, позволяющий выполнять умножение двух чисел по произвольному модулю [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, умножитель на два по модулю 2, параллельный регистр 3, ключ 4, накапливающий сумматор по модулю 5, первые информационные входы устройства 6, вторые информационные входы устройства 7, третьи информационные входы 8, вход установки устройства в начальное состояние 9, тактовый вход устройства 10, информационные выходы устройства 11. На первые информационные входы 6, которые соединены с информационными входами регистра сдвига 1 подаётся код множимого. На вторые информационные входы устройства 7, которые соединены с первыми информационными входами умножителя на два по модулю 2 и с первыми информационными входами накапливающего сумматора по модулю 5, подаётся инверсный код модуля. Третьи информационные входы устройства 8 соединены с первыми информационными входами параллельного регистра 3. На третьи информационные входы устройства 8 подается код множителя. Вход установки устройства в начальное состояние 9 соединен со входами установки в начальное состояние регистра сдвига 1, параллельного регистра 3 и накапливающего сумматора по модулю 5. Тактовый вход устройства 10 соединен с тактовыми входами регистра сдвига 1, параллельного регистра 3 и накапливающего сумматора по модулю 5, выходы которого соединены с информационными выходами устройства 11, а второй информационный вход соединен с выходом ключа 4, управляющий вход которого соединен с выходом младшего разряда регистра сдвига 1, а информационные входы соединены с выходами параллельного регистра 3 и со вторыми информационными входами умножителя на два по модулю 2, выходы которого соединены со вторыми информационными входами регистра сдвига 1.

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

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

На первые информационные входы 6 подается двоичный код множимого A. На вторые информационные входы 7 подается инверсный двоичный код модуля P. На третьи информационные входы 8 подается двоичный код множителя B. Разрядность чисел A, B и P соответствует выражениям (2), (3) и (4).

При подаче сигнала на вход установки устройства в начальное состояние 9 регистр сдвига 1 инициализируется - в него записывается код множимого A, поступающий на первые информационные входы устройства 6, в параллельный регистр 3 записывается код множителя B, а в накапливающий сумматор по модулю 5 записывается нулевое значение. Умножитель на два по модулю 2 вычислит значение (2·B) mod P. В результате на вторых информационных входах параллельного регистра 3 будет сформировано значение (2·B) mod P, а так как младший разряд регистра сдвига 1 соединен с управляющим входом ключа 4, то на его выходах будет сформировано значение a₀·B.

С приходом первого тактового импульса, значение a₀·B просуммируется с нулевым значением в накапливающий сумматоре по модулю 5, значение (2·B) mod P запишется в параллельный регистр 3, код множимого A в регистре сдвига 1 сдвинется на одну позицию в сторону младших разрядов, а умножитель на два по модулю 5 сформирует на своих выходах значение (2²·B) mod P. В результате на вторых информационных входах параллельного регистра 3 будет сформировано значение (2²·B) mod P, а на выходах ключа 4 будет сформировано значение a₁·(2·B) mod P.

С приходом второго тактового импульса, значение a₁·(2·B) mod P с выходов ключа 4 просуммируется по модулю P в накапливающем сумматоре по модулю 5 со значением a₀·B, значение (2²·B) mod P запишется в параллельный регистр 3, код множимого A в регистре сдвига 1 сдвинется еще на одну позицию в сторону младших разрядов, а умножитель на два по модулю 2 сформирует на своих выходах значение (2³·B) mod P. В результате на вторых информационных входах параллельного регистра 3 будет сформировано значение (2³·B) mod P, а на выходах ключа 4 будет сформировано значение a₂·(2²·B) mod P.

На каждом i-ом такте на выходе ключа 4 будет формироваться значение a_i·(2ⁱ·B) mod P, которое в соответствии с (11) будет суммироваться по модулю P в накапливающем сумматоре по модулю 5.

В итоге после n-го такта работы на информационных выходах устройства 11 сформируется значение (A·B)mod P.

Устройство прототип [3] содержит n ключей, (n/2+logn-1) сумматоров, n/2 двухпортовых мультиплексоров и (logn-1) четырехпортовых мультиплексоров.

Предлагаемое устройство содержит регистр сдвига 1, умножитель на два по модулю 2, параллельный регистр 3, ключ 4 и накапливающий сумматор по модулю 5. Умножитель на два по модулю 2 может быть реализован, например, по схеме [1] и содержит сумматор и двухпортовый мультиплексор, а накапливающий сумматор по модулю 5 может быть реализован, например, по схеме [4] и содержит два сумматора, двухпортовый мультиплексор и параллельный регистр. Очевидно, что объем оборудования в предлагаемом устройстве практически в n раз меньше, чем в устройстве прототипе.

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

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

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

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

4. Петренко В.И., Кузьминов Ю.В. Накапливающий сумматор по модулю // Патент РФ № 2500017. Опубл. 27.11.2013. Бюл. № 33.

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах, в криптографических приложениях, в устройствах цифровой обработки сигналов и в системах управления. Технический результат заключается в сокращении объема оборудования. Устройство содержит регистр сдвига 1, умножитель на два по модулю 2, параллельный регистр 3, ключ 4 и накапливающий сумматор по модулю 5, при этом умножитель на два по модулю 2 содержит сумматор и двухпортовый мультиплексор, а накапливающий сумматор по модулю 5 содержит два сумматора, двухпортовый мультиплексор и параллельный регистр. В устройстве вычисляют произведения чисел 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.

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