Permutation graphs, fast forward permutations, and sampling the cycle structure of a permutation
<|reference_start|>Permutation graphs, fast forward permutations, and sampling the cycle structure of a permutation: 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.<|reference_end|>
@article{tsaban2002permutation,
    title={Permutation graphs, fast forward permutations, and sampling the cycle
  structure of a permutation},
    author={Boaz Tsaban},
    journal={Journal of Algorithms 47 (2003), 104--121},
    year={2002},
    doi={10.1016/S0196-6774(03)00017-8},
    archivePrefix={arXiv},
    eprint={cs/0207027},
    primaryClass={cs.CR cs.CC math.CO math.PR}
}