  A permutation P on {1,..,N} is a_fast_forward_permutation_ if for each m the
computational complexity of evaluating P^m(x)$ is small independently of m and
x. Naor and Reingold constructed fast forward pseudorandom cycluses and
involutions. By studying the evolution of permutation graphs, we prove that the
number of queries needed to distinguish a random cyclus from a random
permutation on {1,..,N} is Theta(N) if one does not use queries of the form
P^m(x), but is only Theta(1) if one is allowed to make such queries.
  We construct fast forward permutations which are indistinguishable from
random permutations even when queries of the form P^m(x) are allowed. This is
done by introducing an efficient method to sample the cycle structure of a
random permutation, which in turn solves an open problem of Naor and Reingold.

Cryptography and Security;Computational Complexity;Combinatorics;Probability