Існуючі методи алгоритмів модулярної редукції надвеликих чисел, їх порівняльний аналіз з метою визначення найбільш швидкодіючих. Новий паралельний алгоритм модулярного експоненціювання надвеликих чисел. Порівняльний аналіз методів модулярної редукції.
Аннотация к работе
Київський університет імені тараса ШевченкаЗахист відбудеться "24" червня 1999 р. на засіданні спеціалізованої вченої ради Д 26.001.09 Київського університету імені Тараса Шевченка, м.Київ, пр.Академіка Глушкова 6, корп. Тому зараз акцент в проблематиці захисту інформації зосередився на системах з відкритими ключами. Системи з відкритими ключами базуються не на принципах таємності всіх ключів, а на принципі неможливості перехоплювачу виконати дуже великий обсяг обчислювальних робіт. Системи з відкритими ключами дозволяють створити зручну та гнучку структуру сучасних систем захисту інформації. Вони також знайшли застосування у вирішенні великої кількості задач з нетрадиційними раніше постановками: цифровий підпис, аутентифікація віддалених обєктів, прийняття рішень сторонами, які не мають довіри один до одного, доведення володіння інформацією без розкриття самої інформації та багато інших.У вступі обгрунтовується актуальність тематики досліджень, повязаної з широким розповсюдженням систем захисту інформації, базуючих на ключах загального доступу, визначається місце тематики досліджень дисертації у колі задач захисту інформації та приводиться стислий опис основних результатів роботи. В першій главі дається огляд парадігми, яка використовується в системах захисту даних, базованих на ключах загального доступу. В розділі 1.1. викладаються основні теоретичні концепції систем захисту інформації у компютерних мережах, які базовані на ключах загального доступу. Пряме обчислення таких функцій досить просте, але обернені задачі - розкласти задане велике число на множники; обчислення кореня - знайти x, маючи y, u та m, де y = xu mod m; задача дискретних алгоритмів - знайти u, маючи y, x та m , де y = xu mod m, у наш час компютерно не можуть бути обчисленими при великих числах y, x та m. Нехай модуль m має вигляд m = , 0 <mk-1 <b i 0 ЈЈ mi <b, для i = 0,1,..., k-2, а аргумент x x = , 0 <xk-1 <b і 0 ЈЈ xi <b, для i = 0,1,..., l-2, У розділі 3.1. ми розглядаємо чотири з пяти загальних методів модулярної редукції: класичний метод, метод Баррета, метод Кнута - Флойда та метод А.В.Анісімова.У параграфі 4.1. згадується відомий послідовний бінарний метод обчислення xd mod m. Також наводяться табличні дані обчислення xy mod m з використанням вище наведених пяти методів модулярної редукції. Новий паралельний алгоритм обчислення xy mod m запропоновано у наступному розділі 4.2. Це дає алгоритм з більшим збалансованим завантаженням при виконанні на двох процесорах. Спеціальний алгоритм, який дає високий ступінь паралельної обробки, дано у параграфі 4.3.Визначено особливості пяти методів модулярної редукції, а саме класичного методу, методу Баррета, методу Кнута - Флойда, методу Монтгомері та методу А.В.Анісімова. Цей алгоритм узагальнює бінарний алгоритм Чіоу на випадок довільного базиса системи обчислення. Запропоновано новий рекурсивно-паралельний алгоритм обчислення модулярної редукції, базований на застосуванні лінійних форм Фібоначчі. Метод Флойда - Кнута при великих довжинах чисел дає більші часові показники, тобто програє першим трьом методам. Метод обчислення модулярної експоненти найбільшу швидкодію показує при застосуванні методів Монтгомері та лінійних форм Фібоначчі.
Вывод
Визначено особливості пяти методів модулярної редукції, а саме класичного методу, методу Баррета, методу Кнута - Флойда, методу Монтгомері та методу А.В.Анісімова.
Дано теоретичне обгрунтування методу модулярної редукції Монтгомері.
Запропоновано новий паралельний алгоритм обчислення модулярної експоненти xd mod m. Цей алгоритм узагальнює бінарний алгоритм Чіоу на випадок довільного базиса системи обчислення.
Запропоновано новий рекурсивно-паралельний алгоритм обчислення модулярної редукції, базований на застосуванні лінійних форм Фібоначчі.
Проведено компютерні експерименти по вивченню часових характеристик усіх поданих у роботі алгоритмів.
Теоретичне та практичне порівняння пяти вище згаданих алгоритмів привело до таких висновків. Класичний метод, метод Баррета, метод Монтгомері достатньо близькі за часовими характеристиками. Метод Флойда - Кнута при великих довжинах чисел дає більші часові показники, тобто програє першим трьом методам. Метод А.В.Анісімова дуже корисний при разових обчисленнях модулярної редукції і при невеликих довжинах чисел. Метод обчислення модулярної експоненти найбільшу швидкодію показує при застосуванні методів Монтгомері та лінійних форм Фібоначчі. Серед паралельних варіантів найбільш цікавим є алгоритм, оснований на використанні розкладання ступеня у лінійні форми Фібоначчі.
ОСНОВНІ ПОЛОЖЕННЯ ДИСЕРТАЦІЇ НАДРУКОВАНІ В НАСТУПНИХ ПРАЦЯХ
Elfard S.S. Justification of Montgomery modular reduction // Вісник Київського університету. - 1996. - №1. - C. 401-404.
Elfard S.S. The use of Fibbonacci numbers for information protection // Вісник Київського університету. - 1997. - №3. - C. 212-216.
Elfard S.S. Fast Parallel exponentiation // Вісник Київського університету. - 1998. - №3. - C. 283-286.
Elfard S.S. // Вісник Київського університету. - 1998. - №4. - C. 214-217.
Elfard S.S. Fast Parallel exponentiation (Part 2) // Вісник Київського університету. - 1999. - №1. - C. 259-263.