Detección de ciclo

En informática , la detección de ciclos o la búsqueda de ciclos es el problema algorítmico de encontrar un ciclo en una secuencia de valores de funciones iteradas .

Para cualquier función $f$ que asigna un conjunto finito $S$ a sí misma, y cualquier valor inicial $x 0$ en $S$ , la secuencia de valores de función iterados

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

eventualmente debe usar el mismo valor dos veces: debe haber algún par de índices distintos $i$ y $j$ tales que $x i = x j$ . Una vez que esto sucede, la secuencia debe continuar periódicamente , repitiendo la misma secuencia de valores desde $x i$ hasta $x j - 1$ . La detección de ciclos es el problema de encontrar $i$ y $j$ , dados $f$ y $x 0$ .

Se conocen varios algoritmos para encontrar ciclos rápidamente y con poca memoria. El algoritmo de la liebre y la tortuga de Robert W. Floyd mueve dos punteros a diferentes velocidades a través de la secuencia de valores hasta que ambos apuntan a valores iguales. Alternativamente, el algoritmo de Brent se basa en la idea de búsqueda exponencial . Tanto el algoritmo de Floyd como el de Brent utilizan sólo un número constante de celdas de memoria y toman un número de evaluaciones de funciones que es proporcional a la distancia desde el inicio de la secuencia hasta la primera repetición. Varios otros algoritmos intercambian mayores cantidades de memoria por menos evaluaciones de funciones.

Las aplicaciones de la detección de ciclos incluyen pruebas de la calidad de generadores de números pseudoaleatorios y funciones hash criptográficas , algoritmos computacionales de teoría de números , detección de bucles infinitos en programas informáticos y configuraciones periódicas en autómatas celulares , análisis automatizado de formas de estructuras de datos de listas enlazadas y detección de interbloqueos. para la gestión de transacciones en DBMS .

Ejemplo

La figura muestra una función $f$ que asigna el conjunto $S = {0,1,2,3,4,5,6,7,8}$ a sí mismo. Si se parte de $x 0 = 2$ y se aplica $f$ repetidamente , se ve la secuencia de valores

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

El ciclo en esta secuencia de valores es $6, 3, 1$ .

Definiciones

Sea $S$ cualquier conjunto finito, $f$ cualquier función desde $S$ respecto de sí mismo y $x 0$ cualquier elemento de $S.$ Para cualquier $i > 0$ , sea $x i = f (x i - 1)$ . Sea $μ$ el índice más pequeño tal que el valor $x μ$ reaparece infinitamente a menudo dentro de la secuencia de valores $x i$ , y sea $λ$ (la longitud del bucle) el entero positivo más pequeño tal que $x μ = x λ + μ$ . El problema de detección de ciclos consiste en encontrar $λ$ y $μ$ . ^[1]

Se puede ver el mismo problema en términos teóricos , construyendo un gráfico funcional (es decir, un gráfico dirigido en el que cada vértice tiene un único borde saliente) cuyos vértices son los elementos de $S$ y cuyos bordes asignan un elemento a el valor de la función correspondiente, como se muestra en la figura. El conjunto de vértices alcanzables desde el vértice inicial $x 0$ forma un subgrafo con una forma que se asemeja a la letra griega rho ( $ρ$ ): un camino de longitud $μ$ desde $x 0$ hasta un ciclo de $λ$ vértices. ^[2]

Representación informática

Generalmente, $f$ no se especificará como una tabla de valores, como se muestra en la figura anterior. $Más bien, a un algoritmo de detección de$ ciclo se le puede dar acceso a la secuencia de valores $xi$ o a una subrutina para calcular $f$ . La tarea es encontrar $λ$ y $μ$ mientras se examina la menor cantidad de valores de la secuencia o se realizan la menor cantidad posible de llamadas a subrutinas. Normalmente, también, la complejidad espacial de un algoritmo para el problema de detección de ciclos es importante: deseamos resolver el problema utilizando una cantidad de memoria significativamente menor de la que se necesitaría para almacenar la secuencia completa.

En algunas aplicaciones, y en particular en el algoritmo rho de Pollard para la factorización de enteros , el algoritmo tiene un acceso mucho más limitado a $S$ y a $f$ . En el algoritmo rho de Pollard, por ejemplo, $S$ es el conjunto de números enteros módulo un factor primo desconocido del número a factorizar, por lo que incluso el tamaño de $S$ es desconocido para el algoritmo. Para permitir que se utilicen algoritmos de detección de ciclos con un conocimiento tan limitado, se pueden diseñar en función de las siguientes capacidades. Inicialmente, se supone que el algoritmo tiene en su memoria un objeto que representa un puntero al valor inicial $x 0$ . En cualquier paso, puede realizar una de tres acciones: puede copiar cualquier puntero que tenga a otro objeto en la memoria, puede aplicar $f$ y reemplazar cualquiera de sus punteros por un puntero al siguiente objeto en la secuencia, o puede aplicar una subrutina para determinar si dos de sus punteros representan valores iguales en la secuencia. La acción de prueba de igualdad puede implicar algún cálculo no trivial: por ejemplo, en el algoritmo rho de Pollard, se implementa probando si la diferencia entre dos valores almacenados tiene un máximo común divisor no trivial con el número a factorizar. ^[2] En este contexto, por analogía con el modelo de cálculo de la máquina de punteros , un algoritmo que solo utiliza copia de punteros, avance dentro de la secuencia y pruebas de igualdad puede denominarse algoritmo de puntero.

Algoritmos

Si la entrada se proporciona como una subrutina para calcular $f$ , el problema de detección del ciclo puede resolverse trivialmente usando solo aplicaciones de funciones $λ + μ$ , simplemente calculando la secuencia de valores $x i$ y usando una estructura de datos como una tabla hash para almacenar estos valores y probar si cada valor subsiguiente ya ha sido almacenado. Sin embargo, la complejidad espacial de este algoritmo es proporcional a $λ + μ$ , innecesariamente grande. Además, implementar este método como un algoritmo de puntero requeriría aplicar la prueba de igualdad a cada par de valores, lo que daría como resultado un tiempo cuadrático en general. Por lo tanto, la investigación en esta área se ha concentrado en dos objetivos: utilizar menos espacio que este ingenuo algoritmo y encontrar algoritmos de puntero que utilicen menos pruebas de igualdad.

La tortuga y la liebre de Floyd

El algoritmo de búsqueda de ciclos de Floyd es un algoritmo de puntero que utiliza sólo dos punteros, que se mueven a través de la secuencia a diferentes velocidades. También se le llama "algoritmo de la liebre y la tortuga", en alusión a la fábula de Esopo de La liebre y la tortuga .

El algoritmo lleva el nombre de Robert W. Floyd , a quien Donald Knuth le atribuyó su invención . ^[3]^[4] Sin embargo, el algoritmo no aparece en el trabajo publicado de Floyd, y esto puede ser una atribución errónea: Floyd describe algoritmos para enumerar todos los ciclos simples en un gráfico dirigido en un artículo de 1967, ^[5] pero este artículo no Describa el problema de búsqueda de ciclos en gráficos funcionales que es el tema de este artículo. De hecho, la declaración de Knuth (en 1969), atribuyéndolo a Floyd, sin citar, es la primera aparición impresa conocida y, por lo tanto, puede ser un teorema popular , no atribuible a un solo individuo. ^[6]

La idea clave del algoritmo es la siguiente. Si hay un ciclo, entonces, para cualquier número entero $i \geq μ$ y $k \geq 0$ , $x i = x i + kλ$ , donde $λ$ es la longitud del bucle a encontrar, $μ$ es el índice del primer elemento del ciclo y $k$ es un número entero que representa el número de bucles. Con base en esto, se puede demostrar que $i = kλ \geq μ$ para algún $k$ si y sólo si $x i = x 2 i$ (si $x i = x 2 i$ en el ciclo, entonces existe algún $k$ tal que $2 i = i + kλ$ , lo que implica que $i = kλ$ ; y si hay algunas $i$ y $k$ tales que $i = kλ$ , entonces $2i = i + kλ$ y $x 2 i = x i + kλ$ ). Por lo tanto, el algoritmo solo necesita verificar si hay valores repetidos de esta forma especial, uno dos veces más lejos del inicio de la secuencia que el otro, para encontrar un período $ν$ de una repetición que sea múltiplo de $λ$ . Una vez que se encuentra $ν , el algoritmo vuelve sobre la secuencia desde su inicio para encontrar el primer valor repetido$ $x μ$ en la secuencia, utilizando el hecho de que $λ$ divide $a ν$ y por lo tanto que $x μ = x μ + v$ . Finalmente, una vez conocido el valor de $μ,$ es trivial encontrar la longitud $λ$ del ciclo repetitivo más corto, buscando la primera posición $μ + λ$ para la cual $x μ + λ = x μ$ .

Por tanto, el algoritmo mantiene dos punteros en la secuencia dada, uno (la tortuga) en $x i$ y el otro (la liebre) en $x 2 i$ . En cada paso del algoritmo, aumenta $i$ en uno, moviendo la tortuga un paso hacia adelante y la liebre dos pasos hacia adelante en la secuencia, y luego compara los valores de la secuencia en estos dos punteros. El valor más pequeño de $i > 0$ para el cual la tortuga y la liebre apuntan a valores iguales es el valor deseado $ν$ .

El siguiente código Python muestra cómo se puede implementar esta idea como un algoritmo.

def  floyd ( f ,  x0 )  ->  ( int ,  int ): """Algoritmo de detección del ciclo de Floyd.""" # Fase principal del algoritmo: encontrar una repetición x_i = x_2i. # La liebre se mueve dos veces más rápido que la tortuga y # la distancia entre ellas aumenta en 1 en cada paso. # Eventualmente ambos estarán dentro del ciclo y luego, # en algún momento, la distancia entre ellos será # divisible por el período λ. tortuga = f ( x0 ) # f(x0) es el elemento/nodo al lado de x0. liebre = f ( f ( x0 )) mientras que tortuga != liebre : tortuga = f ( tortuga ) liebre = f ( f ( liebre ))                          # En este punto la posición de la tortuga, ν, que también es igual  # a la distancia entre la liebre y la tortuga, es divisible por  # el período λ. Entonces, la liebre que se mueve en el ciclo un paso a la vez,  # y la tortuga (restablecida a x0) que se mueve hacia el ciclo,  # se cruzarán al comienzo del ciclo. Debido a que la  # distancia entre ellos es constante en 2ν, un múltiplo de λ,  # coincidirán tan pronto como la tortuga alcance el índice μ. # Encuentra la posición μ de la primera repetición.  mu  =  0  tortuga  =  x0  mientras  tortuga  !=  liebre :  tortuga  =  f ( tortuga )  liebre  =  f ( liebre )  # La liebre y la tortuga se mueven a la misma velocidad  mu  +=  1  # Encuentra la duración del ciclo más corto a partir de x_μ  # La liebre se mueve paso a paso mientras la tortuga está quieta.  # lam se incrementa hasta que se encuentra λ.  lam  =  1  liebre  =  f ( tortuga )  mientras que  tortuga  ! =  liebre :  liebre  =  f ( liebre )  lam  +=  1  volver  lam ,  mu

Este código solo accede a la secuencia almacenando y copiando punteros, evaluaciones de funciones y pruebas de igualdad; por lo tanto, califica como un algoritmo de puntero. El algoritmo utiliza $O (λ + μ)$ operaciones de este tipo y $O (1)$ espacio de almacenamiento. ^[7]

algoritmo de Brent

Richard P. Brent describió un algoritmo de detección de ciclos alternativo que, al igual que el algoritmo de la tortuga y la liebre, requiere sólo dos punteros en la secuencia. ^[8] Sin embargo, se basa en un principio diferente: buscar la potencia más pequeña de dos $2 i$ que sea mayor que $λ$ y $μ$ . Para $i = 0, 1, 2, ...$ , el algoritmo compara $x 2 i -1$ con cada valor de secuencia posterior hasta la siguiente potencia de dos, deteniéndose cuando encuentra una coincidencia. Tiene dos ventajas en comparación con el algoritmo de la liebre y la tortuga: encuentra la longitud correcta $λ$ del ciclo directamente, en lugar de tener que buscarla en una etapa posterior, y sus pasos implican sólo una evaluación de la función $f$ en lugar de tres. ^[9]

El siguiente código Python muestra cómo funciona esta técnica con más detalle.

def  brent ( f ,  x0 )  ->  ( int ,  int ): """Algoritmo de detección del ciclo de Brent.""" # fase principal: búsqueda de potencias sucesivas de dos potencia = lam = 1 tortuga = x0 liebre = f ( x0 ) # f(x0) es el elemento/nodo al lado de x0. mientras que tortuga ! = liebre : si poder == lam : # ¿es hora de iniciar un nuevo poder de dos? tortuga = poder de la liebre *= 2 lam = 0 liebre = f ( liebre ) lam += 1                                       # Encuentra la posición de la primera repetición de longitud λ  tortuga  =  liebre  =  x0  para  i  en  rango ( lam ):  # rango(lam) produce una lista con los valores 0, 1, ... , lam-1  liebre  =  f ( liebre )  # La distancia entre la liebre y la tortuga ahora es λ. # A continuación, la liebre y la tortuga se mueven a la misma velocidad hasta que coincidan  mu  =  0  mientras que  tortuga  !=  liebre :  tortuga  =  f ( tortuga )  liebre  =  f ( liebre )  mu  +=  1  volver  lam ,  mu

Al igual que el algoritmo de la liebre y la tortuga, este es un algoritmo de puntero que utiliza pruebas y evaluaciones de funciones $O (λ + μ) y espacio de almacenamiento$ $O (1)$ . No es difícil demostrar que el número de evaluaciones de funciones nunca puede ser mayor que el del algoritmo de Floyd. Brent afirma que, en promedio, su algoritmo de búsqueda de ciclos se ejecuta alrededor de un 36% más rápido que el de Floyd y que acelera el algoritmo rho de Pollard en alrededor de un 24%. También realiza un análisis de caso promedio para una versión aleatoria del algoritmo en la que la secuencia de índices trazada por el más lento de los dos punteros no son las potencias de dos en sí mismas, sino más bien un múltiplo aleatorio de las potencias de dos. Aunque su principal aplicación prevista eran los algoritmos de factorización de números enteros, Brent también analiza aplicaciones para probar generadores de números pseudoaleatorios. ^[8]

algoritmo de gosper

El algoritmo de RW Gosper ^[10]^[11] encuentra el período y los límites inferior y superior del punto de inicio, y , del primer ciclo. La diferencia entre el límite inferior y superior es del mismo orden que el período, es decir . $\lambda$ $\mu _{l}$ $\mu _{u}$ $\mu _{l}+\lambda \sim \mu _{h}$

Ventajas

La característica principal del algoritmo de Gosper es que nunca retrocede para reevaluar la función del generador y es económico tanto en espacio como en tiempo. Podría describirse aproximadamente como una versión concurrente del algoritmo de Brent. Mientras que el algoritmo de Brent aumenta gradualmente la brecha entre la tortuga y la liebre, el algoritmo de Gosper utiliza varias tortugas (se guardan varios valores anteriores), que están espaciadas aproximadamente exponencialmente. Según la nota del elemento 132 de HAKMEM, este algoritmo detectará la repetición antes de la tercera aparición de cualquier valor, es decir, el ciclo se repetirá como máximo dos veces. Esta nota también establece que es suficiente almacenar valores anteriores; sin embargo, la implementación proporcionada ^[10] almacena valores. Por ejemplo, supongamos que los valores de la función son enteros de 32 bits y, por lo tanto, la segunda iteración del ciclo finaliza después de como máximo 2 ³² evaluaciones de la función desde el principio (a saber ). Luego, el algoritmo de Gosper encontrará el ciclo después de como máximo 2 ³² evaluaciones de funciones, mientras consume el espacio de 33 valores (cada valor es un entero de 32 bits). $\Theta (\log \lambda )$ $\Theta (\log(\mu +\lambda ))$ $\mu +2\lambda \leq 2^{32}$

Complejidad

Tras la -ésima evaluación de la función generadora, el algoritmo compara el valor generado con los valores anteriores; observe que sube al menos y al máximo . Por tanto, la complejidad temporal de este algoritmo es . Dado que almacena valores, su complejidad espacial es . Esto se debe al supuesto habitual, presente a lo largo de este artículo, de que el tamaño de los valores de la función es constante. Sin esta suposición, la complejidad del espacio se debe a que necesitamos al menos valores distintos y, por lo tanto, el tamaño de cada valor es . $i$ $O(\log i)$ $i$ $\mu +\lambda$ $\mu +2\lambda$ $O((\mu +\lambda )\cdot \log(\mu +\lambda ))$ $\Theta (\log(\mu +\lambda ))$ $\Theta (\log(\mu +\lambda ))$ $\Omega (\log ^{2}(\mu +\lambda ))$ $\mu +\lambda$ $\Omega (\log(\mu +\lambda ))$

Compensaciones tiempo-espacio

Varios autores han estudiado técnicas para la detección de ciclos que utilizan más memoria que los métodos de Floyd y Brent, pero detectan ciclos más rápidamente. En general, estos métodos almacenan varios valores de secuencia calculados previamente y prueban si cada nuevo valor es igual a uno de los valores calculados previamente. Para hacerlo rápidamente, normalmente utilizan una tabla hash o una estructura de datos similar para almacenar los valores calculados previamente y, por lo tanto, no son algoritmos de puntero: en particular, generalmente no se pueden aplicar al algoritmo rho de Pollard. Donde estos métodos difieren es en cómo determinan qué valores almacenar. Siguiendo a Nivasch, ^[12] examinamos brevemente estas técnicas.

Brent ^[8] ya describe variaciones de su técnica en las que los índices de los valores de secuencia guardados son potencias de un número $R$ distinto de dos. Al elegir $R$ como un número cercano a uno y almacenar los valores de la secuencia en índices que están cerca de una secuencia de potencias consecutivas de $R$ , un algoritmo de detección de ciclos puede usar una cantidad de evaluaciones de funciones que están dentro de un factor arbitrariamente pequeño del óptimo. $λ + μ$ . ^[13]^[14]
Sedgewick, Szymanski y Yao ^[15] proporcionan un método que utiliza $M$ celdas de memoria y requiere, en el peor de los casos, solo evaluaciones de funciones, para alguna constante $c$ , que demuestran ser óptimas. La técnica implica mantener un parámetro numérico $d$ , almacenar en una tabla solo aquellas posiciones en la secuencia que son múltiplos de $d$ , y borrar la tabla y duplicar $d$ siempre que se hayan almacenado demasiados valores. $(\lambda +\mu )(1+cM^{-1/2})$
Varios autores han descrito métodos de puntos distinguidos que almacenan valores de funciones en una tabla basándose en un criterio que involucra los valores, en lugar de (como en el método de Sedgewick et al.) basándose en sus posiciones. Por ejemplo, se pueden almacenar valores iguales a módulo cero, algún valor $d .$ ^[16]^[17] Más simplemente, Nivasch ^[12] le da crédito a DP Woodruff por la sugerencia de almacenar una muestra aleatoria de valores vistos previamente, haciendo una elección aleatoria apropiada en cada paso para que la muestra siga siendo aleatoria.
Nivasch ^[12] describe un algoritmo que no utiliza una cantidad fija de memoria, pero para el cual la cantidad esperada de memoria utilizada (bajo el supuesto de que la función de entrada es aleatoria) es logarítmica en la longitud de la secuencia. Con esta técnica, un elemento se almacena en la tabla de memoria cuando ningún elemento posterior tiene un valor menor. Como muestra Nivasch, los elementos con esta técnica se pueden mantener utilizando una estructura de datos de pila , y cada valor de secuencia sucesivo debe compararse solo con la parte superior de la pila. El algoritmo termina cuando se encuentra el elemento de secuencia repetido con el valor más pequeño. Ejecutar el mismo algoritmo con múltiples pilas, usando permutaciones aleatorias de los valores para reordenar los valores dentro de cada pila, permite un equilibrio tiempo-espacio similar a los algoritmos anteriores. Sin embargo, incluso la versión de este algoritmo con una sola pila no es un algoritmo de puntero, debido a las comparaciones necesarias para determinar cuál de dos valores es menor.

Cualquier algoritmo de detección de ciclos que almacene como máximo valores $M$ de la secuencia de entrada debe realizar al menos evaluaciones de funciones. ^[18]^[19] $(\lambda +\mu )\left(1+{\frac {1}{M-1}}\right)$

Aplicaciones

La detección de ciclos se ha utilizado en muchas aplicaciones.

Determinar la duración del ciclo de un generador de números pseudoaleatorios es una medida de su solidez. Ésta es la aplicación citada por Knuth al describir el método de Floyd. ^[3] Brent ^[8] describe los resultados de probar un generador congruente lineal de esta manera; su período resultó ser significativamente menor de lo anunciado. Para generadores más complejos, la secuencia de valores en la que se encuentra el ciclo puede no representar la salida del generador, sino más bien su estado interno.
Varios algoritmos de teoría de números se basan en la detección de ciclos, incluido el algoritmo rho de Pollard para la factorización de enteros ^[20] y su algoritmo canguro relacionado para el problema de logaritmos discretos . ^[21]
En aplicaciones criptográficas , la capacidad de encontrar dos valores distintos x _{μ −1} y x _{λ + μ −1} asignados por alguna función criptográfica ƒ al mismo valor x _μ puede indicar una debilidad en ƒ . Por ejemplo, Quisquater y Delescaille ^[17] aplican algoritmos de detección de ciclos en la búsqueda de un mensaje y un par de claves estándar de cifrado de datos que asignan ese mensaje al mismo valor cifrado; Kaliski , Rivest y Sherman ^[22] también utilizan algoritmos de detección de ciclos para atacar DES. La técnica también se puede utilizar para encontrar una colisión en una función hash criptográfica . ^[23]
La detección de ciclos puede resultar útil como forma de descubrir bucles infinitos en ciertos tipos de programas informáticos . ^[24]
Las configuraciones periódicas en simulaciones de autómatas celulares se pueden encontrar aplicando algoritmos de detección de ciclos a la secuencia de estados de los autómatas. ^[12]
El análisis de forma de estructuras de datos de listas enlazadas es una técnica para verificar la exactitud de un algoritmo que utiliza esas estructuras. Si un nodo de la lista apunta incorrectamente a un nodo anterior de la misma lista, la estructura formará un ciclo que estos algoritmos pueden detectar. ^[25] En Common Lisp , la impresora S-expression , bajo el control de la *print-circle*variable, detecta la estructura de la lista circular y la imprime de forma compacta.
Teske ^[14] describe aplicaciones en teoría computacional de grupos : determinar la estructura de un grupo abeliano a partir de un conjunto de sus generadores. Los algoritmos criptográficos de Kaliski et al. ^[22] también puede considerarse como un intento de inferir la estructura de un grupo desconocido.
Fich (1981) menciona brevemente una aplicación a la simulación por computadora de la mecánica celeste , que atribuye a William Kahan . En esta aplicación, la detección de ciclos en el espacio de fases de un sistema orbital se puede utilizar para determinar si el sistema es periódico dentro de la precisión de la simulación. ^[18]
En la generación de fractales del conjunto de Mandelbrot se utilizan algunas técnicas de rendimiento para acelerar la generación de imágenes. Uno de ellos se llama "comprobación de períodos", que consiste en encontrar los ciclos en una órbita puntual. Este artículo describe la técnica de "verificación de período". Puedes encontrar otra explicación aquí. Es necesario implementar algunos algoritmos de detección de ciclos para implementar esta técnica.

Referencias

^ Joux, Antoine (2009), Criptoanálisis algorítmico, CRC Press, p. 223, ISBN 9781420070033.
^ ab Joux (2009, pág. 224).
^ ab Knuth, Donald E. (1969), El arte de la programación informática, vol. II: Algoritmos seminuméricos , Addison-Wesley, p. 7, ejercicios 6 y 7
^ Manual de criptografía aplicada, por Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, p. 125, describe este algoritmo y otros
^ Floyd, RW (1967), "Algoritmos no deterministas", J. ACM , 14 (4): 636–644, doi : 10.1145/321420.321422 , S2CID 1990464
^ La función hash BLAKE, por Jean-Philippe Aumasson, Willi Meier, Raphael C.-W. Phan, Luca Henzen (2015), pág. 21, nota al pie 8
^ Joux (2009), Sección 7.1.1, Algoritmo de búsqueda de ciclos de Floyd, págs.
^ abcd Brent, RP (1980), "Un algoritmo de factorización de Monte Carlo mejorado" (PDF) , BIT Numerical Mathematics , 20 (2): 176–184, doi :10.1007/BF01933190, S2CID 17181286.
^ Joux (2009), Sección 7.1.2, Algoritmo de búsqueda de ciclos de Brent, págs.
^ ab "Copia archivada". Archivado desde el original el 14 de abril de 2016 . Consultado el 8 de febrero de 2017 .{{cite web}}: CS1 maint: archived copy as title (link)
^ "Hakmem - Flujos y funciones iteradas - Borrador, aún no revisado".
^ abcd Nivasch, Gabriel (2004), "Detección de ciclos mediante una pila", Cartas de procesamiento de información , 90 (3): 135–140, doi :10.1016/j.ipl.2004.01.016.
^ Schnorr, Claus P .; Lenstra, Hendrik W. (1984), "Un algoritmo de factorización de Monte Carlo con almacenamiento lineal", Matemáticas de la Computación , 43 (167): 289–311, doi :10.2307/2007414, hdl : 1887/3815 , JSTOR 2007414.
^ ab Teske, Edlyn (1998), "Un algoritmo espacialmente eficiente para el cálculo de estructuras de grupos", Matemáticas de la Computación , 67 (224): 1637–1663, Bibcode :1998MaCom..67.1637T, doi : 10.1090/S0025-5718- 98-00968-5.
^ Sedgewick, Robert ; Szymanski, Thomas G.; Yao, Andrew C.-C. (1982), "La complejidad de encontrar ciclos en funciones periódicas", Revista SIAM de Computación , 11 (2): 376–390, doi :10.1137/0211030.
^ van Oorschot, Paul C.; Wiener, Michael J. (1999), "Búsqueda de colisiones paralelas con aplicaciones criptoanalíticas", Journal of Cryptology , 12 (1): 1–28, doi : 10.1007/PL00003816 , S2CID 5091635.
^ ab Quisquater, J.-J.; Delescaille, J.-P., "¿Qué tan fácil es la búsqueda por colisión? Aplicación a DES", Avances en criptología - EUROCRYPT '89, Taller sobre teoría y aplicación de técnicas criptográficas , Apuntes de conferencias en informática, vol. 434, Springer-Verlag, págs. 429–434, doi : 10.1007/3-540-46885-4_43.
^ ab Fich, Faith Ellen (1981), "Límites inferiores para el problema de detección del ciclo", Proc. 13º Simposio ACM sobre Teoría de la Computación , págs. 96–105, doi :10.1145/800076.802462, S2CID 119742106.
^ Allender, Eric W .; Klawe, Maria M. (1985), "Límites inferiores mejorados para el problema de detección de ciclos", Ciencias de la Computación Teórica , 36 (2–3): 231–237, doi : 10.1016/0304-3975(85)90044-1.
^ Pollard, JM (1975), "Un método de Monte Carlo para la factorización", BIT , 15 (3): 331–334, doi :10.1007/BF01933667, S2CID 122775546.
^ Pollard, JM (1978), "Métodos de Monte Carlo para el cálculo de índices $(mod$ $p$ )", Matemáticas de la Computación , Sociedad Matemática Estadounidense, 32 (143): 918–924, doi :10.2307/2006496, JSTOR 2006496, S2CID 235457090.
^ ab Kaliski, Burton S. Jr.; Rivest, Ronald L .; Sherman, Alan T. (1988), "¿Es el estándar de cifrado de datos un grupo? (Resultados de experimentos cíclicos en DES)", Journal of Cryptology , 1 (1): 3–36, doi : 10.1007/BF00206323 , S2CID 17224075.
^ Joux (2009), Sección 7.5, Colisiones en funciones hash, págs.
^ Van Gelder, Allen (1987), "Detección eficiente de bucles en Prolog utilizando la técnica de la tortuga y la liebre", Journal of Logic Programming , 4 (1): 23–31, doi : 10.1016/0743-1066(87)90020 -3.
^ Auguston, Miguel; Hon, Miu Har (1997), "Assertions for Dynamic Shape Analysis of List Data Structures", AADEBUG '97, Actas del tercer taller internacional sobre depuración automática, artículos electrónicos de Linköping sobre informática y ciencias de la información, Universidad de Linköping , págs. 42.

enlaces externos

Gabriel Nivasch, El problema de detección de ciclos y el algoritmo de pila
Tortuga y liebre, repositorio de patrones de Portland
Algoritmo de detección del ciclo de Floyd (La tortuga y la liebre)
Algoritmo de detección del ciclo de Brent (la tortuga teletransportadora)