Detección de ciclos

En informática , la detección de ciclos o hallazgo 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 mapea un conjunto finito $S$ a sí mismo, 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}),\ \puntos ,\ x_{i}=f(x_{i-1}),\ \puntos

debe eventualmente 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 que permiten encontrar ciclos rápidamente y con poca memoria. El algoritmo de la tortuga y la liebre de Robert W. Floyd mueve dos punteros a distintas velocidades a través de la secuencia de valores hasta que ambos apuntan a valores iguales. Por otra parte, el algoritmo de Brent se basa en la idea de búsqueda exponencial . Tanto el algoritmo de Floyd como el de Brent utilizan solo un número constante de celdas de memoria y realizan una cantidad de evaluaciones de funciones que es proporcional a la distancia desde el inicio de la secuencia hasta la primera repetición. Varios otros algoritmos sacrifican mayores cantidades de memoria por menos evaluaciones de funciones.

Las aplicaciones de la detección de ciclos incluyen la prueba de la calidad de generadores de números pseudoaleatorios y funciones hash criptográficas , algoritmos de teoría de números computacionales , 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 bloqueos 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 repetidamente $f$ , 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$ un conjunto finito cualquiera, $f$ una función cualquiera de $S$ a sí mismo y $x 0$ un elemento cualquiera 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 μ$ reaparezca 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 es la tarea de encontrar $λ$ y $μ$ . ^[1]

Se puede ver el mismo problema de forma gráfica , construyendo un gráfico funcional (es decir, un gráfico dirigido en el que cada vértice tiene una única arista saliente) cuyos vértices son los elementos de $S$ y cuyas aristas asignan un elemento al valor de 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 parecida a la letra griega rho ( $ρ$ ): un camino de longitud $μ$ desde $x 0$ a un ciclo de $λ$ vértices. ^[2]

Representación por computadora

Generalmente, $f$ no se especificará como una tabla de valores, como se muestra en la figura anterior. En cambio, se puede dar acceso a un algoritmo de detección de ciclos a la secuencia de valores $x i$ o a una subrutina para calcular $f$ . La tarea es encontrar $λ$ y $μ$ mientras se examinan la menor cantidad posible de valores de la secuencia o se realizan la menor cantidad posible de llamadas a subrutinas. Por lo general, también es importante la complejidad espacial de un algoritmo para el problema de detección de ciclos: deseamos resolver el problema mientras utilizamos una cantidad de memoria significativamente menor que 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 números 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 que se va a factorizar, por lo que incluso el tamaño de $S$ es desconocido para el algoritmo. Para permitir que los algoritmos de detección de ciclos se utilicen con un conocimiento tan limitado, se pueden diseñar basándose en 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 involucrar 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 máquina de puntero , un algoritmo que solo utiliza copia de puntero, avance dentro de la secuencia y pruebas de igualdad puede llamarse algoritmo de puntero.

Algoritmos

Si la entrada se proporciona como una subrutina para calcular $f$ , el problema de detección de ciclos se puede resolver de manera trivial utilizando solo aplicaciones de la función $λ + μ$ , simplemente calculando la secuencia de valores $x i$ y utilizando una estructura de datos como una tabla hash para almacenar estos valores y probar si cada valor posterior ya se ha almacenado. Sin embargo, la complejidad espacial de este algoritmo es proporcional a $λ + μ$ , innecesariamente grande. Además, para implementar este método como un algoritmo de puntero se 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: usar menos espacio que este algoritmo ingenuo 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 punteros que utiliza solo dos punteros, que se mueven a través de la secuencia a diferentes velocidades. También se lo denomina "algoritmo de la liebre y la tortuga", en alusión a la fábula de Esopo La liebre y la tortuga .

El algoritmo recibe su nombre de Robert W. Floyd , a quien Donald Knuth 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 grafo dirigido en un artículo de 1967, ^[5] pero este artículo no describe el problema de búsqueda de ciclos en grafos funcionales que es el tema de este artículo. De hecho, la declaración de Knuth (en 1969), atribuyéndolo a Floyd, sin citarlo, es la primera aparición conocida impresa 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 entero $i \geq μ$ y $k \geq 0$ , $x i = x i + kλ$ , donde $λ$ es la longitud del bucle que se va a encontrar, $μ$ es el índice del primer elemento del ciclo y $k$ es un 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 solo 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 algunos $i$ y $k$ tales que $i = kλ$ , entonces $2i = i + kλ$ y $x 2 i = x i + kλ$ ). Por lo tanto, el algoritmo sólo necesita comprobar 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 un múltiplo de $λ$ . Una vez que se encuentra $ν , el algoritmo vuelve a trazar 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 que se conoce el valor de $μ,$ es trivial encontrar la longitud $λ$ del ciclo repetitivo más corto, buscando la primera posición $μ + λ$ para la que $x μ + λ = x μ$ .

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 esta idea puede implementarse como algoritmo.

def  floyd ( f ,  x0 )  ->  ( int ,  int ): """Algoritmo de detección de ciclos de Floyd.""" # Fase principal del algoritmo: encontrar una repetición x_i = x_2i. # La liebre se mueve el doble de rápido que la tortuga y # la distancia entre ellas aumenta en 1 en cada paso. # Eventualmente ambas estarán dentro del ciclo y entonces, # en algún punto, la distancia entre ellas será # divisible por el periodo λ. tortoise = f ( x0 ) # f(x0) es el elemento/nodo próximo a x0. hare = f ( f ( x0 )) while tortoise != hare : tortoise = f ( tortoise ) hare = f ( f ( hare ))                          # 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 λ. Por lo tanto, la liebre, que se mueve en el ciclo un paso a la vez,  # y la tortuga (reiniciada en x0) que se mueve hacia el ciclo,  # se intersectarán al comienzo del ciclo. Debido a que la  # distancia entre ellas 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 longitud del ciclo más corto comenzando desde x_μ  # La liebre se mueve un paso a la vez mientras la tortuga está quieta.  # lam se incrementa hasta que se encuentra λ.  lam  =  1  liebre  =  f ( liebre )  mientras  tortuga  !=  liebre :  liebre  =  f ( liebre )  lam  +=  1  volver  lam ,  mu

Este código sólo accede a la secuencia mediante el almacenamiento y copia de punteros, evaluaciones de funciones y pruebas de igualdad; por lo tanto, se califica como un algoritmo de puntero. El algoritmo utiliza $O (λ + μ)$ operaciones de estos tipos y $O (1)$ espacio de almacenamiento. ^[7]

Algoritmo de Brent

Richard P. Brent describió un algoritmo alternativo de detección de ciclos que, al igual que el algoritmo de la tortuga y la liebre, requiere solo dos punteros en la secuencia. ^[8] Sin embargo, se basa en un principio diferente: buscar la potencia de dos más pequeña $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 tortuga y la liebre: encuentra la longitud correcta $λ$ del ciclo directamente, en lugar de tener que buscarla en una etapa posterior, y sus pasos implican solo 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 de ciclos de Brent.""" # fase principal: buscar potencias sucesivas de dos power = lam = 1 tortoise = x0 hare = f ( x0 ) # f(x0) es el elemento/nodo próximo a x0. # esto supone que hay un ciclo; de lo contrario, este bucle no terminará while tortoise != hare : if power == lam : # ¿es hora de comenzar una nueva potencia de dos? tortoise = hare power *= 2 lam = 0 hare = f ( hare ) lam += 1                                        # Encuentra la posición de la primera repetición de longitud λ  tortoise  =  hare  =  x0  for  i  in  range ( lam ):  # range(lam) produce una lista con los valores 0, 1, ... , lam-1  hare  =  f ( hare )  # 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 coinciden en  mu  =  0  mientras que  tortuga  !=  liebre :  tortuga  =  f ( tortuga )  liebre  =  f ( liebre )  mu  +=  1  volver  lam ,  mu

Al igual que el algoritmo de la tortuga y la liebre, este es un algoritmo de puntero que utiliza $O (λ + μ)$ pruebas y evaluaciones de funciones y $O (1)$ espacio de almacenamiento. No es difícil demostrar que el número de evaluaciones de funciones nunca puede ser mayor que para el 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 el 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 era en algoritmos de factorización de números enteros, Brent también analiza aplicaciones en la prueba de generadores de números pseudoaleatorios. ^[8]

Algoritmo de Gosper

El algoritmo de RW Gosper ^[10]^[11] encuentra el período , y el límite inferior y superior del punto de partida, y , del primer ciclo. La diferencia entre el límite inferior y superior es del mismo orden que el período, es decir . ${\estilo de visualización \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 generadora 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 de manera exponencial. Según la nota en el ítem 132 de HAKMEM, ^[11] este algoritmo detectará la repetición antes de la tercera aparición de cualquier valor, es decir, el ciclo se iterará como máximo dos veces. Esta nota también indica 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 números enteros de 32 bits y la segunda iteración del ciclo termina después de como máximo 2 ³² evaluaciones de la función desde el comienzo (es decir, ). Luego, el algoritmo de Gosper encontrará el ciclo después de un máximo de 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 valores anteriores; observe que llega hasta al menos y como máximo a . Por lo tanto, la complejidad temporal de este algoritmo es . Dado que almacena valores, su complejidad espacial es . Esto se produce bajo el supuesto habitual, presente en todo este artículo, de que el tamaño de los valores de la función es constante. Sin este supuesto, la complejidad espacial es ya que necesitamos al menos valores distintos y, por lo tanto, el tamaño de cada valor es . ${\estilo de visualización i}$ $O(\log i)$ ${\estilo de visualización 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 entre tiempo y 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 comprueban si cada nuevo valor es igual a uno de los valores calculados previamente. Para hacerlo rápidamente, suelen utilizar 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, normalmente no se pueden aplicar al algoritmo rho de Pollard. En lo que 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 que $R$ sea un número cercano a uno y almacenar los valores de secuencia en índices que estén cerca de una secuencia de potencias consecutivas de $R$ , un algoritmo de detección de ciclos puede utilizar una cantidad de evaluaciones de funciones que se encuentre dentro de un factor arbitrariamente pequeño del valor ó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 que es óptima. 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 limpiar la tabla y duplicar $d$ cuando se hayan almacenado demasiados valores. $(\lambda +\mu )(1+cM^{-1/2})$
Varios autores han descrito métodos puntuales 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 podrían almacenar valores iguales a cero módulo algún valor $d .$ ^[16]^[17] De manera más simple, Nivasch ^[12] atribuye a DP Woodruff la sugerencia de almacenar una muestra aleatoria de valores vistos previamente, haciendo una elección aleatoria apropiada en cada paso para que la muestra permanezca 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. Un elemento se almacena en la tabla de memoria, con esta técnica, 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 solo necesita compararse 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, utilizando 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 los dos valores es menor.

Cualquier algoritmo de detección de ciclos que almacene como máximo $M$ valores 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 longitud del ciclo de un generador de números pseudoaleatorios es una medida de su solidez. Esta es la aplicación citada por Knuth al describir el método de Floyd. ^[3] Brent ^[8] describe los resultados de probar un generador congruencial lineal de esta manera; su período resultó ser significativamente menor que el 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 números enteros ^{[20] y su}algoritmo canguro relacionado para el problema del logaritmo discreto . ^[21]
En aplicaciones criptográficas , la capacidad de encontrar dos valores distintos x _{μ −1} y x _{λ + μ −1} mapeados 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 del Estándar de cifrado de datos que mapean ese mensaje al mismo valor cifrado; Kaliski , Rivest y Sherman ^[22] también usan algoritmos de detección de ciclos para atacar DES. La técnica también puede usarse para encontrar una colisión en una función hash criptográfica . ^[23]
La detección de ciclos puede ser útil como forma de descubrir bucles infinitos en ciertos tipos de programas informáticos . ^[24]
Se pueden encontrar configuraciones periódicas en simulaciones de autómatas celulares aplicando algoritmos de detección de ciclos a la secuencia de estados del autómata. ^[12]
El análisis de forma de las estructuras de datos de listas enlazadas es una técnica para verificar la corrección de un algoritmo que utiliza esas estructuras. Si un nodo de la lista apunta incorrectamente a un nodo anterior en la misma lista, la estructura formará un ciclo que puede ser detectado por estos algoritmos. ^[25] En Common Lisp , la impresora de expresiones S*print-circle* , bajo el control de la variable, detecta la estructura de lista circular y la imprime de forma compacta.
Teske ^[14] describe aplicaciones en la teoría de grupos computacionales : 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 pueden 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 puede utilizarse 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. Una de ellas se denomina "verificación de período", que consiste en encontrar los ciclos en una órbita puntual. Este artículo describe la técnica de "verificación de período". Puede encontrar otra explicación aquí. Para implementar esta técnica, es necesario implementar algunos algoritmos de detección de ciclos.

Referencias

^ Joux, Antoine (2009), Criptoanálisis algorítmico, CRC Press, p. 223, ISBN 9781420070033.
^ por 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ág. 7, ejercicios 6 y 7
^ Handbook of Applied Cryptography, de Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, pág. 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. 225-226.
^ 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. 226-227.
^ 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)
^ ab "Hakmem - Flujos y funciones iteradas - Borrador, aún no revisado". Archivado desde el original el 18 de marzo de 2020. Consultado el 2 de mayo de 2024 .
^ abcd Nivasch, Gabriel (2004), "Detección de ciclos mediante una pila", Information Processing Letters , 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", Mathematics of Computation , 43 (167): 289–311, doi :10.2307/2007414, hdl : 1887/3815 , JSTOR 2007414.
^ ab Teske, Edlyn (1998), "Un algoritmo de uso eficiente del espacio para el cálculo de la estructura de grupo", Mathematics of Computation , 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", SIAM Journal on Computing , 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 de colisiones? Aplicación a DES", Advances in Cryptology – EUROCRYPT '89, Taller sobre la teoría y aplicación de técnicas criptográficas , Lecture Notes in Computer Science, 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 de ciclos", 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", Theoretical Computer Science , 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$ )", Mathematics of Computation , 32 (143), American Mathematical Society: 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. 242–245.
^ 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, Mikhail; Hon, Miu Har (1997), "Afirmaciones para el análisis de formas dinámicas de estructuras de datos de listas", AADEBUG '97, Actas del Tercer Taller Internacional sobre Depuración Automática, Linköping Electronic Articles in Computer and Information Science, Linköping University , págs. 37–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 de ciclos de Floyd (La liebre y la tortuga)
Algoritmo de detección de ciclos de Brent (La tortuga teletransportadora)