Générer des nombres
Pour générer une suite de nombres entre 0 et $m-1$, on a coutume d'utiliser la formule :
$$
x_{i+1} = a \cdot x_i + c \mathbin{\small\\%}{m}
$$
La graine est le nombre $x_0$.
proposition
Montrer que la suite $(x_i){i \geq 0}$ telle que $x = a \cdot x_i + c \mathbin{\small\%}{m}$ est périodique quelque soient $a$, $c$, $m$ et $x_0$ et que sa période est au plus $m$
preuve
preuve
avec le modulo
- théoriques :
- choix de a,c , m pour une longue séquence
- pr(xi > xi+1)
Ne pas faire n'importe quoi. A écrit dans the art of computer programming (vol 2.) :
Random numbers should not be generated with a method chosen at random.
$x_{i+1} = ax_i + c mod m$
- propriétés théoriques :
- une longue séquence
- pr(xi > xi+1)
- pratiques :
- chi 2 : proba et indépendance séquences.
TBD uniforme pas suffisant : 0000000111111111 est bien uniforme TBD xi > x(i+1) : théorique
- faire avec des modulo LCG. Voir aussi https://www.staff.uni-mainz.de/pommeren/Cryptology/Bitstream/1_Classic/ Utiliser des merserne prime pour les Lehmer LCG