Винничук С. Д., Максименко Є. В.
Запропоновано спосіб прискорення методу Ферма факторизації чисел за рахунок проріджування пробних значень невідомої Х при використанні багатьох основ модуля, в якому істотна роль належить виділеній базовій основі модуля bb. Базова основа вибирається з умови максимуму відношення bb до числа тих з Xmodbb, для яких різниця X2 – N є квадратичним залишком по модулю bb (допустимі Xmodbb) і доступної оперативної пам’яті ЕОМ. На підставі bb формується список кроків змінної довжини між найближчими за величиною допустимими Xmodbb. Описано алгоритм МР, який реалізує проріджування пробних значень. Для найбільш часто виконуваних кроків алгоритму МР представлено фрагмент програмного коду на мові С. Представлені результати чисельних експериментів з розкладання чисел на множники, які є добутком двох простих таких, що відношення більшого до меншого не перевищує 4. Показано, що при використанні тільки процедури проріджування пробних значень часові затрати при вирішенні задачі розкладання на множники завжди пропорційні числу (p + q) / 2 – N1/2, де N = pq. Вони істотно залежать від вибору базової основи модуля і множини інших основ.
