устройство для вычисления квадратических остатков по модулю ⁿ+1

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

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КВАДРАТИЧЕСКИХ ОСТАТКОВ ПО МОДУЛЮ 2ⁿ+1, содержащее два входных регистра, три сумматора по модулю 2ⁿ + 1, умножитель по модулю 2ⁿ + 1, вычитатель по модулю 2ⁿ + 1 причем входы разрешения сдвига первого и второго входных регистров соединены с первым тактовым входом устройства, выходы n младших разрядов первого и второго входных регистров соединены с входами первого слагаемого первого и второго сумматоров по модулю 2ⁿ + 1 соответственно, выходы умножителя по модулю 2ⁿ + 1 соединены с входами первого слагаемого третьего сумматора по модулю 2ⁿ + 1 и вычитаемого вычитателя по модулю 2ⁿ + 1, выходы которых являются выходами устройства, отличающееся тем, что, с целью повышения быстродействия, устройство содержит два преобразователя прямого кода в дополнительный и два регистра хранения промежуточных результатов, причем выходы разрядов с (n + 1)-го по 2n первого и второго входных регистров соединены с входами первого и второго преобразователей прямого кода в дополнительный, выходы которых соединены с входами второго слагаемого первого и второго сумматоров по модулю 2ⁿ + 1 соответственно, выходы которых соединены с информационными входами первого и второго регистров хранения промежуточных результатов соответственно, выходы которых соединены с входами третьего слагаемого первого и второго сумматоров по модулю 2ⁿ + 1 соответственно, выход первого регистра хранения промежуточных результатов соединен с входом второго слагаемого третьего сумматора по модулю 2ⁿ + 1 и входом уменьшаемого вычитателя по модулю 2ⁿ + 1, выход второго регистра промежуточных результатов соединен с входом умножителя по модулю 2ⁿ + 1, второй тактовый вход устройства соединен с входами разрешения записи первого и второго регистров хранения промежуточных результатов.

Описание изобретения к патенту

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

Целью изобретения является повышение быстродействия вычислительного процесса.

В основу работы устройства положено следующее.

Двоичное k-разрядное число Х может быть разделено на l групп по n разрядов, где n - четное и равно степени P_k = 2ⁿ + 1. Тогда число Х по модулю может быть представлено

x= a_o+a+a₂+ . . . + a (1) где a_o, a₁, . . . , a_l - группы по n разрядов;

a_o-n-младших разрядов числа Х и т. д.

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

a= P_k-a_i-1 (2)

где i = 2, 4, 6, 8, . . . l 1, a_i-1 - n-разрядов числа Х

Квадратически СОК представляется в виде

w_i= x_i+r_iyP_k;

w^*_i= x_i-r_iyP_k, (3) где r_i² = -1 mod P_k, что выполнимо только при P = 4n + 1, P_k = 2ⁿ + 1, если n четное, то P_k = 2² (2^n-2) + 1 = 4 (2^n-2) + 1 (4) условие выполняется.

Таким образом, с помощью выражений (1), (2) возможна реализация выражений (3), (4), т. е. преобразование комплексного числа в квадратическую СОК.

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

Устройство содержит входные регистры 1, 2, преобразователи 3, 4 прямого кода в дополнительный, сумматоры 5, 6, 10 по модулю 2ⁿ+1, регистры 7, 8 хранения промежуточных результатов, умножитель 9 по модулю 2ⁿ+1, вычитатель 11 по модулю 2ⁿ+1, выходы 12, 13 устройства, первый и второй тактовые входы 14.1 и 14.2 устройства.

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

В исходном состоянии в регистре 1 находится код преобразуемого числа Х, в регистре 2 - код преобразуемого числа Y, регистра 7, 8 обнулены.

На первом такте преобразователя число а_о, определяемое n младшими разрядами преобразуемых чисел Х, Y, поступает на сумматоры 6, 5 по модулю 2ⁿ+1, число а₁, определяемое n вторыми разрядами чисел Х, Y, подается на преобразователи 3, 4 прямого кода в дополнительный. С выхода преобразователей 3, 4 прямого кода в дополнительный подается на вторые входы сумматоров 5, 6 по модулю 2ⁿ+1 код дополнения числа до модуля P_k. По окончании переходных процессов на выходе сумматора 5

x= a_o+a, на входе сумматора 6

y= a_o+a.

Результат суммирования записывается в момент поступления импульса по входу 14.2 в регистры 7, 8.

На втором такте преобразования в момент поступления импульса по входу 14.1 содержимое регистров 1, 2 сдвигается на 2n разрядов вверх и цикл повторяется с добавлением результата предыдущего суммирования, подаваемого с регистров 7, 8.

Когда преобразование произведено, то производится умножение | Y| _Pk⁺на r_i в умножителе 9, и сумматор 10 выполняет операцию

x_i+r _iy, а вычитатель 11 - операцию

x_i-r _iy.

Окончательные результаты снимают с выходов сумматора 10 и вычитателя 11.