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

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

Алгоритм

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

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

2. Выберем целое число [math]\displaystyle{ N }[/math] и вычислим последовательность элементов группы [math]\displaystyle{ \{x_0,x_1,\ldots,x_N\} }[/math] согласно формулам:

• [math]\displaystyle{ x_0 = \alpha^b\, }[/math]
• [math]\displaystyle{ x_{i+1} = x_i\alpha^{f(x_i)} }[/math] для [math]\displaystyle{ i=0,1,\ldots,N-1 }[/math]

3. Вычислим

[math]\displaystyle{ d = \sum_{i=0}^{N-1}f(x_i) }[/math].

Заметим, что

[math]\displaystyle{ x_N = x_0\alpha^d = \alpha^{b+d}\, . }[/math]

4. Начинаем вычислять вторую последовательность элементов группы [math]\displaystyle{ \{y_0,y_1,\ldots\} }[/math] по формулам

• [math]\displaystyle{ y_0 = \beta\, }[/math]
• [math]\displaystyle{ y_{i+1} = y_i\alpha^{f(y_i)} }[/math] для [math]\displaystyle{ i=0,1,\ldots,N-1 }[/math]

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

[math]\displaystyle{ d_n = \sum_{i=0}^{n-1}f(y_i) }[/math].

Заметим, что

[math]\displaystyle{ y_i = y_0\alpha^{d_i} = \beta\alpha^{d_i} }[/math] для [math]\displaystyle{ i=0,1,\ldots,N-1 }[/math]

5. Прекращаем вычисления [math]\displaystyle{ \{y_i\} }[/math] и [math]\displaystyle{ \{d_i\} }[/math], когда выполняется одно из условий

A) [math]\displaystyle{ y_j = x_N }[/math] для некоторого [math]\displaystyle{ j }[/math]. Если последовательности [math]\displaystyle{ \{x_i\} }[/math] и [math]\displaystyle{ \{y_j\} }[/math] «сталкиваются» таким способом, мы имеем:

[math]\displaystyle{ x_N = y_j \Rightarrow \alpha^{b+d} = \beta\alpha^{d_j} \Rightarrow \beta = \alpha^{b+d-d_j} \pmod{n} \Rightarrow x \equiv b+d-d_j \pmod{n-1} }[/math]

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

B) [math]\displaystyle{ d_i \gt b-a+d }[/math]. Если это случилось, алгоритм потерпел неудачу в поиске [math]\displaystyle{ x }[/math]. Может быть сделана другая попытка путём изменения множества [math]\displaystyle{ S }[/math] или/и отображения [math]\displaystyle{ f }[/math].

Сложность

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

Название

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

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

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

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

См. также

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

Литература

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