Editing Cycle detection (section)

==Computer representation==
Except in toy examples like the above, {{mvar|f}} will not be specified as a table of values.  Such a table implies {{math|''O''({{abs|''S''}})}} [[space complexity]], and if that is permissible, an [[associative array]] mapping {{mvar|x<sub>i</sub>}} to {{mvar|i}} will detect the first repeated value.  Rather, a cycle detection algorithm is given a [[black box]] for generating the sequence {{mvar|x<sub>i</sub>}}, and the task is to find {{mvar|λ}} and {{mvar|μ}} using very little memory.

The black box might consist of an implementation of the recurrence function {{mvar|f}}, but it might also store additional internal state to make the computation more efficient.  Although {{math|''x<sub>i</sub>'' {{=}} ''f''(''x''<sub>''i''&minus;1</sub>)}} must be true ''in principle'', this might be expensive to compute directly; the function could be defined in terms of the [[discrete logarithm]] of {{math|''x''<sub>''i''&minus;1</sub>}} or some other [[one-way permutation|difficult-to-compute property]] which can only be practically computed in terms of additional information.  In such cases, the number of black boxes required becomes a figure of merit distinguishing the algorithms.

A second reason to use one of these algorithms is that they are [[pointer algorithm]]s which do no operations on elements of {{mvar|S}} other than testing for equality.  An associative array implementation requires computing a [[hash function]] on the elements of {{mvar|S}}, or [[Comparison sort|ordering them]].  But cycle detection can be applied in cases where neither of these are possible.

The classic example is [[Pollard's rho algorithm]] for [[integer factorization]], which searches for a factor {{mvar|p}} of a given number {{mvar|n}} by looking for values {{mvar|x<sub>i</sub>}} and {{math|''x''<sub>''i''+''λ''</sub>}} which are equal modulo {{mvar|p}} ''without knowing {{mvar|p}} in advance.''<!--In fact, it searches modulo all possible factors simultaneously, a detail not stated explicitly to simplify the example.-->  This is done by computing the [[greatest common divisor]] of the difference {{math|''x<sub>i</sub>'' − ''x''<sub>''i''+''λ''</sub>}} with a known multiple of {{mvar|p}}, namely {{mvar|n}}.  If the gcd is non-trivial (neither 1 nor {{mvar|n}}), then the value is a proper factor of {{mvar|n}}, as desired.<ref name="j224"/>  If {{mvar|n}} is not prime, it must have at least one factor {{math|''p'' ≤ {{sqrt|''n''}}}}, and by the [[birthday paradox]], a random function {{mvar|f}} has an expected cycle length (modulo&nbsp;{{mvar|p}}) of {{math|{{sqrt|''p''}} ≤ {{sqrt|''n''|4}}}}.<!--Not sure how useful this last sentence is.  It's not relevant to cycle detection directly, but motivates the example by answering "why would you want to do this crazy thing?"-->