Винничук С. Д. Многократное прореживание для ускорения метода факторизации Ферма при неравномерных шагах для неизвестной / С. Д. Винничук, Е. В. Максименко // Вісн. Нац. техн. ун-ту України "КПІ". Сер. Інформатика, упр. та обчислюв. техніка. - 2016. - Вип. 64. - С. 13-24. - Библиогр.: 6 назв. - рус.Предложен способ ускорения метода Ферма факторизации чисел за счет прореживания пробных значений неизвестной Х при использовании множества оснований модуля, в котором существенная роль принадлежит выделяемому базовому основанию модуля bb. Базовое основание выбирается из условия максимума отношения bb к числу тех из Xmodbb, для которых разница X2 - N является квадратичным остатком по модулю bb (допустимые Xmodbb) и доступной оперативной памяти ЭВМ. На основании bb формируется список шагов переменной длины между ближайшими по величине допустимыми Xmodbb. Описан алгоритм МР, реализующий прореживание пробных значений. Для наиболее часто выполняемых шагов алгоритма МР представлен фрагмент программного кода на языке С. Представлены результаты численных экспериментов по разложению чисел на множители, являющихся произведением двух простых таких, что отношение большего к меньшему не превосходит 4. Показано, что при использовании только процедуры прореживания пробных значений временные затраты при решении задачи разложения на множители всегда пропорциональны числу (p+q)/2 - N1/2, где N = pq. Они существенно зависят от выбора базового основания модуля и множества других оснований. Індекс рубрикатора НБУВ: З973-047.1
Рубрики:
Шифр НБУВ: Ж29126/Інформ. Пошук видання у каталогах НБУВ
Повний текст Наукова періодика України Додаткова інформація про автора(ів) публікації: (cписок формується автоматично, до списку можуть бути включені персоналії з подібними іменами або однофамільці) ![](/irbis_nbuv/images/info.png) Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"
|