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

Пристрій для піднесення чисел до квадрата за модулем m класу лишків (КЛ), що містить вхідний і вихідний регістри, дешифратор, шифратор, групу m  m  із   -го елементів АБО (де   - ціла частина 2 2 2 3 61798 Мета корисної моделі - спрощення конструкції пристрою за рахунок зменшення кількості обладнання. Поставлена мета вирішується за рахунок того, що у пристрій для піднесення чисел до квадрата за модулем m класу лишків (КЛ), що містить вхідний і вихідний регістри, дешифратор, шифратор, m  m  групу із   -го елементів АБО (де   - ціла 2 2 m , його не більша), при цьому вхід 2 пристрою підключено до входу вхідного регістра, виходи дешифратора попарно (сума чисел, що надана кожній із пар виходів дорівнює значенню модуля m КЛ) підключено до входів відповідних елементів АБО групи, при цьому виходи елементів АБО групи підключено до входів шифратора, вихід якого підключено до входу вихідного регістра, вихід якого є виходом пристрою, а нульовий вихід дешифратора безпосередньо підключено до нульового входу шифратора, згідно корисної моделі, введено перетворювач коду (ПК), до входів якого підключено вихід вхідного регістра, а вихід ПК підключено до входів дешифратора. Технічний результат, який може бути отриманий при використанні запропонованої корисної моделі, полягає в реалізації операції піднесення чисел до квадрата за модулем m КЛ. При цьому суттєво зменшується кількість обладнання пристрою за рахунок використання слідуючої властивості КЛ: частина числа 2 2 (A') (modm) = (m-A') modm. (1) Покажемо це. Нехай А' - число, що треба піднести до квадрата за модулем m і нехай '2  k  m  0    m (2) Тобто, маємо, що 2 (A') =  (mod m). Розглянемо вираз 2 2 . . (m-А') = m -2 m А' + (А') 2 (3) Підставимо вираз (2) в вираз (3), та отримаємо 2 2 . . 2 2 . . . (m-А') = m -2 m А' + (А') =m -2 m А' + k m+ . . +  = m (m-2 А' + k) +  . 2 . . Маємо, що (m-A') mod m = [m (m-2 A' + k) + 2 +  ]mod m =  , тобто (m-А’) =  (mod m). Таким чином виконується рівність (1). При цьому число А' представляється (штучна форма) у вигляді А' = А+ +m/2 для m парного або А' = А + (m-1)/2 - для m непарного ( 0  '  m  1), також як вхідне число А (-(m-1)/2 А+(m + 1)/2), у двійковому коді. На основі (1) у пристрої-найближчому аналозі об'єднуються вихідні шини дешифратора таким чином, щоб сума чисел, що надана кожній із пар виходів дорівнювала значенню модуля m КЛ. Однак використання у найближчому аналозі співвідношення (1) потребує додаткової кількості обладнання: груп елементів І, суматора за модулем m, групи елементів АБО. 4 З метою скорочення обладнання найближчого аналога розглянемо наступні співвідношення 2 2 2 2 (А') = (m-А') =  (mod m) та А = (m - А) = =  (mod m/2), 2 2 або А = (m-А) =  mod [(m-1)/2]. Нехай m - парне. Тоді з урахуванням, що А' = А + m/2 маємо 2 2 2 . .  = (m-А) =[m-(А'-m/2)] =[m -2 m (A'-m/2) + 2 2 . . 2 . . 2 +(A'-m/2) ] = m -2 m (А'-m/2) + (А') -2 А' m/2 + m /4, Тоді отримуємо, що 2 . . . . 2 2 [m -2 m (А'-m/2)-2 А' m/2 + m /4 + (А') ] = 2 =(А') mod m/2. (4) Співвідношення (4) використовується у запропонованій корисній моделі для реалізації операції піднесення чисел до квадрата за модулем m КЛ. На фіг. приведена блок-схема запропонованого пристрою, де: 1 - вхід пристрою; 2 - вхідний регістр; 3 - перетворювач коду - ПК (пристрій для перетворення числа А, що може знаходитися як у додатному, так і в від'ємному числових діапазонах, у число А' = А + m/2 (штучна форма) для m парного та А' = А + (m-1)/2 для m непарного, що знаходиться тільки у додатному числовому діапазоні); 4 - дешифратор (пристрій для перетворення числа А з двійкового коду в унітарний); 5 - двоходові елементи АБО; 6 -шифратор (пристрій для перетворення унітарного коду числа в двійковий); 7 - вихідний регістр; 8 - вихід пристрою. Вхід 1 пристрою підключено до входу вхідного регістра 2, вихід якого підключено до входу перетворювача коду 3, вихід якого підключено до входу дешифратора 4. Виходи шифратора 4 попарно підключено до входів відповідних елементів АБО 5 групи, виходи яких підключено до відповідних входів шифратора 6, вихід якого підключено до входу вихідного регістра 7, вихід 8 якого є вихід пристрою. Нульовий вихід дешифратора 4 безпосередньо підключено до нульового входу шифратора 6. Пристрій працює наступним чином. Через вхід 1 на регістр 2 поступає число А (-(m-1)/2 А+(m + 1)/2) в двійковому коді. Перетворювач коду 3 перетворює число А у число А' = А + m/2 для m парного або А' = А + (m-1)/2 для m непарного (0А'm-1). Дешифратор 4 перетворює число А' в унітарний код, сигнал якого через відповідний елемент АБО 5 поступає на відповідний вхід шифратора 6. Номери входів шифратора 6 відповідають значенням: 2 2 2 0, 1, 2 (mod m), 3 (mod m), 4 (mod m), ..., 2  m       (mod m), для m - парного, або  2    2 2 2 0, 1, 2 (mod m), 3 (mod m), 4 (mod m), ..., 2   m  1     2   (mod m), для m - непарного.   З виходу шифратора 6 результат операції 2 2 A mod(m/2) або A mod[(m-1)/2] в двійковому коді через регістр 7 поступає на вихід 8 пристрою. 5 61798 Розглянемо приклади конкретного виконання 2 пристроєм операції A (mod5) для m=11 (див. табл. 1, 2), тобто (m-1)/2 = 5. Приклад 1. Нехай А= - 3 (- 011). До входу 1 поступає число А= -011. З виходу регістра 2 число А поступає до входу ПК 3. У відповідності з таблицею 1, з виходу ПК 3 значення А' = А + (m-1)/2 = 010 поступає до входу дешифратора 4. Вихідний сигнал дешифратора 4 (який відповідає в унітарному коді числу А'= 2 (табл. 2) по другій шині другої пари шин поступає до входу другого елемента АБО 5. З виходу другого елемента АБО 5 сигнал, 2 що відповідає значенню чотири (2 (mod 11 = 4)) поступає до четвертого входу шифратора 6, який перетворює унітарний код чотири в двійковий 100, який через регістр 7 поступає до виходу 8 при 6 строю. Перевірка. У відповідності з формулою (4) 2 2 маємо: А = (-3) =9 = 4 (mod 5). Таким чином, запропонована корисна модель дозволяє значно спростити конструкцію за рахунок зменшення кількості обладнання пристрою для піднесення чисел до квадрата за модулем m КЛ (як у позитивному, так і у від'ємному числових діапазонах) за рахунок використання співвідношення (4). При цьому скорочується: дві групи елементів І, суматор за модулем m, одна група елементів АБО при збереженні всіх технічних характеристик пристрою. Необхідно відзначити простоту реалізації в пристрої логічних елементів АБО, шифратора, дешифратора, перетворювача коду та можливість їх уніфікації для довільного модуля m КЛ. Таблиця 1 Пристрій для піднесення чисел до квадрата за модулем m КЛ Вхід ПК 3 A mod [(m-1)/2] Десятковий код Двійковий код -5 -101 -4 -100 -3 -011 -2 -010 -1 -001 0 0 1 001 2 010 3 011 4 100 5 101 Вихід ПК 3 A' = [A + (m-1)/2] mod m Десятковий код Двійковий код 0 0000 1 0001 2 0010 3 0011 4 0100 5 0101 6 0110 7 0111 8 1000 9 1001 10 1010 Таблиця 2 Пристрій для піднесення чисел до квадрата за модулем m КЛ. Номер пари вихідних шин дешифратора 4 0 1 2 3 4 5 Значення, що призначають Значення, що признача- Значення, що призначаютьпарі вихідних шин дешиф- ються вхідним шинам ся вихідним шинам шифраратора 4 шифратора 6 тора 6 0 0 000 1,10 1 001 2,9 4 100 3,8 4 100 4,7 1 001 5,6 0 000 7 Комп’ютерна верстка М. Мацело 61798 8 Підписне Тираж 23 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601