We consider two common pseudorandom number generators constructed from iterations of linear and Möbius maps
$x \mapsto gx$ and $ x \mapsto (ax+b)/(cx+d)$
over a residue ring modulo an integer q ≥ 2, which are known as congruential and inversive generators, respectively. There is an extensive literature on the pseudorandomness of elements $u_{n}, n=1,2,...$, of the corresponding orbits. In this talk we are interested in what happens in these orbits at prime times, that is, we study elements $u_{p}$, $p = 2, 3, . . .$, where $p$ runs over primes.
We give a short survey of previous results on the distribution of $u_{p}$ for the above maps and then:
- Explain how B. Kerr, L. Mérai and I. E. Shparlinski (2019) have used a method of N. M. Korobov (1972) to study the congruential generator on primes modulo a large power of a fixed prime, e.g. $q=3^{\gamma }$ with a large $\gamma$. We also give applications of this result to digits of Mersenne numbers $2^{p}-1$.
- Present a result of L. Mérai and I. E. Shparlinski (2020) on the distribution of the inversive generator on primes modulo a large prime, q. The proof takes advantage of the flexibility of Heath-Brown’s identity, while Vaughan’s identity does not seem to be enough for our purpose. We also pose several open questions and discuss links to Sarnak’s conjecture on pseudorandomness of the Möbius function.
