The idea behind this method is that iterated self-maps of finite sets
must cycle. Let *S* be a finite set, *f* : *S**S* be *any* map and
*x*_{0} *S* be some starting point. We define
*x*_{k + 1} = *f* (*x*_{k}) for
*k* 0. By the finiteness of *S* there is some pair (*p*, *q*) so that
*x*_{p + q} = *x*_{p}; but then by applying *f* repeatedly to both sides it is
clear that
*x*_{r + q} = *x*_{r} for all *r* *p*. The smallest *p* so that
*x*_{p} is repeated is called the pre-period *M*; the smallest *q* is
called the period *T* (these depend to some extent on *x*_{0} as well as
*f* and *S*). The points *x*_{0}, ..., *x*_{M} are the ``tail'' and the
points *x*_{M + r}, *r* 0 are the ``head'' the Pollard's (the
name is given for the shape of the letter). Clearly, determining *M*
and *T* (given *S*, *f* and *x*_{0}) is an interesting computational
problem. Before that let us see what this has to do with factoring.

Now suppose
*S* = *S*_{1}×*S*_{2} and
*f* = (*f*_{1}, *f*_{2}), then *f*_{1}
(respectively) *f*_{2}) will have its own (*M*_{1}, *T*_{1}) (respectively
(*M*_{2}, *T*_{2})) as pre-period and period. Each will (in general) be less
than that for *S*; certainly those for *S* are upper bounds.

In particular, let us look at the case where
*S* = /*N*, when *N*
is composite; we know that there are
*S*_{1} = /*a* and
*S*_{2} = /*b*, where *N* = *ab* with *a* and *b* co-prime. Thus we
should look for *T*_{1} (or *T*_{2}). We know we will have found *a*
period when
gcd(*x*_{p + q} - *x*_{p}, *N*) > 1. If this GCD is less than *N* then
we have found a factor (and *T*_{1} is a multiple of *q*) otherwise we
have only found a multiple of *T*; hopefully we will not be so
unlucky!

Another aspect to examine is what kind of maps *f* are ``good'' from
the point of view of finding *M* and *T*. Clearly, we can divide *S*
into the set of repeating points
*S*_{cyclic} and the set of
transients
*S*_{transient} (which are never repeated). If the
latter set is very large, then *M* is likely to be very large. On the
other hand if the former set is very large it is also likely that *T*
is large. Heuristic analysis asserts that for a ``randomly chosen
map'' *f* (i. e. a ``random'' element of
Hom(*S*, *S*))
*M* and *T* are bounded by the condition
*M* + *T* for
#(*S*) large.

Randomly chosen maps may not be good for us since we need the map to
have the form (*f*_{1}, *f*_{2}). In the case when
*S* = /*N* this
condition
*f* = (*f*_{1}, *f*_{2}) can be easily ensured by taking *f* to be a
polynomial map (Chinese Remainder Theorem once again!). However, * every* map on *S* is a polynomial map when *N* is prime so we can
expect that polynomial maps are adequate for our purposes.

Now let us see how we can determine *M* and *T* (actually we are
looking for *T*_{1} but that aspect has been explained earlier so we
will ignore it here). Clearly, storing all the iterates *x*_{k} and
comparing them until we find a match is impractical when *M* and *T*
are large.

The original method suggested by Pollard and Floyd was as follows. Let
us compute also the sequence *y*_{0} = *x*_{0} and
*y*_{k + 1} = *f* (*f* (*y*_{k})). It is
clear, by induction that
*y*_{k} = *x*_{2k}. Thus, if *k* is a multiple of
*T*, we will get *y*_{k} = *x*_{k}. By checking for this identity at each
iterative step we can find a multiple of *T*. Of course, because of
the transient *M* it is unlikely that we will find *T*, but if *M* and
*T* are of comparable size then we will find a small multiple of *T*
this way. Another problem with this approach is that we need to
compute the function *f* three times at each iterate and that can
sometimes be considered expensive.

Another approach was suggested by Brent. Let us first try to look for
the ``size'' of *M* and *T*. Thus, if *M* and *T* have *n* bits, then
we should find a repetition for *k* = 2^{n} - 1 and
*k* + *T* = 2^{n} + *T* - 1, the
latter being less than 2^{n + 1} - 1. Thus, we store
*y*_{n} = *x*_{2n - 1} and
compare it with *x*_{k} when *k* lies between 2^{n} and 2^{n + 1} - 2. It
is clear how we can iterate over this procedure. This procedure
has only one computation of *f* for each iteration. On the other hand,
we are over-estimating *M* by a (worst-case) factor of about 2, which
means we are making twice as many tests as in the Pollard-Floyd
method. Clearly, the choice between the two methods depends on which
is more time consuming--function computation or comparison.

A further improvement to the Brent method is possible if we note that
when we are checking for repetitions between *k* = 2^{n} - 1 and some *k*
between 2^{n} and 2^{n + 1} - 2, we have *already* checked for
periods of size *n* - 1 bits (ignoring *M* for the moment). Thus we can
start making comparisons only after we cross the half-way mark
2^{n} + 2^{n - 1} - 1. Because of *M* (transients again!) we may actually
*not* have checked the periods and so we will only obtain
multiples of *T* if we do this; but we will have saved exactly half
the comparisons in return!

This observation also fits in well with Pollard's idea of reducing the
number of comparisons in his factorisation method as follows. Instead
of computing
gcd(*x*_{k} - *y*_{n}, *N*) at each iteration, he takes the product
of *x*_{k} - *y*_{n} over (say) 10 iterations of *k* and computing GCD only in
time in 10. This reduces the number of comparisons as well.

To make an algorithm we must choose algebraic self-maps *f* on
/*N*. It is clear, that linear maps will have periods equal to
the size of the prime factors so we may as well have used trial
division. We take the next thing that comes to hand which is a map
like
*f* (*x*) = *x*^{2} + 1 and hope it is a ``random enough'' choice! Powering
maps like
*x* *x*^{2}, are better studied via the (*p* - 1) method
which we will see later--in particular, the periodicity of these maps
has to do with a factorisation of (*p* - 1) when *p* is a factor of *N*.
Thus, we will stick with quadratic maps and hope that this is good
enough^{2}; this is similar to the choice of ``small''
numbers as a base in the Miller-Rabin test with one crucial
difference--the outcome of the Pollard will be a ``real''
factorisation, not a probabilistic one. Finally, if we are unsuccessful
(in finding a factorisation) with a given *f* and *x*_{0} we need to
vary *both* and not just *x*_{0}.

After all that verbiage (which is used to disguise the fact that we
are not really sure of the justifications!), let us come to the
algorithm. Pick a small constant *c* other than 0 and 2 and
consider the function
*f* (*x*) = *x*^{2} - *c*. Pick a point *x*_{0} in
/*N*
(usually one of small size). Pick a small number *s* of steps (usually
*s* = 20). Let *y*_{0} = 0, *e* = 0 and *P* = 1 (*e* will count the number of
bits in *M* and *T*). While *k* is between 2^{e} and
2^{e} + 2^{e - 1} - 1,
we set
*x*_{k + 1} = *f* (*x*_{k}). While *k* is between
2^{e} + 2^{e - 1} and
2^{e + 1} - 2, we set
*x*_{k + 1} = *f* (*x*_{k}) *and* multiply *P* by
(*x*_{k} - *y*_{e}). Every *s* steps we compute gcd(*P*, *N*). If this is
greater than 1, then we have found a period (somewhere in the last *s*
steps); otherwise we set *P* to be 1 again and continue. If we found a
GCD, we set *z*_{0} = *y*_{e} and iteratively compute (at most *s* times)
*z*_{l + 1} = *f* (*z*_{l}) and
gcd(*x*_{k} - *z*_{l}, *N*). We will find a non-trivial GCD
for some *l* between 0 and *s* - 1. If this GCD is less than *N* then we
have found a factor; else we have been unsuccessful, so we change *c*
and *x*_{0}. If we found a factor *a* then we can continue, replacing
*N* with *N*/*a*, starting with the given tuple
(*e*, *k*, *x*_{k}, *y*_{e}); we need
not start at the beginning since periods smaller than the one found
have already been (essentially) excluded. Note that all arithmetic
operations (except GCD and subscript arithmetic!) are to be done modulo
*N*/*a* in this continuation.