Processing math: 100%

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

 В и вычислительной алгебре алгоритм «кенгуру» Полларда (а такжелямбда-алгоритм Полларда, см. раздел «Название» ниже) — этоалгоритм решения задачи дискретного логарифмирования. Алгоритм былпредложен в 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=N1i=0f(xi)
. Заметим, что
xN=x0αd=αb+d.
4. Начинаем вычислять вторуюпоследовательность элементов группы {y0,y1,} по формулам

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

 и соответствующую последовательность целых чисел согласно формуле
dn=n1i=0f(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}, которая «сталкиваетсяс» первой последовательностью (подобно встрече короткой и длинной линиибуквы).
 Поллард предпочитает использование названия «алгоритм кенгуру», чтобыизбежать путнаницы с некоторыми параллельными версиями ρ–алгоритма,которые тоже носят название «лямбда-алгоритмы».