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

В {{не переведено 5|Вычислительная теория чисел|вычислительной теории чисел||computational number theory}} и [[Символьные вычисления|вычислительной алгебре]] '''алгоритм «кенгуру» Полларда''' (а также '''лямбда-алгоритм Полларда''', см. раздел «[[#Название|Название]]» ниже) — это [[алгоритм]] решения задачи [[Дискретное логарифмирование|дискретного логарифмирования]]. Алгоритм был предложен в 1978 специалистом в области теории чисел {{iw|Джон Поллард|Дж. М. Поллардом|en|John Pollard (mathematician)}} в той же статье{{sfn|Pollard|1978}}, что и его более известный [[ро-метод Полларда для дискретного логарифмирования|ρ-алгоритм]] для решения той же задачи. Хотя Поллард описывает применение этого алгоритма для задачи дискретного логарифмирования в мультипликативной группе по модулю простого ''p'', он является, фактически, общим алгоритмом дискретного логарифмирования — он будет работать на любой циклической конечной группе.

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

1. Выбираем множество <math>S</math> целых чисел и определяем {{не переведено 5|Псевдослучайность|псевдослучайное отображение||pseudorandom}} <math>f: G \rightarrow S</math>.

2. Выберем целое число <math>N</math> и вычислим последовательность элементов группы <math>\{x_0,x_1,\ldots,x_N\}</math> согласно формулам:
* <math>x_0 = \alpha^b\,</math>
* <math>x_{i+1} = x_i\alpha^{f(x_i)} </math> для <math>i=0,1,\ldots,N-1</math>
3. Вычислим
: <math>d = \sum_{i=0}^{N-1}f(x_i)</math>.
Заметим, что
: <math>x_N = x_0\alpha^d = \alpha^{b+d}\, .</math>
4. Начинаем вычислять вторую последовательность элементов группы <math>\{y_0,y_1,\ldots\}</math> по формулам
* <math>y_0 = \beta\,</math>
* <math>y_{i+1} = y_i\alpha^{f(y_i)}</math> для <math>i=0,1,\ldots,N-1</math>
и соответствующую последовательность целых чисел согласно формуле
: <math>d_n = \sum_{i=0}^{n-1}f(y_i)</math>.
Заметим, что
: <math>y_i = y_0\alpha^{d_i} = \beta\alpha^{d_i}</math> для <math>i=0,1,\ldots,N-1</math>
5. Прекращаем вычисления <math>\{y_i\}</math> и <math>\{d_i\}</math>, когда выполняется одно из условий

: A) <math>y_j = x_N</math> для некоторого <math>j</math>. Если последовательности <math>\{x_i\}</math> и <math>\{y_j\}</math> «сталкиваются» таким способом, мы имеем:
:: <math>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}</math>
: так что мы нашли требуемое.

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

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

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

Первое название — ''алгоритм «кенгуру» Полларда''. Имя относится к аналогии, используемой в статье, где алгоритм был предложен. В статье алгоритм объясняется в терминах использования ''ручного'' [[кенгуру]] для поимки ''дикого''. Как объяснял Поллард{{sfn|Pollard|2000|с=437—447}}, эта аналогия была навеяна «обворожительной» статьёй, опубликованной в том же выпуске журнала ''[[Scientific American]]'', что и публикация [[RSA]] [[Криптосистема с открытым ключом|криптосистемы с открытым ключом]]. Статья{{sfn|Dawson|1977|с=78—89}} описывает эксперимент, в котором «энергетическая цена движения кенгуру, измеренная в терминах потребления кислорода на различных скоростях, была определена путём помещения кенгуру на [[Беговая дорожка (спортивный тренажёр)|беговую дорожку]]».

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

Поллард предпочитает использование названия «алгоритм кенгуру»<ref>{{Cite web |url=http://sites.google.com/site/jmptidcott2/ |title=jmptidcott2<!-- Заголовок добавлен ботом --> |access-date=2016-11-05 |archive-date=2016-08-17 |archive-url=https://web.archive.org/web/20160817064336/https://sites.google.com/site/jmptidcott2/ |deadlink=no }}</ref>, чтобы избежать путнаницы с некоторыми параллельными версиями ρ-алгоритма, которые тоже носят название «лямбда-алгоритмы».

== См. также ==
* [[Радужная таблица]]

== Примечания ==
{{примечания|2}}

== Литература ==
* {{статья
|автор=J. Pollard
|ref=Pollard
|заглавие=Monte Carlo methods for index computation mod p
|издание=Mathematics of Computation
|том=32
|год=1978
}}
* {{статья
|автор=J. Pollard
|ref=Pollard
|заглавие=Kangaroos, Monopoly and Discrete Logarithms
|ссылка=https://archive.org/details/sim_journal-of-cryptology_autumn-2000_13_4/page/437
|издание=Journal of Cryptology
|том=13
|страницы=437—447
|год=2000
}}
* {{статья
|автор=T. J. Dawson
|ref=Dawson
|заглавие=Kangaroos
|издание=Scientific American
|год=1977
|страницы=78—89
}}

{{Теоретико-числовые алгоритмы}}
{{rq|checktranslate|style}}

[[Категория:Теоретико-числовые алгоритмы]]
[[Категория:Вычислительная алгебра]]
[[Категория:Логарифмы]]