A Linear Congruential Generator is an algorithm yielding a pseudo-random sequence defined by the recurrence
Xn+1 = (Xn*a + c ) mod q
Under certain conditions (i.e. values for a,c,q,X0), the sequence satisfies the frequency test: in any sub-sequence of length L (with L big enough) the number of elements smaller than a given k < q is roughly (k/q)*L.
Is there a formal proof of this fact when the modulo q is a prime number chosen uniformly from some (big) interval? Otherwise stated: if q is a uniform random prime and k <= q, does
P(Xn < k) = k/q
hold (for opportune values of a,c,X0)?
Aucun commentaire:
Enregistrer un commentaire