АЛГОРИТМІЧНІ ПРОЦЕСИ ФАКТОРИЗАЦІЇ ВЕЛИКИХ ЧИСЕЛ, ЗАСНОВАНІ НА ТЕОРІЇ ЕЛІПТИЧНИХ КРИВИХ

Анотація

В даній роботі розглядається проблема факторизації великих складових чисел та її
місце серед математичних та інформаційних наук, а також їх прикладних аспектів. Докладно описаний взаємозв’язок між теорією псевдопростих чисел і задачею розкладання числа на прості
множники. Чітко відображена залежність сучасної криптографії від вирішення задачі факторизації, зокрема, фундаментальність даного питання для криптографічного алгоритму RSA на основі, якого створено велике число прикладних криптографічних програм. Дана класифікація сучасних
методів декомпозиції чисел. Описані причини для дослідження кожного с класів. Приведено алгоритм метода Полларда і його аналіз, оскільки він являється деякого роду прародителем методу
еліптичних кривих (метода Ленстри), який безпосередньо розглядається у статті. Серед субекспоненційних методів виділені: «Метод квадратичного решета», та «Метод решета числового поля», як одні з найшвидших, дана їх коротка характеристика, оцінка обчислювальної складності та
порівняльний аналіз між собою та методом Ленстри. Детально описані основи метода Ленстри, а
також ідеї на яких він базується, названі головні особливості математичних операцій на еліптичних кривих і властивості еліптичних кривих як математичних об’єктів, які надають можливість
використовувати їх з цілю факторизації. Детально по крокам описаний сам алгоритм методу.
Приведені результати розкладу великих складових чисел, отримані з допомогою реалізованої на
практиці програми. Метод ретельно проаналізований, дана його обчислювальна оцінка, описані
умови його збіжності. Названі фундаментальні проблеми алгоритму, які підлягають обов’язковому
та найскорішому вирішенню, важливе місце серед яких займають: проблема вибору кривої, проблема генерації псевдовипадкових послідовностей, проблема пошуку гладких чисел. Викладені можливі
варіанти оптимізації, зокрема, оптимізація аналогічна тій, що приводиться в методі Поларда у
якості другої стадії. Поставлено питання щодо взаємодії таких способів оптимізації алгоритму
та можливої реалізації. Підкреслена та обґрунтована перспективність методу еліптичних кривих
в порівнянні з іншими сучасними методами факторизації. Описані пріоритетні шляхи вирішення
проблеми факторизації