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

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

Теорема

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

Доказательство теоремы сводится к возможности представить факториал произведением значений многочлена $f(x)=(x+1)(x+2)(x+3)\centerdot ...\centerdot (x+z)$ в $z$ точках, $y!=f(x_{1})\centerdot ...\centerdot f(x_{z})$ . Для нахождения $z$ значений многочлена быстрее, чем $z^{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}){\pmod {x-x_{i}}}$. Используя алгоритм быстрого умножения многочленов (а так же его модификацию операцию взятия по модулю многочлена), такой как Метод умножения Шёнхаге — Штрассена, применив парадигму разделяй и властвуй, за $O(log(n))$ умножений многочленов (и операций по модулю многочленов) строится дерево, листьями которого будут многочлены (значения) $f(x){\pmod {x-x_{i}}}$, а корнем дерева будет многочлен $f(x){\pmod {(x-x_{1})(x-x_{2})\centerdot ...\centerdot (x-x_{n})}}$.

Пример

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

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

II) $f11:=f1\mod (x-1)(x-5)$

$f12:=f1\mod (x-9)(x-13)$

III)$f111:=f11\mod (x-1)=24\mod 247$

$f112:=f11\mod (x-5)=198\mod 247$

$f121:=f12\mod (x-9)=24\mod 247$

$f122:=f12\mod (x-13)=208\mod 247$

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

Алгоритм

Положим $z=[n^{1/4}]+1,y=z^{2}>n^{1/2},t=n$. Далее с помощью алгоритма теоремы 1 найдем наименьший простой делитель числа НОД(n, y!). Поскольку y! делится на наименьший простой делитель p числа n (так как $p\leqslant n^{1/2}<y$), то алгоритм выдаст именно это число p.

Сложность алгоритма Полларда — Штрассена $O(z\log ^{2}z\log ^{2}t)=O(n^{1/4}\log ^{4}n)$.

Литература

• Vasilenko, O.N. Number-theoretic Algorithms in Cryptography. — American Mathematical Society, 2007. — 243 p. — ISBN 9780821840900.