Алгоритм кенгуру Полларда
В вычислительной теории чисел и алгебре вычислительной алгоритм кенгуру Полларда (также лямбда-алгоритм Полларда , см. Именование ниже) представляет собой алгоритм решения задачи дискретного логарифмирования . Алгоритм был представлен в 1978 году теоретиком чисел Джоном М. Поллардом в той же статье, что и его более известный ро-алгоритм Полларда для решения той же задачи. [ 1 ] [ 2 ] Хотя Поллард описал применение своего алгоритма к задаче дискретного логарифмирования в мультипликативной группе единиц по модулю простого числа p , на самом деле это общий алгоритм дискретного логарифмирования — он будет работать в любой конечной циклической группе.
Алгоритм
[ редактировать ]Предполагать — конечная циклическая группа порядка который генерируется элементом , и мы пытаемся найти дискретный логарифм элемента на базу . Другими словами, человек ищет такой, что . Лямбда-алгоритм позволяет искать через некоторый интервал . Можно выполнить поиск во всем диапазоне возможных логарифмов, задав и .
1. Выберите набор положительных целых чисел со средним примерно и определим псевдослучайную карту .
2. Выберите целое число и вычислить последовательность элементов группы в соответствии с:
3. Вычислить
Обратите внимание:
4. Начните вычисление второй последовательности элементов группы. в соответствии с:
и соответствующая последовательность целых чисел в соответствии с:
- .
Обратите внимание:
5. Перестаньте вычислять условия и при выполнении любого из следующих условий:
- А) для некоторых . Если последовательности и «сталкиваться» таким образом, то мы имеем:
- и вот мы закончили.
- Б) . Если это произошло, то алгоритму не удалось найти . Последующие попытки можно предпринимать, меняя выбор и/или .
Сложность
[ редактировать ]Поллард определяет временную сложность алгоритма как , используя вероятностный аргумент, основанный на предположении, что действует псевдослучайно. С можно представить с помощью бит, это экспоненциально влияет на размер задачи (хотя все же это значительное улучшение по сравнению с тривиальным алгоритмом грубой силы, который требует времени). ). Пример субэкспоненциального алгоритма дискретного логарифма см. в разделе «Алгоритм исчисления индексов» .
Мы
[ редактировать ]Алгоритм известен под двумя названиями.
Первый — «алгоритм кенгуру Полларда». Это название является отсылкой к аналогии, использованной в статье, представляющей алгоритм, где алгоритм объясняется с точки зрения использования ручного кенгуру для ловли дикого кенгуру. Поллард объяснил [ 3 ] что эта аналогия была вдохновлена «увлекательной» статьей, опубликованной в том же номере журнала Scientific American , где описывается RSA криптосистема с открытым ключом . Статья [ 4 ] описал эксперимент, в котором «энергетические затраты на передвижение кенгуру, измеряемые в показателях потребления кислорода на различных скоростях, определялись путем помещения кенгуру на беговую дорожку ».
Второй — «лямбда-алгоритм Полларда». Подобно названию другого алгоритма дискретного логарифмирования Полларда, алгоритма Ро Полларда , это название относится к сходству между визуализацией алгоритма и греческой буквой лямбда ( ). Более короткая черта буквы лямбда соответствует последовательности , поскольку он начинается с позиции b справа от x. Соответственно, более длинный ход соответствует последовательности , который «сталкивается» с первой последовательностью (точно так же, как пересекаются штрихи лямбды), а затем следует за ней впоследствии.
Поллард отдал предпочтение названию «алгоритм кенгуру». [ 5 ] поскольку это позволяет избежать путаницы с некоторыми параллельными версиями его алгоритма ро, которые также называются «лямбда-алгоритмами».
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Поллард, Джон М. (июль 1978 г.) [1977-05-01, 1977-11-18]. «Методы Монте-Карло для расчета индексов (mod p )» (PDF) . Математика вычислений . 32 (143). Департамент математики, Телекоммуникационные исследования Плесси, Таплоу Корт, Мейденхед, Беркшир, Великобритания: Американское математическое общество : 918–924. ISSN 0025-5718 . Архивировано (PDF) из оригинала 3 мая 2013 г. Проверено 19 августа 2023 г. (7 страниц)
- ^ ван Оршот, Пол С .; Винер, Майкл Дж. (1999). «Параллельный поиск коллизий с криптоаналитическими приложениями». Журнал криптологии . 12 (1). Международная ассоциация криптологических исследований : 1–28. ISSN 0933-2790 .
- ^ Поллард, Джон М. (10 августа 2000 г.) [23 января 1998 г., 27 сентября 1999 г.]. «Кенгуру, монополия и дискретные логарифмы» (PDF) . Журнал криптологии . 13 (4). Коттедж Тидмарш, Мэнор Фарм Лейн, Тидмарш, Ридинг, Великобритания: Международная ассоциация криптологических исследований : 437–447. дои : 10.1007/s001450010010 . ISSN 0933-2790 . Архивировано (PDF) из оригинала 18 августа 2023 г. Проверено 19 августа 2023 г. (11 страниц)
- ^ Доусон, Теренс Дж. (1 августа 1977 г.). «Кенгуру». Научный американец . Том. 237, нет. 2. Scientific American, Inc., стр. 78–89. ISSN 0036-8733 . JSTOR 24954004 .
- ^ Поллард, Джон М. «Jmptidcott2» . Архивировано из оригинала 18 августа 2023 г. Проверено 19 августа 2023 г.
- ^ Поллард, Джон М. (июль 2000 г.). «Карточный фокус Краскала» (PDF) . Математический вестник . 84 (500). Коттедж Тидмарш, Мэнор Фарм Лейн, Тидмарш, Ридинг, Великобритания: Математическая ассоциация : 265–267. ISSN 0025-5572 . JSTOR 3621657 . 84.29. Архивировано (PDF) из оригинала 18 августа 2023 г. Проверено 19 августа 2023 г. (1+3 страницы)
Дальнейшее чтение
[ редактировать ]- Черногория, Рави [в Викиданных] ; Тетали, Прасад В. (7 ноября 2010 г.) [31 мая 2009 г.]. Сколько времени нужно, чтобы поймать дикого кенгуру? (PDF) . Материалы сорок первого ежегодного симпозиума ACM по теории вычислений (STOC 2009). стр. 553–560. arXiv : 0812.0789 . дои : 10.1145/1536414.1536490 . S2CID 12797847 . Архивировано (PDF) из оригинала 20 августа 2023 г. Проверено 20 августа 2023 г.