8
G´ en´ erateurs de nombres al´ eatoires
Ce chapitre peut ˆ etre utilis´ e de deux mani` eres : on peut soit en tirer une ou deux heures
de « flash-science », avec un bagage minimum comprenant n´ eanmoins une certaine familiarit´ e avec l’arithm´ etique modulo p, soit traiter le sujet plus en profondeur. Dans ce
cas, il est pr´ ef´ erable d’ˆ etre d´ ej` a familier avec les corps finis ou la congruence modulo
2, parce qu’on a au pr´ ealable regard´ e le chapitre 6 (ou le chapitre 7), par exemple. Les
sections faisant r´ ef´ erence ` a ces chapitres sont clairement indiqu´ ees. Dans ce chapitre,
nous traiterons longuement des registres ` a d´ ecalage qui sont aussi ´ etudi´ es ` a la section 1.4 du chapitre 1, mais les deux traitements sont ind´ ependants. Certains exercices
font appel aux probabilit´ es et peuvent ˆ etre saut´ es si on n’a pas de bagage suffisant de
ce cˆ ot´ e-l` a.
8.1 Introduction
Le 10 avril 1994, un joueur est appr´ ehend´ e par la police au Casino de Montr´ eal.
Son crime ? Il vient de battre toutes les statistiques possibles en remportant trois lots
cons´ ecutifs au jeu de keno, amassant ainsi plus d’un demi-million de dollars
1 . Il est
clairement soup¸ conn´ e d’avoir enfreint les lois des jeux de hasard interdisant la collusion avec les employ´ es du casino, la manipulation des appareils ´ electroniques, etc. Une
enquˆ ete est men´ ee et, apr` es quelques semaines, le joueur est relˆ ach´ e et son lot, capital
et int´ erˆ ets, lui est remis. Et le Casino de Montr´ eal a appris une le¸ con rapide sur les
g´ en´ erateurs de nombres al´ eatoires.
Il reste fort peu d’appareils m´ ecaniques dans les casinos modernes. Seule peut-ˆ etre
la roulette demeure. Les autres jeux ont ´ et´ e remplac´ es par des ordinateurs qui simulent
1 Au keno, le joueur doit choisir une dizaine de nombres dans l’ensemble {1, 2, . . . , 80}. Le
casino tire alors 20 boules parmi 80 boules num´ erot´ ees de 1 ` a 80. Ce tirage peut ´ egalement
ˆ etre fait ´ electroniquement, comme c’est le cas maintenant dans la plupart des casinos. Le lot
gagn´ e d´ epend de la mise du joueur et du nombre de co¨ ıncidences entre les nombres choisis par
le joueur et les num´ eros des boules tir´ ees au sort.
G´ en´ erateurs de nombres al´ eatoires
Ce chapitre peut ˆ etre utilis´ e de deux mani` eres : on peut soit en tirer une ou deux heures
de « flash-science », avec un bagage minimum comprenant n´ eanmoins une certaine familiarit´ e avec l’arithm´ etique modulo p, soit traiter le sujet plus en profondeur. Dans ce
cas, il est pr´ ef´ erable d’ˆ etre d´ ej` a familier avec les corps finis ou la congruence modulo
2, parce qu’on a au pr´ ealable regard´ e le chapitre 6 (ou le chapitre 7), par exemple. Les
sections faisant r´ ef´ erence ` a ces chapitres sont clairement indiqu´ ees. Dans ce chapitre,
nous traiterons longuement des registres ` a d´ ecalage qui sont aussi ´ etudi´ es ` a la section 1.4 du chapitre 1, mais les deux traitements sont ind´ ependants. Certains exercices
font appel aux probabilit´ es et peuvent ˆ etre saut´ es si on n’a pas de bagage suffisant de
ce cˆ ot´ e-l` a.
8.1 Introduction
Le 10 avril 1994, un joueur est appr´ ehend´ e par la police au Casino de Montr´ eal.
Son crime ? Il vient de battre toutes les statistiques possibles en remportant trois lots
cons´ ecutifs au jeu de keno, amassant ainsi plus d’un demi-million de dollars
1 . Il est
clairement soup¸ conn´ e d’avoir enfreint les lois des jeux de hasard interdisant la collusion avec les employ´ es du casino, la manipulation des appareils ´ electroniques, etc. Une
enquˆ ete est men´ ee et, apr` es quelques semaines, le joueur est relˆ ach´ e et son lot, capital
et int´ erˆ ets, lui est remis. Et le Casino de Montr´ eal a appris une le¸ con rapide sur les
g´ en´ erateurs de nombres al´ eatoires.
Il reste fort peu d’appareils m´ ecaniques dans les casinos modernes. Seule peut-ˆ etre
la roulette demeure. Les autres jeux ont ´ et´ e remplac´ es par des ordinateurs qui simulent
1 Au keno, le joueur doit choisir une dizaine de nombres dans l’ensemble {1, 2, . . . , 80}. Le
casino tire alors 20 boules parmi 80 boules num´ erot´ ees de 1 ` a 80. Ce tirage peut ´ egalement
ˆ etre fait ´ electroniquement, comme c’est le cas maintenant dans la plupart des casinos. Le lot
gagn´ e d´ epend de la mise du joueur et du nombre de co¨ ıncidences entre les nombres choisis par
le joueur et les num´ eros des boules tir´ ees au sort.