В и вычислительной алгебре алгоритм «кенгуру» Полларда (а также лямбда-алгоритм Полларда , см. раздел « » ниже) — это алгоритм решения задачи дискретного логарифмирования . Алгоритм был предложен в 1978 специалистом в области теории чисел в той же статье , что и его более известный ρ-алгоритм для решения той же задачи. Хотя Поллард описывает применение этого алгоритма для задачи дискретного логарифмирования в мультипликативной группе по модулю простого 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)})}}$ , что является экспонентой от размера задачи. По этой причине лямбда-алгоритм Полларда считается алгоритмом экспоненциальной сложности . За примером подэкспоненциального по времени алгоритма см. Алгоритм исчисления порядка .

Название

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

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

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

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

См. также

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

Примечания

Литература

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