Нейромережеве налаштування r-додавального блукання в ρ-методі Полларда з використанням спектрального розриву для задачі дискретного логарифмування на еліптичних кривих

Анотація

У статті досліджено два нейромережеві підходи до конфігурування r-додавального блукання в ρ-методі Полларда для розв’язання задачі дискретного логарифмування на еліптичних кривих у короткій формі Вейєрштрасса над простими полями. У першому підході класифікаційна нейронна мережа NM-r прогнозує розмір r таблиці інкрементів, а регресійна нейронна мережа NM-inc безпосередньо генерує нормалізовані коефіцієнти інкрементів (α_i, β_i) на основі контексту кривої та підгрупи. Для цього підходу було сформовано набір даних із наближеними значеннями спектрального розриву та груповим за контекстами розподілом на навчальну, валідаційну й тестову частини. Оцінювання підходу виявило значний дисбаланс цільових класів для NM-r і нестабільність однозначних цільових таблиць інкрементів за точнішого вибіркового оцінювання матриць переходів. Це обмежило можливість надійного наскрізного узагальнення початкової моделі. Виявлені обмеження мотивували розроблення другого підходу, у якому нейронна мережа оцінює скінченну множину таблиць інкрементів-кандидатів і для фіксованого r обирає кандидата з найбільшою прогнозованою спектральною якістю. Для оцінювання цього підходу без вибіркової невизначеності цільових значень було сформовано точний набір даних, що містить 5000 контекстів еліптичних кривих і 480000 конфігурацій-кандидатів для r ∈ {8, 16, 32}. Простий модуль поля p і порядок підгрупи N задовольняли умову 2¹⁵ < p, N < 2²⁰. Цільове значення для кожного кандидата обчислювали за точною матрицею переходів між тегами розміру r × r, побудованою шляхом перебору всіх станів відповідної підгрупи. Моделі оцінювання кандидатів навчали з груповим за контекстами розподілом 80/10/10, порівнювали для декількох представлень вхідних даних і випадкових початкових значень, а їхні параметри фіксували до інтеграції з реалізацією ρ-методу Полларда мовою C#. Під час експериментального порівняння досліджували нейромережевий вибір, детермінований випадковий вибір, оракул наближеного спектрального розриву з L = 512 та оракул точного спектрального розриву. Експеримент виконано на 500 відкладених тестових контекстах із 30 парними запусками для кожного контексту та значення r, унаслідок чого отримано 180000 успішних вимірювань. Для сукупності r ∈ {8, 16, 32} нейромережевий вибір зменшив середню кількість ітерацій, нормалізовану за √N, на 2.52% порівняно з випадковим вибором. Контекстний бутстреп-інтервал із довірчою ймовірністю 95% становив [0.24%, 4.79%], а значення парного рандомізаційного тесту зі зміною знаків становило p = 0.0325. Для r = 8 зменшення кількості ітерацій становило 5.25%, довірчий інтервал із імовірністю 95% дорівнював [1.40%, 9.00%], а скориговане за методом Холма значення для трьох порівнянь нейромережевого та випадкового вибору становило p = 0.0237. Для r = 16 і r = 32 переконливого покращення не отримано. Крім того, збільшення точного спектрального розриву мало лише слабкий зв’язок зі зменшенням кількості ітерацій ρ-методу Полларда, а оракул точного спектрального розриву не забезпечив сталої переваги. Отримані результати демонструють помірний емпіричний виграш від нейромережевого оцінювання кандидатів у дослідженому експериментальному діапазоні, але водночас показують, що спектральний розрив сам по собі не є універсальним предиктором ефективності ρ-методу Полларда.