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

Табличний пристрій для множення чисел за модулем m у класі лишків, що містить перший і другий вхідні регістри, вихідний регістр, перший і другий дешифратори, суматор за модулем два, першу, другу та третю групи елементів АБО, першу та другу групи ключових елементів, комутатор, перший, другий, третій, четвертий, п'ятий, шостий, сьомий та восьмий елементи АБО, перший, другий, третій і четвертий елементи І, при цьому перший та другий входи пристрою підключено до входів відповідно першого та другого вхідних регістрів, виходи яких підключено відповідно до входів першого та другого дешифраторів, перші m  1  0   групи входів першого та другого де2   шифраторів підключені до входів першого та друm 1  гого елементів АБО, а другі   m  1 групи 2   виходів першого та другого дешифраторів підключені до входів третього та четвертого елементів АБО, виходи першого, другого, третього та четвертого елементів АБО підключені до відповідних входів суматора за модулем два, а виходи першого та другого дешифраторів попарно (сума значень, що присвоєна кожній парі вихідних шин дешифратора, дорівнює значенню модуля m) підключені до входів відповідних елементів АБО першої та другої груп, виходи яких підключено до 3 60078 4 зиційній системі числення класу лишків (КЛ), а елементів АБО, вихід п'ятого елемента АБО підктакож при криптографічних перетвореннях інфорлючено до перших входів першого та другого елемації. ментів І, а вихід шостого елемента АБО підключеБлизьким до корисної моделі (аналогом) є но до перших входів третього та четвертого пристрій множення в системі залишкових класів елементів І, одиничний вихід суматора за модулем [а.с. СССР № 550636, МПК G 06 F 7/52, опубл. два підключено до других входів першого та тре1977 р]. До складу пристрою входять вхідні регісттього елементів І, а нульовий вихід суматора за ри, дешифратори, ключі, комутатор, вихідний ремодулем два підключено до других входів другого гістр та логічні блоки пошуку квадрата та квадранта четвертого елементів І, виходи першого та четтів арифметичної таблиці. Застосування у вертого елементів І підключено до входу сьомого пристрої логічного блока пошуку квадрата відноселемента АБО, а виходи другого та третього елено діагоналі квадранта і логічного блока пошуку ментів І підключено до входу восьмого елемента квадрантів відносно осей арифметичної таблиці АБО. призводить до необхідності введення в пристрій Недолік прототипу - обмежені функціональні додаткових елементів: дешифратора номерів баможливості. Це обумовлено тим, що результат зових квадратів квадранта, пасивних трансформамодульного множення двох чисел представляєтьторних лінійок і та ін. ся у закодованому вигляді (у коді табличного мноНедолік аналога - обмежені функціональні моження), що не дозволяє його безпосередньо викожливості. ристовувати у подальшому ланцюгу обчислень. Найбільш близьким до корисної моделі (проВ основу запропонованої корисної моделі постотипом) є пристрій множення в системі залишкотавлено задачу розширення функціональних можвих класів [а.с. СССР № 922731, МПК G 06 F 7/52, ливостей пристрою, за рахунок представлення опубл. 1982 р., БВ № 15]. Пристрій містить перший результату арифметичної операції АВ (mod m) і другий вхідні регістри, вихідний регістр, перший і модульного множення безпосередньо у двійководругий дешифратори, суматор за модулем два, му коді. першу, другу та третю групи елементів АБО, перПоставлена задача вирішується тим, що табшу та другу групи ключових елементів, комутатор, личний пристрій для множення чисел за модулем перший, другий, третій, четвертий, п'ятий, шостий, m у класі лишків містить перший і другий вхідні сьомий та восьмий елементи АБО, перший, друрегістри, вихідний регістр, перший і другий дешигий, третій і четвертий елементи І, при цьому перфратори, суматор за модулем два, першу, другу ший та другий входи пристрою підключено до вхота третю групи елементів АБО, першу та другу дів відповідно першого та другого вхідних групи ключових елементів, комутатор, перший, регістрів, виходи яких підключено відповідно до другий, третій, четвертий, п'ятий, шостий, сьомий входів першого та другого дешифраторів, перші та восьмий елементи АБО, перший, другий, третій і четвертий елементи І, при цьому перший та друm  1  0   групи входів першого та другого дегий входи пристрою підключено до входів відпові2   дно першого та другого вхідних регістрів, виходи шифраторів підключені до входів першого та друяких підключено відповідно до входів першого та  m 1  m  1  гого елементів АБО, а другі  групи  m  1 другого дешифраторів, перші  0   групи  2  2   виходів першого та другого дешифраторів підклювходів першого та другого дешифраторів підключені до входів третього та четвертого елементів чені до входів першого та другого елементів АБО, АБО, виходи першого, другого, третього та четве m 1  ртого елементів АБО підключені до відповідних а другі   m  1 групи виходів першого та 2   входів суматора за модулем два, а виходи першого та другого дешифраторів попарно (сума знадругого дешифраторів підключені до входів тречень, що присвоєна кожній парі вихідних шин детього та четвертого елементів АБО, виходи першифратора, дорівнює значенню модуля m) шого, другого, третього та четвертого елементів підключені до входів відповідних елементів АБО АБО підключені до відповідних входів суматора за першої та другої груп, виходи яких підключено до модулем два, а виходи першого та другого дешиперших входів ключових елементів першої та друфраторів попарно (сума значень, що присвоєна гої груп, до других входів яких підключена керуюча кожній парі вихідних шин дешифратора, дорівнює шина пристрою, а виходи ключових елементів значенню модуля m) підключені до входів відповіпершої та другої груп підключено до першої та дних елементів АБО першої та другої груп, виходи другої групи входів комутатора, виходи якого пояких підключено до перших входів ключових елепарно (сума значень, що присвоєна кожній парі ментів першої та другої груп, до других входів яких вихідних шин комутатора дорівнює значенню мопідключена керуюча шина пристрою, а виходи дуля m) підключено до відповідних елементів АБО ключових елементів першої та другої груп підклютретьої групи, виходи яких підключено до входу чено до першої та другої групи входів комутатора, виходи якого попарно (сума значень, що присвоє m  1 вихідного регістра, одночасно перша 1   та на кожній парі вихідних шин комутатора, дорівнює 2   значенню модуля m) підключено до відповідних  m 1  елементів АБО третьої групи, виходи яких підклюдруга   m  1 групи виходів комутатора чено до входу вихідного регістра, одночасно пер2   підключені до входів відповідно п'ятого та шостого 5 60078 6 безпосередньо в коді табличного множення (таб m  1  m 1  ша 1   m  1 групи вихо та друга  лиця 3, для m=11). 2    2  Алгоритм отримання результату операції табдів комутатора підключені до входів відповідно личного модульного множення визначається нап'ятого та шостого елементів АБО, вихід п'ятого ступним чином: якщо два числа А і В задані за елемента АБО підключено до перших входів перосновою (модулем) m в коді табличного множення шого та другого елементів І, а вихід шостого елевиду A   ai , ai і B  bi , bi мента АБО підключено до перших входів третього та четвертого елементів І, одиничний вихід сумаmi  1  0, якщо 0  ai  2 , тора за модулем два підключено до других входів   ai   , першого та третього елементів І, а нульовий вихід 1 якщо mi  1  ai  mi  1, , суматора за модулем два підключено до других  2  входів другого та четвертого елементів І, виходи тоді для того, щоб отримати добуток першого та четвертого елементів І підключено до AB(modm) цих чисел в коді табличного множення, входу сьомого елемента АБО, а виходи другого та достатньо отримати добуток аi·bi(mod m) в коді третього елементів І підключено до входу восьмотабличного множення і інвертувати отриманий для го елемента АБО, у який, згідно з корисною модобутку індекс  у випадку, якщо  a i відрізняється деллю, введено шифратор, першу та другу групи  елементів І, інвертор за модулем m і четверту групу елементів АБО, при цьому вихід вихідного регістра підключено до входу шифратора, вихід якого підключено до перших входів елементів І першої та другої груп, до других входів яких підключені виходи відповідно восьмого та сьомого елементів АБО, виходи елементів І другої групи підключено до перших входів інвертора за модулем m, до других входів якого підключені шини подачі значення модуля m, а виходи елементів І першої групи та виходи інвертора за модулем m через елементи АБО четвертої групи підключено до виходу пристрою. Введення вказаних ознак дозволяє розширити функціональні можливості прототипу, за рахунок представлення результату арифметичної операції АВ (mod m) модульного множення безпосередньо у двійковому коді при збереженні всіх технічних можливостей пристрою. На кресленні представлено блок-схему табличного пристрою для множення чисел за модулем m у класі лишків. Таблиця 1 - Повна таблиця множення двох чисел за модулем m=11. Таблиця 2 - Таблиця реалізації другого квадранту повної таблиці множення. Таблиця 3 - Таблиця представлення чисел у коді табличного множення за модулем m=11. Таблиця 4 - Таблиця реалізації алгоритму складання за модулем два. В запропонованій корисній моделі використовуються властивості симетрії арифметичної таблиці множення (таблиця 1, для m=11) відносно діагоналі, вертикалі і горизонталей, які проходять m 1 m 1 між значеннями та (m - модуль таб2 2 лиці, тобто, модуль за яким працює пристрій). Тобто виконуються наступні математичні співвідношення АB(mod m)=В·A(mod m), [А (m-В)]mod m=[В (m-A)]modm, АB(mod m)=m-[В(m-A)]modm, ВA(modm)=m-[А(m-5)]modm. Це і визначає можливість реалізації в схемі табличного модульного множення лише 0,25 частини (таблиця 2, для m=11) таблиці 1. При цьому, на відміну від відомих, в запропонованому табличному пристрої операція множення виконується    від  b i . Тобто, індекс у AB(mod m) визначаєте наступним чином: , якщо  аі  bi  0mod 2,   .  , якщо  аі  bi  1mod 2.      На кресленні представлено блок-схему табличного пристрою для множення чисел за модулем m у класі лишків, де: 1, 2 - перший та другий входи пристрою; 3, 4 - перший та другий вхідні регістри; 5, 6 - перший та другий дешифратори (пристрій для перетворення двійкового коду в унітарний); 7, 8, 9 та 10 - перший, другий, третій та четвертий елементи АБО; 11 - суматор за модулем два (пристрій реалізує алгоритм операції додавання за модулем два, що представлено таблицею 4); 12, 13 - перша та друга група елементів АБО; 14, 15 перша та друга група ключових елементів; 16 шина керування пристроєм; 17 - комутатор; 18 третя група елементів АБО; 19 - вихідний регістр; 20, 21 - п'ятий та шостий елементи АБО; 22, 23, 24 і 25 - перший, другий, третій і четвертий елементи І; 26, 27 - сьомий та восьмий елементи АБО; 28 шифратор (пристрій для перетворення унітарного коду в двійковий); 29, 30 - перша та друга групи елементів І; 31 - інвертор за модулем m; 32- шини подачі значення модуля m; 33 - четверта група елементів АБО; 34 - вихід пристрою. Причому, перший 1 та другий 2 входи пристрою підключено до входів відповідно першого 3 та другого 4 вхідних регістрів, виходи яких підключено відповідно до входів першого 5 та другого 6 m  1  дешифраторів. Перші  0   групи входів 2   першого 5 та другого 6 дешифраторів підключені до входів першого 7 та другого 8 елементів АБО, а  m 1  другі   m  1 групи виходів першого 5 та  2  другого 6 дешифраторів підключені до входів третього 9 та четвертого 10 елементів АБО. Виходи першого 7, другого 8, третього 9 та четвертого 10 елементів АБО підключені до відповідних входів суматора 11 за модулем два. Виходи першого 5 та другого 6 дешифраторів попарно (сума значень вихідних шин дорівнює значенню модуля m) підключені до входів відповідних елементів АБО першої 12 та другої 13 груп, виходи яких підключено 7 60078 8 до перших входів ключових елементів першої 14 результату аі·bi(mod m) модульного множення сигта другої 15 груп, до других входів яких підключена нал з виходу комутатора 17 через один з двох керуюча шина 16 пристрою. Виходи ключових елементів АБО 20, 21 надходить на один з других елементів першої 14 та другої 15 груп підключено входів елементів І 22, 23, 24 та 25. Вибір одного з до першої та другої груп входів комутатора 17, двох елементів АБО 20 чи 21 залежить від того, до виходи якого попарно (сума значень вихідних шин  m  1  m 1  якої групи операндів ( 1   m  1 )  чи  дорівнює значенню модуля m) підключено до від2    2  повідних елементів АБО третьої 18 групи, виходи належить результат ai·bi(mоd m) модульного мнояких підключено до входу вихідного регістра 19. ження. Сигнал з виходу одного з елементів І 22,  m  1  m 1  23, 24 чи 25 надходить до входу одного з елеменПерша 1   m  1 групи  та друга  2    2  тів АБО 26 чи 27, вихідні сигнали яких являють виходів комутатора 17 підключені до входів відпособою ознаку ("0" або "1") результату операції, відно п'ятого 20 та шостого 21 елементів АБО. представленого в коді табличного множення. ОдВихід п'ятого 20 елемента АБО підключено до пеночасно сигнал, що відповідає числовому резульрших входів першого 22 та другого 23 елементів І, тату ai·bi(mod m) модульного множення в унітара вихід шостого 21 елемента АБО підключено до ному коді, надходить через один з елементів АБО перших входів третього 24 та четвертого 25 еле18 до числового входу вихідного регістра 19. Таментів І. Одиничний вихід суматора 11 за модулем ким чином, до вихідного регістра 19 буде подано два підключено до других входів першого 22 та результат AB=(,aibi(mod m)) операції модульного третього 24 елементів І, а нульовий вихід - підклюмноження в коді табличного множення. З виходу чено до других входів другого 23 та четвертого 25 регістра 19 сигнал, що відповідає значенню елементів І. Виходи першого 22 та четвертого 25 aibi(mod m) в унітарному коді, надходить до входу елементів І підключено до входу сьомого 26 елешифратора 28, з виходу якого значення aibi(mod мента АБО, а виходи другого 23 та третього 24 m) у двійковому коді надходить до входів елеменелементів І підключено до входу восьмого 27 елетів І першої 29 та другої груп. Вихідний сигнал мента АБО. Вихід вихідного регістра 19 підключеелемента АБО 27 (ознака "0") відкриває елементи но до входу шифратора 28, вихід якого підключено І першої 29 групи, а вихідний сигнал елемента до перших входів елементів І першої 29 та другої АБО 26 (ознака "1") відкриває елементи І другої 30 30 груп, до других входів яких підключені виходи групи. При ознаці "1" з виходу елементів І другої відповідно восьмого 27 та сьомого 26 елементів 30 групи значення аіbi(mod m) у двійковому коді АБО. Виходи елементів І другої 30 групи підклюнадходить до перших входів інвертора 31, до дручено до перших входів інвертора 31 за модулем m, гих входів 32 якого надходить значення модуля m до других входів якого підключені шини 32 подачі у двійковому коді. При ознаці "1", з виходів інверзначення модуля m. Виходи елементів І першої 29 тора 31 значення m - aibi(mod m) (при ознаці "0" з групи та виходи інвертора 31 за модулем m через виходів елементів І групи 28 значення aibi(mod m) елементи АБО четвертої 33 групи підключено до через елементи АБО четвертої 33 групи надходить виходу 34 пристрою. до виходу 34 пристрою. Пристрій працює наступним чином. Входи 1 і 2 Приведемо приклади виконання операції мотабличного пристрою модульного множення по дульного множення для m=11. кодових ланцюгах для операндів А і В зв'язуються Приклад 1. Припустимо: А=1000 (8, (1, 011)), вхідними регістрами 3 і 4. З вхідних регістрів 3 і 4 В=0010 (2, (0, 010)) (див. табл. 3). числа А і В у двійковому коді надходять на відпоПо шині 1 значення першого операнда А=1000 відні дешифратори 5 і 6. Сигнал, що відповідає надходить на вхід регістра 3, з виходу якого він значенню А (В) в унітарному коді, з виходу дешинадходить на вхід дешифратора 5, з виходу якого фратора 5 рядків (6 стовпців) надходить на один з сигнал, що відповідає значенню А=8 в унітарному двох елементів 7 чи 9 АБО (8 чи 10 АБО), одночакоді, надходить на вхід елемента АБО 9 і на вхід сно, цей сигнал надходить на відповідний елемент третього (8+3=11) елемента АБО першої 12 групи. АБО 12 (АБО 13). Сигнал, що відповідає значенню По шині 2 через регістр 4 на вхід дешифратора 6 аі (bi) в унітарному коді, з виходу двовходового надходить значення другого операнда В=0010. З елемента АБО 12 (13) надходить на ключ 14 рядвиходу дешифратора 6 сигнал, що відповідає знаків (15 стовпців). Керуючий сигнал від пристрою ченню В=2 в унітарному коді, надходить на вхід управління по шині 16 одночасно надходить на елемента АБО 8 і на вхід другого елемента АБО два ключі (рядків 14 та стовпців 15). З виходу двох другої 13 групи. Сигнали з виходів елементів АБО відповідних ключових елементів 14 і 15 два сигна9 і 8 надходять відповідно на одиничний і нульоли одночасно надходять на комутатор 17 (матривий входи суматора 11 за модулем два (табл. 4). цю відповідей). В той же час сигнали з виходу двох За рахунок цього присутній сигнал "1" на одиничелементів АБО 7 чи 9 і АБО 8 чи 10 (див. табл. 4) ному виході суматора 11. Сигнал управління шини надходять на одиничні або нульові входи сумато16 одночасно відкриває третій 14 та другий 15 ра 11 за модулем два. З одиничного або нульовоключові елементи груп, через які сигнали, що виго виходу суматора 11 (у залежності від результазначають значення ai=3 і bi=2, надходять на третій ту модульного додавання ознак  a i і  b i двох (рядок) та другий (стовпець) входи комутатора 17 (табл. 2). Вихідний сигнал комутатора 17 по шостій вхідних операндів A   ai , ai і B  bi , bi у коді (табл. 4) вихідній шині через елемент АБО 21 надтабличного множення) сигнал відкриває 22 і 24 ходить на перший вхід елемента І 24, на другий елементи І або 23 і 25 елементи І. В залежності від вхід якого надходить сигнал "1" одиничного виходу     9 60078 10 суматора 11. Одночасно, вихідний сигнал комутана другий вхід якого надходить сигнал "0" одиничтора 17 через п'ятий (5+6=11) елемент АБО треного виходу суматора 11. Одночасно, вихідний тьої 18 групи надходить на вхід регістра 19, з висигнал комутатора 17 через другий (9+2=11) елеходу якого значення п'ять в унітарному коді мент АБО третьої 18 групи надходить на вхід регінадходить на вхід шифратора 28, з виходу якого стра 19, з виходу якого значення два в унітарному значення 0101 надходить на перші входи елеменкоді надходить на вхід шифратора 28, з виходу тів І першої 29 і другої 30 груп. Вихідний сигнал якого значення 0010 надходить на перші входи елемента І 24 через елемент АБО 27 надходить на елементів І першої 29 і другої 30 груп. Вихідний другі входи елементів І 29, з виходів яких через сигнал елемента І 25 через елемент АБО 26 наделементи АБО четвертої 33 групи значення 0101 ходить на другі входи елементів І 30, з виходів надходить на вихід 34 пристрою. Перевірка: АВ=8 яких значення 0010 надходить на перші входи ін2=5(mod 11). вертора 31, на другі входи яких надходить значенПриклад 2. Припустимо: А=1000 (8, (1, 011)), ня модуля m=1011. З виходу інвертора 31 значенВ=1000 (8, (1, 011)) (див. табл. 3). ня 1011-0010=1001 через елементи АБО четвертої По шині 1 значення першого операнда А=1000 33 групи надходить на вихід 34 пристрою. Перевінадходить на вхід регістра 3, з виходу якого він рка: АВ=8 8=9 (mod 11). надходить на вхід дешифратора 5, з виходу якого Таким чином, технічний результат від впровасигнал, що відповідає значенню А=8 в унітарному дження корисної моделі складається з розширення коді, надходить на вхід елемента АБО 9 і на вхід функціональних можливостей прототипу, за рахутретього (8+3=11) елемента АБО першої 12 групи. нок представлення результату арифметичної опеПо шині 2 через регістр 4 на вхід дешифратора 6 рації АВ (mod m) модульного множення безпосенадходить значення другого операнда В=1000. З редньо у двійковому коді при збереженні всіх виходу дешифратора 6 сигнал, що відповідає знатехнічних можливостей пристрою. Ця обставина ченню В=8 в унітарному коді, надходить на вхід дозволяє, при необхідності, безпосередньо викоелемента АБО 10 і на вхід третього (8+3=11) елеристовувати результат модульного множення у мента АБО другої 13 групи. Сигнали з виходів подальшому ланцюгу обчислень. Відмінною ознаелементів АБО 9 і 10 надходять відповідно на пекою корисної моделі є безпосереднє використання рший і другий одиничні входи суматора 11 за мов алгоритмі виконання модульного множення спедулем два (табл. 4). За рахунок цього присутній ціального коду множення. Завдяки цьому виникає сигнал "0" на нульовому виході суматора 11. Сигможливість виключення з табличного пристрою нал управління шини 16 одночасно відкриває треті модульного множення логічних блоків пошуку, що 14 та 15 ключові елементи груп, через які сигнали, приводить також ще і до спрощення структури що визначають значення аi=3 і bi=3, надходять на пристрою, скороченню обладнання та к підвищентретій (рядок) та третій (стовпець) входи комутаню надійності пристрою у цілому. Необхідно відтора 17 (табл. 2). Вихідний сигнал комутатора 17 значити простоту реалізації в пристрої логічних по дев'ятій (табл. 4) вихідній шині через елемент елементів І та АБО та уніфікацію їх для довільного АБО 21 надходить на перший вхід елемента І 25, модуля m КЛ. Таблиця 1 A B 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 2 4 6 8 10 1 3 5 7 9 3 6 9 1 4 7 10 2 5 8 4 8 1 5 9 2 6 10 3 7 5 10 4 9 3 8 2 7 1 6 6 1 7 2 8 3 9 4 10 5 7 3 10 6 2 9 5 1 8 4 8 5 2 10 7 4 1 9 6 3 9 7 5 3 1 10 8 6 4 2 10 9 8 7 6 5 4 3 2 1 Таблиця 2 i a bi 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 2 4 6 8 10 3 6 9 1 4 4 8 1 5 9 5 10 4 9 3 11 60078 12 Таблиця 3 Число Десятковий код Двійковій код 1 2 3 4 5 6 7 8 9 10 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 Код табличного множення Число Значення індексу  Десятковий код 0 1 0 2 0 3 0 4 0 5 1 5 1 4 1 3 1 2 1 1 Таблиця 4 Вихід елемента Вихід елеменАБО 7 та АБО 9 0 1 Вихід елемен0 та АБО 8 Вихід елемен1 та АБО 10 0 1 1 0 Двійковій код 001 010 011 100 101 101 100 011 010 001 13 Комп’ютерна верстка А. Крижанівський 60078 Підписне 14 Тираж 24 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601