Período de generador lineal congruente

Question

¿Cómo se puede calcular la distribución de probabilidad de la duración del periodo de un generador lineal congruente? Es $X_{n+1} = (aX_n + c) \bmod m$ donde $a$ se elige uniformemente al azar de ${1,\dots, m-1}$ y $c$ se elige uniformemente al azar de ${0,\dots, m-1}$ y $m$ es un primer fijo. Tomar el $X_0$ a ser un valor arbitrario de ${0,\dots, m-1}$.

Si es difícil hacerlo exactamente, ¿es posible dar buena límites para el cdf?

Answer 1

Este no puede responder a la pregunta exactamente, pero los resultados obtenidos indican que la respuesta final puede depender de los factores comunes a $a-1$$m$.

---

Preliminar lema y el teorema de

Lema: Supongamos $p$ es el primer y $j\ge2$. Entonces, a menos $p=j=2$, $$ p^k\,|\n\implica\a la izquierda.p^{k-j+2}\,\medio|\,\binom{n}{j}\right.\la etiqueta{1} $$ Además, $$ 2^k\,|\n\implica\a la izquierda.2^{k-1}\,\medio|\,\binom{n}{2}\right.\la etiqueta{2} $$

Prueba: A Menos Que $p=j=2$, $j\lt p^{j-1}$. Por lo tanto, $j$ tiene al la mayoría de las $j-2$ factores de $p$. A continuación, $(1)$ sigue desde el binomio identidad $$ \binom{n}{j} = \frac nj\binom{n-1}{j-1} $$ $(2)$ sigue de $$ \binom{n}{2}=\frac n2(n-1) $$ $\square$

---

Teorema: Supongamos que $$ \begin{align} &\text{(a) for all primes %#%#%, }p\mid m\implies p\mid a-1\\ &\text{(b) }4\mid m\implies4\mid a-1 \end{align} $$ A continuación, $$ \a la izquierda.m\,\medio|\,\frac{a^n-1} {- 1}\right.\implica m\,|\,n $$

Prueba: Supongamos $p$. Por simplicidad de notación, deje $\left.m\,\middle|\,\dfrac{a^n-1}{a-1}\right.$. Entonces $$ \frac{a^n-1} {- 1}=\sum_{j=1}^n\binom{n}{j}r^{j-1}\etiqueta{3} $$ Para cualquier extraño $r=a-1$, suponga que $p\,|\,m$$p^k\,|\,n$. El uso de $\left.p^{k+1}\,\middle|\,\dfrac{a^n-1}{a-1}\right.$, obtenemos $$ n\equiv-\sum_{j=2}^n\binom{n}{j}r^{j-1}\pmod{p^{k+1}}\etiqueta{4} $$ El Lema y la suposición de que $(3)$ dice que $p\,|\,m\implies p\,|\,r$ se divide cada término en $p^{k-j+2}p^{j-1}=p^{k+1}$. Por lo tanto, $(4)$. Bootstrapping), obtenemos que para cualquier extraño $p^{k+1}\,|\,n$, $$ \a la izquierda.p^k\,\medio|\,\frac{a^n-1} {- 1}\right.\implica p^k\,|\n\etiqueta{5} $$ Si $p\,|\,m$,$2\,|\,m$. El uso de $\left.2\,\middle|\,\dfrac{a^n-1}{a-1}\right.$, obtenemos $$ n\equiv-\sum_{j=2}^n\binom{n}{j}r^{j-1}\pmod{2}\etiqueta{6} $$ La suposición de que $(3)$ dice que $p\,|\,m\implies p\,|\,r$ se divide cada término en $2$. Por lo tanto, $(6)$; es decir, $$ \a la izquierda.2\,\medio|\,\frac{a^n-1} {- 1}\right.\implies2\,|\n\etiqueta{7} $$ Si $2\,|\,n$, a continuación, supongamos que $4\,|\,m$ y $2^k\,|\,n$. El uso de $\left.2^{k+1}\,\middle|\,\dfrac{a^n-1}{a-1}\right.$, obtenemos $$ n\equiv-\sum_{j=2}^n\binom{n}{j}r^{j-1}\pmod{2^{k+1}}\etiqueta{8} $$ El Lema y la suposición de que $(3)$ dice que $4\,|\,m\implies4\,|\,r$ se divide cada término en $2^{k-j+1}4^{j-1}=2^{k+j-1}$. Desde $(8)$,$j\ge2$. Bootstrapping), obtenemos que $$ \a la izquierda.2^k\,\medio|\,\frac{a^n-1} {- 1}\right.\implica 2^k\,|\n\etiqueta{9} $$ $2^{k+1}\,|\,n$ y, o bien $(5)$ o $(7)$ muestran que $$ \a la izquierda.m\,\medio|\,\frac{a^n-1} {- 1}\right.\implica m\,|\n\etiqueta{10} $$ $(9)$

---

Supongamos que la secuencia de $\square$ está definido por la recurrencia $$ x_{k+1}=ax_k+b\etiqueta{11} $$ luego, de manera inductiva, tenemos $$ x_k=a^kx_0+\frac{a^k-1} {- 1}b\etiqueta{12} $$ Multiplicando por $x_k$ y añadiendo $a-1$ rendimientos $$ \frac{a^{k_1}-1} {- 1}\equiv\frac{a^{k_2}-1} {- 1}\pmod{m}\implica un^{k_1}\equiv a^{k_2}\pmod{m}\etiqueta{13} $$ Por lo tanto, para investigar la periodicidad de las $1$, nos fijamos en la periodicidad de las $x_k$.

Para maximizar el rango de $\dfrac{a^k-1}{a-1}\bmod{m}$ ,vamos a suponer que $x_k$. Esto implica $$ \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} $$ Es decir, el período de $(a,m)=(b,m)=1$ es el más pequeño de positivos $x_k$ para los que $$ \frac{a^n-1} {- 1}\equiv0\pmod{m}\etiqueta{15} $$ Por el teorema anterior, $n$ y ya no son sólo $m\,|\,n$ residuo clases de $m$, debemos tener $\bmod{\,m}$. Por lo tanto,

Teorema:Supongamos $$ \begin{align} &\text{(a) for all primes %#%#%, }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} $$ A continuación, el sistema modular de la secuencia definida por $$ x_{n+1}\equiv ax_n+b\pmod{m} $$ tiene período de $n=m$.

Answer 2

No hay mucho de una distribución hay. El período es $1$ $a=1$ y $c=0$ o si $a\ne1$ y $X_0=c/(1-a)$; lo contrario es $m-1$.