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

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

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

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

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

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

3. Вычислим

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

Заметим, что

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

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

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

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

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

Заметим, что

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

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

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

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

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

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

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

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

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

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

• 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.