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

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

Алгоритм

Предполагать $G$ — конечная циклическая группа порядка $n$ который генерируется элементом $\alpha$, и мы пытаемся найти дискретный логарифм $x$ элемента $\beta$ на базу $\alpha$. Другими словами, человек ищет $x\in Z_{n}$ такой, что $\alpha ^{x}=\beta$. Лямбда-алгоритм позволяет искать $x$ через некоторый интервал $[a,\ldots ,b]\subset Z_{n}$. Можно выполнить поиск во всем диапазоне возможных логарифмов, задав $a=0$ и $b=n-1$.

1. Выберите набор $S$ положительных целых чисел со средним примерно ${\sqrt {b-a}}$ и определим псевдослучайную карту $f:G\rightarrow S$.

2. Выберите целое число $N$ и вычислить последовательность элементов группы $\{x_{0},x_{1},\ldots ,x_{N}\}$ в соответствии с:

• $x_{0}=\alpha ^{b}\,$
• $x_{i+1}=x_{i}\alpha ^{f(x_{i})}{\text{ for }}i=0,1,\ldots ,N-1$

3. Вычислить

$d=\sum _{i=0}^{N-1}f(x_{i}).$

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

$x_{N}=x_{0}\alpha ^{d}=\alpha ^{b+d}\,.$

4. Начните вычисление второй последовательности элементов группы. $\{y_{0},y_{1},\ldots \}$ в соответствии с:

• $y_{0}=\beta \,$
• $y_{i+1}=y_{i}\alpha ^{f(y_{i})}{\text{ for }}i=0,1,\ldots ,N-1$

и соответствующая последовательность целых чисел $\{d_{0},d_{1},\ldots \}$ в соответствии с:

$d_{n}=\sum _{i=0}^{n-1}f(y_{i})$.

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

$y_{i}=y_{0}\alpha ^{d_{i}}=\beta \alpha ^{d_{i}}{\mbox{ for }}i=0,1,\ldots ,N-1$

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

А) $y_{j}=x_{N}$ для некоторых $j$. Если последовательности $\{x_{i}\}$ и $\{y_{j}\}$ «сталкиваться» таким образом, то мы имеем:

$x_{N}=y_{j}\Rightarrow \alpha ^{b+d}=\beta \alpha ^{d_{j}}\Rightarrow \beta =\alpha ^{b+d-d_{j}}\Rightarrow x\equiv b+d-d_{j}{\pmod {n}}$

и вот мы закончили.

Б) $d_{i}>b-a+d$. Если это произошло, то алгоритму не удалось найти $x$. Последующие попытки можно предпринимать, меняя выбор $S$ и/или $f$.

Сложность

Поллард определяет временную сложность алгоритма как $O({\sqrt {b-a}})$, используя вероятностный аргумент, основанный на предположении, что $f$ действует псевдослучайно. С $a,b$ можно представить с помощью $O(\log b)$ бит, это экспоненциально влияет на размер задачи (хотя все же это значительное улучшение по сравнению с тривиальным алгоритмом грубой силы, который требует времени). $O(b-a)$). Пример субэкспоненциального алгоритма дискретного логарифма см. в разделе «Алгоритм исчисления индексов» .

Мы

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

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

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

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

См. также

• Карточные фокусы Дынкина
• Крускал граф
• Радужный стол

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

• Черногория, Рави [в Викиданных] ; Тетали, Прасад В. (7 ноября 2010 г.) [31 мая 2009 г.]. Сколько времени нужно, чтобы поймать дикого кенгуру? (PDF) . Материалы сорок первого ежегодного симпозиума ACM по теории вычислений (STOC 2009). стр. 553–560. arXiv : 0812.0789 . дои : 10.1145/1536414.1536490 . S2CID   12797847 . Архивировано (PDF) из оригинала 20 августа 2023 г. Проверено 20 августа 2023 г.