Устройство для формирования остатка по произвольному модулю от числа

Устройство для формирования остатка по произвольному модулю от числа

Иллюстрации

Показать все

Реферат

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

Известно устройство для формирования остатка по произвольному модулю от числа, содержащее первый и второй регистр, первый и второй элементы ИЛИ, вычислитель, первую схему сравнения и мультиплексор (Авторское свидетельство СССР N 1633495, кл. H03M 7/18, 1989).

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

Наиболее близким к предлагаемому по технической сущности и достигаемому результату является устройство для формирования остатка по произвольному модулю от числа, содержащее первый регистр, информационные входы которого являются входами кода числа, последовательно соединенные блок постоянной памяти, группу блоков элементов И, блок сумматоров по произвольному модулю и второй регистр, а также элемент задержки и блок инверторов (см. патент РФ №2007033, кл. H03M 7/18, 1994.01.30).

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

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

Для достижения поставленной цели в устройство для формирования остатка по произвольному модулю от числа, содержащее первый и второй регистры, группу блоков элементов И, блок сумматоров по модулю и элемент задержки, причем вход числа соединен с информационными входами первого регистра, выходы которого соединены соответственно с первыми входами группы блоков элементов группы И, выходы которой соединены с первыми входами блока сумматоров по модулю, вход элемента задержки является входом начала вычислений и соединен со входом записи первого регистра, выход второго регистра является выходом устройства, вход модуля соединен со вторыми входами блока сумматоров по модулю, выход блока задержки соединен с выходом окончания работы устройства и входом записи второго регистра, информационные входы которого соединены с выходами блока сумматоров по модулю, введен блок формирования частичных остатков, на первый информационный вход которого подается код модуля, на второй информационный вход подается код числа «1», а информационные выходы соединены со вторыми входами группы блоков элементов И, при этом блок формирования частичных остатков содержит (К-1) сумматоров по модулю, причем первые информационные входы всех сумматоров по модулю соединены с первым информационным входом блока формирования частичных остатков, второй информационный вход блока формирования частичных остатков является его первым информационным выходом и со сдвигом на один разряд в сторону старших соединен со вторым информационным входом первого сумматора по модулю, выход i-го сумматора по модулю является i+1 информационным выходом блока формирования частичных остатков и со сдвигом на один разряд в сторону старших соединен со вторым информационным входом i+1 сумматора по модулю, где i=1, …, K-2, выход К-1 сумматора по модулю является К-ым информационным выходом блока формирования частичных остатков.

Сущность изобретения состоит в реализации следующей идеи приведения чисел по произвольному модулю. Известно, что позиционные системы счисления строятся по следующему принципу. Выбирается некоторое число m - основание системы счисления. Целое число А в m-ичной системе счисления представляется в виде конечной линейной комбинации степеней числа m:

где k - разрядность представляемого числа, a_i - это целые числа, удовлетворяющие неравенству 0≤a_i≤m-1. Для двоичной системы счисления выражение (1) принимает вид:

где a_i принимает значение 0 или 1.

Известно также, что сравнения можно почленно складывать, т.е.:

A₁≡B₁(modP), A₂≡B₂(modP)...(A_k≡B_k(modP).

Тогда справедливо следующее выражение:

Учитывая выражения (2) и (3), можно записать:

Так как для двоичной системы счисления коэффициенты a_i, i=0, …k-1, где k - разрядность представляемого числа А, принимают только два значения 0 и 1, то суммируя заранее вычисленные остатки по модулю Р от чисел 2ⁱ, i=0, … k-1, для тех i, для которых коэффициенты a_i=1, получают остаток по модулю Р от числа А.

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

Устройство для формирования остатка по произвольному модулю от числа содержит (фиг.1) первый регистр 1, блок 2 формирования частичных остатков, группу 3 блоков элементов И, блок 4 сумматоров по модулю, второй регистр 5, элемент 6 задержки. Вход 7 служит для подачи кода числа А, вход 8 служит для подачи кода модуля Р. Вход 9 - вход начала вычисления. Выход 11 - выход конца вычисления. Выход 10 является информационным выходом устройства.

Блок 2 формирования частичных остатков содержит (фиг.2) К-1 сумматоров 14 по модулю. Вход 12 служит для подачи кода модуля Р, выходы 13.1-13.К являются выходами частичных остатков модуля Р. На второй информационный вход блока 2 формирования частичных остатков подается код числа «1».

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

В исходном состоянии регистры 1 и 5 обнулены. На вход 7 подается код числа А. На управляющий вход 9 подается сигнал начала вычислений. Под воздействием сигнала начала вычислений в регистр 1 записывается код числа А. На вход 8 подается код модуля Р и блок 2 формирования частичных остатков формирует частичные остатки от чисел 2ⁱ по модулю Р, которые подаются на вторые информационные входы группы блоков 3 элементов «И». Поразрядно в блоке 3 элементов И умножаются частичные остатки модуля Р и разряды числа А, поступающие на первые входы блока. В блоке 4 сумматоров по модулю результаты умножения складываются и снова вычисляются по модулю Р. Результат поступает на вход регистра 5, выход которого является информационным выходом устройства для формирования остатка по произвольному модулю от числа. Под воздействием импульса, поступающего с выхода элемента задержки 6, рассчитанного на задержку, равную времени формирования остатка, в регистр 5 происходит запись результата, который в результате этого появляется на выходе устройства. Импульс с выхода элемента задержки 6 поступает также на выход 11 устройства, свидетельствуя об окончании процесса формирования остатка.

Блок 2 формирования частичных остатков работает следующим образом (см. фиг.2). На первый вход первого сумматора 14 по модулю и на выход 13.0 поступает логическая единица. На вторые входы всех сумматоров 14 по модулю подается код модуля. Результат вычислений с выхода сумматора 14 по модулю поступает на соответствующий выход блока 13.i, где i=1…K-1, а также со сдвигом на один разряд в сторону старшего поступает на первый вход следующего по схеме сумматора 14 по модулю. Каждый сумматор 14 по модулю сравнивает модуль и поступающее число. Если модуль больше числа, то на выход сумматора 14 по модулю подается число, иначе - разность модуля и числа.

Рассмотрим работу устройства для формирования частичных остатков на примере. Зададим начальные условия. A=29₁₀=11101₂, модуль Р=13₁₀=1101₂

Коэффициент 2i	20	21	22	23	24
2i (modl3)	1	2	4	8	3
Код числа А	1	0	1	1	1
Результат логической операции «И»	1	0	4	8	3
Суммирование		16
Сумма по mod 13		3

Проверим: 29≡3 mod 13.

Эффективность заявляемого устройства перед устройством-прототипом заключается в существенном уменьшении объема оборудования при формировании остатков. Расчеты показывают, что если проводить вычисления с 64-разрядными числами, то устройство-прототип должно иметь блок постоянной памяти для хранения k*l частичных остатков, где k=64 количество разрядов числа, l=2⁶⁴ количество модулей, то есть объем блока постоянной памяти составит k*l=64*2⁶⁴=2⁷⁰ ячеек. В заявляемом устройстве при тех же исходных данных вырабатывается k частичных остатков, т.е. объем оборудования составляет 64=2⁶ сумматоров, т.к. частичные остатки вычисляются в процессе формирования остатка для одного определенно заданного модуля.

Устройство для формирования остатка по произвольному модулю от числа, содержащее первый и второй регистры, группу блоков элементов «И», блок сумматоров по модулю и элемент задержки, причем вход числа соединен с информационными входами первого регистра, выходы которого соединены соответственно с первыми входами группы блоков элементов «И», выходы которой соединены с первыми входами блока сумматоров по модулю, вход элемента задержки является входом начала вычислений и соединен со входом записи первого регистра, выход второго регистра является выходом устройства, вход кода модуля соединен со вторыми входами блока сумматоров по модулю, выход элемента задержки соединен с выходом окончания работы устройства и входом записи второго регистра, разрядные входы которого соединены с выходами блока сумматоров по модулю, отличающееся тем, что в него введены (К-1) сумматоров по модулю, на вторые информационные входы которых подается код модуля, на первый информационный вход первого сумматора по модулю и на второй информационный вход группы блоков элементов «И» подается код числа «1», выход i-го сумматора по модулю соединен со вторым информационным входом группы блоков элементов «И» и со сдвигом на один разряд в сторону старших с первым информационным входом i+1 сумматора по модулю, где i=1, …, K-2, выход К-1 сумматора по модулю соединен со вторым информационным входом группы блоков элементов «И».