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

 Наукова періодика України 

---

Додаткова інформація про автора(ів) публікації:
(cписок формується автоматично, до списку можуть бути включені персоналії з подібними іменами або однофамільці)

• Винничук Степан Дмитрович (фізико-математичні науки)

  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"