Optimization of Pollard's (p—1)-algorithm.pdf Рассмотрим (p — 1)-алгоритм Полларда факторизации числа N [1]. Алгоритм состоит из следующих шагов. Шаг 1. Выбираем число k. Шаг 2. Выбираем произвольное a, 1 < a < N. Шаг 3. Вычисляем d = (a, N). Если d > 1, получили нетривиальный делитель N. Шаг 4. Вычисляем D = (ak — 1,N). Если 1 < D < N, то D — нетривиальный делитель N. Если D = 1, возвращаемся к шагу 1, а при D = N — к шагу 2. Вопрос оптимального выбора параметра k не исследован до настоящего времени с нужной полнотой. Автором реализованы следующие подходы к выбору числа k: k — произведение нескольких случайных чисел; k — факториал некоторого числа, k — произведение степеней простых чисел; k — наименьшее общее кратное нескольких чисел. После анализа работы программы выбран третий метод, поскольку он работает быстрее остальных и даёт больше удачных разложений [2]. Зафиксируем a = 2 и рассмотрим работу (p — 1)-алгоритма Полларда при следующих допущениях: 1) k — произведение нескольких первых простых чисел в заданной степени; 2) исследуемое число N представляет собой произведение двух простых множителей, p и q. Пусть D = (ak — 1, N); Op(a), Oq (a) —показатели числа a по модулям p и q соответственно. Возможны три случая: 1) k кратно ровно одному из чисел Op(a), Oq(a). В этом случае получим 1 < D < N, и нетривиальный делитель D найден; 2) k не кратно ни одному из Op(a), Oq(a). В этом случае D = 1; 3) k кратно и Op(a), и Oq(a). В этом случае D = N. Таким образом, для удачного нахождения делителя N нужно выбрать параметр k не слишком большим и не слишком маленьким. Заметим, что k кратно Op(a) для любого a, если k кратно p — 1. Это, в свою очередь, гарантированно выполняется, если k является произведением всех простых чисел p ^ л/N/2 в степенях logp(\/N/2). Такой выбор k хорошо работает для сравнительно небольших чисел N, однако при увеличении числа N становится неприемлемым. Предлагается следующий алгоритм выбора k в процессе работы программы. Пусть k = papa .. .p", где p1, ..., p^ — первые l простых, a — некоторая константа. Будем рассматривать изменение k только за счёт изменения количества простых l. Идея выбора l состоит в том, чтобы выбрать его не слишком большим и не слишком малым, исходя из результатов работы программы (при слишком малом значении l результатом является 1, а при слишком большом — N). При этом l выбирается методом, похожим на половинное деление. При каждом значении l вычисляется D(l) = (ak — 1, N), k = р^рО;.. .pa. Параметр l выбирается следующим образом: Ш а г 1. lmin • -1, lmax • 1. Ш а г 2. lmax • lmax ' 2; l lmax. Шаг 3. Вычислить D = D(l); — если D = 1, то перейти к шагу 2; — если D = N, то перейти к шагу 4; — если 1 < D < N — выход, делитель найден. Ш а г 4. lmin • lmax/2; lmidl • lmin + (lmax lmin)/2; l • lmidl. Шаг 5. Вычислить D = D(l); — если D = 1, то lmin •= lmidl; lmidl •= lmin + (lmax — lmin)/2; l •= lmidl; перейти к шагу 5; — если D = N, то lmax •= lmidl; lmidl •= lmin + (lmax — lmin)/2; l •= lmidl; перейти к шагу 5; — если 1 < D < N — выход, делитель найден. Проведены эксперименты на заранее сформированных массивах чисел, представляющих собой произведение двух простых, с разрядностью 20, 40 и 60 десятичных знаков. Из 10000 чисел разрядностью 20 десятичных знаков были разложены 4250, среднее время на обработку одного числа составило 1,42 с. Разрядность максимального числа, которое было разложено на множители, составляет 60 десятичных знаков: 1052808008400417645876606027989867285487720871343057551778083 = = 123547896523698521452369860571 ■ 8521456358412963587456325968473, время разложения — 29 мин 23 с.

Скачать электронную версию публикации