МОДЕЛЮВАННЯ ПРОЦЕСІВ ФОРМУВАННЯ АЛГОРИТМІВ ФАКТОРИЗАЦІЇ НА ОСНОВІ ТЕОРІЇ ЕЛІПТИЧНИХ КРИВИХ
Анотація
У даній статті описується проблема факторизації. Вказується на фундаментальне місце даної задачi в ряді чисто математичних і прикладних наук. Обґрунтовується важливість подальшого розгляду різних підходів вирішення даної проблеми. Аналізуються структурні класи методів факторизації. Дається їх умовна класифікація на експоненціальні і субекспоненціальнi на основі їх обчислювальної складності. Описано основні субекспоненціальнi методи, докладно аналізується проблема чіткого визначення субекспонеціальної складності. Дається визначення L-нотації, на основі якої даються оцінки обчислювальної складності субекспоненціальних алгоритмів. Обґрунтовується вибір підходу на основі теорії еліптичних кривих, як найбільш перспективного. Детально описано і проаналізовано алгоритм еліптичних кривих. Ідея методу ґрунтується на побудові псевдокривої над кільцем лишкiв складеного числа. Завдяки цьому вдається отримувати ситуації, коли неможливо знайти зворотний елемент в заданому кільці при складанні двох точок кривої, що сигналізує про знаходження дільника. Головною особливістю методу є залежність його обчислювальної складності від найменшого дільника числа, що факторизується, а не від безпосередньо нього самого. Описано основні проблеми методу та можливі шляхи його оптимізації. Окрему увагу приділено проблемі евристичного характеру алгоритму і випадкової генерації кривих. У статті описується проблема співвідношення між числом згенерованих кривих і необхідною границею базового методу еліптичних кривих. Дослідження цієї проблеми виконано за допомогою програмної реалізації методу, на основі описаного алгоритму для чисел чиї дільники не перевищують п'ять десяткових знаків. Представлені результати цього дослідження для різних випадків початкової границі. Отримані результати вказують на залежність витрачаємого часу, кінцевої границі при процесі факторизації і кількості кривих, що використовуються пiд час факторизації від кількості кривих після якого збільшується границя методу еліптичних кривих. Внаслiдок аналізу цього методу, проведено дослідження кількості випадків отримання дільника складеного числа, за допомогою дискримінанту кривої.
