Cycle Detection - Applications

Applications

Cycle detection has been used in many applications.

• Determining the cycle length of a pseudorandom number generator is one measure of its strength. This is the application cited by Knuth in describing Floyd's method. Brent describes the results of testing a linear congruential generator in this fashion; its period turned out to be significantly smaller than advertised. For more complex generators, the sequence of values in which the cycle is to be found may not represent the output of the generator, but rather its internal state.
• Several number-theoretic algorithms are based on cycle detection, including Pollard's rho algorithm for integer factorization and his related kangaroo algorithm for the discrete logarithm problem.
• In cryptographic applications, the ability to find two distinct values x_μ−-1 and x_λ+μ−-1 mapped by some cryptographic function ƒ to the same value x_μ may indicate a weakness in ƒ. For instance, Quisquater and Delescaille apply cycle detection algorithms in the search for a message and a pair of Data Encryption Standard keys that map that message to the same encrypted value; Kaliski, Rivest, and Sherman also use cycle detection algorithms to attack DES. The technique may also be used to find a collision in a cryptographic hash function.
• Cycle detection may be helpful as a way of discovering infinite loops in certain types of computer programs.
• Periodic configurations in cellular automaton simulations may be found by applying cycle detection algorithms to the sequence of automaton states.
• Shape analysis of linked list data structures is a technique for verifying the correctness of an algorithm using those structures. If a node in the list incorrectly points to an earlier node in the same list, the structure will form a cycle that can be detected by these algorithms.
• Teske describes applications in computational group theory: determining the structure of an Abelian group from a set of its generators. The cryptographic algorithms of Kaliski et al. may also be viewed as attempting to infer the structure of an unknown group.
• Fich briefly mentions an application to computer simulation of celestial mechanics, which she attributes to William Kahan. In this application, cycle detection in the phase space of an orbital system may be used to determine whether the system is periodic to within the accuracy of the simulation.