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

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

АлгоритмПравить

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

1. Выбираем множество $S$$S$  целых чисел и определяем псевдослучайное отображение^[en] $f:G\to <!--\; \to \; -->S$$f:G\rightarrow S$ .

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

• $x_0={\mathrm{\alpha <!--\; \alpha \; -->}}^b$$x_{0}=\alpha ^{b}\,$ 
• $x_{i+1}=x_i{\mathrm{\alpha <!--\; \alpha \; -->}}^{f(x_i)}$$x_{i+1}=x_{i}\alpha ^{f(x_{i})}$  для $i=0,1,\dots <!--\; \dots \; -->,N-<!--\; -\; -->1$$i=0,1,\ldots ,N-1$ 

3. Вычислим

$d=\underset{i=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}f(x_i)$$d=\sum _{i=0}^{N-1}f(x_{i})$ .

Заметим, что

$x_N=x_0{\mathrm{\alpha <!--\; \alpha \; -->}}^d={\mathrm{\alpha <!--\; \alpha \; -->}}^{b+d}.$$x_{N}=x_{0}\alpha ^{d}=\alpha ^{b+d}\,.$ 

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

• $y_0=\mathrm{\beta <!--\; \beta \; -->}$$y_{0}=\beta \,$ 
• $y_{i+1}=y_i{\mathrm{\alpha <!--\; \alpha \; -->}}^{f(y_i)}$$y_{i+1}=y_{i}\alpha ^{f(y_{i})}$  для $i=0,1,\dots <!--\; \dots \; -->,N-<!--\; -\; -->1$$i=0,1,\ldots ,N-1$ 

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

$d_n=\underset{i=0}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}f(y_i)$$d_{n}=\sum _{i=0}^{n-1}f(y_{i})$ .

Заметим, что

$y_i=y_0{\mathrm{\alpha <!--\; \alpha \; -->}}^{d_i}=\mathrm{\beta <!--\; \beta \; -->}{\mathrm{\alpha <!--\; \alpha \; -->}}^{d_i}$$y_{i}=y_{0}\alpha ^{d_{i}}=\beta \alpha ^{d_{i}}$  для $i=0,1,\dots <!--\; \dots \; -->,N-<!--\; -\; -->1$$i=0,1,\ldots ,N-1$ 

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

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

$x_N=y_j\Rightarrow <!--\; \Rightarrow \; -->{\mathrm{\alpha <!--\; \alpha \; -->}}^{b+d}=\mathrm{\beta <!--\; \beta \; -->}{\mathrm{\alpha <!--\; \alpha \; -->}}^{d_j}\Rightarrow <!--\; \Rightarrow \; -->\mathrm{\beta <!--\; \beta \; -->}={\mathrm{\alpha <!--\; \alpha \; -->}}^{b+d-<!--\; -\; -->d_j}(\mathrm{mod}n)\Rightarrow <!--\; \Rightarrow \; -->x\equiv <!--\; \equiv \; -->b+d-<!--\; -\; -->d_j(\mathrm{mod}n-<!--\; -\; -->1)$$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}}$ 

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

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

СложностьПравить

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

НазваниеПравить

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

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

Второе название — лямбда-алгоритм Полларда. Очень похоже на имя другого алгоритма Полларда для дискретного логарифмирования, ρ-алгоритма, и это имя связано с похожестью визуализации алгоритма с греческой буквой лямбда ($\mathrm{\lambda <!--\; \lambda \; -->}$$\lambda$ ). Короткая линия буквы лямбда соответствует последовательности $\{x_i\}$$\{x_i\}$ . Соответственно, длинная линия соответствует последовательности $\{y_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.