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