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

Анотація

У даній статті описані можливості використання апарату теорії еліптичних кривих, зокрема, при вирішенні задачі факторизації складеного числа. Дана задача займає фунда-ментальне положення серед як чисто математичних, так і прикладних наук. Розглянуто проблему імовірнісного принципу роботи субекспоненційних методів факторизації. Дан порівняльний аналіз існуючих субекспоненційних методів факторизації. Описані основні ідеї, переваги та недоліки ме-тода решета числового поля, окрема увага уділяється проблемі визначення гладкого числа для да-ного класу алгоритмів. Обґрунтовано вибір методу, заснованого на теорії еліптичних кривих. . Ідея методу ґрунтується на побудові псевдокривої над кільцем лишкiв складеного числа. Завдяки цьому вдається отримувати ситуації, коли неможливо знайти зворотний елемент в заданому кі-льці при складанні двох точок кривої, що сигналізує про знаходження дільника. Головною особливі-стю методу є залежність його обчислювальної складності від найменшого дільника числа, що фа-кторизується, а не від безпосередньо нього самого. Обґрунтована перспективність дослідження та розвитку цього метода. Описані головні задачі, що виникають при докладному аналізі методу еліптичних кривих. Особлива увага приділяється імовірнісному і субекспоненціальному характеру методу. Описана та проаналізована проблема визначення терміну субекспоненційна складність ал-горитму, зокрема аналізується субекспоненційна складність безпосередньо методу еліптичних кривих. Описано основні напрямки розвитку та оптимізації метода. Дано та проаналізовано мож-ливі підходи до вирішення описаних проблем. Розглядана можливість створення імовірнісної моде-лі, що використовує теорію еліптичних кривих при факторизації. В основі заданого рішення поля-гає використання ефективних генераторів псевдо випадкових чисел. На основі проведеного аналізу проводяться подальші дослідження для всіх відомих алгоритмів факторизації субекспоненціально-го класу з урахуванням можливості розробки імовірнісного підходу. Також увага приділяється пи-танням щодо дискримінанту кривої, та його властивостям що дозволяють на його основі отриму-вати дільники складеного числа.