Алгоритм кенгуру Полларда
Алгоритм в вычислительной теории чисел

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

Алгоритм

Предположим, что есть конечная циклическая группа порядка , которая порождается элементом , и мы стремимся найти дискретный логарифм элемента по основанию . Другими словами, мы ищем такое, что . Алгоритм лямбда позволяет искать в некотором интервале . Можно искать во всем диапазоне возможных логарифмов, установив и . Г {\displaystyle G} н {\displaystyle n} α {\displaystyle \альфа} х {\displaystyle x} β {\displaystyle \бета} α {\displaystyle \альфа} х ∈ З н {\displaystyle x\in Z_{n}} α х = β {\displaystyle \альфа ^{x}=\бета } х {\displaystyle x} [ а , … , б ] ⊂ З н {\displaystyle [a,\ldots ,b]\subset Z_{n}} а = 0 {\displaystyle а=0} б = н − 1 {\displaystyle b=n-1}

1. Выберите набор положительных целых чисел со средним значением приблизительно и определите псевдослучайную карту . С {\displaystyle S} б − а {\displaystyle {\sqrt {ба}}} ф : Г → С {\displaystyle f:G\rightarrow S}

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

  • х 0 = α б {\displaystyle x_{0}=\альфа ^{b}\,}
  • х я + 1 = х я α ф ( х я )  для  я = 0 , 1 , … , Н − 1 {\displaystyle x_{i+1}=x_{i}\alpha ^{f(x_{i})}{\text{ для }}i=0,1,\ldots ,N-1}

3. Вычислить

г = ∑ я = 0 Н − 1 ф ( х я ) . {\displaystyle d=\sum _{i=0}^{N-1}f(x_{i}).}

Обратите внимание, что:

х Н = х 0 α г = α б + г . {\displaystyle x_{N}=x_{0}\альфа ^{d}=\альфа ^{b+d}\,.}

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

  • у 0 = β {\displaystyle y_{0}=\beta \,}
  • у я + 1 = у я α ф ( у я )  для  я = 0 , 1 , … , Н − 1 {\displaystyle y_{i+1}=y_{i}\alpha ^{f(y_{i})}{\text{ для }}i=0,1,\ldots ,N-1}

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

г н = ∑ я = 0 н − 1 ф ( у я ) {\displaystyle d_{n}=\sum _{i=0}^{n-1}f(y_{i})} .

Обратите внимание, что:

у я = у 0 α г я = β α г я  для  я = 0 , 1 , … , Н − 1 {\displaystyle y_{i}=y_{0}\альфа ^{d_{i}}=\бета \альфа ^{d_{i}}{\mbox{ для }}i=0,1,\ldots ,N-1}

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

A) для некоторых . Если последовательности и «сталкиваются» таким образом, то имеем: у дж = х Н {\displaystyle y_{j}=x_{N}} дж {\displaystyle j} { х я } {\displaystyle \{x_{i}\}} { у дж } {\displaystyle \{y_{j}\}}
х Н = у дж ⇒ α б + г = β α г дж ⇒ β = α б + г − г дж ⇒ х ≡ б + г − г дж ( мод н ) {\displaystyle 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}}}
и вот мы закончили.
B) . Если это произошло, то алгоритм не смог найти . Последующие попытки можно предпринять, изменив выбор и/или . г я > б − а + г {\displaystyle d_{i}>b-a+d} х {\displaystyle x} С {\displaystyle S} ф {\displaystyle f}

Сложность

Поллард дает временную сложность алгоритма как , используя вероятностный аргумент, основанный на предположении, что действует псевдослучайно. Поскольку может быть представлено с использованием битов, это экспоненциально по размеру проблемы (хотя все еще является значительным улучшением по сравнению с тривиальным алгоритмом грубой силы, который занимает время ). Пример алгоритма дискретного логарифма с субэкспоненциальным временем см. в алгоритме исчисления индексов . О ( б − а ) {\displaystyle O({\sqrt {ba}})} ф {\displaystyle f} а , б {\displaystyle а,б} О ( бревно ⁡ б ) {\displaystyle O(\log b)} О ( б − а ) {\displaystyle O(ба)}

Нейминг

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

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

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

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

Смотрите также

Ссылки

  1. ^ Поллард, Джон М. (июль 1978 г.) [1977-05-01, 1977-11-18]. "Методы Монте-Карло для вычисления индекса (mod p)" (PDF) . Математика вычислений . 32 (143). Математический факультет, Plessey Telecommunications Research, Taplow Court, Maidenhead, Berkshire, UK: American Mathematical Society : 918– 924. ISSN  0025-5718. Архивировано (PDF) из оригинала 2013-05-03 . Получено 2023-08-19 .(7 страниц)
  2. ^ Ван Ооршот, Пол К .; Винер, Майкл Дж. (1999). «Параллельный поиск коллизий с криптоаналитическими приложениями». Журнал криптологии . 12 (1). Международная ассоциация криптологических исследований : 1– 28. doi : 10.1007/PL00003816. ISSN  0933-2790.
  3. ^ Поллард, Джон М. (2000-08-10) [1998-01-23, 1999-09-27]. "Кенгуру, монополия и дискретные логарифмы" (PDF) . Журнал криптологии . 13 (4). Tidmarsh Cottage, Manor Farm Lane, Tidmarsh, Reading, UK: Международная ассоциация криптологических исследований : 437– 447. doi :10.1007/s001450010010. ISSN  0933-2790. Архивировано (PDF) из оригинала 2023-08-18 . Получено 2023-08-19 .(11 страниц)
  4. ^ Доусон, Теренс Дж. (1977-08-01). «Кенгуру». Scientific American . Т. 237, № 2. Scientific American, Inc. стр.  78–89 . ISSN  0036-8733. JSTOR  24954004.
  5. ^ Поллард, Джон М. "Jmptidcott2". Архивировано из оригинала 2023-08-18 . Получено 2023-08-19 .
  6. ^ Поллард, Джон М. (июль 2000 г.). «Карточный фокус Крускала» (PDF) . The Mathematical Gazette . 84 (500). Tidmarsh Cottage, Manor Farm Lane, Tidmarsh, Reading, UK: The Mathematical Association : 265– 267. doi :10.2307/3621657. ISSN  0025-5572. JSTOR  3621657. 84.29. Архивировано (PDF) из оригинала 2023-08-18 . Получено 2023-08-19 .(1+3 страницы)

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

  • Montenegro, Ravi [at Wikidata] ; Tetali, Prasad V. (2010-11-07) [2009-05-31]. Сколько времени потребуется, чтобы поймать дикого кенгуру? (PDF) . Труды сорок первого ежегодного симпозиума ACM по теории вычислений (STOC 2009). стр.  553–560 . arXiv : 0812.0789 . doi :10.1145/1536414.1536490. S2CID  12797847. Архивировано (PDF) из оригинала 20.08.2023 . Получено 20.08.2023 .
Получено с "https://en.wikipedia.org/w/index.php?title=Поллард%27s_кенгару_алгоритм&oldid=1269587122"