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

07.02.2021

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

Теорема

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

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

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

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

Пример

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

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

II) f 11 := f 1 mod ( x − 1 ) ( x − 5 ) {displaystyle f11:=f1mod (x-1)(x-5)}

f 12 := f 1 mod ( x − 9 ) ( x − 13 ) {displaystyle f12:=f1mod (x-9)(x-13)}

III) f 111 := f 11 mod ( x − 1 ) = 24 mod 247 {displaystyle f111:=f11mod (x-1)=24mod 247}

f 112 := f 11 mod ( x − 5 ) = 198 mod 247 {displaystyle f112:=f11mod (x-5)=198mod 247}

f 121 := f 12 mod ( x − 9 ) = 24 mod 247 {displaystyle f121:=f12mod (x-9)=24mod 247}

f 122 := f 12 mod ( x − 13 ) = 208 mod 247 {displaystyle f122:=f12mod (x-13)=208mod 247}

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

Алгоритм

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

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