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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Алгоритм Полларда — Штрассена однозначно находит разложение числа на два множителя за арифметических операций. Сравним по скорости с методом квадратичных форм Шенкса, но, в отличие от него, требует выделение большого объёма памяти. Используется для ускорения вычислений второго этапа метода факторизации с помощью эллиптических кривых.[1] Алгоритм основан на следующей теореме.

Пусть . Тогда для любого натурального числа t наименьший простой делитель числа НОД(t, y!) может быть найден за арифметических операций.

Доказательство теоремы сводится к возможности представить факториал произведением значений многочлена в точках, . Для нахождения значений многочлена быстрее, чем , используется алгоритм быстрого умножения вектора на матрицу Вандермонда.[2]

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

[править | править код]

Быстрое умножение вектора на матрицу Вандермонда эквивалентно нахождению значений многочлена . Метод быстрого нахождения значений многочлена строится на том факте, что . Используя алгоритм быстрого умножения многочленов (а так же его модификацию операцию взятия по модулю многочлена), такой как Метод умножения Шёнхаге — Штрассена, применив парадигму разделяй и властвуй, за умножений многочленов (и операций по модулю многочленов) строится дерево, листьями которого будут многочлены (значения) , а корнем дерева будет многочлен .[3]

Пусть надо найти делитель числа . Для этого нам нужно найти . При прямом вычислении 16! mod 247 потребуется 15 раз умножить числа и взять их модуль, что сопоставимо с прямым перебором всех возможных делителей. Однако на больших числах количество операций можно уменьшить как квадратный корень, используя алгоритм быстрого нахождения значений многочлена. Действительно, рассмотрим многочлен , тогда . Степень многочлена равна . Теперь покажем как за операций умножения и взятия по модулю многочленов мы сможем вычислить значения многочлена в точках 1, 5, 9 и 13. Для этого выполним шагов и построим дерево:

I)

II)

III)

Все вычисления полиномов производятся с помощью алгоритмов быстрого умножения полиномов в кольце вычетов . Последним шагом находим .

Положим . Далее с помощью алгоритма теоремы 1 найдем наименьший простой делитель числа НОД(n, y!). Поскольку y! делится на наименьший простой делитель p числа n (так как ), то алгоритм выдаст именно это число p.

Сложность алгоритма Полларда — Штрассена .

Литература

[править | править код]
  • Vasilenko, O.N. Number-theoretic Algorithms in Cryptography. — American Mathematical Society, 2007. — 243 p. — ISBN 9780821840900.

Примечания

[править | править код]
  1. 20 Years of ECM.
  2. Effcient computation with structured matrices and arithmetic expressions // NNT : 2011ENSL0652. Архивировано 2 февраля 2017 года.
  3. Алгоритм быстрого умножения матрицы Вандермонда на вектор. Дата обращения: 23 января 2017. Архивировано 10 января 2017 года.