Editing Cycle detection (section)

==Definitions==

Let {{mvar|S}} be any finite set, {{mvar|f}} be any [[Endofunction#Endofunctions|endofunction]] from {{mvar|S}} to itself, and {{math|''x''<sub>0</sub>}} be any element of {{mvar|S}}. For any {{math|''i'' > 0}}, let {{math|1=''x<sub>i</sub>'' = ''f''(''x''<sub>''i'' &minus; 1</sub>)}}. Let {{mvar|μ}} be the smallest index such that the value {{mvar|x<sub>μ</sub>}} reappears infinitely often within the sequence of values {{mvar|x<sub>i</sub>}}, and let {{mvar|λ}} (the loop length) be the smallest positive integer such that {{math|1=''x<sub>μ</sub>'' = ''x''<sub>''λ'' + ''μ''</sub>}}. The cycle detection problem is the task of finding {{mvar|λ}} and {{mvar|μ}}.<ref name=Joux>{{citation|title=Algorithmic Cryptanalysis|chapter=7. Birthday-based algorithms for functions|first=Antoine|last=Joux|author-link=Antoine Joux|publisher=CRC Press|year=2009|isbn=978-1-420-07003-3|page=223|url=https://books.google.com/books?id=buQajqt-_iUC&pg=PA223}}.</ref>

One can view the same problem [[graph theory|graph-theoretically]], by constructing a [[functional graph]] (that is, a [[directed graph]] in which each vertex has a single outgoing edge) the vertices of which are the elements of {{mvar|S}} and the edges of which map an element to the corresponding function value, as shown in the figure. The set of vertices [[Reachability|reachable]] from  starting vertex {{math|''x''<sub>0</sub>}} form a subgraph with a shape resembling the [[Rho (letter)|Greek letter rho]] ({{mvar|ρ}}): a path of length {{mvar|μ}} from {{math|''x''<sub>0</sub>}} to a [[Cycle (graph theory)|cycle]] of {{mvar|λ}} vertices.<ref name="j224">{{harvtxt|Joux|2009|page=224}}.</ref>

Practical cycle-detection algorithms do not find {{mvar|λ}} and {{mvar|μ}} exactly.{{r|Joux}}  They usually find lower and upper bounds {{math|''μ<sub>l</sub>'' &leq; ''μ'' &leq; ''μ<sub>h</sub>''}} for the start of the cycle, and a more detailed search of the range must be performed if the exact value of {{mvar|μ}} is needed.  Also, most algorithms do not guarantee to find {{mvar|λ}} directly, but may find some multiple {{math|''kλ'' < ''μ'' + ''λ''}}.  (Continuing the search for an additional {{math|''kλ''/''q''}} steps, where {{mvar|q}} is the smallest prime divisor of {{mvar|kλ}}, will either find the true {{mvar|λ}} or prove that {{math|''k'' {{=}} 1}}.)