Алгоритм «кенгуру» Полларда

В вычислительной теории чисел и вычислительной алгебре алгоритм «кенгуру» Полларда (а также лямбда-алгоритм Полларда, см. раздел «Название» ниже) — это алгоритм решения задачи дискретного логарифмирования. Алгоритм был предложен в 1978 специалистом в области теории чисел Дж. М. Поллардом в той же статье, что и его более известный ρ-алгоритм для решения той же задачи. Хотя Поллард описывает применение этого алгоритма для задачи дискретного логарифмирования в мультипликативной группе по модулю простого p, он является, фактически, общим алгоритмом дискретного логарифмирования — он будет работать на любой циклической конечной группе.

Алгоритм

Пусть $G$ — конечная циклическая группа порядка $n$, генерируемая элементом $\alpha$, и мы ищем дискретный логарифм $x$ элемента $\beta$ по основанию $\alpha$. Другими словами, мы ищем $x\in Z_{n}$, такое, что $\alpha ^{x}=\beta$. Лямбда-алгоритм позволяет нам искать $x$ в некотором подмножестве $\{a,\ldots ,b\}\subset Z_{n}$. Мы можем искать полный набор возможных логарифмов, приняв $a=0$ и $b=n-1$, хотя в этом случае ρ-алгоритм будет эффективнее. Поступаем следующим образом:

1. Выбираем множество $S$ целых чисел и определяем псевдослучайное отображение $f:G\rightarrow S$.

2. Выберем целое число $N$ и вычислим последовательность элементов группы $\{x_{0},x_{1},\ldots ,x_{N}\}$ согласно формулам:

• $x_{0}=\alpha ^{b}\,$
• $x_{i+1}=x_{i}\alpha ^{f(x_{i})}$ для $i=0,1,\ldots ,N-1$

3. Вычислим

$d=\sum _{i=0}^{N-1}f(x_{i})$.

Заметим, что

$x_{N}=x_{0}\alpha ^{d}=\alpha ^{b+d}\,.$

4. Начинаем вычислять вторую последовательность элементов группы $\{y_{0},y_{1},\ldots \}$ по формулам

• $y_{0}=\beta \,$
• $y_{i+1}=y_{i}\alpha ^{f(y_{i})}$ для $i=0,1,\ldots ,N-1$

и соответствующую последовательность целых чисел согласно формуле

$d_{n}=\sum _{i=0}^{n-1}f(y_{i})$.

Заметим, что

$y_{i}=y_{0}\alpha ^{d_{i}}=\beta \alpha ^{d_{i}}$ для $i=0,1,\ldots ,N-1$

5. Прекращаем вычисления $\{y_{i}\}$ и $\{d_{i}\}$, когда выполняется одно из условий

A) $y_{j}=x_{N}$ для некоторого $j$. Если последовательности $\{x_{i}\}$ и $\{y_{j}\}$ «сталкиваются» таким способом, мы имеем:

$x_{N}=y_{j}\Rightarrow \alpha ^{b+d}=\beta \alpha ^{d_{j}}\Rightarrow \beta =\alpha ^{b+d-d_{j}}\Rightarrow x\equiv b+d-d_{j}{\pmod {n}}$

так что мы нашли требуемое.

B) $d_{i}>b-a+d$. Если это случилось, алгоритм потерпел неудачу в поиске $x$. Может быть сделана другая попытка путём изменения множества $S$ или/и отображения $f$.

Сложность

Поллард указал для алгоритма временную сложность ${\scriptstyle O({\sqrt {b-a}})}$, основываясь на вероятностной аргументации, что вытекает из предположения, что f действует псевдослучайно. Заметим, что в случае, когда размер множества {a, …, b} измеряется а битах, что обычно в теории сложности, множество имеет размер log(b − a), так что алгоритмическая сложность равна ${\scriptstyle O({\sqrt {b-a}})=O(2^{{\frac {1}{2}}\log(b-a)})}$, что является экспонентой от размера задачи. По этой причине лямбда-алгоритм Полларда считается алгоритмом экспоненциальной сложности. За примером подэкспоненциального по времени алгоритма см. Алгоритм исчисления порядка.

Название

Алгоритм известен под двумя названиями.

Первое название — алгоритм «кенгуру» Полларда. Имя относится к аналогии, используемой в статье, где алгоритм был предложен. В статье алгоритм объясняется в терминах использования ручного кенгуру для поимки дикого. Как объяснял Поллард, эта аналогия была навеяна «обворожительной» статьёй, опубликованной в том же выпуске журнала Scientific American, что и публикация RSA криптосистемы с открытым ключом. Статья описывает эксперимент, в котором «энергетическая цена движения кенгуру, измеренная в терминах потребления кислорода на различных скоростях, была определена путём помещения кенгуру на беговую дорожку».

Второе название — лямбда-алгоритм Полларда. Очень похоже на имя другого алгоритма Полларда для дискретного логарифмирования, ρ-алгоритма, и это имя связано с похожестью визуализации алгоритма с греческой буквой лямбда ($\lambda$). Короткая линия буквы лямбда соответствует последовательности $\{x_{i}\}$. Соответственно, длинная линия соответствует последовательности $\{y_{i}\}$, которая «сталкивается с» первой последовательностью (подобно встрече короткой и длинной линии буквы).

Поллард предпочитает использование названия «алгоритм кенгуру», чтобы избежать путнаницы с некоторыми параллельными версиями ρ-алгоритма, которые тоже носят название «лямбда-алгоритмы».

См. также

• Радужная таблица

Литература

• J. Pollard. Monte Carlo methods for index computation mod p // Mathematics of Computation. — 1978. — Т. 32.
• J. Pollard. Kangaroos, Monopoly and Discrete Logarithms // Journal of Cryptology. — 2000. — Т. 13. — С. 437—447.
• T. J. Dawson. Kangaroos // Scientific American. — 1977. — С. 78—89.