В вычислительной теории чисел и вычислительной алгебре , алгоритм Кенгуру Полларда (также алгоритм лямбды Полларда , см Именование ниже) является алгоритмом для решения дискретного логарифмирования проблемы. Алгоритм был представлен в 1978 году теоретиком чисел Дж. М. Поллардом в той же статье, что и его более известный алгоритм ро Полларда для решения той же проблемы. [1] Хотя Поллард описал применение своего алгоритма к проблеме дискретного логарифмирования в мультипликативной группе единиц по модулю простого p, это фактически общий алгоритм дискретного логарифмирования - он будет работать в любой конечной циклической группе.
Алгоритм
Предполагать конечная циклическая группа порядка который генерируется элементом , и мы стремимся найти дискретный логарифм элемента к базе . Другими словами, человек ищет такой, что . Лямбда-алгоритм позволяет искать через некоторое время . Можно искать весь диапазон возможных логарифмов, задав а также .
1. Выберите набор целых чисел и определить псевдослучайное отображение.
2. Выберите целое число и вычислить последовательность элементов группы в соответствии с:
3. Вычислить
Обратите внимание:
4. Начните вычислять вторую последовательность элементов группы. в соответствии с:
и соответствующая последовательность целых чисел в соответствии с:
- .
Обратите внимание:
5. Прекратите вычислять сроки а также при выполнении любого из следующих условий:
- А) для некоторых . Если последовательности а также "столкнуться" таким образом, то мы имеем:
- и вот мы закончили.
- Б) . Если это происходит, значит, алгоритм не смог найти . Последующие попытки можно сделать, изменив выбор и / или .
Сложность
Поллард дает временную сложность алгоритма как , основанный на вероятностном аргументе, который следует из предположения, что действует псевдослучайно. Когда размер наборадля поиска измеряется в битах , как это нормально в теории сложности , набор имеет размер, поэтому сложность алгоритма равна , что экспоненциально зависит от размера задачи. По этой причине лямбда-алгоритм Полларда считается алгоритмом экспоненциального времени . Для примера алгоритма субэкспоненциального дискретного логарифмирования по времени см. Алгоритм расчета индекса .
Именование
Алгоритм известен под двумя названиями.
Первый - это «алгоритм кенгуру Полларда». Это имя является отсылкой к аналогии, использованной в статье, представляющей алгоритм, где алгоритм объясняется в терминах использования ручного кенгуру для поимки дикого кенгуру. Поллард объяснил [2], что эта аналогия была вдохновлена «увлекательной» статьей, опубликованной в том же номере журнала Scientific American, где излагается криптосистема с открытым ключом RSA . В статье [3] описан эксперимент, в котором «энергетическая стоимость передвижения кенгуру, измеренная с точки зрения потребления кислорода на различных скоростях, определялась путем помещения кенгуру на беговую дорожку ».
Второй - «лямбда-алгоритм Полларда». Подобно имени другого алгоритма дискретного логарифмирования Полларда, алгоритма ро Полларда , это имя указывает на сходство между визуализацией алгоритма и греческой буквой лямбда (). Более короткий штрих буквы лямбда соответствует последовательности, поскольку он начинается с позиции b справа от x. Соответственно, более длинный ход соответствует последовательности, которая "сталкивается" с первой последовательностью (точно так же, как пересекаются штрихи лямбда-выражения), а затем следует за ней впоследствии.
Поллард отдает предпочтение названию «алгоритм кенгуру» [4], поскольку это позволяет избежать путаницы с некоторыми параллельными версиями его алгоритма rho, которые также называются «лямбда-алгоритмами».
Смотрите также
Рекомендации
- ^ Дж. Поллард, Методы Монте-Карло для вычисления индекса (mod p) , Математика вычислений, Том 32, 1978
- ^ JM Поллард, Кенгуру, Монополия и дискретных логарифмов , журнал криптологии, том 13, стр. 437-447, 2000
- ↑ TJ Dawson, Kangaroos , Scientific American, август 1977, стр. 78–89.
- ^ http://sites.google.com/site/jmptidcott2/