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

Алгоритмическая проблема

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

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

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

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

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

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

Пример

Эта функция определяет циклы {4} и {1, 6, 3}.

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

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

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

Определения

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

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

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

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

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

Алгоритмы

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

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

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

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

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

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

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

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

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

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

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

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

Следующий код Python более подробно демонстрирует, как работает эта техника.

def  brent ( f ,  x0 )  ->  ( int ,  int ): """Алгоритм обнаружения цикла Брента.""" # основная фаза: поиск последовательных степеней двойки power = lam = 1 tortoise = x0 hare = f ( x0 ) # f(x0) — это элемент/узел, следующий за x0. # это предполагает, что есть цикл; в противном случае этот цикл не будет завершен while tortoise != hare : if power == lam : # пора начинать новую степень двойки? tortoise = hare power *= 2 lam = 0 hare = f ( hare ) lam += 1                                        # Найти позицию первого повторения длины λ  черепаха  =  заяц  =  x0  для  i  в  диапазоне ( lam ):  # range(lam) создает список со значениями 0, 1, ... , lam-1  заяц  =  f ( hare )  # Расстояние между зайцем и черепахой теперь равно λ. # Далее заяц и черепаха движутся с одинаковой скоростью, пока не согласятся  mu  =  0 ,  пока  черепаха  !=  заяц :  черепаха  =  f ( черепаха )  заяц  =  f ( заяц )  mu  +=  1  вернуться  лам ,  му

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

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

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

Преимущества

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

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

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

Приложения

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

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

Ссылки

1. Жу, Антуан (2009), Алгоритмический криптоанализ, CRC Press, стр. 223, ISBN 9781420070033.
2. Joux (2009, стр. 224).
3. Knuth, Donald E. (1969), Искусство программирования, т. II: Получисленные алгоритмы , Addison-Wesley, стр. 7, упражнения 6 и 7
4. Справочник по прикладной криптографии, Альфред Дж. Менезес, Пол К. ван Ооршот, Скотт А. Ванстоун, стр. 125, описывает этот алгоритм и другие.
5. Флойд, РВ (1967), «Недетерминированные алгоритмы», J. ACM , 14 (4): 636–644, doi : 10.1145/321420.321422 , S2CID  1990464
6. Хэш-функция BLAKE, Жан-Филипп Омассон, Вилли Мейер, Рафаэль К.-В. Фан, Лука Хензен (2015), с. 21, сноска 8
7. Жу (2009), Раздел 7.1.1, Алгоритм поиска цикла Флойда, стр. 225–226.
8. Брент, RP (1980), «Улучшенный алгоритм факторизации Монте-Карло» (PDF) , BIT Numerical Mathematics , 20 (2): 176–184, doi :10.1007/BF01933190, S2CID  17181286.
9. Жу (2009), Раздел 7.1.2, Алгоритм поиска цикла Брента, стр. 226–227.
10. "Архивная копия". Архивировано из оригинала 2016-04-14 . Получено 2017-02-08 .{{cite web}}: CS1 maint: archived copy as title (link)
11. "Hakmem -- Потоки и итерированные функции -- Черновик, пока не проверен". Архивировано из оригинала 2020-03-18 . Получено 2024-05-02 .
12. Ниваш, Габриэль (2004), «Обнаружение цикла с использованием стека», Information Processing Letters , 90 (3): 135–140, doi :10.1016/j.ipl.2004.01.016.
13. Шнорр, Клаус П.; Ленстра , Хендрик В. (1984), «Алгоритм факторизации Монте-Карло с линейным хранилищем», Математика вычислений , 43 (167): 289–311, doi :10.2307/2007414, hdl : 1887/3815 , JSTOR  2007414.
14. Teske, Edlyn (1998), "Алгоритм с эффективным использованием пространства для вычисления структуры группы", Mathematics of Computation , 67 (224): 1637–1663, Bibcode : 1998MaCom..67.1637T, doi : 10.1090/S0025-5718-98-00968-5.
15. Седжвик, Роберт ; Шимански, Томас Г.; Яо, Эндрю К.-К. (1982), «Сложность поиска циклов в периодических функциях», SIAM Journal on Computing , 11 (2): 376–390, doi :10.1137/0211030.
16. ван Ооршот, Пол К.; Винер, Майкл Дж. (1999), «Параллельный поиск коллизий с использованием криптоаналитических приложений», Журнал криптологии , 12 (1): 1–28, doi : 10.1007/PL00003816 , S2CID  5091635.
17. Quisquater, J.-J.; Delescaille, J.-P., "Насколько прост поиск коллизий? Применение к DES", Advances in Cryptology – EUROCRYPT '89, Workshop on the Theory and Application of Cryptographic Techniques , Lecture Notes in Computer Science, т. 434, Springer-Verlag, стр. 429–434, doi : 10.1007/3-540-46885-4_43.
18. Fich, Faith Ellen (1981), "Нижние границы для проблемы обнаружения цикла", Proc. 13th ACM Symposium on Theory of Computing , стр. 96–105, doi :10.1145/800076.802462, S2CID  119742106.
19. Аллендер, Эрик В.; Клаве , Мария М. (1985), «Улучшенные нижние границы для задачи обнаружения цикла», Теоретическая информатика , 36 (2–3): 231–237, doi : 10.1016/0304-3975(85)90044-1.
20. Поллард, Дж. М. (1975), «Метод Монте-Карло для факторизации», BIT , 15 (3): 331–334, doi :10.1007/BF01933667, S2CID  122775546.
21. Поллард, Дж. М. (1978), «Методы Монте-Карло для вычисления индекса (mod p )», Математика вычислений , 32 (143), Американское математическое общество: 918–924, doi : 10.2307/2006496, JSTOR  2006496, S2CID  235457090.
22. Kaliski, Burton S. Jr.; Rivest, Ronald L .; Sherman, Alan T. (1988), «Является ли стандарт шифрования данных группой? (Результаты циклических экспериментов по DES)», Journal of Cryptology , 1 (1): 3–36, doi : 10.1007/BF00206323 , S2CID  17224075.
23. Жу (2009), Раздел 7.5, Коллизии в хэш-функциях, стр. 242–245.
24. Ван Гелдер, Аллен (1987), «Эффективное обнаружение циклов в Прологе с использованием техники черепахи и зайца», Журнал логического программирования , 4 (1): 23–31, doi : 10.1016/0743-1066(87)90020-3.
25. Auguston, Michael; Hon, Miu Har (1997), «Утверждения для динамического анализа формы списочных структур данных», AADEBUG '97, Труды третьего международного семинара по автоматической отладке, Linköping Electronic Articles in Computer and Information Science, Linköping University , стр. 37–42.

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

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