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

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

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

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

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

Целью изобретения является сокращение аппаратурных затрат.

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

В квадратическую систему остатков число переводится следующим образом:



Это выражение возможно в том случае, если r_i² = -1modP_i (1). Выражение (1) возможно только для модуля Р = 4n + 1, тогда Р можно представить как Р = 2ⁿ + 1, где n - четное. Найти остаток по модулю Р = 2ⁿ + 1 можно следующим образом:

... a_k2^kn;

Так как r_i² = -1modP_i и 2ⁿ = -1mod P, то =r_i, тогда r_i = 2^n/2, так как n - четное, то и 2^n/2 - четное и кратно двум, умножение на r_i равно умножению на 2^n/2 и соответствует сдвигу числа. Таким образом возможно наложение квадратических остатков без умножения.

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

Устройство содержит два входных сумматора 1, 2, накапливающие бистабильные сумматоры 3, 4 по модулю, сумматор 5 по модулю, вычитатель 6 по модулю, выходы 7, 8 устройства, группу тактовых входов 9.1-9.5 устройства.

Входные сумматоры 1, 2 функционально известные устройства. Входной регистр 2 имеет разрядов на 2^n/2 больше регистра 1, что дает возможность производить сдвиг на 2^n/2, что соответствует умножению на r_i. Накапливающие бистабильные сумматоры 3, 4 функционально известные элементы. Это сумматоры, в первый момент производящие сложение, а во второй момент - вычитание, с одновременным накапливанием результата.

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

В исходном состоянии преобразуемое число х + jy, где х - находится во входном регистре 1, а y - во втором регистре 2, накапливающие бистабильные сумматоры обнулены. Устройство готово к работе.

Первый такт поступает на вход 9.3, что соответствует сдвигу и умножению на 2^n/2, затем начинается преобразование. По второму такту сдвиг производится в обратном направлении, и число преобразуется, начиная с младших разрядов и по окончании переходных процессов на выходах суммато- ров 3, 4: a

По третьему такту a₀-a , где а₀,а₁ - n младших разрядов чисел х и r_iy и т.д. По окончании нахождения остатков на выходах сумматоров 3, 4 получают

x и r_iy

Тогда на выходах 7 и 8 устройства получают результат

x+r_iy и x-r_iy