Модифікований алгоритм факторизації великих чисел методом Ферма з використанням базової основи модуля

Abstract

Метод факторизації Ферма вважається кращим при факторизації чисел виду N = p • q у випадках коли множники p і q близькі за значенням. Обчислювальна складність базового алгоритму методу факторизації Ферма визначається кількістю пробних значень Х при вирішенні рівняння Y² = X² – N, а також складністю виконання арифметичних операцій з великими числами: зведення в квадрат, складання, обчислення квадратного кореня. Зниження обчислювальної складності зазначеного методу забезпечується за рахунок використання безлічі основ модулів в рівнянні Y²modb = (X²-N)modb, що в свою чергу дозволяє знехтувати складністю операцій обчислення квадратного кореня. Для зменшення числа пробних значень Х розглядалася можливість використання базової (первинної) основи модуля bb. Оптимальний вибір базової основи модуля bb дозволяє зменшити число пробних Х на величину, близьку за значенням до величини коефіцієнта прискорення z(N, bb) = bb/bb*, де bb* – число елементів множини коренів рівняння (Ymodb)²modb = ((Xmodb)²modb - Nmodb)modb. Показано, що в загальному випадку базова основа модуля bb є добутком ступенів простих чисел р, коефіцієнт прискорення для якого z(N, bb) є функцією Nmodp і показників ступенів р. Визначено ступінь впливу значення залишків Nmodp (в разі р=2 використовуються залишки Nmod8) і показників ступенів простих р на величину коефіцієнта прискорення z(N, bb)). Запропоновано постановку задачі пошуку оптимального значення базової основи модуля bb при обмеженнях на обсяг пам'яті ЕОМ і спосіб її вирішення. Наведено оцінку ефективності запропонованого модифікованого алгоритму методу факторизації Ферма. Встановлено, що запропонований алгоритм для чисел 2¹⁰²⁴ забезпечує зниження обчислювальної складності в порівнянні з базовим алгоритмом в середньому в 10⁷ разів. Використання запропонованого методу дозволить проектувати більш ефективні, з точки зору швидкодії, апаратно-програмні засоби проведення криптоаналізу асиметричних криптографічних алгоритмів та, як наслідок, підвищити якість оцінки криптостійкості алгоритму RSA.