Ви є тут

Алгоритми модулярної арифметики великих чисел

Автор: 
Мекуш Оксана Григорівна
Тип роботи: 
Дис. канд. наук
Рік: 
2005
Артикул:
0405U003919
129 грн
Додати в кошик

Вміст

РОЗДІЛ 2
Модулярне експоненціювання
В системах захисту інформації з відкритими ключами, таких як RSA [33],
Ель-Гамаля [34], Діффі-Хелмана [35] та інших [36-40] однією з найбільш
використовуваних і часовитратною є операція модулярного експоненціювання, що
висуває на перший план важливе завдання - прискорення виконання даної операції.
Підвищити швидкість виконання різних операцій можна двома шляхами: зарахунок
покращення апаратного або/та програмного забезпечення комп’ютерних систем. В
даній роботі зупинимось детально на другому напрямку – розробці швидких
алгоритмів модулярного експоненціювання.
Ця проблема привернула до себе багато уваги, але результати нових досліджень не
систематизовані і не класифіковані, тому в цьому розділі розглянемо відомі
методи швидкого експоненціювання, оцінимо їх складність, проаналізуємо відносні
переваги і недоліки, а також удосконалимо швидкий паралельний метод
експоненціювання, що базується на представленні експонент з допомогою лінійних
форм.
Примітивний метод обчислення , де , -деяка група, вимагає множення, але
розроблено багато методів експоненціювання, для яких піднесення до степеня
можна виконати за значно меншу кількість кроків. Хоча методи розглянуті нижче
можна застосувати для будь-якої групи і, навіть, півгрупи, ми працюватимемо з
модулярним експоненціюванням, тобто експоненціюванням в групі лишків ().
Методи модулярного експоненціювання будемо розглядати в наступній,
запропонованій автором класифікації:
1) загальні методи, де основа і експонента -довільні;
2) з фіксованою експонентою, де експонента -фіксована, а основа -довільна;
3) з фіксованою основою, де основа -фіксована, а експонента -довільна;
4) методи, що базуються на особливостях модуля ;
5) з перекодуванням експоненти;
6) паралельні методи.
2.1 . Загальні методи обчислення
Більшість загальних методів експоненціювання, тобто методів, які не
використовують ніяких особливостей експонент або основи експоненціювання, і,
таким чином, можуть в згальному застосовуватись, можна розглядати як деякий
варіант методу ковзаючих вікон. Цей метод базується на деякому блоковому
розбитті бінарного представлення експоненти . Блоки називають вікнами. Існує
кілька варіантів цього методу, які визначаються розбиттям і скануванням вікон,
а також методом модулярного множення. Вікна можуть приймати прийняті раніше
значення або будуватись адаптивним способом. Вони можуть зчитуватись зліва
направо або навпаки. Модулярне множення може виконуватись з допомогою
звичайного множення поєднаного з модулярною редукцією або із застосуванням
множення по методу Монтгомері.
2.1.1. Методи ковзаючих вікон зліва направо
Будь-який метод ковзаючих вікон зліва направо базується на розбитті: , де є
деяким блоковим розбиттям бінарного представлення експоненти . Застосуємо
звичайну стратегію вибору вікон, тобто, щоб результуючі значення вікон належали
фіксованій множині . Маємо наступний алгоритм.
Алгоритм 2.1. Модулярне експоненціювання з допомогою ковзаючих вікон зліва
направо (експонента зчитується зліва направо).
На вході: , , і ;
На виході: .
1. Для всіх обчислити ;
2. ;
3. ;
4. поки робити:
4.1. знайти відповідний бітовий рядок :;
для до робити: ;
;
.
Обчислення для всіх може бути ефективно виконане з використанням адитивних
ланцюжків (підроділ 2.2).
Розглянемо деякі найбільш важливі можливості вибору множин і відповідні їм
вікна.
Ё. В цьому випадку і ми отримали так званий бінарний метод експоненціювання
зліва направо. Він вимагає піднесень до квадрату і множень, де -вага Хемінга,
яка визначає кількість одиничних біт в бінарному представленні . Бінарний метод
експоненціювання зліва направо також називають “піднеси до квадрату і
перемнож”, оскільки він базується на повторенні піднесень до квадрату і
множень. Йому більше ніж 2000 років. В [17] найбільш повно викладено історію та
бібліографію методу.
Ё, для деякого . Параметр приймається як розмір вікна. Цей варіант був
запропонований Тербером (Thurber) [41] в термінах адитивних ланцюжків,
використовуючи два види вікон: нульові вікна, що складаються лише з нулів, і
непарні вікна, які починаються з 1 і мають довжину не більше . В цьому випадку
крок 1 алгоритму 1 заміняється наступним:
1.1. ;
1.2. ;
1.3. ;
1.4. для до крок 2 робити .
Крок 4.1. заміняється на:
4.1. якщо то інакше знайти найдовший бітовий рядок такий, що і .
Обчислювальна складність даного алгоритму буде: множень (крок 1), піднесень до
квадрату (крок 4.2) і множень (крок 4.3).
Ё для деяких і -непарного, . Цей випадок був розглянутий Мюллером (Mцller) [42]
як альтернатива до методу ковзаючих вікон, які використовують тільки нульові і
непарні вікна в деякому середовищі з обмеженою пам’яттю. Іноді доступна пам’ять
є більшою, ніж потрібно для методу ковзаючих вікон з вікном розміру , але її
недостатньо для вікна розміру . Щоб використати переваги більшого вікна,
потрібно намагатись застосувати метод, наведений вище з вікном розміру , допоки
обчислені значення вікон знаходяться в передобчисленому діапазоні. В цьому
випадку, крок 1 алгоритму1 заміняється наступним кроком:
;
;
;
для до крок 2 робити .
Крок 4.1. заміняється на:
4.1. якщо то інакше знайти найдовший бітовий рядок такий, що і і . Отриманий
таким способом метод називають методом ковзаючих вікон зліва направо з
фракційними вікнами.
Ё, для деякого . Цей варіант був запропонований Брауером (Brauer) [43] в
термінах адитивних ланцюжків, використовуючи лише вікна довжиною . В цьому
випадку крок 1 алгоритму 1 заміняється наступним:
1.1. ;
1.2. для до робити ;
а крок 4.1. буде: .
Отриманий метод називається -арним зліва направо аб