Алгоритм кенгуру Pollards - Pollards kangaroo algorithm - Wikipedia

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

Алгоритм

Предполагать конечная циклическая группа порядка который генерируется элементом , и мы стремимся найти дискретный логарифм элемента к базе . Другими словами, человек ищет такой, что . Лямбда-алгоритм позволяет искать через некоторое время . Можно искать весь диапазон возможных логарифмов, задав и .

1. Выберите набор целых чисел и определим псевдослучайный карта .

2. Выберите целое число и вычислить последовательность элементов группы в соответствии с:

3. Вычислить

Обратите внимание:

4. Начните вычислять вторую последовательность элементов группы. в соответствии с:

и соответствующая последовательность целых чисел в соответствии с:

.

Обратите внимание:

5. Прекратите вычислять сроки и при выполнении любого из следующих условий:

А) для некоторых . Если последовательности и "столкнуться" таким образом, то мы имеем:
и вот мы закончили.
Б) . Если это происходит, значит, алгоритм не смог найти . Последующие попытки можно сделать, изменив выбор и / или .

Сложность

Поллард дает временную сложность алгоритма как , основанный на вероятностном аргументе, который следует из предположения, что действует псевдослучайно. Когда размер набора подлежащие поиску измеряется в биты, как это обычно бывает в теория сложности, набор имеет размер , поэтому сложность алгоритма равна , что экспоненциально зависит от размера проблемы. По этой причине лямбда-алгоритм Полларда считается экспоненциальное время алгоритм. Для примера субэкспоненциальное время алгоритм дискретного логарифмирования, см. алгоритм расчета индекса.

Именование

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

Первый - «алгоритм кенгуру Полларда». Это имя является ссылкой на аналогию, используемую в статье, представляющей алгоритм, где алгоритм объясняется с точки зрения использования приручить кенгуру поймать дикий кенгуру. Поллард объяснил[2] что эта аналогия была вдохновлена ​​«увлекательной» статьей, опубликованной в том же номере Scientific American как экспозиция ЮАР криптосистема с открытым ключом. Статья[3] описал эксперимент, в котором «энергетическая стоимость передвижения кенгуру, измеренная с точки зрения потребления кислорода при различных скоростях, определялась путем помещения кенгуру на беговая дорожка ".

Второй - «лямбда-алгоритм Полларда». Как и название другого алгоритма дискретного логарифмирования Полларда, Алгоритм ро Полларда, это название указывает на сходство между визуализацией алгоритма и Греческая буква лямбда (). Более короткий штрих буквы лямбда соответствует последовательности , поскольку он начинается с позиции b справа от x. Соответственно, более длинный ход соответствует последовательности , который "сталкивается" с первой последовательностью (точно так же, как пересекаются штрихи лямбда-выражения), а затем следует за ней впоследствии.

Поллард отдает предпочтение названию «алгоритм кенгуру»,[4] поскольку это позволяет избежать путаницы с некоторыми параллельными версиями его алгоритма rho, которые также называются «лямбда-алгоритмами».

Смотрите также

Рекомендации

  1. ^ Дж. Поллард, Методы Монте-Карло для вычисления индекса (mod p), Математика вычислений, Том 32, 1978
  2. ^ Дж. М. Поллард, Кенгуру, монополия и дискретные логарифмы, Journal of Cryptology, Volume 13, pp. 437–447, 2000 г.
  3. ^ Т. Дж. Доусон, Кенгуру, Scientific American, август 1977 г., стр. 78–89.
  4. ^ http://sites.google.com/site/jmptidcott2/