Mathematics – Number Theory
Scientific paper
2004-05-07
Mathematics
Number Theory
20 pages. One of the quoted results (Theorem 23 in the previous version) is stated for any unbounded monotone function psi(x),
Scientific paper
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 $(\Z/n\Z)^\times$.
Kurlberg Par
Pomerance Carl
No associations
LandOfFree
On the period of the linear congruential and power generators does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the period of the linear congruential and power generators, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the period of the linear congruential and power generators will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-470305