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

 

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

Союз Советскня

Социалистических

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополмительное к авт. саид-ву у896620 (22) Заявлено 17 ° 02.81 (21) 3250548/18-24 f$$) М. Кд.з с присоединением заявки М

С 06 F 7/49

Государственный комитет

СССР по делам изобретений и открытий (23) ПриоритетОпубликовано 15.1282. бюллетень М 46 (ЮЗ}УДК 681 ° 325 (088.8) Дата опубликования описания 15.12.82 (72) Авторы изобретения

В.A Êðàñíîáàåâ и A Â.Êîðîëåâ (71) Заявитель (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ПО МОДУЛЮ Изобретение относится к вычисли1 тельной технике.

По основному авт.св. Р 896620 известно устройство для умножения по модулю, содержащее первый и: второй входные регистры, дешифраторы, две группы элементов ИЛИ, первую группу элементов И, две группы ключей,первый, второй, третий, четвертый, пятый элементы ИЛЙ, первый и второй элементы И, выходной регистр, первый и второй входные регистры подключены выходами ко входам. соответствующих дешифраторов, выходы первой:и второй групп которых подключены к.соответствующим входам элементов ИЛИ первой и второй групп, выходы которых подключены к соответствующим входам ключей соответственно первой и второй. групп, первые н вторые-группы выходов первого и второго дешифраторов подключены соответственно ко входам первого и второго, третьего и четвертого элементов ИЛИ, а также содержит и коммутаторов (n > log P, P - модуль) сумматор по модулю Р, две группы элементов И, причем соответствующие входы первой группы вхо« дов коммутаторов объединены и подключены к выходам соответствукщих ключей первой группы, соответствующие входы второй-группы входов коммутаторов объединены и. подключены к ,выходам соответствующих ключей второй группы, выходы коммутаторов подключены к соответствующим входам первой группы выходного регистра, .вторая группа входов которого подключена к группе выходов сумматора по модулю Р, первая группа входов которого подключена соответственно к выходам ключей первой группы, информационные входы, которых являются входами кода константы Р, а управляющие входы объединены и подключены к выходу пятого элемента ИЛИ, входЫ которого подключены к выходам соответственно первого и второго элементов И, первые входы которых подключены к выходам соответственно первого и второго элементов ИЛИ, а вторые входы - к выходам соответственна третьего и четвертого элементов ИЛИ, первые входы соответствующих. элемен25 тов И второй и третьей групп объединены и подключены к соответствующим выходам выходного регистра, вторые входы элементов И второй и третьей групп объединены и подключены к выхо-.

ЗО ду пятого элемента ItJIH вторая груп9&1991 па входов сумматора по модулю P подключена к выходам соответствующих элементов И второй группы, группы выходов элементов И третьей группы является выходом устройства. В этом устройстве используются свойства сим- 5 метрии арифметической таблицы. Ири этом реализация операции модульного умножения осуществляется посредством п коммутаторов, реализующих ответы по каждому из п разрядов результа- 10 та (1) .

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

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

Как принято, в схеме модульного умножения используются свойства симметрии арифметической таблицы относительно- левой и правой диагоналей, вертикали и горизонтали, проходящих между числами Р-3/2, и Р+1(2, где P модуль таблицы. Это и определяет воз-З5 можность реализации в схеме табличного умножения только 0,25 части таблицы коммутатора. Операция модульного умножения выполняется в коде табличного умножения. 40

Алгоритм получения результата операции модульного умножения определяется так: если два числа A и В заданы по основанию Р в коде табличного умножения А = (g,à), В = (@, В) 145 то для того, чтобы получить произведение этих чисел по модулю достаточно получить произведение 0 и (moodP) в коде табличного умножения и инвертировать его индекс g в слу- 50 чае, если gö отлично от / р, где

О, если 0 (а « — М Р+1

1, если - — с ааР 55если с ф / р

Г= у, если 60

В прототипе в качестве коммутатора, определяющего результат операции модульного умножения, используется не единая таблица, а и более мелких таблиц, реализующих ответы по каждому 65 из и разрядов коммутатора, где иколичество двоичных раз рядов в записи операндов A и В, т.е. п > log>P.

Результат операции представляется двоичным кодом.

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

На чертеже представлена блок-схема устройства.

На схеме обозначено первый и второй входные регистры 1,дешифраторы 2, первая и вторая группы элементов ИЛИ

3 и 4, первая и вторая группа ключей

5 и 6, группа коммутаторов 7, выходной регистр 8, первая, вторая и третья группы элементов И 9-11, первый, второй, третий, четвертый и пятый элемены ИЛИ 12-16, первый и второй элементы И, 17 и 18, сумматор пО модулю Р 19, третья группа элементов

ИЛИ 20.

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

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

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

Случай, когда с = . Входные операнды A и В,представленные в двоичном коде, поступают в входные регистры 1. Через соответствующие дешифраторы 2 эти операнды в унитарном коде поступают на соответствующие элементы первой и второй групп

ИЛИ 3 и 4. Сигнал по управляющему входу открывает ключи групп 5 и 6, и операнды одновременно поступают на входы всех коммутаторов 7 ° В тех коммутаторах 7, где определены значения разрядов результата для данных операндов A и В (единицы в узлах таблиц), на входной шине (выходе коммутатора), подключенной к соответствующему разряду выходного регистра

8, появляется сигнал. Этот сигнал переводит соответствующий разряд выходного регистра 8 в единичное состояние (выходной сигнал К-го коммутатора 7 переводит к единичное состояние К-й разряд регистра 8). Одновременно сигналы с выходов дешифраторов .2 поступают на два из четырех элемен981991 тов ИЛИ 12-15 такиы образом, .что элементы И 17 и 18 закрыты, и выходной управляющий сигнал элемента ИЛИ 16 отсутствует (так как при fa = gp = О, задействованы первый и третий элементы ИЛИ 12 и 14, а при g> = = 1 вто5 рой и четвертый элементы KHH 13 и 15).

Таким образом, в выходном регистре

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

Это значение через открытые элементы

И третьей группы 11 поступают на выход устройства.

Случай, когда п Ф gg. Как и в первом случае (а) в регистр 8 из ковмутаторов 7 поступает операнд (результат операции) в двоичном коде. Но теперь на выходе элемента ИЛИ 16 присутствует управляющий сигнал (для

It =1, f p = 0 задействованы второй и четвертый элементы ИЛИ 13 и 15, от- 2ц крывающие первый элемент И 17, а для go = 0 н gp,=- 1, задействованы первый н четвертый элементы ИЛИ 12 и 14, т.е. открыт второй элемент

И 18). Выходной сигнал пятого эле- Я5 мента NIH 16 открывает элементы И первой и второй групп 9 и 10 и закрывает элементы 11. При этом на первую группу входов сумматора по модулю P 19, через элементы И пер- Зп вой группы 9 поступает константа Р в двоичном коде, а на вторую группу входов сумматора по модулю Р 19,через элементы И второй группы 10 поступает ссщержнмое регистра 8..С выхода сумматора 19 через элементы

HJIH третьей группы 20 на выход устройства поступает содержимое регистра 8. Это и будет являться результатом операции модульного умножения.

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

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

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

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР

896620, кл. G 06 F 7/72, 1982 (прототип).