Editing Cycle detection (section)

==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.<ref name="knuth"/> Brent<ref name="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 theory|number-theoretic]] algorithms are based on cycle detection, including [[Pollard's rho algorithm]] for integer factorization<ref>{{citation|first=J. M.|last=Pollard|title=A Monte Carlo method for factorization|journal=BIT|volume=15|year=1975|pages=331–334|doi=10.1007/BF01933667|issue=3|s2cid=122775546}}.</ref> and his related [[Pollard's kangaroo algorithm|kangaroo algorithm]] for the [[discrete logarithm]] problem.<ref>{{citation|first=J. M.|last=Pollard|title=Monte Carlo methods for index computation {{math|(mod ''p''}})|journal=[[Mathematics of Computation]]|volume=32|issue=143|year=1978|pages=918–924|doi=10.2307/2006496|publisher=American Mathematical Society|jstor=2006496|s2cid=235457090 }}.</ref>
*In [[Cryptography|cryptographic]] applications, the ability to find two distinct values ''x''<sub>''μ''&minus;1</sub> and ''x''<sub>''λ''+''μ''&minus;1</sub> mapped by some cryptographic function ''ƒ'' to the same value ''x''<sub>''μ''</sub> may indicate a weakness in ''ƒ''. For instance, Quisquater and Delescaille<ref name="qd"/> 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; [[Burt Kaliski|Kaliski]], [[Ron Rivest|Rivest]], and [[Alan Sherman|Sherman]]<ref name="krs">{{citation|first1=Burton S. Jr.|last1=Kaliski|first2=Ronald L.|last2=Rivest|author-link2=Ron Rivest|first3=Alan T.|last3=Sherman|title=Is the Data Encryption Standard a group? (Results of cycling experiments on DES)|journal=[[Journal of Cryptology]]|volume=1|issue=1|year=1988|pages=3–36|doi=10.1007/BF00206323|s2cid=17224075|doi-access=free}}.</ref> also use cycle detection algorithms to attack DES. The technique may also be used to find a [[hash collision|collision]] in a [[cryptographic hash function]].<ref>{{harvtxt|Joux|2009}}, Section 7.5, Collisions in hash functions, pp. 242–245.</ref>
*Cycle detection may be helpful as a way of discovering [[infinite loop]]s in certain types of [[computer program]]s.<ref>{{citation|first=Allen|last=Van Gelder|title=Efficient loop detection in Prolog using the tortoise-and-hare technique|journal=Journal of Logic Programming|volume=4|issue=1|pages=23–31|year=1987|doi=10.1016/0743-1066(87)90020-3|doi-access=free}}.</ref>
*[[Oscillator (cellular automaton)|Periodic configurations]] in [[cellular automaton]] simulations may be found by applying cycle detection algorithms to the sequence of automaton states.<ref name="nivasch"/>
*[[Shape analysis (software)|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.<ref>{{citation|first1=Mikhail|last1=Auguston|first2=Miu Har|last2=Hon|contribution=Assertions for Dynamic Shape Analysis of List Data Structures|pages=37–42|title=AADEBUG '97, Proceedings of the Third International Workshop on Automatic Debugging|series=Linköping Electronic Articles in Computer and Information Science|publisher=[[Linköping University]]|url=http://www.ep.liu.se/ea/cis/1997/009/04/|year=1997}}.</ref> In [[Common Lisp]], the [[S-expression]] printer, under control of the <code>*print-circle*</code> variable, detects circular list structure and prints it compactly.
*Teske<ref name="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.<ref name="krs"/> may also be viewed as attempting to infer the structure of an unknown group.
*{{harvtxt|Fich|1981}} 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.<ref name="fich"/>
*In [[Mandelbrot Set]] fractal generation some performance techniques are used to speed up the image generation. One of them is called "period checking", which consists of finding the cycles in a point orbit. This article describes the "[[wikibooks:Fractals/Iterations_in_the_complex_plane/Mandelbrot_set/mandelbrot#Periodicity_checking|period checking]]" technique. You can find another explanation [http://math.bu.edu/DYSYS/FRACGEOM/node1.html#SECTION00010000000000000000 here]. Some cycle detection algorithms have to be implemented in order to implement this technique.