УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КВАДРАТИЧЕСКИХ ОСТАТКОВ ПО МОДУЛЮ Российский патент 1994 года по МПК H03M7/18 

Описание патента на изобретение RU2020757C1

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

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

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

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

Это выражение возможно в том случае, если ri2 = -1modPi (1). Выражение (1) возможно только для модуля Р = 4n + 1, тогда Р можно представить как Р = 2n + 1, где n - четное. Найти остаток по модулю Р = 2n + 1 можно следующим образом:
... ak2kn;
Так как ri2 = -1modPi и 2n = -1mod P, то =ri, тогда ri = 2n/2, так как n - четное, то и 2n/2 - четное и кратно двум, умножение на ri равно умножению на 2n/2 и соответствует сдвигу числа. Таким образом возможно наложение квадратических остатков без умножения.

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

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

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

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

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

Первый такт поступает на вход 9.3, что соответствует сдвигу и умножению на 2n/2, затем начинается преобразование. По второму такту сдвиг производится в обратном направлении, и число преобразуется, начиная с младших разрядов и по окончании переходных процессов на выходах суммато- ров 3, 4: a
По третьему такту a0-a , где а01 - n младших разрядов чисел х и riy и т.д. По окончании нахождения остатков на выходах сумматоров 3, 4 получают
x и riy
Тогда на выходах 7 и 8 устройства получают результат
x+riy и x-riy

Похожие патенты RU2020757C1

название год авторы номер документа
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КВАДРАТИЧЕСКИХ ОСТАТКОВ ПО МОДУЛЮ 2+1 1991
  • Оленев Александр Анатольевич
RU2012136C1
УСТРОЙСТВО ДЛЯ ПРЕОБРАЗОВАНИЯ ЧИСЛА В КВАДРАТИЧЕСКИЕ ОСТАТКИ 1992
  • Оленев Александр Анатольевич
  • Червяков Николай Иванович
  • Горлачев Игорь Викторович
  • Федорцов Сергей Владимирович
RU2029436C1
Устройство для вычисления остатка по модулю 2 @ +1 1990
  • Червяков Николай Иванович
  • Оленев Александр Анатольевич
SU1734212A1
Арифметико-логическое устройство для умножения чисел по модулю 2017
  • Петренко Вячеслав Иванович
  • Свистунов Николай Юрьевич
  • Стручков Игорь Владиславович
RU2653263C1
УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ПОЗИЦИОННЫХ ХАРАКТЕРИСТИК НЕПОЗИЦИОННОГО КОДА 1991
  • Червяков Н.И.
  • Ремизов С.Л.
RU2020756C1
АРИФМЕТИКО-ЛОГИЧЕСКОЕ УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ, ВЫЧИТАНИЯ И УМНОЖЕНИЯ ЧИСЕЛ ПО МОДУЛЮ 2019
  • Петренко Вячеслав Иванович
  • Тебуева Фариза Биляловна
  • Свистунов Николай Юрьевич
RU2711051C1
Устройство для умножения чисел по произвольному модулю 2020
  • Петренко Вячеслав Иванович
RU2755734C1
УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ ОТ ЧИСЛА 1990
  • Петренко Вячеслав Иванович
  • Чипига Александр Федорович
RU2029434C1
Устройство для умножения чисел 1990
  • Бобровский Алексей Иванович
  • Прохорович Андрей Михайлович
SU1714595A1
АРИФМЕТИЧЕСКИЙ ВЫЧИСЛИТЕЛЬ 2004
  • Шевелев Сергей Степанович
RU2292580C2

Иллюстрации к изобретению RU 2 020 757 C1

Реферат патента 1994 года УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КВАДРАТИЧЕСКИХ ОСТАТКОВ ПО МОДУЛЮ

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

Формула изобретения RU 2 020 757 C1

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

Документы, цитированные в отчете о поиске Патент 1994 года RU2020757C1

IEEE Transactions on Computers, vol
Скоропечатный станок для печатания со стеклянных пластинок 1922
  • Дикушин В.И.
  • Левенц М.А.
SU35A1

RU 2 020 757 C1

Авторы

Оленев А.А.

Червяков Н.И.

Даты

1994-09-30Публикация

1991-04-30Подача