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

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

ТеоремаПравить

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

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

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

Быстрое умножение вектора $(a_0,...,a_n{)}^t$$(a_{0},...,a_{n})^{t}$  на матрицу Вандермонда эквивалентно нахождению $n$$n$  значений $x_i$$x_{i}$  многочлена $f(x)=a_0+a_{1}x+...+a_n{x}^n$$f(x)=a_{0}+a_{1}x+...+a_{n}x^{n}$ . Метод быстрого нахождения $n$$n$  значений многочлена строится на том факте, что $a_0+a_{1}x+...+a_n{x}^n=f(x_i)(\mathrm{mod}x-<!--\; -\; -->x_i)$$a_{0}+a_{1}x+...+a_{n}x^{n}=f(x_{i}){\pmod {x-x_{i}}}$ . Используя алгоритм быстрого умножения многочленов (а так же его модификацию операцию взятия по модулю многочлена), такой как Метод умножения Шёнхаге — Штрассена, применив парадигму разделяй и властвуй, за $O(log(n))$$O(log(n))$  умножений многочленов (и операций по модулю многочленов) строится дерево, листьями которого будут многочлены (значения) $f(x)(\mathrm{mod}x-<!--\; -\; -->x_i)$$f(x){\pmod {x-x_{i}}}$ , а корнем дерева будет многочлен $f(x)(\mathrm{mod}(x-<!--\; -\; -->x_1)(x-<!--\; -\; -->x_2)\cdot <!--\; \cdot \; -->...\cdot <!--\; \cdot \; -->(x-<!--\; -\; -->x_n))$$f(x){\pmod {(x-x_{1})(x-x_{2})\centerdot ...\centerdot (x-x_{n})}}$ .

ПримерПравить

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

I) $f1:=f(x)\mathrm{mod}(x-<!--\; -\; -->1)(x-<!--\; -\; -->5)(x-<!--\; -\; -->9)(x-<!--\; -\; -->13)$$f1:=f(x)\mod (x-1)(x-5)(x-9)(x-13)$ 

II) $f11:=f1\mathrm{mod}(x-<!--\; -\; -->1)(x-<!--\; -\; -->5)$$f11:=f1\mod (x-1)(x-5)$ 

$f12:=f1\mathrm{mod}(x-<!--\; -\; -->9)(x-<!--\; -\; -->13)$$f12:=f1\mod (x-9)(x-13)$ 

III)$f111:=f11\mathrm{mod}(x-<!--\; -\; -->1)=24\mathrm{mod}247$$f111:=f11\mod (x-1)=24\mod 247$ 

$f112:=f11\mathrm{mod}(x-<!--\; -\; -->5)=198\mathrm{mod}247$$f112:=f11\mod (x-5)=198\mod 247$ 

$f121:=f12\mathrm{mod}(x-<!--\; -\; -->9)=24\mathrm{mod}247$$f121:=f12\mod (x-9)=24\mod 247$ 

$f122:=f12\mathrm{mod}(x-<!--\; -\; -->13)=208\mathrm{mod}247$$f122:=f12\mod (x-13)=208\mod 247$ 

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