Алгоритм Полларда — Штрассена

Алгоритм Полларда — Штрассена однозначно находит разложение числа $n$ на два множителя за $O (n^{1 / 4} \log^{4} n)$ арифметических операций. Сравним по скорости с методом квадратичных форм Шенкса, но, в отличие от него, требует выделение большого объёма памяти. Используется для ускорения вычислений второго этапа метода факторизации с помощью эллиптических кривых.^[1] Алгоритм основан на следующей теореме.

Теорема

Пусть $z \in ℕ, y = z^{2}$ . Тогда для любого натурального числа t наименьший простой делитель числа НОД(t, y!) может быть найден за $O (z \log^{2} z \log^{2} t)$ арифметических операций.

Доказательство теоремы сводится к возможности представить факториал произведением значений многочлена $f (x) = (x + 1) (x + 2) (x + 3) \cdot . . . \cdot (x + z)$ в $z$ точках, $y! = f (x_{1}) \cdot . . . \cdot f (x_{z})$ . Для нахождения $z$ значений многочлена быстрее, чем $z^{2}$ , используется алгоритм быстрого умножения вектора на матрицу Вандермонда.^[2]

Быстрое умножение вектора на матрицу Вандермонда

Быстрое умножение вектора $(a_{0}, . . ., a_{n})^{t}$ на матрицу Вандермонда эквивалентно нахождению $n$ значений $x_{i}$ многочлена $f (x) = a_{0} + a_{1} x + . . . + a_{n} x^{n}$ . Метод быстрого нахождения $n$ значений многочлена строится на том факте, что $a_{0} + a_{1} x + . . . + a_{n} x^{n} = f (x_{i}) (\mod x - x_{i})$ . Используя алгоритм быстрого умножения многочленов (а так же его модификацию операцию взятия по модулю многочлена), такой как Метод умножения Шёнхаге — Штрассена, применив парадигму разделяй и властвуй, за $O (l o g (n))$ умножений многочленов (и операций по модулю многочленов) строится дерево, листьями которого будут многочлены (значения) $f (x) (\mod x - x_{i})$ , а корнем дерева будет многочлен $f (x) (\mod (x - x_{1}) (x - x_{2}) \cdot . . . \cdot (x - x_{n}))$ .^[3]

Пример

Пусть надо найти делитель числа $N = 13 \cdot 19 = 247$ . Для этого нам нужно найти $\gcd ([24 7^{1 / 2}]! (\mod 247), 247) = \gcd (16! (\mod 247), 247) = \gcd (104, 247) = 13$ . При прямом вычислении 16! mod 247 потребуется 15 раз умножить числа и взять их модуль, что сопоставимо с прямым перебором всех возможных делителей. Однако на больших числах количество операций можно уменьшить как квадратный корень, используя алгоритм быстрого нахождения $N^{1 / 4}$ значений многочлена. Действительно, рассмотрим многочлен $f (x) = x (x + 1) (x + 2) (x + 3)$ , тогда $16! mod 2 47 = f (1) f (5) f (9) f (13) mod 2 47$ . Степень многочлена $f (x)$ равна $[N^{1 / 4}]$ . Теперь покажем как за $l o g (N^{1 / 4})$ операций умножения и взятия по модулю многочленов мы сможем вычислить значения многочлена в $N^{1 / 4}$ точках 1, 5, 9 и 13. Для этого выполним $l o g (N^{1 / 4})$ шагов и построим дерево:

I) $f 1 : = f (x) mod (x - 1) (x - 5) (x - 9) (x - 13)$

II) $f 11 : = f 1 mod (x - 1) (x - 5)$

$f 12 : = f 1 mod (x - 9) (x - 13)$

III) $f 111 : = f 11 mod (x - 1) = 24 mod 247$

$f 112 : = f 11 mod (x - 5) = 198 mod 247$

$f 121 : = f 12 mod (x - 9) = 24 mod 247$

$f 122 : = f 12 mod (x - 13) = 208 mod 247$

Все вычисления полиномов производятся с помощью алгоритмов быстрого умножения полиномов в кольце вычетов $Z_{247}$ . Последним шагом находим $\gcd (24 \cdot 198 \cdot 24 \cdot 208 mod 247, 247) = 13$ .