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

Пристрій для піднесення комплексних чисел в квадрат за комплексним модулем у модулярній системі числення, що містить перший дешифратор, першу групу елементів АБО, шифратор, при . чисел A . Найбільш близьким за технічною суттю і результатом, що досягається, є пристрій для піднесення чисел у степінь за модулем m [а. с. СРСР №1160397, МПК G 06 F 7/49, 1985. Б.В. №21, 1985р.], що містить елементи І та АБО, групу дешифраторів. Недоліком відомого пристрою (прототипу) низькі функціональні можливості. Прототип не мо UA . лем m = p + qi у модулярній системі числення. Відомий пристрій (аналог) для піднесення чисел за модулем m, що містить вхідні та вихідні регістри, дешифратори, елементи І та АБО, комутатори [а. с. СРСР №1034036, МПК G 06 F 7/72, 1982]. Даний пристрій дозволяє підносити дійсні числа за модулем m. Недоліком відомого пристрою (аналогу) є низькі функціональні можливості. Пристрій не може . підносити до квадрату за модулем m комплексних (19) Корисна модель належить до обчислювальної техніки і призначена для піднесення комплексних чисел . A = a + bi в квадрат за комплексним моду 3 40905 же підносити до квадрату за комплексним моду. лем m комплексного числа . A . В основу корисної моделі поставлено задачу розширити функціональні можливості за рахунок вдосконалення пристрою для піднесення чисел в квадрат за модулем шляхом можливості організації операції піднесення чисел . A = a + bi в квадрат . за комплексним модулем m = p + qi . Поставлене завдання вирішується тим, що пристрій для піднесення комплексних чисел . A = a + bi в квадрат за комплексним модулем . m = p + qi у модулярній системі числення, який містить перший дешифратор, першу групу елементів АБО, шифратор, блок множення b j ⋅ ρ(mod m ) , ⎛. ⎞ де ρ = u ⋅ q − v ⋅ p⎜ m = p + q ⋅ i, u ⋅ p + v ⋅ q = 1⎟ , сума⎜ ⎟ ⎝ ⎠ 2 2 тор a j + b jρ = h j (mod N) , де N=р +q , другу групу ( ) елементів АБО, другий дешифратор. При цьому ⎛ ⎡m ⎤ ⎞ виходи ⎜ 1 ÷ ⎢ ⎥ ⎟ – першого дешифратора ([x] ⎜ ⎟ ⎝ ⎣ 2 ⎦⎠ ціла частина числа х, його не більша) підключено до перших входів відповідних елементів АБО першої групи, до других входів яких підключено відпо⎛ ⎡m ⎤ ⎞ відно виходи ⎜ ⎢ ⎥ + 1⎟ ÷ m − 1 першого дешифра⎜ 2 ⎟ ⎝⎣ ⎦ ⎠ тора. Сума значень, що надана кожній парі вхідних шин елемента АБО першої групи дорівнює значенню модуля m. Виходи елементів АБО першої групи підключено до відповідних входів шифратора, вихід якого є виходом дійсного значення результату операції. Вхід дійсного числа А пристрою підключено до перших входів елементів АБО другої групи, виходи яких підключено до входу першого дешифратора. Шини дійсної та уявної частин комплексного числа . A = a + bi підключено до перших входів a j + b jρ = h j (mod N) ( ) відповідно та блока суматора множення b jρ(mod N) до другого входу якого підключена шина подачі значення коефіцієнту ізоморфізму ρ=u·qv·p. Вихід блока множення підключено до другого входу суматора, вихід якого підключено до других входів елементів АБО другої групи. Вихід шифратора підключено до входу другого дешифратора, вихід якого є виходом комплексного значення результату виконання операції. На рисунку представлена блок-схема запропонованого пристрою, де: 1 - вхід дійсного числа А; 2 - вхід комплексного числа . A = a j + b ji (21 вхід значення а, 22 - вхід значення b); 3 - суматор 2 2 a j + b jρ mod N (N=p +q ); 4 - блок множення ( ) b jρ(mod N) ; 5 - шина подачи значення коефіцієнта ρ=u·q-v·p ізоморфізму; 6 - друга група елементів 4 АБО; 7 - перший дешифратор (пристрій для перетворення двійкового коду в унітарний код); 8 - перша група елементів АБО; 9 - шифратор (пристрій для перетворення унітарного коду в двійковий код); 10 - вихід дійсного результату операції A 2 (mod m ) j (перший режим роботи пристрою); 11 другий дешифратор (пристрій для перетворення двійкового коду в непозиційний код, тобто пристрій для визначення комплексного лишку A 2 (mod m ) j за значення дійсного лишку n2 (mod m ) ); 12 - вихід j комплексного результату (другий режим роботи .⎞ ⎛ пристрою) операції . A 2 = ⎜ mod m ⎟ . ⎜ ⎟ ⎝ ⎠ У відповідності з першою фундаментальною теоремою Гауса за заданому комплексному моду. лю m = p + qi , норма якого дорівнює N=p2+q2, для якого найбільший загальний дільник (НЗД) дорівнює одиниці, тобто (p, q)=1, комплексне число . A = a j + b ji порівнянне з одним і лише одним лишком з ряду чисел 0, l, 2,..., N-2, N-1, .⎞ ⎛ тобто a j + b ji ≡ n⎜ mod m ⎟ (n - натуральне чис⎜ ⎟ ⎝ ⎠ ло). Ця теорема встановлює ізоморфізм між комплексними числами, та їх дійсними лишками, що дає можливість реалізувати операцію піднесення комплексних чисел . A = a j + b ji в квадрат за ком ( ) . плексним модулем m = p + qi за допомогою алгоритмів, що реалізовують операцію піднесення чисел А в квадрат за модулем m в дійсній області. .⎞ ⎛ Таким чином, . A = n⎜ mod m ⎟ , тобто існує еквівале⎜ ⎟ ⎝ ⎠ нтність a j + b ji ≈ hi Лишок hj визначається за формулою а+bρ=h(modN), де ρ=u·q-v·p, а цілі числа u і v визначаються з відомого співвідношення ρ=u·q-v·p=1. Вираз u·q-v·p=ρ, який встановлює відповід. ність між комплексним h та дійсним h лишками має назву коефіцієнту ізоморфізму. Перший вхід пристрою підключено до шини 1 подачи дійсного значення числа А. Другий вхід пристрою підключено до шин 2 подачи комплекс. ного числа . A = a j + b ji за модулем m = p + qi (21 вхід значення а, 22 - вхід значення b). Вхід 21 безпосередньо підключено до першого входу суматора 3, а вхід 22 підключено до першого входу блоку 4 множення b jρ(mod N) , до другого входу якого підключена шина 5 подачи значення коефіцієнта ρ=u·q-v·p ізоморфізму. Вихід блоку 4 множення 5 40905 підключено до другого входу суматора 3, вихід якого разом з входом 1 через другу групу елементів АБО 6, підключено до входів першого дешифратора 7. Виходи першого дешифратора 7 попарно (сума значень, що надана кожній парі вхідних шин елемента АБО 8 першої групи дорівнює значенню модуля m), підключено до відповідних входів шифратора 9, вихід якого підключено до виходу 10 дійсного результату операції А2(modm), а також до входу другого дешифратора 11, вихід 12 (121, 122) якого є вихід комплексного результату .⎞ ⎛ операції . A 2 = ⎜ mod m ⎟ . ⎜ ⎟ ⎝ ⎠ Пристрій працює наступним чином. Пристрій працює у двох режимах. Перший режим, якщо на вхід 1 подається дійсне значення а числа А. Робота пристрою аналогічна роботі прототипу. Другий режим, якщо на вхід 2 подається комплексно число . A = a j + b ji . На вхід 21 поступає значення а, а на вхід 22 - значення b. З виходу блоку 4 множення у двійковому коді на перший вхід суматора 3 подається значення bρ, а на другий вхід якого поступає значення а. З виходу суматора 3 за модулем N=p2+q2 значення (a+bρ)=h(modN), у двійковому коді (ρ=u·q-v·p), через групу елементів 6 АБО поступає на відповідний вхід дешифратора 7. З виходу дешифратору 7 значення h в унітарному коді через відповідний елемент АБО 8 підключено до відповідного входу шифратору 9, з виходу якого значення h2(modN) у двійковому коді поступає на вихід 10 (для першого режиму) та на вхід дешифратору 11 (другий режим). З виходу дешифратора 11 значення .⎞ ⎛ . A 2 = ⎜ mod m ⎟ , що відповідає значенню h2(modN), ⎜ ⎟ ⎝ ⎠ поступає на вихід 12 (121- дійсне значення .⎞ ⎛ . A 2 = ⎜ mod m ⎟ , 122 уявне значення ⎜ ⎟ ⎝ ⎠ .⎞ ⎛ . A 2 = ⎜ mod m ⎟ ). ⎜ ⎟ ⎝ ⎠ Розглянемо приклад конкретного виконання операції піднесення комплексних чисел в квадрат . за модулем m = 3 + 4i . В цьому випадку u=-1, v=1, 2 2 2 2 N=p +q =3 +4 =25, ρ=u·q-v·p=(-1)·4-1·3=-7. В таблиці 1 представлено значення, що надано парі вихідних шин дешифратора 7. В таблиці 2 представлено дійсні найменші позитивні h лишки, що . відповідають комплексним найменшим лишкам h . за модулем m = 3 + 4i . 6 Нехай необхідно визначити лишок в модулярній системі числення квадрату числа . A = 5 + i за . модулем m = 3 + 4i (N=25). На вхід 2 поступає . число A = 5 + i . На вхід 21 поступає значення а=5, а на вхід 22 - значення b=1. На першій вхід блоку 4 множення поступає значення одиниця, а на другий вхід по шині 5 поступає значення ρ=-1. На вхід суматора 3 поступає значення 5 та b·ρ=-7. На виході суматора 3 маємо (5-7)mod25=(-2)mod25=(252)mod25=23(mod25). Це значення через групу елементів 6 АБО в двійковому коді поступає на вхід (першого) дешифратора 7. З виходу дешифратора 7 значення 23 в унітарному коді по 23 вихідній шині, через другий елемент АБО 8 (див. табл. 1) поступає на четвертий (див. табл. 1) вхід шифратора 9. Значення чотири в двійковому коді поступає на вхід дешифратора 11. З виходу дешифратора 11 на другий вихід 12 пристрою в двійковому коді подається результат операції, тоб.⎞ ⎛ то . A j = ⎜ mod m ⎟ = 3i (див. табл. 2). На вихід 121 ⎜ ⎟ ⎝ ⎠ дійсне значення частини (а=0) комплексного числа .⎞ ⎛ .A 2⎜ mod m ⎟ , а на вихід 12 уявна (b=3) частина 2 j⎜ ⎟ ⎝ ⎠ .⎞ ⎛ .A 2⎜ mod m ⎟ . j⎜ ⎟ ⎝ ⎠ Перевірка. Вихідне число . A = 5 + i піднесемо до . квадрату. Маємо A 2 = (5 + i)2 = 25 + 10i + i2 = 25 + 10i − 1 = 24 + 10i . . Визначимо лишок h числа 24+10i за модулем . m = 3 + 4i . Спочатку обчислимо дійсний лишок h за модулем N=25. Маємо a+b·ρ≡h(modN)=(24+10·7))mod25=(-46)mod25=4(mod25). У відповідності з даними табл. 2 дійсний лишок h порівняно (відповідає) з комплексним лишком 3i. Таким чином, корисна модель (пристрій для піднесення комплексних чисел в квадрат за комплексним модулем у модулярній системі числення) значно розширює функціональні можливості прототипу. Дана корисна модель дозволяє виконувати операцію піднесення чисел в квадрат за модулем як в дійсній так і в комплексній областях. 7 40905 8 Таблиця 1 Номер вихідної пари дешифратора 7 1 2 3 4 5 6 7 8 9 10 11 12 Значення, що надано парі вихідних шин дешифратора 7 1,24 2,23 3,22 4,21 5,20 6,19 7,18 8,17 9,16 10,15 11,14 12,13 Значення, що надано входам шифратора 9 1 4 9 16 0 11 24 14 6 0 21 19 Таблиця 2 Вхід дешифратора 11, h 2 (mod N) j 1 2 3 4 5 6 7 8 9 10 11 12 Вихід 12 дешифратора 11, . ⎞ . 2⎛ A j ⎜ mod m ⎟ ⎟ ⎜ ⎠ ⎝ -3+3i -2+3i -1+3i 3i 1+3i 2+3i -1+6i 6i -2+2i -1+2i 2i 1+2i Комп’ютерна верстка Л. Купенко Вхід дешифратора 11, h 2 (mod N) j 13 14 15 16 17 18 19 20 21 22 23 24 0 Підписне Вихід 12 дешифратора 11, . ⎞ . 2⎛ A j ⎜ mod m ⎟ ⎟ ⎜ ⎠ ⎝ -2+5i -1 + 5i 5i 1+5i -1+i i -3+4i -2+4i -1+2i 4i 1+4i 2+4i 0+0i Тираж 28 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601