# Period of (non-linear) congruential generator

This is a follow up to Period of linear congruential generator .

How can you calculate the probability distribution of the period length of a general congruential generator? That is $X_{n+1} = \sum_{i=0}^k a_i X_n^i \bmod m$ where the $a_i \in \mathbb{Z_m}$ are chosen uniformly at random, $k>1$ is a fixed integer 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?

-
Do I understand correctly that you want $X_{n+1}=bX_n$, with $b=\sum_{i=0}^ka_i^i$ (where the superscript denotes the $i$-th power?), so the question is basically asking for the probability that $b$ is $0$ or $1$ if the $a_i$ are uniformly distributed? –  joriki Nov 27 '12 at 14:56
@joriki. Typo, sorry. Fixed. –  ArtM Nov 27 '12 at 15:07