¿Por qué los números primos en módulo dan lugar a distribuciones más uniformes?

Question

Supongamos una secuencia como la siguiente:

$S_{n} = (S_{n-1} * c_{1} + c_{2})\text{ mod } m$

Este es el generador pseudoaleatorio que se encuentra en la función aleatoria de la mayoría de los lenguajes de programación.

Se sabe que un primo $m$ da lugar a una distribución más uniforme de los números aleatorios, como resultado de un mayor período para $S_{n}$ . Como resultado, $m$ es típicamente un número primo.

¿Por qué los números primos suelen dar lugar a períodos mayores que los números factorizables para la aritmética del módulo?

Answer 1

Según Wikipedia el período es como máximo $m$ y es igual a $m$ sólo si

1. $\gcd(c_2,m)=1$ ,

2. $p\mid m$ implica $p\mid c_1-1$ para todos los primos $p$ y

3. $4\mid m$ implica $4\mid c_1-1$ .

Así que $m$ no tiene por qué ser primordial, pero es más fácil cumplir y comprobar estas condiciones si lo es.