Методы факторизации натуральных чисел. Ишмухаметов Ш.Т. - 58 стр.

Глава 2. Простые алгоритмы факторизации                                               59

выполнится для k             <    p − 1. Найдутся даже такие a                <   n, что
уже a2 ≡ 1 (modp). Для таких a скорость схождения метода будет
значительно выше. Поэтому, можно ускорить сходимости (p − 1)–
метода    Полларда,          запуская       алгоритм       с    несколькими   значениями
a. В статье «Pollard ρ on the Play Station 3», размещенной на сайте
http://www.hyperelliptic.org/tanja/SHARCS/slides09/03-bos.pdf, приводятся
примеры программирования алгоритмов факторизации, включая ρ и (p − 1)
методы Полларда с возможностью распараллеливания на игровой консоли
Sony Play Station 3, имеющей 8 сопроцессоров.

Пример

        Пусть p = 29–делитель n, тогда, p − 1 = 28 = 22 · 7. Для каждого
a ≤ 28 найдем наименьшее k такое, что ak ≡ 1 ( mod p). Приведем фрагмент
полученной таблицы:
a   2     3     4   5    6    7   8     9    10 11 12 13 14 15 16 17
k 28 28 14 14 14 7 28 14 28 28                         4       14 28 28   7   4
        Среди 28 значений a < 29 окажется 12 значение с показателем k = 28,
по 6 значений с показателем k = 14 и k = 7, 2 значения с k = 4, по одному с
k = 2 и k = 1. Математическое ожидание наименьшего показателя k равно:

              M [k] = (12 · 28 + 6 · 14 + 6 · 7 + 2 · 4 + 2 · 1)/28 ≈ 16, 85

Таким образом, выбирая удачное a < n, можно получить значительный
выигрыш по сравнению с произвольным.

Дальнейшие улучшения алгоритма

        Для ускорения всех вычислений Поллард предложил использовать
быстрое преобразование Фурье (a Fast Fourier Transform) для всех основных
операций.
        Дальнейшие улучшения алгоритма были предложены П.Монтгомери
[36]. Он заметил, что на второй стадии алгоритма большую часть времени
отнимает вычисление для каждого простого числа qi из интервала [B1 ; B2 ]