Результат интеллектуальной деятельности: Арифметико-логическое устройство для умножения чисел по модулю

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

Известно устройство для умножения чисел по произвольному модулю (Патент РФ №2316042, МПК G06F 7/523, G06F 7/72, Бюл. №3, 2008 г.), содержащее (m-1) сумматоров, (m-1) мультиплексоров, m ключей, (m-2) блоков сдвига, инвертор и сумматор по модулю, где m - количество разрядов в двоичном коде второго множителя.

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

Наиболее близким по технической сущности к заявляемому изобретению является арифметико-логическое устройство для выполнения операции умножения, содержащее три n-разрядных регистра, где n - разрядность умножаемых чисел, электронный ключ, входную и выходную n-разрядные шины, модуль управляющего блока (Бабич Н.П., Жуков И.А. Компьютерная схемотехника. Методы построения и проектирования: Учебное пособие. - К.: МК-Пресс, 2004. - 576 с. рис. 9.16, стр. 299-308).

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

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

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

Сущность изобретения заключается в реализации следующего способа нахождения произведения чисел А и В по модулю Р. Операндами являются числа А и В, значения которых находятся в диапазоне от 0 до (Р-1) включительно.

Числа А и В, имеющие разрядность n, могут быть представлены в двоичном виде:

где a_i и b_i - коэффициенты в двоичном представлении чисел А и В, .

В случае различной разрядности чисел А и В за n принимается большая из разрядностей, а старшие разряды числа с меньшей разрядностью дополняются нулевыми.

Произведение А⋅В(mod P) можно записать в виде:

где r_i - i-й частичный остаток.

Таким образом, операция умножения чисел А и В по модулю Р может быть выполнена путем последовательного нахождения n частичных остатков вида:

где , и последующего сложения по модулю Р тех из них, для которых коэффициент b_i=1.

Частичные остатки могут быть вычислены по следующему рекуррентному правилу:

Нулевым частичным остатком r₀ является само число А. Для последовательного формирования остальных (n-1) частичных остатков может быть использован n-разрядный накапливающий сумматор по модулю, на вход которого на первом такте поступает число А, а на каждом последующем такте - значение, которое на предыдущем такте было на его выходе. Операция умножения предыдущего частичного остатка r_i-1 на 2 по модулю Р в таком случае осуществляется как сложение r_i-1 по модулю Р с самим собой.

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

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

Информационные входы n-разрядных регистров 3, 4 соединены со входной n-разрядной шиной 1, управляющий вход первого n-разрядного регистра 3 соединен с первым выходом модуля управляющего блока 10, второй управляющий вход второго n-разрядного регистра 4 соединен с седьмым выходом модуля управляющего блока.

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

На фиг. 2 представлена схема модуля управляющего блока 10 арифметико-логического устройства для умножения чисел по модулю.

Модуль управляющего блока содержит два двухвходовых элемента И 10.1, 10.10, двухвходовый элемент ЗАПРЕТ 10.2, r-разрядный счетчик 10.3, где r=⎡log₂(2n+4)⎤, r-входовый дешифратор 10.4, RS-триггер 10.5, три n-входовых элемента ИЛИ 10.6, 10.7, 10.8, (n-1)-входовый элемент ИЛИ 10.9. Первый вход первого двухвходового элемента И 10.1 является первым входом модуля управляющего блока 10, второй вход является вторым входом модуля управляющего блока 10, а выход соединен со счетным входом r-разрядного счетчика 10.3 и с запрещающим входом двухвходового элемента ЗАПРЕТ 10.2, выход которого соединен с управляющим входом r-разрядного счетчика 10.3, выходы которого соединены с соответствующими информационными входами r-входового дешифратора 10.4, первый выход которого является первым выходом модуля управляющего блока 10, а также соединен с R-входом RS-триггера 10.5, выход которого является вторым выходом модуля управляющего блока 10. Второй выход r-входового дешифратора 10.4 соединен с первым входом первого n-входового элемента ИЛИ 10.6, выход которого является четвертым выходом модуля управляющего блока 10. Третий выход r-входового дешифратора 10.4 является третьим выходом модуля управляющего блока 10 и соединен с S-входом RS-триггера 10.5 и с первым входом второго n-входового элемента ИЛИ 10.7, выход которого является пятым выходом модуля управляющего блока 10. Каждый 2k-й выход r-входового дешифратора 10.4, где k=2, 3, …, n, соединен с k-м входом второго n-входового элемента ИЛИ 10.7 и с (k-1)-м входом третьего n-входового элемента ИЛИ 10.8, выход которого соединен со вторым входом второго двухвходового элемента И 10.10, первый вход которого является третьим входом 13 модуля управляющего блока 10, а выход является шестым выходом модуля управляющего блока 10. Каждый (2k+1)-й выход r-входового дешифратора 10.4, где k=2, 3, …, n, соединен с k-м входом первого n-входового элемента ИЛИ 10.6 и с (k-1)-м входом (n-1)-входового элемента ИЛИ 10.9, выход которого является седьмым выходом модуля управляющего блока 10, (2n+2)-й выход r-входового дешифратора 10.4 соединен с n-м входом третьего n-входового элемента ИЛИ 10.8, (2n+3)-й выход r-входового дешифратора 10.4 соединен с разрешающим входом двухвходового элемента ЗАПРЕТ 10.2, а также является восьмым выходом модуля управляющего блока 10.

Арифметико-логическое устройство для умножения чисел по модулю работает следующим образом.

Умножение n-разрядных чисел А и В по модулю Р осуществляется за (2n+3) тактов. В исходном состоянии r-разрядный счетчик 10.3 обнулен, на вход 11 подается логический «0». Для начала работы устройства и на протяжении всего цикла умножения на вход 11 устройства подается сигнал логической «1». При этом тактовые импульсы, поступающие на вход 12, начинают подсчитываться r-разрядным счетчиком 10.3. Результат подсчета подается на вход r-входового дешифратора 10.4, и на его выходах с номерами 1, …, (2n+3) последовательно появляются импульсы.

С приходом первого тактового импульса на вход 12 на первом выходе r-входового дешифратора 10.4 появляется сигнал логической единицы, который поступает на выход y₁ модуля управляющего блока 10, а также на R-вход RS-триггера 10.5. Сигнал с выхода y₁ модуля управляющего блока 10 поступает на первые управляющие входы (входы сброса) первого и второго n-разрядных накапливающих сумматоров 6, 7 по модулю, вызывая их обнуление, а также на управляющий вход первого n-разрядного регистра 3. В результате этого происходит считывание кода модуля Р со входной n-разрядной шины 1 в первый n-разрядный регистр 3, с выхода которого код модуля подается на первые информационные входы (входы модуля) первого и второго n-разрядных накапливающих сумматоров 6, 7 по модулю. В результате сброса RS-триггера 10.5 на выходе y₂ модуля управляющего блока 10 появляется сигнал логического «0», который поступает на управляющий вход n-разрядного мультиплексора 2, подключая тем самым информационный вход третьего n-разрядного регистра 5 к входной шине 1.

С приходом второго тактового импульса на вход 12 сигнал логической «1» появляется на втором выходе r-входового дешифратора 10.4 и подается через первый n-входовый элемент ИЛИ 10.6 на выход y₄ модуля управляющего блока 10. Этот сигнал поступает на управляющий вход третьего n-разрядного регистра 5, в результате чего происходит считывание в данный регистр кода множителя А, являющегося нулевым частичным остатком.

С приходом третьего тактового импульса на вход 12 сигнал логической «1» появляется на третьем выходе r-входового дешифратора 10.4, откуда поступает на S-вход RS-триггера 10.5, переводя его в единичное состояние. Также этот сигнал поступает на выход y₃ и через второй n-входовый элемент ИЛИ 10.7 на выход y₅ модуля управляющего блока 10. В результате перевода RS-триггера 10.5 в единичное состояние на выходе y₂ модуля управляющего блока 10 появляется сигнал логической «1», который поступает на управляющий вход n-разрядного мультиплексора 2, подключающего информационный вход третьего n-разрядного регистра 5 к выходу первого n-разрядного накапливающего сумматора 7 по модулю до окончания текущего и начала следующего цикла умножения. Сигнал с выхода y₃ модуля управляющего блока 10 поступает на первый управляющий вход второго n-разрядного регистра 4, в результате чего происходит считывание в данный регистр кода множителя В. Сигнал с выхода y₅ модуля управляющего блока 10 поступает на второй управляющий вход первого n-разрядного накапливающего сумматора 7 по модулю (вход тактовых импульсов), в результате чего в первый n-разрядный накапливающий сумматор 7 по модулю записывается код множителя А.

С приходом 2k-го тактового импульса, где k=2, 3, …, n, сигнал логической «1» появляется на 2k-м выходе r-входового дешифратора 10.4, откуда подается через второй n-входовый элемент ИЛИ 10.7 на выход y₅ модуля управляющего блока 10. Этот сигнал поступает на второй управляющий вход первого n-разрядного накапливающего сумматора 7 по модулю, в результате чего к значению, хранимому в первом n-разрядном накапливающем сумматоре 7 по модулю, прибавляется значение, находящееся в третьем n-разрядном регистре 5, и на выходе первого n-разрядного накапливающего сумматора 7 по модулю формируется следующий частичный остаток. Если значением младшего разряда второго n-разрядного регистра 4 является «1», то на выход y₆ модуля управляющего блока 10 через третий n-входовый элемент ИЛИ 10.8 и второй двухвходовый элемент И 10.10 подается сигнал логической «1», который поступает на второй управляющий вход (вход тактовых импульсов) второго n-разрядного накапливающего сумматора 6 по модулю, в результате чего хранимое в нем значение складывается по модулю Р с текущим частичным остатком, находящимся в третьем n-разрядном регистре 5.

С приходом (2k+1)-го тактового импульса, где k=2, 3, …, n, сигнал логической «1» появляется на (2k+1)-м выходе r-входового дешифратора 10.4, откуда подается через первый n-входовый элемент ИЛИ 10.6 на выход y₄ модуля управляющего блока 10, а также на выход y₇ модуля управляющего блока 10 через (n-1)-входовый элемент ИЛИ 10.9. Сигнал с выхода y₄ модуля управляющего блока 10 поступает на управляющий вход третьего n-разрядного регистра 5, в результате чего происходит считывание в данный регистр с выхода первого накапливающего сумматора 7 по модулю частичного остатка, который будет использован на следующем такте. Сигнал с выхода y₇ модуля управляющего блока 10 поступает на второй управляющий вход второго n-разрядного регистра 4, что приводит к сдвигу находящегося в нем значения на один разряд вправо.

С приходом (2n+2)-го тактового импульса сигнал логической «1» появляется на (2n+2)-м выходе r-входового дешифратора 10.4, откуда поступает на n-й вход третьего n-входового элемента ИЛИ 10.8. Если значением младшего разряда второго n-разрядного регистра 4 является «1», то на выход y₆ модуля управляющего блока 10 через третий n-входовый элемент ИЛИ 10.8 и второй двухвходовый элемент И 10.10 подается сигнал логической «1», который поступает на второй управляющий вход (вход тактовых импульсов) второго n-разрядного накапливающего сумматора 6 по модулю, в результате чего хранимое в нем значение складывается по модулю Р с частичным остатком, записанным в третьем n-разрядном регистре 5.

С приходом (2n+3)-го тактового импульса сигнал логической «1» появляется на (2n+3)-м выходе r-входового дешифратора 10.4, откуда поступает на выход y₈ модуля управляющего блока 10 и на разрешающий вход двухвходового элемента ЗАПРЕТ 10.2. С выхода y₈ модуля управляющего блока 10 сигнал поступает на управляющий вход n-разрядного электронного ключа 8, и результат умножения А на В по модулю Р поступает с выхода второго n-разрядного накапливающего сумматора 6 по модулю на выходную n-разрядную шину 9. После спада (2n+3)-го тактового импульса на запрещающий вход двухвходового элемента ЗАПРЕТ 10.2 поступает логический «0» и на его выходе устанавливается сигнал логической «1», который подается на управляющий вход (вход сброса) r-разрядного счетчика 10.3 и, таким образом, обнуляет счетчик. Цикл умножения завершен.

Рассмотрим работу арифметико-логического устройства для умножения чисел по модулю на конкретном примере.

Пусть n=4, А=7, В=9, Р=13. Умножение по модулю выполняется за (2n+3)=11 тактов.

На первом такте производится считывание с входной n-разрядной шины 1 кода модуля Р=13₁₀=1101₂.

На втором такте с входной n-разрядной шины 1 считывается код множителя А=7₁₀=0111₂.

На третьем такте с входной n-разрядной шины 1 считывается код множителя В=9=1001₂, а код множителя А=7=0111₂ записывается в первый n-разрядный накапливающий сумматор 7 по модулю.

На четвертом такте происходит вычисление первого частичного остатка: 7+7≡1 (mod 13). Поскольку младший разряд В=1001₂ равен 1, к содержимому второго n-разрядного накапливающего сумматора 6 по модулю прибавляется значение нулевого частичного остатка: 0+7≡7 (mod 13).

На пятом такте сдвигается на один разряд вправо содержимое второго n-разрядного регистра 4, в котором хранится значение множителя В=1001₂, т.е. В^/=0100₂, а также происходит запись первого частичного остатка, равного 1, в третий n-разрядный регистр 5.

На шестом такте происходит вычисление второго частичного остатка: 1+1≡2 (mod 13). Младший разряд В^/=0100₂ равен 0, поэтому первый частичный остаток, хранящийся в третьем n-разрядном регистре 5, не прибавляется к содержимому второго n-разрядного накапливающего сумматора 6 по модулю.

На седьмом такте сдвигается на один разряд вправо содержимое второго n-разрядного регистра 4, в котором хранится значение В^/=0100₂, т.е. В^//=0010₂, а также происходит запись второго частичного остатка, равного 2, в третий n-разрядный регистр 5.

На восьмом такте происходит вычисление третьего частичного остатка: 2+2≡4 (mod 13). Младший разряд В^//=0010₂ равен 0, поэтому второй частичный остаток, хранящийся в третьем n-разрядном регистре 5, не прибавляется к содержимому второго n-разрядного накапливающего сумматора 6 по модулю.

На девятом такте сдвигается на один разряд вправо содержимое второго n-разрядного регистра 4, в котором хранится значение В^//=0010₂, т.е. В^///=0001₂, а также происходит запись третьего частичного остатка, равного 4, в третий n-разрядный регистр 5.

Поскольку младший разряд В^///=0001₂ равен 1, на десятом такте к содержимому второго n-разрядного накапливающего сумматора 6 по модулю прибавляется значение третьего частичного остатка, хранящегося в третьем n-разрядном регистре 5: 7+4≡11 (mod 13).

На одиннадцатом такте содержимое второго n-разрядного накапливающего сумматора 6 по модулю подается на выходную n-разрядную шину 9. Таким образом, результат операции умножения по модулю равен 11. Умножение выполнено корректно, поскольку 7⋅9≡11 (mod 13).