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

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано в вычислительных машинах и устройствах, функционирующих в системе остаточных классов. Цель изобретения - уменьшение количества оборудования. Цель достигается за счет сохранения возможности модульного умножения путем введения сумматора 15 по модулю два, двух элементов И 16, 18 и элемента НЕ 17. Сущность изобретения: замена двух групп элементов И двумя элементами И при проведении операции модульного умножения. 1 ил.

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

Известно устройство (аналог) для умножения в системе остаточных классов (авт. св. N 922731, кл. G 06 F 7/52, 1982), содержащее входные регистры, дешифраторы, ключи, коммутатор, выходной регистр, сумматор по модулю два, группы элементов ИЛИ, элементы И и ИЛИ. Недостаток данного устройства - большой объем используемого оборудования.

Близким по технической сущности (аналогом) к предлагаемому изобретению является устройство (1), содержащее входные регистры, дешифраторы, группы элементов ИЛИ, элементы ИЛИ, группы элементов И, коммутатор, шифратор, сумматор по модулю Р, выходной регистр, элементы И. Недостаток устройства - большой объем используемого оборудования.

Наиболее близким по технической сущности (прототипом) к предполагаемому изобретению является устройство (2), содержащее входные и выходной регистры, два дешифратора, три группы элементов ИЛИ, четыре группы элементов И, пять элементов ИЛИ, два элемента И, табличный вычислитель значений вида α^lβ^l(modP/2) + P/2 (P - модуль) и шифратор.

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

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

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

Технический результат достигается тем, что в устройство, содержащее два входные и выходной регистры, два дешифратора, две группы элементов И, табличный вычислитель значений вида α^lβ^l(modP/2) + P/2, два элемента ИЛИ, три группы элементов ИЛИ и шифратор, причем входы первого и второго операндов устройства соединены соответственно с входами первого и второго входных регистров, выходы которых соединены соответственно с входами первого и второго дешифраторов, первые группы выходов которых соединены соответственно с первыми входами элементов ИЛИ первой и второй группы и входами первого и второго элементов ИЛИ, а вторые группы выходов - с вторыми входами элементов ИЛИ первой и второй групп, выходы табличного вычислителя значения вида α^lβ^l(modP/2) + P/2 соединены соответственно с первыми входами элементов И первой и второй групп, выходы которых соединены с первыми и вторыми входами элементов ИЛИ третьей группы, введены сумматор по модулю два, два элемента И и элемент НЕ, причем выходы первого и второго элементов ИЛИ соединены соответственно с первым и вторым входами сумматора по модулю два, выход которого соединен с первым входом второго элемента И и входом элемента НЕ, выход которого соединен с первым входом первого элемента И, вторые входы первого и второго элементов И соединены с входом управления устройством, а выходы - соответственно с вторыми входами элементов И первой и второй групп, выходы элементов ИЛИ первой и второй группы соединены соответственно с первой и второй группами входов табличного вычислителя значений вида α^lβ^l(modP/2) + P/2, выходы элементов ИЛИ третьей группы соединены с входами шифратора, выход которого соединен с входом выходного регистра, выход которого является выходом устройства.

Сущность изобретения состоит в замене двух групп элементов И двумя элементами И при проведении операции модульного умножения.

Возможность достижения положительного эффекта от использования данного изобретения состоит в уменьшении количества оборудования.

На чертеже представлена структурная схема устройства, где 1 - вход первого операнда устройства, 2 - вход второго операнда устройства, 3 - первый входной регистр, 4 - второй входной регистр, 5 - первый дешифратор, 6 - второй дешифратор, 7 - первая группа элементов ИЛИ, 8 - вторая группа элементов ИЛИ, 9 - первый элемент ИЛИ, 10 - второй элемент ИЛИ, 11 - табличный вычислитель значений вида α^lβ^l(modP/2) + P/2, 12 - первая группа элементов И, 13 - вторая группа элементов И, 14 - третья группа элементов ИЛИ, 15 - сумматор по модулю два, 16 - второй элемент И, 17 - элемент НЕ, 18 - первый элемент И, 19 - вход управления устройством, 20 - шифратор, 21 - выходной регистр, 22 - выход устройства.

Входы первого 1 и второго 2 операндов устройства соединены соответственно с входами первого 3 и второго 4 входных регистров, выходы которых соединены соответственно с входами первого 5 и второго 6 дешифраторов, первые группы выходов которых соединены соответственно с первыми входами элементов ИЛИ первой 7 и второй 8 групп и входами первого 9 и второго 10 элементов ИЛИ, а вторые группы выходов - с вторыми входами элементов ИЛИ первой 7 и второй 8 групп, выходы табличного вычислителя 11 значений вида α^lβ^l(modP/2) + P/2 соединены соответственно с первыми входами элементов И первой 12 и второй 13 групп, выходы которых соединены с первыми и вторыми входами элементов ИЛИ третьей 14 группы, выходы первого 9 и второго 10 элементов ИЛИ соединены соответственно с первым и вторым входами сумматора 15 по модулю два, выход которого соединен с первым входом второго 16 элемента И и входом элемента НЕ 17, выход которого соединен с первым входом первого 18 элемента И, вторые входы первого 18 и второго 16 элементов И соединены с входом 19 управления устройством, а выходы - соответственно с вторыми входами элементов И первой 12 и второй 13 групп, выходы элементов ИЛИ первой 7 и второй 8 групп соединены соответственно с первой и второй группами входов табличного вычислителя 11 значений вида α^lβ^l(modP/2) + P/2, выходы элементов ИЛИ третьей 14 группы соединены с входами шифратора 20, выход которого соединен с входом выходного 21 регистра, выход которого является выходом 22 устройства.

Устройство для умножения по модулю работает следующим образом.

По входам 1 и 2 входные операнды А' и В' в двоичном коде поступают на соответствующие входные регистры 3 и 4, с выходов которых поступают на соответствующие дешифраторы 5 и 6. С выходов дешифраторов 5 и 6 операнды А' и В' в десятичном коде поступают на соответствующие элементы ИЛИ 7 и 8, с выходов которых операндыα¹ и β¹(А¹ = (γ_A¹,α^l), В^l =(γ_B,β^l)) поступают на входы табличного вычислителя 11. Выходной сигнал табличного вычислителя 11, соответствующий значению α^lβ^l(modP/2) + P/2, поступает на первые входы К-го элемента И 12 группы и К-го элемента И 13 группы (К = 1,2,...,Р-1).

Если γ_A^l= γ_B^l, то выходной сигнал сумматора по модулю 15 два отсутствует, а присутствует на выходе элемента НЕ 17, который по сигналу 19 открывает элементы И 12 группы. В этом случае сигнал с выхода К-го элемента И 12 группы поступает на вход К-го элемента ИЛИ 14 группы, с выхода которого сигнал поступает на вход шифратора 20 и далее поступает на вход регистра 21, с выхода которого результат операции модульного умножения в двоичном коде поступает на выход 22 устройства.

Если γ_A^l≠γ_B^l, то сигнал с выхода сумматора 15 по модулю два присутствует. Этот сигнал открывает элементы И 13 группы по сигналу 19. В этом случае сигнал с выхода К-го элемента И 13 поступает на вход (Р-К)-го элемента ИЛИ 14 группы.

Рассмотрим пример конкретного выполнения операции модульного умножения для Р = 14. Пусть А' = 3, В' = 9. Тогда по входам 1 и 2 операнды А' = 0011 и В' = 1001 поступают в соответствующие входные регистры, с выходов которых поступают на соответствующие дешифраторы 5 и 6, с выходов которых операнды А' и В' в десятичном коде поступают на третий вход первой группы входов табличного вычислителя 11 и на пятый вход второй группы входов вычислителя 11, выходной сигнал которого поступает на первые входы первых элементов И 12 и И 13 групп. В данном случае γ_A^l≠γ_B^l, поэтому сигнал с выхода сумматора 15 по модулю два открывает элементы И 13 группы по сигналу 19 и с выхода первого элемента И 13 сигнал поступает на вход тринадцатого элемента ИЛИ 14 группы, с выхода которого сигнал поступает на вход шифратора 20, с входа которого результат операции модульного умножения 13₁₀ = 1101₂ поступает на вход регистра 21 и далее на выход 22 устройства.

Формула изобретения

УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛ ПО МОДУЛЮ, содержащее два входных и выходной регистры, два дешифратора, две группы элементов И, табличный вычислитель значений вида mod + , два элемента ИЛИ, три группы элементов ИЛИ и шифратор, причем входы первого и второго операндов устройства соединены соответственно с входами первого и второго входных регистров, выходы которых соединены соответственно с входами первого и второго дешифраторов, выходы первых групп которых соединены соответственно с первыми входами элементов ИЛИ первой и второй групп и входами первого и второго элементов ИЛИ, а выходы вторых групп - с вторыми входами элементов ИЛИ первой и второй групп, выходы табличного вычислителя значений вида mod + соединены соответственно с первыми входами элементов И первой и второй групп, выходы которых соединены соответственно с первыми и вторыми входами элементов ИЛИ третьей группы, выходы которых соединены с входами шифратора, выход которого соединен с входом выходного регистра, выход которого соединен с выходом устройства, отличающееся тем, что, с целью уменьшения количества оборудования, в него введены сумматор по модулю два, два элемента И и элемент НЕ, причем выходы первого и второго элементов ИЛИ соединены соответственно с первым и вторым входами сумматора по модулю два, выход которого соединен с первым входом первого элемента И и входом элемента НЕ, выход которого соединен с первым входом второго элемента И, вторые входы первого и второго элементов И соединены с управляющим входом устройства, а выходы - сооответственно с вторыми входами элементов И первой и второй групп, выходы элементов ИЛИ первой и второй групп соединены соответственно с входами первой и второй групп табличного вычислителя значений вида mod + .

РИСУНКИ

Рисунок 1