# Period of linear congruential generator

How can you calculate the probability distribution of the period length of a linear congruential generator? That is $X_{n+1} = (aX_n + c) \bmod m$ where $a$ is chosen uniformly at random from $\{1,\dots, m-1\}$ and $c$ is chosen uniformly at random from $\{0,\dots, m-1\}$ and $m$ is a fixed prime. Take $X_0$ to be some arbitrary value from $\{0,\dots, m-1\}$.

If it is hard to do exactly, is it possible to give good bounds for the cdf?

-

This may not address the question exactly, but the results derived indicate that the final answer may depend on the factors common to $a-1$ and $m$.

A preliminary lemma and theorem

Lemma: Suppose $p$ is prime and $j\ge2$. Then, unless $p=j=2$, $$p^k\,|\,n\implies\left.p^{k-j+2}\,\middle|\,\binom{n}{j}\right.\tag{1}$$ Furthermore, $$2^k\,|\,n\implies\left.2^{k-1}\,\middle|\,\binom{n}{2}\right.\tag{2}$$

Proof: Unless $p=j=2$, $j\lt p^{j-1}$. Thus, $j$ has at most $j-2$ factors of $p$. Then $(1)$ follows from the binomial identity $$\binom{n}{j} = \frac nj\binom{n-1}{j-1}$$ $(2)$ follows from $$\binom{n}{2}=\frac n2(n-1)$$ $\square$

Theorem: Suppose that \begin{align} &\text{(a) for all primes p, }p\mid m\implies p\mid a-1\\ &\text{(b) }4\mid m\implies4\mid a-1 \end{align} Then, $$\left.m\,\middle|\,\frac{a^n-1}{a-1}\right.\implies m\,|\,n$$

Proof: Assume $\left.m\,\middle|\,\dfrac{a^n-1}{a-1}\right.$. For simplicity of notation, let $r=a-1$. Then $$\frac{a^n-1}{a-1}=\sum_{j=1}^n\binom{n}{j}r^{j-1}\tag{3}$$ For any odd $p\,|\,m$, assume that $p^k\,|\,n$ and $\left.p^{k+1}\,\middle|\,\dfrac{a^n-1}{a-1}\right.$. Using $(3)$, we get $$n\equiv-\sum_{j=2}^n\binom{n}{j}r^{j-1}\pmod{p^{k+1}}\tag{4}$$ The Lemma and the assumption that $p\,|\,m\implies p\,|\,r$ says that $p^{k-j+2}p^{j-1}=p^{k+1}$ divides each term in $(4)$. Thus, $p^{k+1}\,|\,n$. Bootstrapping, we get that for any odd $p\,|\,m$, $$\left.p^k\,\middle|\,\frac{a^n-1}{a-1}\right.\implies p^k\,|\,n\tag{5}$$ If $2\,|\,m$, then $\left.2\,\middle|\,\dfrac{a^n-1}{a-1}\right.$. Using $(3)$, we get $$n\equiv-\sum_{j=2}^n\binom{n}{j}r^{j-1}\pmod{2}\tag{6}$$ The assumption that $p\,|\,m\implies p\,|\,r$ says that $2$ divides each term in $(6)$. Thus, $2\,|\,n$; that is, $$\left.2\,\middle|\,\frac{a^n-1}{a-1}\right.\implies2\,|\,n\tag{7}$$ If $4\,|\,m$, then assume that $2^k\,|\,n$ and that $\left.2^{k+1}\,\middle|\,\dfrac{a^n-1}{a-1}\right.$. Using $(3)$, we get $$n\equiv-\sum_{j=2}^n\binom{n}{j}r^{j-1}\pmod{2^{k+1}}\tag{8}$$ The Lemma and the assumption that $4\,|\,m\implies4\,|\,r$ says that $2^{k-j+1}4^{j-1}=2^{k+j-1}$ divides each term in $(8)$. Since $j\ge2$, we have $2^{k+1}\,|\,n$. Bootstrapping, we get that $$\left.2^k\,\middle|\,\frac{a^n-1}{a-1}\right.\implies 2^k\,|\,n\tag{9}$$ $(5)$ and either $(7)$ or $(9)$ show that $$\left.m\,\middle|\,\frac{a^n-1}{a-1}\right.\implies m\,|\,n\tag{10}$$ $\square$

Suppose the sequence $x_k$ is defined by the recurrence $$x_{k+1}=ax_k+b\tag{11}$$ then, inductively, we have $$x_k=a^kx_0+\frac{a^k-1}{a-1}b\tag{12}$$ Multiplying by $a-1$ and adding $1$ yields $$\frac{a^{k_1}-1}{a-1}\equiv\frac{a^{k_2}-1}{a-1}\pmod{m}\implies a^{k_1}\equiv a^{k_2}\pmod{m}\tag{13}$$ Therefore, to investigate the periodicity of $x_k$, we look at the periodicity of $\dfrac{a^k-1}{a-1}\bmod{m}$.

To maximize the range of $x_k$ ,we will assume that $(a,m)=(b,m)=1$. This implies \begin{align} \frac{a^{k_1}-1}{a-1}\equiv\dfrac{a^{k_2}-1}{a-1}\pmod{m} &\implies\frac{a^{k_1-k_2}-1}{a-1}a^{k_2}\equiv0\pmod{m}\\[6pt] &\implies\frac{a^{k_1-k_2}-1}{a-1}\equiv0\pmod{m}\tag{14} \end{align} That is, the period of $x_k$ is the smallest positive $n$ for which $$\frac{a^n-1}{a-1}\equiv0\pmod{m}\tag{15}$$ By the theorem above, $m\,|\,n$ and since there are only $m$ residue classes $\bmod{\,m}$, we must have $n=m$. Thus,

Theorem: Suppose \begin{align} &\text{(a) for all primes p, }p\mid m\implies p\mid a-1\\ &\text{(b) }4\mid m\implies4\mid a-1\\ &\text{(c) }\gcd(b,m)=1 \end{align} Then the modular sequence defined by $$x_{n+1}\equiv ax_n+b\pmod{m}$$ has period $m$.

-

There's not much of a distribution there. The period is $1$ if $a=1$ and $c=0$ or if $a\ne1$ and $X_0=c/(1-a)$; otherwise it's $m-1$.

-
Is $c/(1-a)$ uniformly distributed? – ArtM Nov 27 '12 at 13:32
@ArtM: Yes, it's just $(1-a)^{-1}$ times $c$, so it takes all $m$ values as $c$ ranges over all $m$ values. – joriki Nov 27 '12 at 13:42
Thanks very much. – ArtM Nov 27 '12 at 13:52
@ArtM: You're welcome! – joriki Nov 27 '12 at 14:01
@ArtM: Sorry, there was a mistake; the period is otherwise $m-1$, not $m$. – joriki Nov 27 '12 at 14:59