On the period of the linear congruential and power generators

We consider the periods of the linear congruential and the power generators modulo $n$ and, for fixed choices of initial parameters, give lower bounds that hold for ``most’’ $n$ when $n$ ranges over three different sets: the set of primes, the set of products of two primes (of similar size), and the set of all integers. For most $n$ in these sets, the period is at least $n^{1\mathrm{/}2+ϵ(n)}$ for any monotone function $ϵ(n)$ tending to zero as $n$ tends to infinity. Assuming the Generalized Riemann Hypothesis, for most $n$ in these sets the period is greater than $n^{1-ϵ}$ for any $\epsilon

0$\mathrm{.}Moreover,theperiodisunconditionallygreaterthan$n^{1/2+\delta}$, for some fixed $\delta >0$, for a positive proportion of $n$ in the above mentioned sets. These bounds are related to lower bounds on the multiplicative order of an integer $e$ modulo $p-1$, modulo $\lambda (pl)$, and modulo $\lambda (m)$ where $p,l$ range over the primes, $m$ ranges over the integers, and where $\lambda (n)$ is the order of the largest cyclic subgroup of $(\mathbb{Z}\mathrm{/}n\mathbb{Z}{)}^{\times }$.