АНАЛІЗ ТА РОЗВИТОК ІСНУЮЧИХ АЛГОРИТМІВ РОЗВ’ЯЗАННЯ ПРОБЛЕМИ ДИСКРЕТНОГО ЛОГАРИФМА

Анотація

У даній роботі описана постановка та сутність задачі дискретного логарифмування, що є на даному етапі важливою математичною проблемою, а в прикладному аспекті – основою криптографії з відкритим ключем. Ця задача є базою для створення сеансового ключа у роботі Діффі-Хеллмана та багатьох криптографічних протоколах. У даній роботі прикладна сутність задачі дискретного логарифмування аналізується з точки зору створення алгоритмів електронного цифрового підпису, а зокрема описується проблема створення двох і більше електронних цифрових підписів на одному документі, що потребує не лише створення ефективних алгоритмів підпису, а й забезпечення надійності протоколів обміну ключами. У роботі описується класична математична постановка задачі дискретного логарифмування та проводиться детальний аналіз існуючого метода вирішення цієї проблеми. У ході аналізу позначаються недоліки запропонованого алгоритму та обґрунтування випадків, при яких цей алгоритм не може вирішити проблему дискретного логарифмування. Для більш детального дослідження проводиться аналіз алгоритму при різних вхідних значеннях. На основі цього було доведено, що при деяких значеннях алгоритм не має змоги вирішити проблему дискретного логарифмування. Цей факт дає змогу ставити під сумнів саме існування алгоритму вирішення задачі дискретного логарифмування для загального випадка. Більш того було доведено, що основні етапи алгоритму самі по собі складають задачі експоненційної складності. У роботі був запропонований алгоритм, що будується на основі певного ітераційного процесу. При зазначених умовах, що накладаються на вхідні данні, цей алгоритм має менше кроків та спрощенні обчислення у порівнянні з існуючим алгоритмом. Окрім цього, необхідно зазначити, що запропонований алгоритм має певні недоліки, що полягають у складнощах комп’ютерної реалізації. При практичному використанні такого методу необхідно зберігати та обробляти великий масив даних, окрім цього постає проблема створення ефективного методу пошуку конкретного числа у таких масивах даних. Окрім того, у роботі наведені сучасні проблеми, у яких запропоновано використовувати метод дискретного логарифмування.