as you know the general formula for pseudo random generator is this
U(n)=a*U(n−1)+b [mod z]
where we have control of U(n-1) and a and b and z
i want to know if there is formula that give you how much generate number before it start repeating those numbers ?
E.g
if we have
- a = 2
- b = 5
- U(n-1) = 6
- z = 26
we have 12 number generated before the sequence start repeating itself
Iterated Function
Shows the non modulo form has iterates:$$a^nx+\frac{a^n-1}{a-1}b,\quad a\neq1\tag{wikipedia}$$ Which, any time z is odd, can be turned into an equivalent with a and b coprime to z, and we can use Euler's totient theorem to reduce it to x in $\varphi(z)$ iterations. x being our equivalent to Uo . Which if a and b are coprime to z already, also holds for even moduli. Via group theory and Lagranges theorem (I think), then every pair of inputs, will create a cycle that is of length a divisor of this maximal order.