On the period of the linear congruential and power generators

Abstract

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/2+\epsilon (n)}$ for any monotone function $\epsilon (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-\epsilon }$ for any $\epsilon >0$. Moreover, the period is unconditionally greater than $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}/n\mathbb{Z}{)}^{\times }$.

20 pages. One of the quoted results (Theorem 23 in the previous version) is stated for any unbounded monotone function psi(x), but it appears that the proof only supports the case when psi(x) is increasing rather slowly. As a workaround, we provide a modified version of Theorem 23, and change the argument in the proof of Theorem 27 (Theorem 25 in the previous version)

Cited by in corpus (9)

• The iterated Carmichael λ-function and the number of cycles of the power generator
• On the Distribution of Pseudopowers
• Almost all primes have a multiple of small Hamming weight
• The dynamical zeta function for commuting automorphisms of zero-dimensional groups
• Lower bounds for periods of Ducci sequences
• On the Order of $a$ modulo $n$ on Average
• Average Results on the Order of $a$ modulo $p$
• Periodic points and tail lengths of split polynomial maps modulo primes
• Counting dynamical systems over finite fields