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

avec le modulo

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$

TBD uniforme pas suffisant : 0000000111111111 est bien uniforme TBD xi > x(i+1) : théorique

  1. 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