Period of the power generator and small values of Carmichael’s function

Abstract:

Consider the pseudorandom number generator \begin{equation*} u_n\equiv u_{n-1}^e\pmod {m},\quad 0\le u_n\le m-1,\quad n=1,2,\ldots , \end{equation*} where we are given the modulus $m$, the initial value $u_0=\vartheta$ and the exponent $e$. One case of particular interest is when the modulus $m$ is of the form $pl$, where $p,l$ are different primes of the same magnitude. It is known from work of the first and third authors that for moduli $m=pl$, if the period of the sequence $(u_n)$ exceeds $m^{3/4+\varepsilon }$, then the sequence is uniformly distributed. We show rigorously that for almost all choices of $p,l$ it is the case that for almost all choices of $\vartheta ,e$, the period of the power generator exceeds $(pl)^{1-\varepsilon }$. And so, in this case, the power generator is uniformly distributed. We also give some other cryptographic applications, namely, to ruling-out the cycling attack on the RSA cryptosystem and to so-called time-release crypto. The principal tool is an estimate related to the Carmichael function $\lambda (m)$, the size of the largest cyclic subgroup of the multiplicative group of residues modulo $m$. In particular, we show that for any $\Delta \ge (\log \log N)^3$, we have $\lambda (m)\ge N\exp (-\Delta )$ for all integers $m$ with $1\le m\le N$, apart from at most $N\exp \left (-0.69\left (\Delta \log \Delta \right )^{1/3}\right )$ exceptions.