В вычислительной теории чисел[en] и вычислительной алгебре алгоритм «кенгуру» Полларда (а также лямбда-алгоритм Полларда, см. раздел «Название» ниже) — это алгоритм решения задачи дискретного логарифмирования. Алгоритм был предложен в 1978 специалистом в области теории чисел Дж. М. Поллардом[en] в той же статье[1], что и его более известный ρ-алгоритм для решения той же задачи. Хотя Поллард описывает применение этого алгоритма для задачи дискретного логарифмирования в мультипликативной группе по модулю простого p, он является, фактически, общим алгоритмом дискретного логарифмирования — он будет работать на любой циклической конечной группе.
Пусть — конечная циклическая группа порядка , генерируемая элементом , и мы ищем дискретный логарифм элемента по основанию . Другими словами, мы ищем , такое, что . Лямбда-алгоритм позволяет нам искать в некотором подмножестве . Мы можем искать полный набор возможных логарифмов, приняв и , хотя в этом случае ρ-алгоритм будет эффективнее. Поступаем следующим образом:
1. Выбираем множество целых чисел и определяем псевдослучайное отображение[en] .
2. Выберем целое число и вычислим последовательность элементов группы согласно формулам:
3. Вычислим
Заметим, что
4. Начинаем вычислять вторую последовательность элементов группы по формулам
и соответствующую последовательность целых чисел согласно формуле
Заметим, что
5. Прекращаем вычисления и , когда выполняется одно из условий
Поллард указал для алгоритма временную сложность , основываясь на вероятностной аргументации, что вытекает из предположения, что f действует псевдослучайно. Заметим, что в случае, когда размер множества {a, …, b} измеряется а битах, что обычно в теории сложности, множество имеет размер log(b − a), так что алгоритмическая сложность равна , что является экспонентой от размера задачи. По этой причине лямбда-алгоритм Полларда считается алгоритмом экспоненциальной сложности. За примером подэкспоненциального по времени алгоритма см. Алгоритм исчисления порядка.
Алгоритм известен под двумя названиями.
Первое название — алгоритм «кенгуру» Полларда. Имя относится к аналогии, используемой в статье, где алгоритм был предложен. В статье алгоритм объясняется в терминах использования ручного кенгуру для поимки дикого. Как объяснял Поллард[2], эта аналогия была навеяна «обворожительной» статьёй, опубликованной в том же выпуске журнала Scientific American, что и публикация RSA криптосистемы с открытым ключом. Статья[3] описывает эксперимент, в котором «энергетическая цена движения кенгуру, измеренная в терминах потребления кислорода на различных скоростях, была определена путём помещения кенгуру на беговую дорожку».
Второе название — лямбда-алгоритм Полларда. Очень похоже на имя другого алгоритма Полларда для дискретного логарифмирования, ρ-алгоритма, и это имя связано с похожестью визуализации алгоритма с греческой буквой лямбда ( ). Короткая линия буквы лямбда соответствует последовательности . Соответственно, длинная линия соответствует последовательности , которая «сталкивается с» первой последовательностью (подобно встрече короткой и длинной линии буквы).
Поллард предпочитает использование названия «алгоритм кенгуру»[4], чтобы избежать путнаницы с некоторыми параллельными версиями ρ-алгоритма, которые тоже носят название «лямбда-алгоритмы».
Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .