Устройство для вычисления квадратических остатков по модулю n+1
Изобретение относится к вычислительной технике и может быть использовано в специализированных системах для сопряжения вычислительных устройств, функционирующих в квадратической системе остаточных классов. Целью изобретения является повышение быстродействия устройства. Преимущество устройства достигается за счет введения преобразователей 3, 4 прямого кода в дополнительный и регистров 7, 8 хранения промежуточного результата, что позволяет увеличить быстродействие почти в 2 раза устройства, содержащего входные регистры 1, 2, сумматоры 5, 6, 10 по модулю 2n+1, умножитель 9 по модулю 2n+1 и вычитатель 11 по модулю 2n+1 . 1 ил.
Изобретение относится к вычислительной технике и может быть использовано для сопряжения вычислительных устройств, функционирующих в квадратичной системе остаточных классов (СОК).
Целью изобретения является повышение быстродействия вычислительного процесса. В основу работы устройства положено следующее. Двоичное k-разрядное число Х может быть разделено на l групп по n разрядов, где n - четное и равно степени Pk = 2n + 1. Тогда число Х по модулю может быть представлено x= ao+a+a2+ . . . + a (1) где ao, a1, . . . , al - группы по n разрядов; ao-n-младших разрядов числа Х и т. д. Кодопреобразователь преобразует n разрядов так, чтобы на его выходе была реализована функция дополнения числа до нужного модуля, т. е. a= Pk-ai-1 (2) где i = 2, 4, 6, 8, . . . l 1, ai-1 - n-разрядов числа Х Квадратически СОК представляется в виде wi= xi+riyPk; w*i= xi-riyPk, (3) где ri2 = -1 mod Pk, что выполнимо только при P = 4n + 1, Pk = 2n + 1, если n четное, то Pk = 22 (2n-2) + 1 = 4 (2n-2) + 1 (4) условие выполняется. Таким образом, с помощью выражений (1), (2) возможна реализация выражений (3), (4), т. е. преобразование комплексного числа в квадратическую СОК. На чертеже приведена схема устройства для вычисления квадратических остатков. Устройство содержит входные регистры 1, 2, преобразователи 3, 4 прямого кода в дополнительный, сумматоры 5, 6, 10 по модулю 2n+1, регистры 7, 8 хранения промежуточных результатов, умножитель 9 по модулю 2n+1, вычитатель 11 по модулю 2n+1, выходы 12, 13 устройства, первый и второй тактовые входы 14.1 и 14.2 устройства. Устройство работает следующим образом. В исходном состоянии в регистре 1 находится код преобразуемого числа Х, в регистре 2 - код преобразуемого числа Y, регистра 7, 8 обнулены. На первом такте преобразователя число ао, определяемое n младшими разрядами преобразуемых чисел Х, Y, поступает на сумматоры 6, 5 по модулю 2n+1, число а1, определяемое n вторыми разрядами чисел Х, Y, подается на преобразователи 3, 4 прямого кода в дополнительный. С выхода преобразователей 3, 4 прямого кода в дополнительный подается на вторые входы сумматоров 5, 6 по модулю 2n+1 код дополнения числа до модуля Pk. По окончании переходных процессов на выходе сумматора 5 x= ao+a, на входе сумматора 6 y= ao+a. Результат суммирования записывается в момент поступления импульса по входу 14.2 в регистры 7, 8. На втором такте преобразования в момент поступления импульса по входу 14.1 содержимое регистров 1, 2 сдвигается на 2n разрядов вверх и цикл повторяется с добавлением результата предыдущего суммирования, подаваемого с регистров 7, 8. Когда преобразование произведено, то производится умножение | Y| Pk+на ri в умножителе 9, и сумматор 10 выполняет операцию xi+r iy, а вычитатель 11 - операциюxi-r iy. Окончательные результаты снимают с выходов сумматора 10 и вычитателя 11.
Формула изобретения
РИСУНКИ
Рисунок 1