Processing math: 100%

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

Алгоритм Полларда — Штрассена однозначно находит разложениечисла 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).