Jump to content

Алгоритм кенгуру Полларда

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

Алгоритм

[ редактировать ]

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

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

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

3. Вычислить

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

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

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

.

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

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

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

Сложность

[ редактировать ]

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

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

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

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

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

См. также

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

Дальнейшее чтение

[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: c02de9d766763e824d3b4fc51d43c3f3__1693731000
URL1:https://arc.ask3.ru/arc/aa/c0/f3/c02de9d766763e824d3b4fc51d43c3f3.html
Заголовок, (Title) документа по адресу, URL1:
Pollard's kangaroo algorithm - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)