Русская Википедия:Алгоритм «кенгуру» Полларда
В Шаблон:Не переведено 5 и вычислительной алгебре алгоритм «кенгуру» Полларда (а также лямбда-алгоритм Полларда, см. раздел «Название» ниже) — это алгоритм решения задачи дискретного логарифмирования. Алгоритм был предложен в 1978 специалистом в области теории чисел Шаблон:Iw в той же статьеШаблон:Sfn, что и его более известный ρ-алгоритм для решения той же задачи. Хотя Поллард описывает применение этого алгоритма для задачи дискретного логарифмирования в мультипликативной группе по модулю простого 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 <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, эта аналогия была навеяна «обворожительной» статьёй, опубликованной в том же выпуске журнала Scientific American, что и публикация RSA криптосистемы с открытым ключом. СтатьяШаблон:Sfn описывает эксперимент, в котором «энергетическая цена движения кенгуру, измеренная в терминах потребления кислорода на различных скоростях, была определена путём помещения кенгуру на беговую дорожку».
Второе название — лямбда-алгоритм Полларда. Очень похоже на имя другого алгоритма Полларда для дискретного логарифмирования, ρ-алгоритма, и это имя связано с похожестью визуализации алгоритма с греческой буквой лямбда (<math>\lambda</math>). Короткая линия буквы лямбда соответствует последовательности <math>\{x_i\}</math>. Соответственно, длинная линия соответствует последовательности <math>\{y_i\}</math>, которая «сталкивается с» первой последовательностью (подобно встрече короткой и длинной линии буквы).
Поллард предпочитает использование названия «алгоритм кенгуру»[1], чтобы избежать путнаницы с некоторыми параллельными версиями ρ-алгоритма, которые тоже носят название «лямбда-алгоритмы».
См. также
Примечания
Литература
Шаблон:Теоретико-числовые алгоритмы Шаблон:Rq
