Оцінка обчислювальних затрат p-методу Поларда в залежності від вибору відображення та початкового наближення для малих факторизованих чисел

Анотація

Для ряду задач захисту інформації криптостійкістьвикористовуваних алгоритмів пов’язана з вирішенням обчислювальної задачі розкладання на множники (факторизації) багаторозрядних чисел. Алгоритми сучасних методів факторизації можуть використовувати, якскладову, інші відомі алгоритми. Тому дослідженнявластивостей відомих методів та розробка способівприскорення їх роботи є актуальною задачею. Для -методу Поларда факторизації відомі загальні оцінкидля числа ітерацій, але не представлені результати досліджень щодо впливу на нього початкового наближен-ня. Для оцінки такого впливу запропоновано визнача-ти середнє число ітерацій для p-метода Поларда наприкладі 2*107 варіантів чисел, що не перевищують 231,виду N=p∙q, де p и q прості. При визначенні середніхзначень числа ітерацій розраховувалось сумарне числоітерацій для всіх досліджуваних варіантів чисел N, якеділилось на число цих варіантів. Для забезпеченнярозкладання чисел на множники кожен раз, коли іте-раційний процес зациклювався, константа с в поліномі,що реалізує ітераційний процес 21 ( )mod    k k x x c N ,збільшувалась на одиницю. Проведені дослідження зоцінки середнього значення числа ітерацій в заледностівід вибору константи с в поліномі, а також від виборупочаткового наближення. Визначено, що для дослі-джуваних варіантів чисел середнє значення числа іте-рацій менше ніж відомі оцінки, а за рахунок виборупочаткового наближення воно може бути зменшенебільш ніж на третину.