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

Пристрій для піднесення чисел до квадрата за модулем m, що містить вхідний і вихідний регістри, першу гр упу елементів АБО, першу гр упу елементів І, дешифратор, шифратор, при цьому вхід пристрою підключений до входу вхідного регістра, вихід якого підключений до входу де шифратора, 3 39493 перших входів елементів І першої та др угої гр уп. До други х входів елементів І першої та другої гр уп підключено відповідно шини ознаки задання числового діапазону реалізації операції піднесення чисел до квадрату за модулем m - додатнього (+) та від'ємного (-). Виходи елементів І другої гр упи підключено до перших входів суматора за модулем m, до других входів якого підключено шини подачі значення m/2. Виходи елементів І першої групи та суматора за модулем m через другу гр упу елементів АБО підключено до входу вихідного регістру, вихід якого є ви ходом пристрою. Технічний результат, який може бути отриманий при використанні корисної моделі, полягає в одержанні пристрою для піднесення чисел до квадрату за модулем m, в якому реалізується операція як в додатньому, так і в від'ємному числових діапазонах. Відомий алгоритм виконання операції піднесення чисел до квадрату за модулем m для чисел ( ) ( 4 X¶ , що знаходяться в додатньому діапазоні 0 £ X ¶ £ m - 1 , де m - модуль, за яким функціонує пристрій. X 2 (mod= a , m) ¶ = k × m + a ( k - натуральне число; X Для визначення результату операції чисел до квадрату за модулем m , як нього X 2 (mod m ) , так і для від'ємного ¶ тобто 0 £ a < m ). піднесення для додатX 2в (mod m) ¶ числових діапазонів, в цьому випадку число X¢ ¶ знаходиться тільки у додатньому числовому інтервалі 0 £ X¢ < m . Представимо число X ¶в , що ле¶ жить в додатньому та від'ємному числових діапаm m зонах - £ X ¶в < + , в штучній формі, таким 2 2 ¢¶ = X ¶в + m (див. табл. 1 для m=14). Розчином X 2 глянемо вираз [ ) Нехай 2 ¶ ] [ ] 2 2 2 2 X 2в modm 2 = X ¢ - m 2 modm 2 = (X ¢¶ ) - 2 × X ¢ × m 2 + m 4 modm 2 = (X ¢ ) - X ¢¶ × m + m 4 modm 2 = a ¶ ¶ ¶ ¶ Пристрій по довільному модулю m представ, так, як X¢¶ = X ¶в + m 2 число позитивне. Щоб лено на Фіг.1, де: 1 - вхід пристрою; 2 - вхідний одержати результат операції піднесення чисел до регістр; 3 - дешифратор (пристрій для перетвоквадрату за модулем m, також в штучній формі, рення чисел з двійкового коду в унітарний); 4 2 m +m . перша група елементів АБО; 5 - шифратор (принеобхідно реалізувати вираз X ¶в mod 2 2 стрій для визначення значень X 2 (mod m ) та ¶ Таким чином, алгоритм визначення результату (X ¢¶ )2 mod m ); 6, 7 - перша та др уга групи елеменоперації для чисел додатнього X¶ та від'ємного тів І; 8, 9 – шини ознаки, відповідно, додатнього (+) X ¶в діапазонів визначається виразом та від'ємного (-) діапазонів реалізації операцій під(X ¢¶ )2 mod m + m 2 mod m . несення чисел до квадрату за модулем m ; 10 суматор за модулем m ; 11 - шини подачі значення 2 Тобто, é X ¶в + m 2 mod m + m 2 ù mod m . m .; 12 - друга гр упа елементів АБО; 13 - вихідê ú ë û 2 Таким чином, для додатнього діапазону чисел ний регістр; 14 – вихід пристрою. На Фіг.2 представлено пристрій за модулем на вхід пристрою подається значення X¶ , а для m =14. В табл. 1 представлено числовий діапазон від'ємного діапазону чисел на вхід пристрою подадля X¶ , X ¶в та X¶ чисел. ¢ ється значення X¢¶ = X ¶в + m 2 . В цьому випадку, на 2 виході пристрою маємо значення (X ¶ ) mod m або 2 ( [ ) ] ) ( (X ) mod m . 2 ¶в Таблиця 1 X¶ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 X ¶в -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 0 1 2 3 4 5 6 7 8 9 10 11 12 13 X¢¶ X ¶в + m = 2 В табл. 2 представлено алгоритм функціонування шифратора 5. Таблиця 2 Входи ши фратора 5 X¶ , X¢ ¶ 1 Виходи ши фратора 5 (X ¶ ) mod m , (X ¢ ) mod m ¶ 2 2 Елементи АБО 4 першої гр упи разом з шифратором 5 реалізують виконання умови X 2 (mod m) = (m - X) 2 mod m . 2 3 4 5 6 0001 0100 1001 0010 1011 1000 Вхід 1 пристрою підключено до входу вхідного 2 регістру, ви хід якого підключено до входу де шифратора 3, виходи якого попарно підключено до входів елементів 4 АБО першої групи, виходи яких 5 39493 6 підключено до входів шифратора 5. Виходи шифпає на вхід регістра 13. 2 ратора 5 підключено до перших входів елементів І Перевірка: (X ¶ ) mod m = 122 (mod14) = 4 . першої 6 та другої 7 груп. До други х входів елемеДругий випадок. Варіант 1. Нехай X ¶в = - 5 . В нтів І першої 6 та др угої 7 гр уп підключено, відповідно, шини ознаки (+) додатнього 8 та від'ємного цьому випадку присутній сигнал шини 9. На вхід 1 (-) 9 діапазонів. Виходи елементів І другої 7 групи пристрою поступає значення підключено до перших входів суматора 10 за мо-= = - 5 + 7 2 у війковому 0010 коді. З X¢¶ X ¶в + m = 2 дулем m , до других входів якого підключено шини другого ви ходу деши фратора 3 сигнал, що відпо11 значення m 2 . Виходи елементів І першої 6 відає значенню два, через другий елемент АБО 4 групи та суматора 10 через другу 12 групу елеменпоступає на другий вхід ши фратора 5. З ви ходу тів АБО підключено до входу вихідного регістру 13, шифратора 5 значення вихід 14 якого є виходом пристрою. = 2 2 (mod14) 4 у двійковому 0100 коді (X ¢¶ )2 mod m= Пристрій функціонує наступним чином (Фіг.1). через відкриті елементи І 7 поступає на перші вхоЗа входом 1 в перший регістр 2 заноситься знади суматора 10, на другі входи якого по шині 11 чення X ¶ X¢¶ = X ¶в + m 2 у двійковому коді. Дешипоступає у двійковому 0111 значенні m 14= 7 . З виходу суматора 10 значення фратор 3 перетворює двійковий код в унітарний. = 2 2 Сигнал, що відповідає значенню операнда X ¶ (X ¶ ) , ¢ 2 (A¶¢ ) mod m + m 2 mod m = (4 + 7)mod14 = 11 у двійчерез відповідний елемент АБО 4 першої групи ковому 1011 коді через елементи АБО 12 поступає поступає на вхід ши фратора 5. З ви ходу ши фра2 на вхід регістра 13. тора 5 значення X ¶ (mod m ) або значення Перевірка: 2 (X ¶¢ ) mod m в двійковому коді поступають на пер(X ¶в )2 mod m = (- 5)2 mod14 = 25(mod14) = 11. ші входи елементів І першої 6 та другої 7 гр уп. Другий випадок. Варіант 2. Нехай X ¶в = 5 . В Перший випадок. Необхідно визначити ре2 цьому випадку присутній сигнал шини 9. На вхід 1 зультат операції X ¶ (mod m ) для чисел в додатпристрою поступає значення ньому числовому діапазоні. У цьому випадку при= = 5 + 7 12 у війковому 1100 коді. З X¢¶ X ¶в + m = сутній сигнал шини 8 (+). Він відкриває елементи І 2 2 6 першої групи. Значення X ¶ (mod m ) в двійковому другого (2+12) виходу деши фратора 3 сигнал, що відповідає значенню дванадцять, через другий коді через елементи І 6, елементи АБО 12 постуелемент АБО 4 поступає на другий вхід ши фратопає на вхід ви хідного 13 регістра. Другий випадок. Необхідно визначити резульра 5. З ви ходу шифратора 5 значення 22 (mod14) , 2 так, як 12+2=m=14, тобто чотири у двійковому тат операції (X ¶ ) mod m для чисел у від'ємному ¢ 0100 коді через елементи І 7 поступає на перші числовому діапазоні. В цьому випадку присутній входи суматора 10, на другі входи якого по шині 11 сигнал шини 9 (-). Він відкриває елементи І 7 друпоступає у двійковому коді 0111 значення 2 гої групи. Значення (X ¶ ) mod m у двійковому коді ¢ m = 14 = 7 . 3 виходу суматора 10 значення 2 2 поступає на перші входи суматора 10 за модулем m , на другі входи якого в двійковому коді поступає (4 + 7 )m od14 = 11 , тобто 1011, поступає на вхід регістра 13. значення m 2 . З виходу суматора 10 значення Перевірка: (X ¢¶ )mod m + m 2 mod m через елементи АБО 12 (X ¶в )2 mod m = 52 (mod14) = 25(mod14) = 11. поступає на вхід вихідного 13 регістру. Технічний результат, який виходить від викоРозглянемо приклад реалізації операції ристання даної корисної моделі полягає в реалізації операції піднесення чисел до квадрату за мо(X ¶ )2 mod m , (X ¶ в )2 modm для m =14 (Фіг.2). дулем m , як в додатному так і від'ємному Перший випадок. Нехай X ¶ = 12 . В цьому вичислових діапазонах. Це значно розширює функпадку присутній сигнал шини 8. Значення 1100 з ціональні можливості пристрою для піднесення виходу регістра 2 поступає на вхід дешифратора чисел до квадрату за модулем m . 3, з дванадцятого виходу якого сигнал через другий (12+2=m=14) елемент АБО 4 поступає на другий вхід ши фратора 5, з виходу якого значення (X ¶ )2 mod m = (12)2 mod14 = 4 у двійковому 0100 коді через елементи І 6, елементи АБО 12 посту ( ) [ [ ] [ ] ] 7 Комп’ютерна в ерстка А. Крулевський 39493 8 Підписне Тираж 28 прим. Міністерство осв іт и і науки України Держав ний департамент інтелектуальної в ласності, вул. Урицького, 45, м. Київ , МСП, 03680, Україна ДП “Український інститут промислов ої в ласності”, вул. Глазунова, 1, м. Київ – 42, 01601