«Р — 1» метод Полларда

Один из первых подходов к разложению на множители чисел частного вида был предложен^[1] Джоном Поллардом в 1974 году. Пусть т — натуральное, нечетное, составное число, которое мы хотим разложить на множители и р- некоторый простой делитель числа т.

Пусть а — произвольное целое число, взаимно простое р. Зафиксируем целое число к такое, что р — 1к, тогда согласно малой теореме Ферма выполнено сравнение.

откуда следует, что р| (а^к — 1). Таким образом, задача определения неизвестного делителя р сводится к вычислению НОД (га, а^к — 1) и определению величины к.

Предположим, что нам дополнительно известно, что все простые делители числа р— 1 не превосходят некоторой константы В, то есть.

где pi — различные простые числа такие, что pi < В. В этом случае определим в качестве к произведение всех простых чисел, не превосходящих величины В,.

где величины ^ удовлетворяют неравенствам.

то есть тi = flog^ р]. Для данной величины к выполнено условие р — 1к, следовательно она может быть использована для поиска нетривиального делителя р.

На практике при разложении числа гп на множители неизвестны ни точное значение величины В, ни размер простого делителя р. Поэтому описанная выше идея реализуется в виде следующего теста.

Вначале исходя из быстродействия вычислительного средства, реализующего тест, выбирается значение константы В. После строится число к, определяемое равенством (13.15). При этом величины т{ полагаются равными единице практически для всех значений, кроме нескольких начальных простых чисел. Далее несколько раз случайным образом выбирается вычет а и вычисляется значение d = нод (га, а^к — 1). Если величина d отлична от единицы, то нетривиальный делитель найден. Заметим, что нам достаточно для определения величины d вычислять значение а^к -1 по модулю числа га.

Алгоритм 13.6 («р — 1» метод Полларда)^[2][3]

а должно равняться 2).

• 4. Если НОД (а, т) > 1, то завершить алгоритм с результатом р = а.
• 5. Вычислить d = НОД (m, а^к — 1 (mod т)).
• 6. Если т > d> 1, то завершить алгоритм с результатом р = d.
• 7. Если i < с, то вернуться па шаг 3. В противном случае, завершить

алгоритм с уведомлением о неудаче. ?

Поскольку мы определили величины у меньшими, чем flogp, р — ^то могут найтись вычеты а такие, что их показатель по модулю р не будет делить к. В связи с этим мы выполняем несколько проверок, число которых определяется параметром с. При практической реализации алгоритма величина с может принимать небольшие значения.

Как можно заметить, «р — 1» метод Поллада представляет собой аналог алгоритма пробного деления, изложенного нами ранее. Только в данном случае мы перебором ищем не делители числа т, а делители числа р — 1, собранные в виде произведения в число к.

• [1] См. Pollard J.M. Theorems on Factorization And Primality Testing //Proceedings of the Cambridge Philosophical Society. — №. 3. — Vol. 76. — 1974. -pp. 521−528.
• [2] Вход: Целое составное число га, границы Висе N. Выход: Целое, быть может, составное число р такое, что рт.
• [3] Используя алгоритм 13.1, построить все простые числа РьРг, • •непревосходящие величины В, и определить величину к равенством (13.15). 2. Определить г = 0. 3. Вычислить г = г4−1, положить, а = pi (при г = 1 значение параметра