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

Анотація

У даній роботі описана постановка задачі дискретного логарифмування, яка є важ-ливою математичної проблемою, яка наразі є невирішеною. Проаналізовано алгоритм обчислення дискретного логарифма Силвера-Поліга-Хеллмана і вказані його недоліки, що виникають через вико-ристання чисел спеціального типу, званих гладкими. Вказана проблема, яка виникає при пошуку глад-ких простих чисел великої розрядності. Процес пошуку таких чисел уповільнює алгоритм Силвера-Поліга-Хеллмана, крім того не відомо чи можливо знайти гладкі прості числа необхідної розряднос-ті, адже їх кількість серед простих чисел надзвичайно мала, що ставить під питання ефективність використання алгоритму. Було введено поняття гладкого простого числа, запропонована класифіка-ція в залежності від зростання поспіль розташованих множників на ідеально гладкі і частково глад-кі прості числа. Були проаналізовані перші десять мільйонів простих чисел на гладкість, серед яких ідеально гладких виявлено кілька десятків. Виникає необхідність у перевірці гіпотези про кінцеву кі-лькість ідеально гладких чисел. Частково гладкі прості числа можуть значно уповільнити роботу алгоритму, адже невідома точна структура числа, кількість співмножників та різниця між ними. Також враховується, що при зростанні простих чисел, різниця між ними теж зростатиме. Показа-но, що для пошуку гладких простих чисел і аналізу їх властивостей необхідно знати, як розподілені прості числа в залежності від кількості простих співмножників, адже у випадку задачі дискретного логарифмування необхідно знаходити гладкі числа з кількістю співмножників більшою за 5-6. Наве-дені результати розподілу перших десяти мільйонів простих чисел та видвинуті припущення щодо можливих законів розподілу. Наведено проблема побудови міри гладкості, яка має бути розглянута в залежності від різниці суміжних співмножників та їх степенів.