lundi 12 septembre 2016

Distribution of linear congruential generator with uniform prime modulus

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