Period of the power generator and small values of Carmichael's function (Q2723531)

The paper considers the pseudorandom number generator NEWLINE\[NEWLINEu_n= u_{n-1}^e\pmod m, \quad 0\leq u_n\leq m-1,\;n=1,2,\dots,NEWLINE\]NEWLINE where the modulus \(m\), the initial state \(u_0=v\) and the exponent \(e\) are given. One particularly interesting case is when the modulus is of the form \(m=pl\) where \(p\) and \(l\) are different primes of the same magnitude. The authors show that for almost all choices of \(p\), \(l\) it holds for almost all choices of \(v\), \(e\) that the period of the generator exceeds \((pl)^{1-\varepsilon}\). From earlier work by some of the authors it follows that this implies that the power generator is uniformly distributed. NEWLINENEWLINENEWLINEOne application of the results are a rigorous proof that the cycling attack on the RSA cryptosystem has a negligible chance to be efficient. NEWLINENEWLINENEWLINEIn the Corrigendum a corrected proof of Theorem 8 is given.