Спосіб приведення за модулем цілих чисел

Реферат: Спосіб приведення за модулем цілих чисел полягає в оцінці частки за допомогою операцій, які можуть бути попередньо обчислені або менш затратні, ніж ділення багатократної точності. Використовують множення цілих чисел з відкладеним переносом, що реалізує послідовність дії пристроїв "РЕГІСТРА", "ДОДАВАННЯ" та "МНОЖЕННЯ" у двох каналах та додатковим включенням тимчасових змінних. UA 118066 U (12) UA 118066 U UA 118066 U 5 Корисна модель належить до автоматики й обчислювальної техніки і може бути використана в системах криптографічного захисту інформації для розширення їх можливостей. Відомим аналогом є спосіб приведення цілих чисел за модулем, який використовує послідовну дію пристроїв "РЕГІСТРІВ", "ДОДАВАННЯ" та "ДІЛЕННЯ" згідно з алгоритмом ділення в стовпчик [1]. Він може бути використаний для приведення за модулем цілих чисел довільного розміру. На вхід двох каналів пристроїв "РЕГІСТРІВ", "ДОДАВАННЯ" та "ДІЛЕННЯ" подаються число a  (am1,..., ai,..., a1, a0 ) та просте число p  (pn1,..., pi,..., p1, p0 ) , які представлені як набір машинних слів, де ai та pi - відповідні машинні слова чисел a та p , m кількість машинних слів, необхідних для представлення числа a (m  log b a) , n - кількість 10 машинних слів, необхідних для представлення числа p (n  logb p) , b - число, що займає w біт (b  2 w ) , w - розмір машинного слова в бітах (наприклад w=32). Спочатку в "РЕГІСТРІ" виконується ініціалізація залишку r  a . На наступному кроці, якщо виконується умова r  pb m , в пристрої "ДОДАВАННЯ" відбувається вирівнювання r  r  pb m . Основу алгоритму складає 15 20 цикл ділення в стовпчик в інтервалі i  (n  m  1 n] ], на кожній ітерації якого відбуваються , наступні дії. 1. Оскільки залишок r повинен бути менше модуля p , то виконується перевірка ri  pn 1. 2. Якщо умова перевірки в пункті 1 задовольняється, то в пристрої "ДОДАВАННЯ" частка q зменшується на одиницю: q  b  1 . 3. Якщо умова перевірки в пункті 1 не задовольняється, то в пристрої "ДІЛЕННЯ" виконується цілочисельне ділення двох сусідніх машинних слів числа r , на найстарше машинне слово модуля p : q  (rib  ri1)di pn1 . 4. В "РЕГІСТРІ" зберігається тимчасовий результат y  q(pn1b  pn2 ) . 5. В пристрої "ДОДАВАННЯ," якщо виконується умова, що у більше ніж відповідні три сусідні 25 машинні слова залишку ( y  rib 2  ri 1b  ri  2 ) , частка зменшується на одиницю q  q  1 , та в "РЕГІСТРІ" змінюються значення умови y  y  (pn1b  pn2 ) . 6. В пристрої "ДОДАВАННЯ" записується залишок: r  r  qpb i n . 7. Оскільки значення r не може бути від'ємним, то в пристрої "ДОДАВАННЯ" виконується 30 35 40 перевірка r  0 і при необхідності виконується корекція: r  r  qpb i n . За допомогою пристрою "ДІЛЕННЯ" на виході "РЕГІСТРА" отримуємо результат r  a mod p(r  p) . Недоліком аналога є те, що приведення цілих чисел за модулем, яке базується на основі ділення в стовпчик, вимагає великої кількості операцій складання ділення, додавання та присвоєння, що виконуються за допомогою послідовної дії пристроїв "ДОДАВАННЯ", "ДІЛЕННЯ" та "РЕГІСТР", тому при приведенні великих цілих чисел за модулем він буде повільним у часі. Найближчим аналогом до корисної моделі є спосіб приведення цілих чисел за модулем [2], що ґрунтується на оцінці частки a div p, за допомогою операцій, які можуть бути попередньо обчисленні або менш затратні, ніж ділення багатократної точності. Цей спосіб може бути використаний для приведення за модулем цілих чисел довільного розміру. На вхід пристроїв "РЕГІСТРІВ", "ДОДАВАННЯ", "МНОЖЕННЯ" та "ДІЛЕННЯ" подаються число a  (am1,..., ai,..., a1, a0 ) та просте число p  (pn1,..., pi,..., p1, p0 ) , які представлені як набір машинних слів, де ai та pi - відповідні машинні слова чисел a та p , m - кількість машинних слів, необхідних для представлення числа a (m  log b a) , n - кількість машинних слів, необхідних для представлення числа p (n  log b p) , b - число, що займає w (b  2 w ) , w 45 розмір машинного слова в бітах (наприклад w=32). Число а знаходиться в інтервалі 0  a  b2k , де k  logb p  1 . Для виконання операції приведення за модулем, необхідно виконати  2k  попереднє обчислення в пристрої "ДІЛЕННЯ" та зберегти "РЕГІСТРІ" константу    b  . Після  p    цього необхідно в пристроях "МНОЖЕННЯ", "ДІЛЕННЯ" та "РЕГІСТРІВ" виконати оцінку частки  q  ((adi bk 1)  )dibk 1 . Далі, використовуючи тимчасові "РЕГІСТРИ" r1 та r2 ,   1 UA 118066 U  вираховуються проміжні значення r1  (a mod bk 1) та r1  (q  p mod bk 1) за допомогою пристроїв "ДІЛЕННЯ". Для обчислення залишку r в пристрої "ДОДАВАННЯ" виконується віднімання: r  r1  r2 . Для врахування переносу (якщо r  0 ) в пристрої "ДОДАВАННЯ" 5 10 15 20 25 30 35 40 виконується операція: r  r  bk 1 значення якої записується до "РЕГІСТРУ". У випадку, якщо отриманий залишок r  p , в пристрої "ДОДАВАННЯ" виконується корекція r r  p , доки r не стане менше p . На виході "РЕГІСТРА" за допомогою пристрою "ДІЛЕННЯ" записується результат r  a mod p(r  p) . Недоліками найближчого аналога є те, що для виконання операцій множення використовується алгоритм, який має високу внутрішню зв'язність, потребує врахування переносів при накопиченні суми та не дозволяє ефективно виконувати спарювання операцій на сучасних суперскалярних процесорах. В основу корисної моделі поставлена задача створення способу приведення за модулем цілих чисел, який за рахунок використання способу множення цілих чисел з відкладеним переносом [3] дозволив би виконувати меншу кількість операцій, що в свою чергу забезпечує зменшення часу на отримання результату обчислення за допомогою послідовної дії пристроїв "РЕГІСТРА", "ДОДАВАННЯ" та "ДІЛЕННЯ". Поставлена задача вирішується тим, що для отримання можливості зниження обчислювальної складності та зменшення часу на отримання результату приведення за модулем цілих чисел завдяки позбавленню необхідності враховують перенос після кожної арифметичної операції за допомогою послідовної дії пристроїв "РЕГІСТРА", "ДОДАВАННЯ" та "ДІЛЕННЯ", згідно з алгоритмом приведення за модулем цілих чисел з використанням відкладеного переносу. Суть запропонованого способу приведення за модулем цілих чисел полягає в виконанні процедури множення за допомогою способу множення цілих чисел [3], в якому реалізовано відкладений перенос - для зберігання w-розрядних змінних використовуються 2w-розрядні змінні, що дозволяє позбавитися від обліку переносу з w-розрядної змінної, після кожної арифметичної операції. Перенос накопичується в старшій частині 2w-розрядної змінної і може бути врахований при необхідності, який відрізняється від способу-прототипу додатковим включенням тимчасових змінних, які зберігаються у відповідних пристроях "РЕГІСТРАХ", та виконанням над ними послідовної дії пристроїв "МНОЖЕННЯ" та "ДОДАВАННЯ". В пристроях "РЕГІСТР" та "ДОДАВАННЯ" запропонована реалізація відкладеного переносу, яка дозволяє незалежно проводити складання результатів відповідних добутків у стовпчиках, що дає можливість накопичувати суми старших і молодших розрядів окремо. Після завершення накопичення суми на кожній ітерації циклу, для формування результату необхідно виконати корегування (врахувати перенос) за допомогою пристрою "ДОДАВАННЯ": r1  r1  Hi (r0 ) , r2  r2  Hi (r1) і сформувати результат ci  low (r0 ) . На вхід "РЕГІСТРУ" подається число a  (an21,..., ai,..., a1, a0 ) , яке представлено як добуток цілих чисел d і f , та просте число p  (pg1,..., pi,..., p1, p0 ) . Числа a та p подаються у пристрої "МНОЖЕННЯ" у вигляді наборів машинних слів, де ai та pi - відповідні машинні слова чисел a та p , n2 - кількість машинних слів, необхідних для представлення числа a (n2  logb a) , g 45 50 кількість машинних слів, необхідних для представлення числа p (g  logb p) , n - кількість машинних слів, необхідних для представлення чисел d та f (n  log 2 w d  log 2 w f ) , b - число, що займає w біт (b  2 w ) , w - розмір машинного слова в бітах (наприклад w=32). Для виконання операції приведення за модулем в пристрої "ДІЛЕННЯ" виконується попереднє  2k  обчислення константи    b  та збереження результату в "РЕГІСТРІ".  p    Після цього, в пристроях "РЕГІСТР", "МНОЖЕННЯ" і "ДОДАВАННЯ" двох каналів послідовно виконуються часткові множення за допомогою способу множення цілих чисел, з використанням 2 UA 118066 U відкладеного переносу. Перед кожним частковим множенням відбувається ініціалізація 2w – w w розрядних тимчасових змінних r ( 2 ) та r (2 ) в "РЕГІСТРАХ": 0 1 w 5 w ( ( r02 )  0, r12 )  0 . Основу першого часткового множення складають два цикли в пристроях "МНОЖЕННЯ" та "ДОДАВАННЯ" формування результату множення. Перший канал пристроїв "ДОДАВАННЯ" формується в інтервалі x  [0, n2) та в пристроях "МНОЖЕННЯ" в інтервалах i  [k  1 kn 2) та , j  [ x, kn 2  k  1) , де kn 2  min( k  x; n2) . Другий канал пристроїв "ДОДАВАННЯ" формується в інтервалі x  [n2, n3) з використанням допоміжного інтервалу e  [k, k  n) , де n3  n  n2 , та в пристроях "МНОЖЕННЯ" в інтервалах 10 i  [e, n2) та j  [n2  1 e  1) . У вкладених каналах , пристроїв "МНОЖЕННЯ" виконується множення (u)(2w )  a( w )  ( w ) результатом якого є ціле i j число розміром 2w, яке потім розділяється в "РЕГІСТРАХ" на два w - розрядних u( w ) і  ( w ) . Накопичення відкладеного переносу відбувається в "РЕГІСТРАХ" в старших частинах 2ww w розрядних тимчасових змінних r ( 2 ) та r (2 ) на кожній ітерації: 0 1 ( r02 15 w ) w (  r02 w )  ( w ) , w ( ( r12 )  r12 )  u( w ) . На кожній ітерації циклу формування результату в пристроях "РЕГІСТРУ", "ДОДАВАННЯ" та "МНОЖЕННЯ" виконується корегування (врахування переносу):   ,  hi r ( q( w )  low( w ) r02w ) , k w 20 w ( ( ( 2w ) r12 )  r12 ) (w) 0 та відбувається зміна тимчасових змінних r0 та r1 :   r . ( w ( r02 )  low ( w ) r12w ) , w 25 ( ( r12 )  hi( w ) 12w ) Отримане в результаті першого часткового множення значення q використовується в другому частковому множенні. Основу другого часткового множення також складають два канали формування результату множення. Перший канал в пристрої "ДОДАВАННЯ" формується в інтервалі x  [0, n) та в пристроях "МНОЖЕННЯ" в інтервалах x  [0, n] та j  [ x,0] . Другий канал пристроїв "ДОДАВАННЯ" формується в інтервалі x  [n, k  1) з використанням допоміжного інтервалу e  [1 k  n) , та в пристроях "МНОЖЕННЯ" в інтервалах , i  [e, n) та j  [n  1 e  1) . У вкладених каналах пристроїв "МНОЖЕННЯ" виконується множення , 30 ) (u)(2w )  q( w1i  p(j w ) результатом якого є ціле число розміром 2w, яке потім розділяється на k два w - розрядних u( w ) і  ( w ) . Накопичення відкладеного переносу відбувається в "РЕГІСТРАХ" w w в старших частинах 2w - розрядних тимчасових змінних r ( 2 ) та r ( 2 ) на кожній ітерації: 0 1 ( r02 w w 35 ) (  r02 w )  ( w ) , w ( ( r12 )  r12 )  u( w ) . На кожній ітерації циклу формування результату в пристроях "РЕГІСТРУ", "ДОДАВАННЯ" та "МНОЖЕННЯ" виконується корегування (врахування переносу):   .  hi r ( q( w)  low( w) r02w) , x w w ( ( ( 2w ) r12 )  r12 ) (w) 0 та відбувається зміна тимчасових змінних r0 та r1 : 40     ( w ( ( w ( r02 )  low ( w ) r12w ) , r12 )  hi( w ) r12w ) . 3 UA 118066 U По завершенні двох часткових множень в "РЕГІСТРІ" за допомогою пристрою "МНОЖЕННЯ"   відбувається формування найстаршого значення q( w )  low( w ) r (2w ) . k 1 0 В пристроях "РЕГІСТР" і "МНОЖЕННЯ" враховується можливий перенос за допомогою пристрою "ДОДАВАННЯ" визначається значення індексу j (j знаходиться в інтервалі [k,0] ) для 5 якого перестає виконуватися умова q( w )  a( w ) . В пристрої "РЕГІСТР" за допомогою пристроїв j j "ДОДАВАННЯ", якщо q(j w )  a(j w ) і "ДІЛЕННЯ" враховується перенос у великому числі r  (2 w )k 1  a mod( 2 w )k 1 , 10 15 20 25 30 35 інакше перенос не враховується у великому числі r  a mod( 2 w )k 1 . Для обчислення залишку c , в пристрої "ДОДАВАННЯ" виконується віднімання одного великого числа від іншого: c  r  q . У випадку, якщо отриманий залишок c  p , в пристрої "РЕГІСТР" за допомогою пристрою "ДОДАВАННЯ" виконується корекція c  c  p , доки r не стане менше p . На виході "РЕГІСТРУ" за допомогою пристрою "ДІЛЕННЯ" отримується результат c  a mod p . Таким чином, за рахунок додаткового включення тимчасових змінних, які зберігаються у відповідних пристроях, та виконанням над ними послідовної дії пристроїв "РЕГІСТРІВ", "ДОДАВАННЯ", "МНОЖЕННЯ" та "ДІЛЕННЯ" цілих чисел, вдається зменшити кількість виконуваних операцій та зменшити час отримання результату обчислення приведення за модулем цілих чисел довільної довжини. Джерело інформації: 1. Bosselaers A., Govaerts R., Vandewalle J. Comparison of three modular reduction functions. Advances in Cryptology-CRYPTO' 93. Springer Berlin Heidelberg, pp. 175-186. 2. Barrett P.D. Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor, " Advances in Cryptology, Proc.Crypto'86, LNCS 263, A.M. Odlyzko, Ed., Springer-Verlag, 1987, pp. 311-323. 3. Пат. 111632 Україна, МПК G06F 7/253 (2006.01). Спосіб множення цілих чисел / А.О.Охріменко, В.Ю.Ковтун, М.Г.Ковтун, С.П.Євсеев, О.Г.Король, С.Ю.Ковтун. - № u201511473; заявл. 23.11.2015; опублік. 25.11.2016, Бюл. № 22. ФОРМУЛА КОРИСНОЇ МОДЕЛІ Спосіб приведення за модулем цілих чисел, що полягає в оцінці частки за допомогою операцій, які можуть бути попередньо обчислені або менш затратні, ніж ділення багатократної точності, який відрізняється тим, що використовують множення цілих чисел з відкладеним переносом, що реалізує послідовність дії пристроїв "РЕГІСТРА", "ДОДАВАННЯ" та "МНОЖЕННЯ" у двох каналах та додатковим включенням тимчасових змінних, що дозволяє зменшити час отримання результату обчислення приведення за модулем цілих чисел довільної довжини. Комп’ютерна верстка В. Мацело Міністерство економічного розвитку і торгівлі України, вул. М. Грушевського, 12/2, м. Київ, 01008, Україна ДП “Український інститут інтелектуальної власності”, вул. Глазунова, 1, м. Київ – 42, 01601 4