Алгоритм Полларда

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

Алгоритм


 Пусть G — конечная циклическая группа порядка n, генерируемая элементом α, и мы ищем дискретный логарифм x элемента β по основанию α. Другими словами, мы ищем xZn, такое, что αx=β. Лямбда-алгоритм позволяет нам искать x в некотором подмножестве {a,,b}Zn. Мы можем искать полный набор возможных логарифмов, приняв a=0 и b=n1, хотя в этом случае ρ–алгоритм будет эффективнее. Поступаем следующим образом:
 1. Выбираем множество S целых чисел и определяем f:GS.
 2. Выберем целое число N и вычислим последовательность элементов группы {x0,x1,,xN} согласно формулам:

  • x0=αb
  • xi+1=xiαf(xi) для i=0,1,,N1

 3. Вычислим
d=i=0N1f(xi)
. Заметим, что
xN=x0αd=αb+d.
4. Начинаем вычислять вторую последовательность элементов группы {y0,y1,} по формулам

  • y0=β
  • yi+1=yiαf(yi) для i=0,1,,N1

 и соответствующую последовательность целых чисел согласно формуле
dn=i=0n1f(yi)
. Заметим, что
yi=y0αdi=βαdi
для i=0,1,,N1 5. Прекращаем вычисления {yi} и {di}, когда выполняется одно из условий

  A) yj=xN для некоторого j. Если последовательности {xi} и {yj} «сталкиваются» таким способом, мы имеем:
 :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\}

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


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

Сложность


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

Название


 Алгоритм известен под двумя названиями.
 Первое название — алгоритм «кенгуру» Полларда. Имя относится к аналогии, используемой в статье, где алгоритм был предложен. В статье алгоритм объясняется в терминах использования ручного кенгуру для поимки дикого. Как объяснял Поллард, эта аналогия была навеяна «обворожительной» статьёй, опубликованной в том же выпуске журнала Scientific American, что и публикация RSA криптосистемы с открытым ключом. Статья описывает эксперимент, в котором «энергетическая цена движения кенгуру, измеренная в терминах потребления кислорода на различных скоростях, была определена путём помещения кенгуру на беговую дорожку».
 Второе название — лямбда-алгоритм Полларда. Очень похоже на имя другого алгоритма Полларда для дискретного логарифмирования, ρ–алгоритма, и это имя связано с похожестью визуализации алгоритма с греческой буквой лямбда (λ). Короткая линия буквы лямбда соответствует последовательности {xi}. Соответственно, длинная линия соответствует последовательности {yi}, которая «сталкивается с» первой последовательностью (подобно встрече короткой и длинной линии буквы).
 Поллард предпочитает использование названия «алгоритм кенгуру», чтобы избежать путнаницы с некоторыми параллельными версиями ρ–алгоритма, которые тоже носят название «лямбда-алгоритмы».