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

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

Теорема


 Пусть z\N,y=z2. Тогда для любого натурального числа t наименьший простой делитель числа НОД(t, y!) может быть найден за O(zlog2zlog2t) арифметических операций.
 Доказательство теоремы сводится к возможности представить факториал произведением значений многочлена f(x)=(x+1)(x+2)(x+3)...(x+z) в z точках, y!=f(x1)...f(xz) . Для нахождения z значений многочлена быстрее, чем z2, используется алгоритм быстрого умножения вектора на матрицу Вандермонда.

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


 Быстрое умножение вектора (a0,...,an)t на матрицу Вандермонда эквивалентно нахождению n значений xi многочлена f(x)=a0+a1x+...+anxn. Метод быстрого нахождения n значений многочлена строится на том факте, что a0+a1x+...+anxn=f(xi)(modxxi). Используя алгоритм быстрого умножения многочленов (а так же его модификацию операцию взятия по модулю многочлена), такой как Метод умножения Шёнхаге — Штрассена, применив парадигму разделяй и властвуй, за O(log(n)) умножений многочленов (и операций по модулю многочленов) строится дерево, листьями которого будут многочлены (значения) f(x)(modxxi), а корнем дерева будет многочлен f(x)(mod(xx1)(xx2)...(xxn)).

agraphПример
 Пусть надо найти делитель числа N=1319=247. Для этого нам нужно найти gcd([2471/2]!(mod247),247)=gcd(16!(mod247),247)=gcd(104,247)=13. При прямом вычислении 16! mod 247 потребуется 15 раз умножить числа и взять их модуль, что сопоставимо с прямым перебором всех возможных делителей. Однако на больших числах количество операций можно уменьшить как квадратный корень, используя алгоритм быстрого нахождения N1/4 значений многочлена. Действительно, рассмотрим многочлен f(x)=x(x+1)(x+2)(x+3) , тогда 16!mod247=f(1)f(5)f(9)f(13)mod247. Степень многочлена f(x) равна [N1/4]. Теперь покажем как за log(N1/4) операций умножения и взятия по модулю многочленов мы сможем вычислить значения многочлена в N1/4 точках 1, 5, 9 и 13. Для этого выполним log(N1/4) шагов и построим дерево:
 I) f1:=f(x)mod(x1)(x5)(x9)(x13)
 II) f11:=f1mod(x1)(x5)
f12:=f1mod(x9)(x13)
 III)f111:=f11mod(x1)=24mod247
f112:=f11mod(x5)=198mod247
f121:=f12mod(x9)=24mod247
f122:=f12mod(x13)=208mod247
 Все вычисления полиномов производятся с помощью алгоритмов быстрого умножения полиномов в кольце вычетов Z247. Последним шагом находим gcd(2419824208mod247,247)=13.

Алгоритм


 Положим z=[n1/4]+1,y=z2>n1/2,t=n. Далее с помощью алгоритма теоремы 1 найдем наименьший простой делитель числа НОД(n, y!). Поскольку y! делится на наименьший простой делитель p числа n (так как pn1/2<y), то алгоритм выдаст именно это число p.
 Сложность алгоритма Полларда — Штрассена O(zlog2zlog2t)=O(n1/4log4n).