Cycle Detection - Computer Representation

Computer Representation

Generally, ƒ will not be specified as a table of values, as we have given it in the figure above. Rather, we may be given access either to the sequence of values x_i, or to a subroutine for calculating ƒ. The task is to find λ and μ while examining as few values from the sequence or performing as few subroutine calls as possible. Typically, also, the space complexity of an algorithm for the cycle detection problem is of importance: we wish to solve the problem while using an amount of memory significantly smaller than it would take to store the entire sequence.

In some applications, and in particular in Pollard's rho algorithm for integer factorization, the algorithm has much more limited access to S and to ƒ. In Pollard's rho algorithm, for instance, S is the set of integers modulo an unknown prime factor of the number to be factorized, so even the size of S is unknown to the algorithm. We may view a cycle detection algorithm for this application as having the following capabilities: it initially has in its memory an object representing a pointer to the starting value x₀. At any step, it may perform one of three actions: it may copy any pointer it has to another object in memory, it may apply ƒ and replace any of its pointers by a pointer to the next object in the sequence, or it may apply a subroutine for determining whether two of its pointers represent equal values in the sequence. The equality test action may involve some nontrivial computation: in Pollard's rho algorithm, it is implemented by testing whether the difference between two stored values has a nontrivial gcd with the number to be factored. In this context, we will call an algorithm that only uses pointer copying, advancement within the sequence, and equality tests a pointer algorithm.