4
$\begingroup$

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?

2 Answers 2

5

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$.

0

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$.

  • 0
    @joriki Did you forget to fix it?2013-05-17