Характеристика існуючих методів алгоритмів модулярної редукції надвеликих чисел та їх порівняльний аналіз з метою визначення найбільш швидкодіючих. Математичне обґрунтування метода Монтгомері. Паралельні алгоритми обчислення модулярного експоненціювання.
Автореферат дисертації на здобуття наукового ступеня кандидата фізико-математичних наукРобота виконана на кафедрі математичної інформатики Київського університету імені Тараса Шевченка. Науковий керівник: доктор фізико математичних наук, професор Анісімов Анатолій Васильович, (Київський університет імені Тараса Шевченка, професор) Офіційні опоненти: доктор фізико-математичних наук, професор Захист відбудеться "24" червня 1999 р. на засіданні спеціалізованої вченої ради Д 26.001.09 Київського університету імені Тараса Шевченка, м.Київ, пр.Академіка Глушкова 6, корп.Тому зараз акцент в проблематиці захисту інформації зосередився на системах з відкритими ключами. Системи з відкритими ключами базуються не на принципах таємності всіх ключів, а на принципі неможливості перехоплювачу виконати дуже великий обсяг обчислювальних робіт. Системи з відкритими ключами дозволяють створити зручну та гнучку структуру сучасних систем захисту інформації. Вони також знайшли застосування у вирішенні великої кількості задач з нетрадиційними раніше постановками: цифровий підпис, аутентифікація віддалених обєктів, прийняття рішень сторонами, які не мають довіри один до одного, доведення володіння інформацією без розкриття самої інформації та багато інших. Головні її результати є оригінальними висновками по вибору найкращих методів модулярної редукції, а також відносяться до практичної сфери і можуть бути використані при розробці систем захисту інформації, які базуються на ключах загального доступу, та в інших системах, які використовують багаторозрядну арифметику.У параграфі 4.1. згадується відомий послідовний бінарний метод обчислення xd mod m. Також наводяться табличні дані обчислення xy mod m з використанням вище наведених пяти методів модулярної редукції. Новий паралельний алгоритм обчислення xy mod m запропоновано у наступному розділі 4.2. Це дає алгоритм з більшим збалансованим завантаженням при виконанні на двох процесорах. Спеціальний алгоритм, який дає високий ступінь паралельної обробки, дано у параграфі 4.3.Визначено особливості пяти методів модулярної редукції, а саме класичного методу, методу Баррета, методу Кнута - Флойда, методу Монтгомері та методу А.В. Анісімова. Цей алгоритм узагальнює бінарний алгоритм Чіоу на випадок довільного базису системи обчислення. Запропоновано новий рекурсивно-паралельний алгоритм обчислення модулярної редукції, базований на застосуванні лінійних форм Фібоначчі. Метод Флойда - Кнута при великих довжинах чисел дає більші часові показники, тобто програє першим трьом методам. Метод обчислення модулярної експоненти найбільшу швидкодію показує при застосуванні методів Монтгомері та лінійних форм Фібоначчі.
Вывод
Визначено особливості пяти методів модулярної редукції, а саме класичного методу, методу Баррета, методу Кнута - Флойда, методу Монтгомері та методу А.В. Анісімова.
Дано теоретичне обґрунтування методу модулярної редукції Монтгомері.
Запропоновано новий паралельний алгоритм обчислення модулярної експоненти xd mod m. Цей алгоритм узагальнює бінарний алгоритм Чіоу на випадок довільного базису системи обчислення.
Запропоновано новий рекурсивно-паралельний алгоритм обчислення модулярної редукції, базований на застосуванні лінійних форм Фібоначчі.
Проведено компютерні експерименти по вивченню часових характеристик усіх поданих у роботі алгоритмів.
Теоретичне та практичне порівняння пяти вище згаданих алгоритмів привело до таких висновків. Класичний метод, метод Баррета, метод Монтгомері достатньо близькі за часовими характеристиками. Метод Флойда - Кнута при великих довжинах чисел дає більші часові показники, тобто програє першим трьом методам. Метод А.В. Анісімова дуже корисний при разових обчисленнях модулярної редукції і при невеликих довжинах чисел. Метод обчислення модулярної експоненти найбільшу швидкодію показує при застосуванні методів Монтгомері та лінійних форм Фібоначчі. Серед паралельних варіантів найбільш цікавим є алгоритм, оснований на використанні розкладання ступеня у лінійні форми Фібоначчі.
Основні положення дисертації надруковані в наступних працях
1. Elfard S.S. Justification of Montgomery modular reduction // Вісник Київського університету. - 1996. - №1. - C. 401-404.
2. Elfard S.S. The use of Fibbonacci numbers for information protection // Вісник Київського університету. - 1997. - №3. - C. 212-216.
3. Elfard S.S. Fast Parallel exponentiation // Вісник Київського університету. - 1998. - №3. - C. 283-286.
4. Elfard S.S. // Вісник Київського університету. - 1998. - №4. - C. 214-217.
5. Elfard S.S. Fast Parallel exponentiation (Part 2) // Вісник Київського університету. - 1999. - №1. - C. 259-263.
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
