| Floyd's Cycle-finding Algorithm |
Website Links For Floyds |
Information AboutFloyd's Cycle-finding Algorithm |
|
It is sometimes called the "tortoise and the hare"-algorithm. The following discussion is couched in terms of pseudo-random sequences in particular, of great importance in analyzing pseudo-random number generators and in applications to factoring algorithms such as Pollard's Rho Algorithm . Let : be a pseudo-random Function , with ''S'' a finite set of cardinality ''n''. Define a sequence ''a''''i'' as: : Clearly such a sequence must cycle after at most ''n'' iterations of the pseudo-random function, because there are only ''n'' possible values for an element. The naïve way to find the length of the cycle is to store each element of the sequence and, at each iteration, look among all the stored elements for duplicates. This means that the storage requirement is O(μ + λ), where μ is the length of the cycle and λ is the length of the tail (i.e. the part of the sequence that does not cycle). Note that if we find two elements of the sequence such that : |
|
|