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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сложность алгоритма Полларда — Штрассена ${\displaystyle 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.