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

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

Алгоритм

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

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

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

• $x_0={\alpha }^b$
• $x_{i+1}=x_i{\alpha }^{f(x_i)}$ для $i=0,1,\dots ,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,\dots \}$ по формулам

• $y_0=\beta$
• $y_{i+1}=y_i{\alpha }^{f(y_i)}$ для $i=0,1,\dots ,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,\dots ,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(\mathrm{mod}n)$

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

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

Сложность

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

Название

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

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

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

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

См. также

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

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья