Пристрій для множення по довільному модулю

Пристрій для множення у системі залишкових класів по довільному модулю, який містить вхідні регістри (1), дешифратори (2), першу, другу (3) та третю (8) групи елементів АБО, кожна з яких місP 1 тить елементів АБО (де Р - модуль системи 2 залишкових класів, по якому працює даний пристрій для множення), перший та другий ключі (6), P 1 кожен з яких містить елементів І, комутатор 2 (7), суматор по модулю два (5), елементи І (11) та АБО (4, 10, 12), при цьому перший та другий вхідні регістри послідовно з'єднані з входами відповідно першого та другого дешифраторів, перший та Р-1 виходи першого та другого дешифраторів з'єднані відповідно з першим елементом АБО першої та другої груп елементів АБО (3), другий та Р-2 виходи першого та другого дешифраторів з'єднані відповідно з другим елементом АБО першої та другої P 1 P 1 груп елементів АБО (3), виходи та 2 2 першого та другого дешифраторів з'єднані відпоP 1 відно з елементом АБО першої та другої 2 груп елементів АБО (3), виходи першої та другої груп елементів АБО (3) з'єднані відповідно з першими входами першого та другого ключів (6), другі 2 (19) 1 3 75965 4 тів І третьої та четвертої груп (14), останній вихід Р, другий вхід якого є входом константи модуля Р, шифратора з'єднаний з першими входами n елеперший вихід суматора по модулю Р з'єднаний з ментів І третьої та четвертої груп (14), другі входи другим входом першого елемента АБО четвертої елементів І третьої та четвертої груп (14) з'єднугрупи (16), n-1 вихід суматора по модулю Р з'єднаються відповідно з сьомим та восьмим елементаний з другим входом останнього елемента АБО ми АБО (12), перший вихід четвертої групи елемечетвертої групи (16), n вихід суматора по модулю нтів І (14) з'єднаний з першим входом першого Р з'єднаний з n входом вихідного регістру, перший елемента АБО четвертої групи (16), останній вихід вихід четвертої групи елементів АБО (16) з'єдначетвертої групи елементів І (14) з'єднаний з перний з першим входом вихідного регістру, останній шим входом останнього елемента АБО четвертої вихід четвертої групи елементів АБО (16) з'єднагрупи (16), виходи третьої групи елементів І (14) ний з n-1 входом вихідного регістру. з'єднані з першими входами суматора по модулю Винахід відноситься до обчислювальної техніки і призначений для множення по довільному модулю. Відомий пристрій для множення по довільному модулю, що містить вхідні регістри. дешифратори, групи елементів АБО, групи елементів І, суматор по модулю два, елементи 1 і а АБО, комутатори та вихідний регістр [а.с. СРСР №885999, кл G 06 F 7/72, 1979, Б.В. №77, 1981р.]. Недоліком відомого пристрою є низькі функціональні можливості. Найбільш близьким за технічною суттю і результатом, що досягається, є пристрій для множення по довільному модулю [а.с. СРСР №922731, кл G 06 F 7/52, 1978, Б.В. №15, 1982р.], ще містить вхідні регістри, дешифратори, першу, другу та третю групи елементів АБО які містять P 1 елементів АБО, перший та другій ключі які 2 P 1 містять елементів 1, комутатор, суматор по 2 модулю два, елементи 1 та АБО, при цьому перший та другій вхідні регістри послідовно з'єднані з входами відповідно першого та другого дешифраторів, перший та Р-1 виходи першого та другого дешифраторів з'єднані відповідно з першим елементом АБО першої та другої груп елементів АБО, другий та Р-2 виходи першого та другого дешифраторів з'єднані відповідно з другим елементом АБО першої та другої груп елементів P 1 P 1 АБО, виходи та першого та другого 2 2 P 1 дешифраторів з'єднані відповідно з елемен2 том АБО першої та другої груп елементні АБО, виходи першої та другої груп елементів АБО з'єднані відповідно з першими входами першого та другого ключів, другі входи першого та другого ключів з'єднані з управляючою шиною та є входаP 1 ми керування пристрою, перший, другій та 2 виходи першого та другого дешифраторів підключені відповідно до входів першого та друго P 1 виходи пер2 шого та другого дешифраторів підключені відповідно до входів третього та четвертого елементів АБО, виходи першого, другого, третього та четвертого елементні АБО підключені до відповідних входів суматора по модулю два, виходи першого та другого ключів підключені відповідно до першої та другої груп входів комутатора, перша група виходів комутатора підключена до входів п'ятого елемента АБО та до перших входів третьої груп 11 елементів АБО, друга група виходів комутатора підключена до входів шостого елемента АБО та до других входів третьої групи елементів АБО, вихід п'ятого елемента АБО з'єднаний з першими входами першого та другого елементів І, вихід шостого елемента АБО з'єднаний з першими входами третього та четвертого елементів І, перший вихід суматора по модулю два підключений до других входів першого та третього елементів І, а другий вихід суматора по модулю два підключений до других входів другого та четвертого елементів І, виходи першого та четвертого елементів І з'єднані з входами сьомого елемента АБО, а виходи другого та третього елементів І з'єднані з входами восьмого елемента АБО. Недоліком відомого пристрою є низькі функціональні можливості, які полягають в тому що результат операції множення представляється у коді табличного множення, що в свою чергу не дозволяє безпосередньо використовувати результат модульного множення у подальших обчисленнях електронної обчислювальної машини. В основу винаходу поставлено задачу - розширити функціональні можливості за рахунок вдосконалення пристрою для множення по довільному модулю шляхом представлення результату операції у двійковому коді. Поставлене завдання вирішується тим, що у пристрій для множення у системі залишкових класів по довільному модулю, якій містить вхідні регістри, дешифратори, першу, другу та третю P 1 групи елементів АБО які містять елементів 2 АБО, перший та другій ключі які містять го елементів АБО, а Р-1, Р-2 та 5 75965 6 третьої та четвертої груп, другі входи елементів І P 1 елементів І, комутатор, суматор по модулю третьої та четвертої груп з'єднуються відповідно з 2 сьомим та восьмим елементами АБО, перший два, елементи 1 та АБО, при цьому перший та вихід четвертої групи елементів І з'єднаний з пердругій вхідні регістри послідовно з'єднані з входашим входом першого елемента АБО четвертої ми відповідно першого та другого дешифраторів, групи, останній вихід четвертої групи елементів І перший та Р-1 виходи першого та другого з'єднаний з першим входом останнього елемента дешифраторів з'єднані відповідно з першим елеАБО четвертої групи, виходи третьої групи ментом АБО першої та другої груп елементів АБО, елементів І з'єднані з першими входами суматора другий та Р-2 виходи першого та другого по модулю Р, другий вхід якого є входом константи дешифраторів з'єднані відповідно з другим елемодуля Р, перший вихід суматора по модулю Р ментом АБО першої та другої груп елементів АБО, з'єднаний з другим входом першого елемента АБО P 1 P 1 четвертої групи, n-1 вихід суматора по модулю Р виходи та першого та другого 2 2 з'єднаний з другим входом останнього елемента P 1 АБО четвертої групи, n вихід суматора по модулю дешифраторів з’єднані відповідно з елеменР з'єднаний з n входом вихідного регістру, перший 2 вихід четвертої групи елементів АБО з'єднаний з том АБО першої та другої груп елементів АБО, першим входом вихідного регістру, останній вихід виходи першої та другої груп елементів АБО четвертої групи елементів АБО з'єднаний з n-1 з’єднані відповідно з першими входами першого та входом вихідного регістру. другого ключів, другі входи першого та другого Введення вказаних ознак дозволяє розширити ключів з’єднані з управляючою шиною та є входафункціональні можливості за рахунок представP 1 ми керування пристрою, перший, другій та лення результату операції у двійковому коді. Що в 2 свою чергу дозволяє безпосередньо використовувиходи першого та другого дешифраторів вати результат операції модульного множення підключені відповідно до входів першого та друго(який представлений у двійковому коді) у P 1 подальшій послідовності операцій електронної го елементів АБО, а Р-1, Р-2 та виходи пер2 обчислювальної машини. шого та другого дешифраторів підключені На фіг. 1 представлена блок-схема пристрою відповідно до входів третього та четвертого множення по довільному модулю. Пристрій для елементів АБО, виходи першого, другого, третього множення у системі залишкових класів по та четвертого елементів АБО підключені до довільному модулю містить вхідні регістри 1, девідповідних входів суматора по модулю два, вихошифратори 2, першу, другу 3 та третю 8 групи ди першого та другого ключів підключені P 1 елементів АБО які містять елементів АБО, відповідно до першої та другої груп входів комута2 тора, перша група виходів комутатора підключена перший, другій, третій та четвертий елементи АБО до входів п'ятого елемента АБО та до перших 4, суматор по модулю два 5, перший та другій входів третьої групи елементів АБО, друга група P 1 виходів комутатора підключена до входів шостого ключі 6 які містять елементів 1, комутатор 7, 2 елемента АБО та до других входів третьої групи п’ятий та шостий елементи АБО 10, перший, елементів АБО, вихід п'ятого елемента АБО другій, третій та четвертий елементи І 11, сьомий з'єднаний першими входами першого та другого та восьмий елементи АБО 12, шифратор 13, третю елементів І, вихід шостого елемента АБО та четверту групи елементів І 14, які містять з'єднаний і першими входами третього та четверn=[log2(P-1)]+1 елементів І, суматор по модулю Р того елементів І, перший вихід суматора по моду15, четверту групу елементів АБО 16, яка містить лю два підключений до других входів першого та п-1 елементів АБО, та вихідний регістр 17. третього елементів І, а другий вихід суматора по Вхідні регістри 1 послідовно з'єднані з входами модулю два. підключений до других входів другого своїх дешифраторів 2, перший та Р-1 виходи та четвертого елементів І, виходи першого та четдешифраторів 2 з'єднані відповідно з першим вертого елементів І з'єднані з входами сьомого елементом АБО першої та другої груп елементів елемента АБО, а виходи другого та третього АБО 3, другий та Р-2 виходи дешифраторів 2 елементів І з'єднані з входами восьмого елемента з'єднані відповідно з другим елементо АБО першої АБО, згідно з винаходом введені шифратор. третю P 1 та четверту групи елементів 1, які містять та другої груп елементів АБО 3, виходи та 2 n=[log2(P-1)]+1 елементів I, суматор по модулю Р, четверту групу елементів АБО, яка містить n-1 P 1 дешифраторів 2 з'єднані відповідно з елементів АБО, та вихідний регістр, вихід якого є 2 виходом пристрою, при цьому перший вхід шифP 1 елементом АБО першої та другої груп ратора з'єднаний з виходом першого елемента 2 АБО третьої групи, останній вхід шифратора елементів АБО 3, виходи першої та другої груп P 1 елементів АБО 3 з'єднані відповідно з першими з'єднаний з виходом елемента АБО третьої 2 входами першого та другого ключів 6, другі входи групи, перший вихід шифратора з'єднаний з перпершого та другого ключів 6 з'єднані з управляюшими входами перших елементів І третьої та чою шиною Іупр, та є входами керування пристрою. четвертої груп, останній вихід шифратора з'єднаний з першими входами n елементів І 7 P 1 виходи дешифраторів 2 підключені відповідно до входів першого та другоP 1 го елементів АБО 4, а Р-1, Р-2 та виходи 2 дешифраторив 2 підключені відповідно до входів третього та четвертого елементів АБО 4, виходи першого, другого, третього та четвертого елементів АБО 4 підключені до відповідних входів суматора по модулю два 5. Виходи першого та другого ключів 6 підключені відповідно до першої та другої груп входів комутатора 7. Перша група виходів комутатора 7 підключена до входів п’ятого елемента АБО 10 та до перших входів третьої групи елементів АБО 8, друга група виходів комутатора 7 підключена до входів шостого елемента АБО 10 та до других входів третьої групи елементів АБО 8, вихід п'ятого елемента АБО 10 з'єднаний з першими входами першого та другого елементів І 11, вихід шостого елемента АБО 10 з'єднаний з першими входами третьої о та четвертого елементів І 11, перший вихід суматора по модулю два 5 підключений до других входів першого та третього елементів 1 11, а другий вихід суматора по модулю два підключений до других входів другого та четвертого елементів І 11. Виходи першого та четвертого елементів І 11 з'єднані з входами сьомого елемента АБО 12, а виходи другого та третього елементів І 11 з’єднані з входами восьмого елемента АБО 12. Перший вхід шифратора 13 з'єднаний з виходом першого елемента АБО третьої групи 8, останній вхід шифратора 13 P 1 з'єднаний з виходом елемента АБО третьої 2 групи 8, перший вихід шифратора 13 з'єднаний з першими входами перших елементів І третьої та четвертої груп 14. Останній вихід шифратора 13 з'єднаний з першими входами n елементів І третьої та четвертої груп 14. Другі входи елементів І третьої та четвертої груп 14 з'єднуються відповідно з сьомим та восьмим елементами АБО 12. Перший вихід четвертої групи елементів І 14 з'єднаний з першим входом першого елемента АБО четвертої групи 16, а останній вихід четвертої групи елементів І 14 з'єднаний з першим входом останнього елемента АБО четвертої групи 16. Виходи третьої групи елементів І 14 з'єднані з першими входами суматора по модулю Р 15, другий вхід якого є входом константи модуля Р. Перший вихід суматора по модулю Р 15 з'єднаний з другим входом першого елемента АБО четвертої групи 16, n-1 вихід суматора по модулю Р 15 з'єднаний з другим входом останнього елемента АБО четвертої групи 16, n вихід суматора по модулю Р з'єднаний з n входом вихідного регістру 17. Перший вихід четвертої групи елементів АБО 16 з'єднаний з першим входом вихідного регістру 17. Останній вихід четвертої групи елементів АБО 16 з'єднаний з n-1 входом вихідного регістру 17. Дешифратори 2 призначені для перетворення операндів чисел машинного представлення у операнди десяткового коду. Шифратор 13 призначений для перетворення операндів чисел десяткового коду у операнди чисел машинного представлення. Перший, другій та 75965 8 Суматор по модулю Р 15 призначений інвертування операнду, який поступає з третьої групи елементів АБО 14. Нехай Хі=( х, і,),та Yi=( y,yі,) - вхідні операнди у коді табличного множення, тоді керуючий сигнал буде присутній на сьомому елементі І 12, коли х y, а якщо х= y, тоді керуючий сигнал буде присутній на восьмому елементі І 12. Таким чином суматор 15 по модулю Р буде інвертувати операнд якщо х y. На фіг. 2 представлена блок-схема пристрою множення по модулю Р=11. Наведемо приклад роботи пристрою для модуля Р=11. Входи пристрою модульного множення для операндів Х та Y зв'язуються з цифровою обчислювальною машиною. З вхідних регістрів 1 операнди чисел поступають на свої дешифратори 2. Сигнал з виходу дешифратора 2 строк (стовпців) одночасно поступає на двоходові 3 елементи АБО та п'яти входові 4 елементи АБО. Сигнал з виходу двоходового елемента АБО поступає на першу групу елементів І 6 строк (стовпців). Керуючий сигнал від пристрою керування одночасно поступає на першу групу елементів 1 6 (строк стовпців), та з виходу першої групи елементів І 6 сигнали поступають на комутатор 7. Сигнал з виходу п'ятивходового елемента АБО 4 поступає на одиничний та нульовий входи суматора 5 по модулю два. З одиничного або нульового виходів суматора 5 (в залежності від результатів модульний. додавання) сигнал поступає на два І 11. В залежності від результату модульного множення на один з других входів елементів І 11 поступає сигнал з виходу комутатора через один з двох елементів АБО 10. Вибір одного з двох елементів АБО 10 залежить від того до якої групи операндів (0-5 або 6-10) відноситься результат модульного множення. Алгоритм отримання результату операції визначається наступним сніг відношенням: якщо два числа Х та Y задані по підставі Р у коді табличного множення Хі=( х, і,),та Yi=( y,yі,), то для того щоб отримати добуток цих чисел по модулю Рі, достатньо отримати добуток . (modPі) у коді табличного добуток та і yі інвертувати його індекс , якщо х відрізняється від y, де Рі 1 0, якщо 0 хі 2 . x Рі 1 1 якщо , хіРі 1 2 Сигнал з виходу елемента І 11 поступає на вхід елемента АБО 12, вихід якого з'єднується з першими входами елементів І 14. Цей сигнал представляє код індексу („0" або „І"). Одночасно код результату модульного множення поступає через елемент АБО 8 на вхід шифратора 13, де перетворюється у операнд машинного представлення. Розрядність шифратора визначається формулою n=[log2(P-1)]+1, та дорівнює l=4. З виходу шифратора 13 сигнал поступає на другі входи елементів І 14. В залежності від коду індексу („0" або „І") відчиняється одна з двох груп елементів I 14. Як 9 75965 10 кількість яких визначається формулою n=[log2(Pщо код індексу дорівнює нулю ( =0), тоді сигнал з 1)]+1. Виходи з першого по n-1 з'єднуються з елевиходу елементів І 14 поступає на елементи АБО ментами АБО 16, а останній n-й вихід з'єднується з 16. А якщо код індексу дорівнює одиниці ( =1), тоді входом вихідного регістра 17. Виходи елементів сигнал з виходу елементів І 14 поступає на перАБО 16 також з'єднуються входами вихідного ший вхід суматора 15, на другий вхід якого регістра 17. подається значення модулю Р=11. При цьому суТаким чином у вихідному регістрі буде матор 15 інвертує значення яке подається на його міститься результат операції у машинному коді. перший вхід. Суматор 15 має чотири виходи n=4 Комп’ютерна верстка М. Клюкін Підписне Тираж 26 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601