Пристрій для піднесення чисел до квадрата за модулем m модулярної системи числення

Пристрій для піднесення чисел до квадрата за модулем m модулярної системи числення (МСЧ), що містить вхідний і вихідний регістри, дешифра 2 3 51512 Тобто, маємо, що A2 (mod m). Розглянемо вираз (3) (m - A)2 m2 - 2 m A A 2. Підставимо вираз (2) в вираз (3), та отримаємо (m - A)2 m2 - 2 m A A2 m2 - 2 m A k m m (m - 2 A k) . Маємо, що (m фратора 5, вихід якого підключено до входу вихідного регістра 6, вихід 7 якого є вихід пристрою, а нульовий вихід дешифратора 3 підключено до нульового входу шифратора 5. Пристрій працює наступним чином. Через вхід 1 на регістр 2 поступає число A(0 A m 1) в двійковому коді. Дешифратор 3 перетворює число А в унітарний код, сигнал якого через відповідний елемент АБО 4 поступає на відповідний вхід шифратора 5. Номери входів шифратора 5 відповідають значенням: 0, 1, 22 (mod m), 32 (mod m), A ) 2 mod m [m (m 2 A 4 k) ] mod m , (m A )2 (mod m) . Таким чином виконується рівність (1). Використовуючи властивість (1) МСЧ, необхідно в пристрої об'єднати вихідні шини дешифратора таким чином, щоб сума чисел, що надана кожній із пар виходів дорівнювала значенню модуля m МСЧ. На Фіг. приведена блок-схема запропонованого пристрою, де: 1 - вхід пристрою; 2 - вхідний регістр; 3 - дешифратор (пристрій для перетворення числа А з двійкового коду в унітарний); 4 - двоходові елементи АБО; 5 - шифратор (пристрій для перетворення унітарного коду числа в двійковий); 6 - вихідний регістр; 7 - вихід пристрою. Вхід 1 пристрою підключено до входу вхідного регістра 2, вихід якого підключено до входу дешифратора 3. виходи шифратора 3 попарно підключено до входів відповідних елементів АБО 4 групи, виходи яких підключено до відповідних входів ши 42 (mod m),..., m 2 2 (mod m). З виходу шифратора 5 результат операції A 2 (mod m) в двійковому коді через регістр 6 поступає на вихід 7 пристрою. Розглянемо приклади конкретного виконання пристроєм операції для A 2 (mod 11) A 9 (A 1001). На вхід 1 поступає число A 1001 . З виходу регістра 2 число A 1001 поступає на вхід дешифратора 3. У відповідності з таблицею 1, реалізації операції A(mod 11) , вихідний сигнал дешифратора 3 (який відповідає в унітарному коді числу дев'ять (A 1001)) по другій ( A 9) шині другої пари (9+2=11) шин поступає на вхід другого елемента АБО 4. Таблиця Реалізація операції A2 (mod 11) Номер пари вихідних шин дешифратора 3 0 1 2 3 4 5 Значення, що призначають Значення, що призна- Значення, що призначаютьпарі вихідних шин дешиф- чаються вхідним шинам ся вихідним шинам шифраратора 3 шифратора 5 тора 5 0 0 0000 1,10 1 0001 2,9 4 0100 3,8 9 1001 4,7 5 0101 5,6 3 0011 З виходу другого (2+9=11) елемента АБО 4 сигнал, що відповідає значенню чотири (22 (mod 11 92 (mod 11) 4)) (2 поступає на четвертий вхід шифратора 5, який перетворює унітар ний код чотири (92 (mod 11 4) в двійковий 0100, який через регістр 6 поступає на вихід 7 пристрою. Перевірка: (92 4(mod 11) . Нехай А=0 (А = 0000). Через вхід 1 на регістр 2 поступає число А = 0000. З нульового виходу шифратора 3 сигнал, що відповідає значенню А=0000, поступає на нульовий вхід шифратора 5. Таким чином, на виході 7 пристрою буде значення 0000. Таким чином запропонований винахід дозволяє значно зменшити кількість обладнання пристрою для піднесення чисел в квадрат за модулем m модулярної системи числення за рахунок використання слідуючої властивості МСЧ A 2 (mod m) (m A )2 mod m , при збереженні всіх технічних характеристик пристрою. При цьому зменшується час виконання арифметичних операцій. 5 Комп’ютерна верстка Н. Лиcенко 51512 6 Підписне Тираж 26 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601