The paper considers the pseudorandom number generator
where the modulus , the initial state and the exponent are given. One particularly interesting case is when the modulus is of the form where and are different primes of the same magnitude. The authors show that for almost all choices of , it holds for almost all choices of , that the period of the generator exceeds . From earlier work by some of the authors it follows that this implies that the power generator is uniformly distributed.
One application of the results are a rigorous proof that the cycling attack on the RSA cryptosystem has a negligible chance to be efficient.
In the Corrigendum a corrected proof of Theorem 8 is given.