Спосіб множення цілих чисел

Реферат: Спосіб множення цілих чисел, при якому виконують процедуру множення двох цілих чисел, який використовує послідовну дію пристроїв "МНОЖЕННЯ", "РЕЄСТР ЗСУВУ" та "ДОДАВАННЯ" у двох каналах згідно з алгоритмом множення. Додатково включають тимчасові змінні, які зберігаються у відповідних пристроях циклів "РЕЄСТР ЗСУВУ", та виконують над ними послідовну дію пристроїв "МНОЖЕННЯ" та "ДОДАВАННЯ". UA 111632 U (12) UA 111632 U UA 111632 U 5 Корисна модель належить до автоматики й обчислювальної техніки і може бути використана в системах криптографічного захисту інформації для розширення їх можливостей. Відомий спосіб множення двох цілих чисел, який використовує послідовну дію пристроїв "МНОЖЕННЯ" згідно алгоритму множення в стовпчик [1]. Він може бути використаний для множення двох чисел довільного розміру. На вхід подаються два числа a  (an, ..., ai , ..., a1, a0 ) та b  (bn, ..., bi , ..., b1, b0 ) де ai і bi - машинні слова чисел a і b , де n - кількість машинних слів, необхідних для представлення числа (n  log w a) , w - розмір машинного слова в бітах. 2 Далі у першому пристрої "МНОЖЕННЯ" частина машинних слів a i (i  0, n) послідовно, 10 15 20 рядками, перемножується на всі частини другого множника b j ( j  1 n) . Проміжний результат , множення a i і b j формується з урахуванням всіх переносів. Кожен проміжний результат зміщується вліво на w-біт в пристрої "РЕЄСТР ЗСУВУ", а потім всі проміжні результати послідовно додаються в пристрої "ДОДАВАННЯ". На фіг. 1 зображене множення двох чисел у стовпчик, для n  3 . Недоліком цього способу є те, що множення двох цілих чисел, що базується на основі множення в стовпчик, вимагає великої кількості операцій множення в стовпчик, що виконуються за допомогою послідовної дії пристроїв "МНОЖЕННЯ", тому при множенні великих чисел він буде повільним у часі. Найбільш близьким до запропонованого технічним рішенням, вибраним як прототип, є спосіб множення цілих чисел Comba [2], що ґрунтується на виконанні процедури множення в стовпчик, за допомогою послідовної дії пристроїв "МНОЖЕННЯ", "РЕЄСТРУ ЗСУВУ" та "ДОДАВАННЯ". На вхід пристроїв "МНОЖЕННЯ" подаються два числа a і b , які наведені як набір машинних слів a  (an, ..., ai, ..., a1, a0 ) та b  (bn, ..., bi, ..., b1, b0 ) , де n - кількість машинних слів, необхідних для представлення числа (n  log w a) , w - розмір машинного слова в бітах. На 2 25 виході пристрою "МНОЖЕННЯ" отримується результат c  a  b розміром 2n машинних слів. Даний спосіб реалізує алгоритм множення в стовпчик з невеликою різницею: перемножується частина множника ai (I  0, n) на всі частини іншого множника b j ( j  1 n) , в порядку виконання , умови (I  j  k ) у стовпчиках, а не послідовно по рядках. Основу "МНОЖЕННЯ" складають два канали пристроїв які реалізують два цикли формування результату множення. Перший пристрій   формує результат в інтервалі k  1 n та містить реалізацію циклу множення в інтервалах , 30       I  0, k та j  k, 0 . Другий пристрій формує результат в інтервалі k  n, 2n  1 з використанням допоміжного інтервалу     l  1, n  1   та містить реалізацію вкладеного циклу множення в інтервалах i  l, n  1 та j  k  l, n  l . У вкладених пристроях за допомогою пристрою "РЕЄСТР ЗСУВУ" обчислюється добуток (uv )( 2 w )  a( w )  b( w ) , результатом якого є 2w - розрядне ціле i i 35 число, яке потім розділяється на два w - розрядних u( w ) і v( w ) числа. Накопичення суми відбувається в пристрої "ДОДАВАННЯ" та "РЕЄСТР ЗСУВУ" w - розрядних тимчасових змінних r0 , r1 і r2 на кожній ітерації: ( ( r0w )  r0w )  v ( w ) ( ( r1 w )  r1 w )  u( w )  carry, carry  0 40 ( ( r2w )  r2w )  carry, carry  0. Присвоєння кінцевого результату, а також зміна акумуляторів суми r0 , r1 і r2 , відбувається в пристрої "ДОДАВАННЯ" на кожній ітерації циклу формування результату: ( c ( w )  r0w ), k ( ( r0w )  r1 w ), ( ( r1 w )  r2w ), 45 ( r2w )  0. 1 UA 111632 U Після завершення циклів формування результату в пристрої "ДОДАВАННЯ" відбувається 5 ) ( обчислення c ( w1  r0w ) . 2n На виході пристрою "МНОЖЕННЯ" формується ціле число c  (c2n1, ..., ck , ..., c1, c0 ) . На фіг. 2 зображене множення двох чисел способом Comba, для n  3 . Недоліками даного способу є те, що множення цілих чисел вимагає великої кількості операцій в пристроях "МНОЖЕННЯ" та "ДОДАВАННЯ" з накопиченням суми з переносом в w бітних тимчасових змінних r0 , r1 і r2 в пристроях "РЕЄСТР ЗСУВУ"; його висока внутрішня 30 зв'язність з урахуванням переносів між r0 , r1 і r2 , що не дозволяє виконувати спарювання таких операцій на сучасних суперскалярних процесорах. В основу способу поставлена задача створення способу множення цілих чисел, який дозволив би виконувати меншу кількість операцій за допомогою послідовної дії пристроїв "МНОЖЕННЯ", "РЕЄСТР ЗСУВУ" та "ДОДАВАННЯ" цілих чисел, згідно алгоритму множення цілих чисел з використанням відкладеного переносу. Технічний результат, який може бути отриманий при здійснені способу полягає в отриманні можливості зниження обчислювальної складності завдяки позбуття необхідності враховувати перенос після кожної арифметичної операції за допомогою послідовної дії пристроїв "МНОЖЕННЯ", "РЕЄСТР ЗСУВУ" та "ДОДАВАННЯ" цілих чисел, згідно алгоритму множення цілих чисел. Сутність запропонованого способу множення цілих чисел полягає в виконанні процедури множення, за допомогою послідовної дії пристроїв "МНОЖЕННЯ", "РЕЄСТР ЗСУВУ" та "ДОДАВАННЯ" згідно алгоритму множення, який відрізняється від способу-прототипу додатковим включенням тимчасових змінних, які зберігаються у відповідних пристроях "РЕЄСТР ЗСУВУ", та виконанням над ними послідовної дії пристроїв "МНОЖЕННЯ" та "ДОДАВАННЯ". В пристрої "РЕЄСТР ЗСУВУ" та "ДОДАВАННЯ" запропонована реалізація відкладеного переносу, яка дозволяє незалежно проводити складання результатів відповідних добутків у стовпчиках, що дає можливість накопичувати суми старших і молодших розрядів окремо. Після завершення накопичення суми на кожній ітерації циклу, для формування результату необхідно виконати корегування (врахувати перенос) за допомогою пристрою "ДОДАВАННЯ": r1  r1  Hi (r0 ) , 35 r2  r2  Hi (r1) і сформувати результат ci  low (r0 ) . На фіг. 1 наведено множення двох чисел в стовпчик, для n  3 . На фіг. 2 наведено множення двох чисел способом Comba, для n  3 . На фіг. 3 показана реалізація відкладеного переносу. На фіг. 4 показана графічна інтерпретація циклу формування результату 10 15 20 25   запропонованого способу множення в інтервалі k  0, n для n  3 . На фіг. 5 показана графічна інтерпретація циклу формування результату запропонованого способу множення в інтервалі  40 45  k  n, 2n  1 для n  3 . На вхід пристрою "МНОЖЕННЯ" подається два великих числа a і b , які представляються у вигляді машинних слів a  (an, ..., ai, ..., a1, a0 ) та b  (bn, ..., bi, ..., b1, b0 ) розміром w -біт, n кількість машинних слів необхідних для представлення чисел a і b . На виході отримуємо результат c  a  b розміром 2n машинних слів. Основу вказаного способу множення складають пристрої "МНОЖЕННЯ", "РЕЄСТР ЗСУВУ" та "ДОДАВАННЯ" які реалізують цикли формування результату множення. Пристрої першого   циклу формує результат в інтервалі k  0, n та містить вкладений цикл множення в інтервалах     i  [0, k ] та j  0,k . Пристрої другого циклу формують результат в інтервалі k  n, 2n  1 з   використанням допоміжного інтервалу l  1, n  1 та містить вкладений цикл множення в інтервалах   i  l, n та j  k  l, n  l . У вкладених пристроях за допомогою пристрою "МНОЖЕННЯ" обчислюється добуток (uv )( 2 w )  a( w )  b( w ) результатом якого є 2w -розрядне i i 50 ціле число, яке потім розділяється на два w -розрядних u( w ) і v( w ) числа. Накопичення суми відбувається в пристрої "ДОДАВАННЯ" w -розрядних тимчасових змінних r0 , r1 і r2 на кожній ітерації: 2 UA 111632 U ( ( r02 w )  r02 w )  v ( w ), r ( 2 w )  r ( 2 w )  u( w ) . 1 1 В пристрої "РЕЄСТР ЗСУВУ" на кожній ітерації циклу формування результату виконується корегування (врахування переносу) з використанням 2w -розрядних тимчасових змінних r1 та 5 r2 ( r2 заздалегідь проініціалізована): ( ( ( r12w)  r12w)  hi( w)(r02w) ) , ( ( ( r22w)  r22w)  hi( w)(r12w) ) та відбувається присвоєння кінцевого результату і зміна тимчасових змінних r0 , r1 і r2 ( c( w )  low( w )(r02w ) ) , k 10 ( ( r02w)  low( w)(r12w) ) , ( ( r12w)  low( w)(r22w) ) , ( r22 w )  0 . Наприкінці в пристрої "ДОДАВАННЯ" відбувається формування результату ) ( c( w1  low( w)(r02w) ) . 2n 15 Результатом множення є ціле число c  (c2n1, ..., ck , ..., c1, c0 ) . На фіг. 4 показана графічна інтерпретація циклу формування результату пристроями   "МНОЖЕННЯ", "РЕЄСТР ЗСУВУ" та "ДОДАВАННЯ" в інтервалі k  0, n , а на фіг. 5 показана графічна інтерпретація циклу формування результату пристроями "МНОЖЕННЯ", "РЕЄСТР  20 25 30  ЗСУВУ" та "ДОДАВАННЯ" в інтервалі k  n, 2n  1 для запропонованого способу множення при n  3 , де чітко простежуються складання результатів відповідних добутків за стовпчиками. Таким чином, за рахунок додаткового включення тимчасових змінних, які зберігаються у відповідних пристроях, та виконанням над ними послідовної дії пристроїв "МНОЖЕННЯ", та "ДОДАВАННЯ" цілих чисел, вдається зменшити кількість виконуваних операцій та зменшити час отримання результату обчислення множення двох цілих чисел довільної довжини. Джерела інформації: 1. Handbook of Elliptic and Hyperelliptic Curve Cryptography / Henri Cohen, Gerhard Frey, Roberto Avanzi, Christophe Doche, Tanja Lange, Kim Nguyen, and Frederik Vercauteren. - Chapman & Hall/CRC.-2005. - P. 848. 2. Comba, P. G. Exponentiation cryptosystems on the IBM PC // IBM Systems Journal.-1990. Vol. 29. - No. 4, December 1990. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 35 Спосіб множення цілих чисел, при якому виконують процедуру множення двох цілих чисел, який використовує послідовну дію пристроїв "МНОЖЕННЯ", "РЕЄСТР ЗСУВУ" та "ДОДАВАННЯ" у двох каналах згідно з алгоритмом множення, який відрізняється тим, що додатково включають тимчасові змінні, які зберігаються у відповідних пристроях циклів "РЕЄСТР ЗСУВУ", та виконують над ними послідовну дію пристроїв "МНОЖЕННЯ" та "ДОДАВАННЯ". 3 UA 111632 U 4 UA 111632 U Комп’ютерна верстка М. Мацело Державна служба інтелектуальної власності України, вул. Василя Липківського, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут інтелектуальної власності”, вул. Глазунова, 1, м. Київ – 42, 01601 5