Обнаружение цикла - Cycle detection

Эта статья о повторяющихся функциях. Для другого использования см. Обнаружение цикла (теория графов).

В Информатика, обнаружение цикла или поиск цикла это алгоритмический проблема поиска цикла в последовательность из повторяющаяся функция ценности.

Для любого функция ж что отображает конечный набор S самому себе, и любое начальное значение Икс₀ в S, последовательность значений повторяемой функции

${\displaystyle x_{0},\ x_{1}=f(x_{0}),\ x_{2}=f(x_{1}),\ \dots ,\ x_{i}=f(x_{i-1}),\ \dots }$

должен в конечном итоге использовать одно и то же значение дважды: должна быть какая-то пара различных индексов я и j такой, что Икс_я = Икс_j. Как только это произойдет, последовательность должна продолжиться. периодически, повторяя ту же последовательность значений из Икс_я к Икс_{j − 1}. Обнаружение цикла - это проблема поиска я и j, данный ж и Икс₀.

Известно несколько алгоритмов быстрого нахождения циклов с небольшим объемом памяти. Роберт В. Флойд с алгоритм черепаха и заяц перемещает два указателя с разной скоростью по последовательности значений, пока они оба не укажут на равные значения. В качестве альтернативы алгоритм Брента основан на идее экспоненциальный поиск. Алгоритмы как Флойда, так и Брента используют только постоянное количество ячеек памяти и выполняют ряд вычислений функций, которые пропорциональны расстоянию от начала последовательности до первого повторения. Некоторые другие алгоритмы жертвуют большим объемом памяти за меньшее количество вычислений функций.

Приложения обнаружения цикла включают проверку качества генераторы псевдослучайных чисел и криптографические хеш-функции, вычислительная теория чисел алгоритмы, обнаружение бесконечные циклы в компьютерных программах и периодических конфигурациях в клеточные автоматы, автоматизированный анализ формы из связанный список структуры данных, обнаружение тупиковые ситуации для управление транзакциями в СУБД.

пример

Функция из и в набор {0,1,2,3,4,5,6,7,8} и соответствующий функциональный граф

На рисунке показана функция ж который отображает набор S = {0,1,2,3,4,5,6,7,8} себе. Если начать с Икс₀ = 2 и неоднократно применяет ж, видна последовательность значений

2, 0, 6, 3, 1, 6, 3, 1, 6, 3, 1, ....

Цикл в этой последовательности значений равен 6, 3, 1.

Определения

Позволять S любое конечное множество, ж быть любой функцией из S себе, и Икс₀ быть любым элементом S. Для любого я > 0, позволять Икс_я = ж(Икс_{я − 1}). Позволять μ наименьший индекс такой, что значение Икс_μ повторяется бесконечно часто в последовательности значений Икс_я, и разреши λ (длина цикла) - наименьшее положительное целое число такое, что Икс_μ = Икс_{λ + μ}. Проблема обнаружения цикла - это задача поиска λ иμ.^[1]

Можно увидеть ту же проблему теоретико-графовый, построив функциональный график (это ориентированный граф в котором каждая вершина имеет одно выходящее ребро), вершины которого являются элементами S и края которых сопоставляют элемент с соответствующим значением функции, как показано на рисунке. Множество вершин достижимый от начальной вершины Икс₀ сформировать подграф с формой, напоминающей Греческая буква ро (ρ): путь длины μ от Икс₀ к цикл из λ вершины.^[2]

Компьютерное представление

В общем, ж не будет указываться в виде таблицы значений, как показано на рисунке выше. Скорее, алгоритму обнаружения цикла может быть предоставлен доступ либо к последовательности значений Икс_я, или подпрограмме для расчета ж. Задача найти λ и μ при этом проверяется как можно меньше значений из последовательности или выполняется как можно меньше вызовов подпрограмм. Как правило, также космическая сложность алгоритма для задачи обнаружения цикла имеет важное значение: мы хотим решить проблему, используя объем памяти, значительно меньший, чем потребуется для хранения всей последовательности.

В некоторых приложениях, в частности в Алгоритм ро Полларда для целочисленная факторизация, алгоритм имеет гораздо более ограниченный доступ к S и чтобы ж. Например, в алгоритме ро Полларда S представляет собой набор целых чисел по модулю неизвестного простого множителя числа, которое нужно разложить на множители, поэтому даже размер S неизвестно алгоритму. Чтобы позволить использовать алгоритмы обнаружения цикла с такими ограниченными знаниями, они могут быть разработаны на основе следующих возможностей. Первоначально предполагается, что алгоритм имеет в своей памяти объект, представляющий указатель к начальному значению Икс₀. На любом этапе он может выполнить одно из трех действий: он может скопировать любой имеющийся указатель на другой объект в памяти, он может применить ж и заменить любой из его указателей указателем на следующий объект в последовательности, или он может применить подпрограмму для определения того, представляют ли два из его указателя равные значения в последовательности. Действие проверки равенства может включать в себя некоторые нетривиальные вычисления: например, в алгоритме ро Полларда оно реализуется путем проверки того, имеет ли разница между двумя сохраненными значениями нетривиальный характер. наибольший общий делитель с числом, которое нужно разложить.^[2] В этом контексте по аналогии с указатель Модель вычисления, алгоритм, который использует только копирование указателя, продвижение в последовательности и проверки равенства, может быть назван алгоритмом указателя.

Алгоритмы

Если ввод задан как подпрограмма для вычисления ж, проблема обнаружения цикла может быть тривиально решена, используя только λ + μ функции приложения, просто вычисляя последовательность значений Икс_я и используя структура данных например, хеш-таблица чтобы сохранить эти значения и проверить, было ли уже сохранено каждое последующее значение. Однако пространственная сложность этого алгоритма пропорциональна λ + μ, излишне большой. Кроме того, чтобы реализовать этот метод как указатель алгоритм потребует применения теста на равенство к каждой паре значений, что приведет к квадратичному времени в целом. Таким образом, исследования в этой области были сосредоточены на двух целях: использование меньшего пространства, чем этот наивный алгоритм, и поиск алгоритмов указателей, которые используют меньше тестов на равенство.

Черепаха и Заяц Флойда

Алгоритм обнаружения цикла "черепаха и заяц" Флойда, примененный к последовательности 2, 0, 6, 3, 1, 6, 3, 1, ...

Алгоритм поиска цикла Флойда представляет собой алгоритм указателя, который использует только два указателя, которые перемещаются по последовательности с разной скоростью. Его также называют "алгоритмом черепахи и зайца", отсылая к басне Эзопа о Черепаха и заяц.

Алгоритм назван в честь Роберт В. Флойд, которому приписывают свое изобретение Дональд Кнут.^[3][4] Однако алгоритм не появляется в опубликованной работе Флойда, и это может быть неправильной атрибуцией: Флойд описывает алгоритмы для перечисления всех простых циклов в ориентированный граф в статье 1967 г.^[5] но эта статья не описывает проблему поиска циклов в функциональных графах, которая является предметом данной статьи. Фактически, заявление Кнута (1969 г.), приписывающее его Флойду, без цитирования, является первым известным появлением в печати и, таким образом, может быть народная теорема, не относящиеся к одному человеку.^[6]

Ключевое понимание алгоритма заключается в следующем. Если есть цикл, то для любых целых чисел я ≥ μ и k ≥ 0, Икс_я = Икс_{я + kλ}, где λ длина петли, которую нужно найти, и μ - индекс первого элемента цикла. На основании этого можно показать, что я = kλ ≥ μ для некоторых k если и только если Икс_я = Икс_2яТаким образом, алгоритму нужно только проверить повторяющиеся значения этой специальной формы, одно в два раза дальше от начала последовательности, чем другое, чтобы найти период. ν повторения, кратного λ.Однажды ν найден, алгоритм повторяет последовательность от ее начала, чтобы найти первое повторяющееся значение Икс_μ в последовательности, используя тот факт, что λ разделяет ν и поэтому Икс_μ = Икс_{μ + v}. Наконец, как только значение μ известно, что найти длину λ кратчайшего повторяющегося цикла путем поиска первой позиции μ + λ для которого Икс_{μ + λ} = Икс_μ.

Таким образом, алгоритм поддерживает два указателя на заданную последовательность, один (черепаха) в Икс_я, а другой (заяц) на Икс_2я. На каждом шаге алгоритма он увеличивается я на один, перемещая черепаху на один шаг вперед, а зайца на два шага вперед в последовательности, а затем сравнивает значения последовательности на этих двух указателях. Наименьшее значение я > 0 для которого черепаха и заяц указывают на равные значения, является искомым значением ν.

Следующее Python код показывает, как эту идею можно реализовать в виде алгоритма.

def Флойд(ж, x0):    # Основная фаза алгоритма: поиск повторения x_i = x_2i.    # Заяц движется вдвое быстрее черепахи и    # расстояние между ними увеличивается на 1 с каждым шагом.    # В конце концов они оба окажутся внутри цикла, а затем,    # в какой-то момент расстояние между ними будет    # делится на период λ.    черепаха = ж(x0) # f (x0) - это элемент / узел рядом с x0.    заяц = ж(ж(x0))    в то время как черепаха != заяц:        черепаха = ж(черепаха)        заяц = ж(ж(заяц))      # В этот момент положение черепахи ν, которое также равно    # к расстоянию между зайцем и черепахой, делится на    # период λ. Так заяц двигается по кругу шаг за шагом,     # и черепаха (сбросить на x0) движется к кругу, будет     # пересекаются в начале круга. Поскольку     # расстояние между ними постоянно на 2ν, кратном λ,    # они согласятся, как только черепаха достигнет индекса μ.    # Найдите позицию μ первого повторения.     му = 0    черепаха = x0    в то время как черепаха != заяц:        черепаха = ж(черепаха)        заяц = ж(заяц)   # Заяц и черепаха двигаются с одинаковой скоростью        му += 1     # Находим длину кратчайшего цикла, начиная с x_μ    # Заяц двигается шаг за шагом, пока черепаха неподвижна.    # lam увеличивается до тех пор, пока не будет найдено λ.    лам = 1    заяц = ж(черепаха)    в то время как черепаха != заяц:        заяц = ж(заяц)        лам += 1     вернуть лам, му

Этот код обращается к последовательности только путем сохранения и копирования указателей, оценок функций и тестов на равенство; поэтому он квалифицируется как алгоритм указателя. Алгоритм использует О(λ + μ) операции этих типов, и О(1) место для хранения.^[7]

Алгоритм Брента

Ричард П. Брент описал альтернативный алгоритм определения цикла, который, как и алгоритм черепахи и зайца, требует только двух указателей на последовательность.^[8] Однако он основан на другом принципе: поиск самых маленьких сила двух 2^я это больше, чем оба λ и μ. Для я = 0, 1, 2, ..., алгоритм сравнивает Икс_2^я−1 с каждым последующим значением последовательности до следующей степени двойки, останавливаясь при нахождении совпадения. Он имеет два преимущества по сравнению с алгоритмом черепахи и зайца: он находит правильную длину. λ цикла напрямую, вместо того, чтобы искать его на следующем этапе, а его этапы включают только одну оценку ж а не три.^[9]

В следующем коде Python более подробно показано, как работает этот метод.

def Brent(ж, x0):    # основная фаза: поиск последовательных степеней двойки    мощность = лам = 1    черепаха = x0    заяц = ж(x0)  # f (x0) - это элемент / узел рядом с x0.    в то время как черепаха != заяц:        если мощность == лам:  # пора ли начинать новую степень двойки?            черепаха = заяц            мощность *= 2            лам = 0        заяц = ж(заяц)        лам += 1    # Найти позицию первого повторения длины λ    черепаха = заяц = x0    для я в ассортимент(лам):    # range (lam) создает список со значениями 0, 1, ..., lam-1        заяц = ж(заяц)    # Расстояние между зайцем и черепахой теперь λ.    # Далее заяц и черепаха двигаются с одинаковой скоростью, пока не согласятся    му = 0    в то время как черепаха != заяц:        черепаха = ж(черепаха)        заяц = ж(заяц)        му += 1     вернуть лам, му

Подобно алгоритму черепахи и зайца, это алгоритм указателя, который использует О(λ + μ) тесты и оценки функций и О(1) место для хранения. Нетрудно показать, что количество вычислений функций никогда не может быть больше, чем для алгоритма Флойда. Брент утверждает, что в среднем его алгоритм поиска цикла работает примерно на 36% быстрее, чем алгоритм Флойда, и что он ускоряет Алгоритм полларда ро примерно на 24%. Он также выполняет анализ среднего случая для рандомизированной версии алгоритма, в которой последовательность индексов, отслеживаемых более медленным из двух указателей, не является степенью двойки как таковой, а скорее рандомизированным кратным степени двойки. Хотя его основное предполагаемое применение было в алгоритмах целочисленной факторизации, Брент также обсуждает приложения для тестирования генераторов псевдослучайных чисел.^[8]

Алгоритм госпера

Р. В. Госпер алгоритм^[10][11] находит период ${\displaystyle \lambda }$, а также нижнюю и верхнюю границы начальной точки, ${\displaystyle \mu _{l}}$ и ${\displaystyle \mu _{u}}$, первого цикла. Разница между нижней и верхней границей того же порядка, что и период, например. ${\displaystyle \mu _{l}+\lambda \sim \mu _{h}}$.

Основная особенность алгоритма Госпера заключается в том, что он никогда не выполняет резервное копирование для переоценки функции генератора и экономичен как в пространстве, так и во времени. Это можно примерно описать как параллельную версию алгоритма Брента. В то время как алгоритм Брента постепенно увеличивает разрыв между черепахой и зайцем, алгоритм Госпера использует несколько черепах (сохраняются несколько предыдущих значений), которые расположены примерно по экспоненте. Согласно примечанию в HAKMEM пункт 132, этот алгоритм обнаружит повторение до третьего появления любого значения, например. цикл будет повторяться не более двух раз. В этом примечании также говорится, что достаточно хранить ${\displaystyle \Theta (\log \lambda )}$ предыдущие значения; однако предоставленная реализация^[10] магазины ${\displaystyle \Theta (\log(\mu +\lambda ))}$ ценности. Например: значения функции - 32-битные целые числа, и априори известно, что вторая итерация цикла заканчивается не более чем через 2³² оценки функций с самого начала, а именно. ${\displaystyle \mu +2\lambda \leq 2^{32}}$. Тогда достаточно сохранить 33 32-битных целых числа.

На ${\displaystyle i}$-я оценка функции генератора, алгоритм сравнивает сгенерированное значение с ${\displaystyle O(\log i)}$ предыдущие значения; заметьте, что ${\displaystyle i}$ доходит как минимум до ${\displaystyle \mu +\lambda }$ и самое большее ${\displaystyle \mu +2\lambda }$. Следовательно, временная сложность этого алгоритма равна ${\displaystyle O((\mu +\lambda )\cdot \log(\mu +\lambda ))}$. Поскольку он хранит ${\displaystyle \Theta (\log(\mu +\lambda ))}$ значений, его пространственная сложность составляет ${\displaystyle \Theta (\log(\mu +\lambda ))}$. Это происходит при обычном предположении, присутствующем в этой статье, что размер значений функции постоянен. Без этого предположения сложность пространства равна ${\displaystyle \Omega (\log ^{2}(\mu +\lambda ))}$ поскольку нам нужно как минимум ${\displaystyle \mu +\lambda }$ различные значения и, следовательно, размер каждого значения ${\displaystyle \Omega (\log(\mu +\lambda ))}$.

Компромиссы между пространством и временем

Ряд авторов изучили методы обнаружения циклов, которые используют больше памяти, чем методы Флойда и Брента, но обнаруживают циклы быстрее. Как правило, эти методы хранят несколько ранее вычисленных значений последовательности и проверяют, равно ли каждое новое значение одному из ранее вычисленных значений. Чтобы сделать это быстро, они обычно используют хеш-таблица или аналогичная структура данных для хранения ранее вычисленных значений и, следовательно, не является алгоритмом указателя: в частности, они обычно не могут быть применены к алгоритму rho Полларда. Эти методы различаются тем, как они определяют, какие значения хранить. Вслед за Ниващем^[12] мы кратко рассмотрим эти методы.

• Brent^[8] уже описывает варианты своей техники, в которых индексы сохраненных значений последовательности являются степенями числа. р кроме двух. Выбирая р быть числом, близким к единице, и сохранение значений последовательности в индексах, которые близки к последовательности последовательных степеней р, алгоритм обнаружения цикла может использовать ряд оценок функции, которые находятся в пределах произвольно малого коэффициента оптимального λ + μ.^[13][14]
• Седжвик, Шимански и Яо^[15] предоставить метод, который использует M ячейки памяти и требует только в худшем случае ${\displaystyle (\lambda +\mu )(1+cM^{-1/2})}$ оценки функций, для некоторой постоянной c, который они считают оптимальным. Методика предполагает поддержание числового параметра d, сохраняя в таблице только те позиции в последовательности, которые кратны d, и очистка стола и удвоение d всякий раз, когда было сохранено слишком много значений.
• Несколько авторов описали выдающаяся точка методы, которые хранят значения функций в таблице на основе критерия, включающего значения, а не (как в методе Седжевика и др.) на основе их положения. Например, значения равны нулю по модулю некоторого значения d может быть сохранен.^[16][17] Проще говоря, Ниващ^[12] выражает благодарность Д. П. Вудраффу за предложение хранить случайную выборку ранее увиденных значений, делая соответствующий случайный выбор на каждом этапе, чтобы выборка оставалась случайной.
• Ниващ^[12] описывает алгоритм, который не использует фиксированный объем памяти, но для которого ожидаемый объем используемой памяти (в предположении, что входная функция является случайной) является логарифмической по длине последовательности. При использовании этого метода элемент сохраняется в таблице памяти, когда ни один из последующих элементов не имеет меньшего значения. Как показывает Nivasch, предметы с этой техникой можно обслуживать, используя структура данных стека, и каждое последующее значение последовательности нужно сравнивать только с вершиной стека. Алгоритм завершается, когда обнаруживается повторяющийся элемент последовательности с наименьшим значением. Выполнение того же алгоритма с несколькими стеками с использованием случайных перестановок значений для изменения порядка значений в каждом стеке позволяет найти компромисс между пространством и временем, аналогичный предыдущим алгоритмам. Однако даже версия этого алгоритма с одним стеком не является алгоритмом указателя из-за необходимости сравнения, чтобы определить, какое из двух значений меньше.

Любой алгоритм обнаружения цикла, который хранит не более M значения из входной последовательности должны выполнять не менее ${\displaystyle (\lambda +\mu )\left(1+{\frac {1}{M-1}}\right)}$ оценки функций.^[18][19]

Приложения

Обнаружение цикла использовалось во многих приложениях.

• Определение продолжительности цикла генератор псевдослучайных чисел это одна мера его силы. Это приложение, которое цитирует Кнут при описании метода Флойда.^[3] Brent^[8] описывает результаты тестирования линейный конгруэнтный генератор таким образом; его срок оказался значительно меньше заявленного. Для более сложных генераторов последовательность значений, в которой должен быть найден цикл, может представлять не выход генератора, а его внутреннее состояние.
• Несколько теоретико-числовой алгоритмы основаны на обнаружении цикла, в том числе Алгоритм ро Полларда для целочисленной факторизации^[20] и связанные с ним кенгуру алгоритм для дискретный логарифм проблема.^[21]
• В криптографический приложения, возможность найти два различных значения Икс_{μ −- 1} и Икс_{λ + μ −- 1} отображается некоторой криптографической функцией ƒ на то же значение Икс_μ может указывать на слабость ƒ. Например, Quisquater и Delescaille^[17] применять алгоритмы обнаружения цикла при поиске сообщения и пары Стандарт шифрования данных ключи, которые отображают это сообщение в одно и то же зашифрованное значение; Калиски, Ривест, и Шерман^[22] также используют алгоритмы обнаружения цикла для атаки DES. Этот метод также можно использовать для поиска столкновение в криптографическая хеш-функция.^[23]
• Обнаружение цикла может быть полезным как способ обнаружения бесконечные циклы в определенных типах компьютерные программы.^[24]
• Периодические конфигурации в клеточный автомат моделирование может быть найдено путем применения алгоритмов обнаружения цикла к последовательности состояний автомата.^[12]
• Анализ формы из связанный список Структуры данных - это метод проверки правильности алгоритма с использованием этих структур. Если узел в списке неправильно указывает на более ранний узел в том же списке, структура сформирует цикл, который может быть обнаружен этими алгоритмами.^[25] В Common Lisp, то S-выражение принтер, под управлением * круглая печать * переменная, определяет круговую структуру списка и компактно распечатывает ее.
• Теске^[14] описывает приложения в вычислительная теория групп: определение структуры Абелева группа от набора его генераторов. Криптографические алгоритмы Калиски и др.^[22] может также рассматриваться как попытка вывести структуру неизвестной группы.
• Фич (1981) кратко упоминает приложение к компьютерное моделирование из небесная механика, которую она приписывает Уильям Кахан. В этом приложении обнаружение цикла в фазовое пространство орбитальной системы может использоваться, чтобы определить, является ли система периодической в ​​пределах точности моделирования.^[18]
• В генерации фракталов Мандельброта используются некоторые методы повышения производительности для ускорения генерации изображений. Один из них называется «проверка периода» и в основном заключается в нахождении циклов на точечной орбите. В этой статье описывается "проверка периода "техника и Вот вы можете найти лучшее объяснение. Чтобы реализовать это, необходимо реализовать некоторые алгоритмы обнаружения цикла.

использованная литература

1. Жу, Антуан (2009), Алгоритмический криптоанализ, CRC Press, стр. 223, г. ISBN  9781420070033.
2. Жу (2009, п. 224).
3. Кнут, Дональд Э. (1969), Искусство программирования, т. II: получисловые алгоритмы, Эддисон-Уэсли, стр. 7, упражнения 6 и 7
4. Справочник по прикладной криптографии, Альфред Дж. Менезес, Пол К. ван Оршот, Скотт А. Ванстон, п. 125, описывает этот алгоритм и другие
5. Флойд, Р. (1967), «Недетерминированные алгоритмы», J. ACM, 14 (4): 636–644, Дои:10.1145/321420.321422, S2CID  1990464
6. Хеш-функция BLAKE, Жан-Филипп Аумассон, Вилли Мейер, Рафаэль К.-В. Фан, Лука Хензен (2015), п. 21 год, сноска 8
7. Жу (2009), Раздел 7.1.1, Алгоритм поиска цикла Флойда, стр. 225–226.
8. Брент, Р. П. (1980), «Улучшенный алгоритм факторизации Монте-Карло» (PDF), BIT вычислительная математика , 20 (2): 176–184, Дои:10.1007 / BF01933190, S2CID  17181286.
9. Жу (2009), Раздел 7.1.2, Алгоритм поиска цикла Брента, стр. 226–227.
10. «Архивная копия». Архивировано из оригинал на 2016-04-14. Получено 2017-02-08.
11. http://www.inwap.com/pdp10/hbaker/hakmem/flows.html
12. Ниваш, Габриэль (2004), «Обнаружение цикла с использованием стека», Письма об обработке информации, 90 (3): 135–140, Дои:10.1016 / j.ipl.2004.01.016.
13. Шнорр, Клаус П.; Ленстра, Хендрик В. (1984), «Алгоритм факторизации Монте-Карло с линейной памятью», Математика вычислений, 43 (167): 289–311, Дои:10.2307/2007414, HDL:1887/3815, JSTOR  2007414.
14. Теске, Эдлин (1998), "Экономичный алгоритм для вычисления структуры группы", Математика вычислений, 67 (224): 1637–1663, Дои:10.1090 / S0025-5718-98-00968-5.
15. Седжвик, Роберт; Szymanski, Thomas G .; Яо, Эндрю К.-К. (1982), "Сложность нахождения циклов в периодических функциях", SIAM Журнал по вычислениям, 11 (2): 376–390, Дои:10.1137/0211030.
16. van Oorschot, Paul C .; Винер, Майкл Дж. (1999), «Параллельный поиск коллизий с криптоаналитическими приложениями», Журнал криптологии, 12 (1): 1–28, Дои:10.1007 / PL00003816, S2CID  5091635.
17. Quisquater, J.-J .; Делескайль, Ж.-П., "Насколько прост поиск столкновений? Применение в DES", Достижения в криптологии - EUROCRYPT '89, Семинар по теории и применению криптографических методов, Конспект лекций по информатике, 434, Springer-Verlag, стр. 429–434, Дои:10.1007/3-540-46885-4_43.
18. Фич, Фейт Эллен (1981), "Нижние оценки для задачи обнаружения цикла", Proc. 13-й ACM Симпозиум по теории вычислений, стр. 96–105, Дои:10.1145/800076.802462.
19. Аллендер, Эрик В.; Клаве, Мария М. (1985), "Улучшенные нижние границы для задачи обнаружения цикла", Теоретическая информатика, 36 (2–3): 231–237, Дои:10.1016/0304-3975(85)90044-1.
20. Поллард, Дж. М. (1975), "Метод Монте-Карло для факторизации", НЕМНОГО, 15 (3): 331–334, Дои:10.1007 / BF01933667, S2CID  122775546.
21. Поллард, Дж. М. (1978), «Методы Монте-Карло для вычисления индексов. (мод п)", Математика вычислений, Американское математическое общество, 32 (143): 918–924, Дои:10.2307/2006496, JSTOR  2006496.
22. Калиски, Бертон С., мл .; Ривест, Рональд Л.; Шерман, Алан Т. (1988), «Является ли стандарт шифрования данных группой? (Результаты циклических экспериментов по DES)», Журнал криптологии, 1 (1): 3–36, Дои:10.1007 / BF00206323, S2CID  17224075.
23. Жу (2009), Раздел 7.5, Коллизии в хэш-функциях, стр. 242–245.
24. Ван Гелдер, Аллен (1987), "Эффективное обнаружение петель в Прологе с использованием техники черепахи и зайца", Журнал логического программирования, 4 (1): 23–31, Дои:10.1016/0743-1066(87)90020-3.
25. Августон, Михаил; Хон, Миу Хар (1997), "Утверждения для анализа динамической формы структур данных списка", AADEBUG '97, Труды Третьего Международного семинара по автоматической отладке, Электронные статьи Linköping по информатике и информатике, Линчёпингский университет, стр. 37–42.

внешние ссылки

• Габриэль Ниваш, Проблема обнаружения цикла и алгоритм стека
• Черепаха и Заяц, Портлендский репозиторий паттернов
• Алгоритм обнаружения цикла Флойда (Черепаха и заяц)
• Алгоритм обнаружения цикла Брента (телепортирующаяся черепаха)