Мекуш Оксана Григорівна. Алгоритми модулярної арифметики великих чисел : дис... канд. фіз.- мат. наук: 01.05.01 / Київський національний ун-т ім. Тараса Шевченка. - К., 2005.
Анотація до роботи:
Мекуш О.Г. Алгоритми модулярної арифметики великих чисел. – Рукопис.
Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.01 – теоретичні основи інформатики та кібернетики. – Київський національний університет імені Тараса Шевченка. – Київ, 2005.
Дисертаційна робота присвячена дослідженню алгоритмів модулярної арифметики. Зроблено огляд основних алгоритмів модулярної редукції, запропоновано ефективний ітеративний алгоритм модулярної редукції. Класифіковані алгоритми модулярного експоненціювання, удосконалено паралельний метод експоненціювання, що базується на представленні експоненти з допомогою лінійних форм числових послідовностей. Запропоновано модель каскадного кодування по криптографічній схемі Рабіна, обгрунтовано мінімальну довжину додатку для усунення неоднозначності декодування. Дано огляд алгоритмів модулярного мультиекспоненціювання, представлено два нові ефективні паралельні методи. Ймовірносні алгоритми групової верифікації модулярного експоненціювання застосовані до групової верифікації цифрових підписів DSA-типу, запропонований загальний тест малих експонент для прискорення їх верифікації.
В дисертаційній роботі розроблені нові ефективні алгоритми модулярної арифметики, що розв’язують важливу задачу прискорення шифрації-дешифрації інформації в криптографічних системах реального часу і мають істотне значення для розробки математичного та програмного забезпечення сучасних систем захисту інформації.
В роботі поставлено та вирішено такі завдання:
запропоновано новий ітеративний алгоритм модулярної редукції,
який є ефективним при визначених умовах, накладених на модуль;
здійснено експериментальне порівняння швидкості запропонованого методу з іншими методами модулярної редукції, що підтвердило перевагу його обчислювальної ефективності;
удосконалено швидкий алгоритм модулярного експоненціювання, який базується на представленні експоненти з допомогою лінійних форм числових послідовностей і легко застосовується до паралельних багатопроцесорних систем;
здійснено експериментальне порівняння швидкостей даного методу модулярного експоненціювання для різних числових послідовностей, що підтвердило перевагу його обчислювальної ефективності;
розроблено програмне забезпечення практичної реалізації класу довгих чисел та операцій над ними, алгоритмів модулярної редукції (класичного, Барета, ітеративного), модулярного експоненціювання з допомогою лінійних форм числових послідовностей, а також представлення великих чисел з допомогою дерев послідовностей максимального рангу, що використане при проведенні обчислювальних експериментів;
обгрунтовано ефективну модель каскадного кодування по криптографічній схемі Рабіна, а також метод усунення неоднозначності декодування.
запропоновано два ефективні паралельні методи модулярного мультиекспоненціювання, які базуються на методах модулярного експоненціювання і дають не гірші показники складності обчислень за існуючі методи мультиекспоненціювання;
запропоновано та обгрунтовано так званий “загальний тест малих експонент”, який дозволяє здійснювати групову верифікацію цифрових підписів типу DSA, що, із врахуванням швидких методів модулярного мультиекспоненціювання, дозволяє в свою чергу значно прискорити процес верифікації цифрових підписів.
Найбільш перспективними застосуваннями результатів даної роботи є прискорення реалізацій криптографічних систем захисту інформації, що базуються на методах ключів загального доступу, а також різноманітних алгоритмів, в яких застосовуються операції модулярної арифметики.
Публікації автора:
Ткачук (Мекуш) О.Г. Застосування криптографічної схеми Рабіна до каскадного кодування інформації // Вісник Київського університету. Сер. фіз.-мат. науки. – 2002. - Вип. 4.- С.245-248.
Мекуш О.Г. Усунення неоднозначності декодування криптографічної схеми Рабіна // Вісник Київського університету. Сер. фіз.-мат. науки. – 2003. - Вип. 2.- С.180-184.
Анісімов А.В., Мекуш О.Г. Ітеративний алгоритм обчислення модулярної редукції // Вісник Київського університету. Сер. фіз.-мат. науки. – 2004. - Вип. 2.- С.179-183.
Мекуш О.Г. Паралельні методи мультиекспоненціювання // Вісник Київського університету. Сер. фіз.-мат. науки. – 2004. - Вип. 4.- С.217-222.
Мекуш О.Г. Групова верифікація цифрових підписів // Вісник Київського університету. Сер. фіз.-мат. науки. – 2005. - Вип. 2.- С.281-285.
Мекуш О.Г. Захист інформації за криптографічною схемою Рабіна // Проблеми впровадження інформаційних технологій в економіці. Міжнародна науково-практична конференція.- Ірпінь, 2003.-С.638-639.
Мекуш О.Г. Групова верифікація цифрових підписів // Світ інформації та телекомунікацій-2005. Міжнародна науково-технічна конференція.-Київ, 2005.-С.136-137.
