Наукова періодика України Інформатика та математичні методи в моделюванні


Касянчук М. М. 
Експериментальне дослідження програмної реалізації методів модулярного експоненціювання / М. М. Касянчук, І. З. Якименко, Т. М. Долинюк, Н. А. Рендзеняк // Інформатика та математичні методи в моделюванні. - 2015. - Т. 5, № 4. - С. 376-382. - Режим доступу: http://nbuv.gov.ua/UJRN/Itmm_2015_5_4_13
Виконання арифметичних операцій над багаторозрядними числами є досить важливою задачею сучасної теорії чисел та асиметричної криптографії. Проведено експериментальне дослідження часової складності модулярного експоненціювання з використанням середовища програмування Python 3.4.0 різними методами: пониження степеня за допомогою виділення квадратів (бінарний), кубів (3-арний), системи залишкових класів та її модифікованої досконалої форми. Операції виконувалися над числами різної розрядності та з різною вагою Хемінга. Показано, що при малих розрядностях найбільшою швидкодією характеризується метод пониження степенів за допомогою кубів. Починаючи з 1024 біт найменший час для виконання операції модулярного піднесення до степеня витрачається при застосуванні методу модифікованої досконалої форми системи залишкових класів. При дослідженні часової складності модулярного експоненціювання в залежності від ваги Хемінга встановлено, що найбільший час затрачається, коли вага Хемінга максимальна. При її зменшенні час виконання різко зменшується і надалі залишається майже постійним.Сумісне виконання алгоритму Евкліда та перемноження двох багаторозрядних чисел є досить важливою задачею сучасної теорії чисел, обчислювальної математики та асиметричної криптографії, зокрема, криптосистеми Рабіна. Проведено експериментальне дослідження часових характеристик програмної реалізації вказаних операцій класичним та запропонованим методами із застосуванням мови програмування високого рівня C++. У запропонованому методі передбачено використання проміжних результатів алгоритму Евкліда та звертання до наявної у пам'яті комп'ютера таблиці квадратів. Для дослідження використовувалися числа різної розрядності. Показано, що в переважній більшості розглянутих випадків запропонований метод характеризується більш високою швидкодією, середній час виконання операцій зменшується приблизно в 1,3 рази. Для нівелювання випадкових впливів на час роботи усі обчислення повторювалися 5000 разів. Запропонований метод ефективно можна використовувати для сумісного виконання алгоритму Евкліда та перемноження двох багаторозрядних чисел.Знаходження мультиплікативного оберненого елемента за модулем дуже часто є необхідною умовою для розв'язування багатьох задач сучасної теорії чисел, обчислювальної та прикладної математики, асиметричної криптографії, зокрема, криптосистем RSA та Ель-Гамаля. Проведено експериментальне дослідження часових характеристик програмної реалізації пошуку оберненого елемента за модулем на основі класичного методу розширеного алгоритму Евкліда та запропонованих методів додавання модуля та додавання залишку із застосуванням мови програмування високого рівня C++. Для дослідження використовувалися числа різної розрядності. Показано, що в переважній більшості розглянутих випадків метод додавання модуля характеризується більш високою швидкодією в порівнянні з двома іншими. Представлено графічні залежності середнього часу пошуку оберненого елемента різними методами від розрядності вибраних чисел. Для нівелювання випадкових впливів на час роботи усі обчислення повторювалися 100 разів. Запропоновані методи ефективно можна використовувати для пошуку оберненого елемента за модулем.
  Повний текст PDF - 426.855 Kb    Зміст випуску     Цитування публікації

Цитованість авторів публікації:
  • Касянчук М.
  • Якименко І.
  • Долинюк Т.
  • Рендзеняк Н.

  • Бібліографічний опис для цитування:

    Касянчук М. М. Експериментальне дослідження програмної реалізації методів модулярного експоненціювання / М. М. Касянчук, І. З. Якименко, Т. М. Долинюк, Н. А. Рендзеняк // Інформатика та математичні методи в моделюванні. - 2015. - Т. 5, № 4. - С. 376-382. - Режим доступу: http://nbuv.gov.ua/UJRN/Itmm_2015_5_4_13.

    Додаткова інформація про автора(ів) публікації:
    (cписок формується автоматично, до списку можуть бути включені персоналії з подібними іменами або однофамільці)
  • Якименко Ігор Зіновійович (технічні науки)
  •   Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"
     
    Відділ інформаційно-комунікаційних технологій
    Пам`ятка користувача

    Всі права захищені © Національна бібліотека України імені В. І. Вернадського