8.1 Introduction
251
a n = a n+M = a n+qN +r = a n+r .
Comme N est le plus petit entier tel que a n = a n+N , n´ ecessairement r = 0. Donc, N
divise M .
Exemple 8.3 Un g´ en´ erateur de nombres al´ eatoires tr` es populaire est le g´ en´ erateur
lin´ eaire congruentiel. Il g´ en` ere des nombres appartenant ` a E = {1, . . . , p − 1} par la
r` egle
x n = ax n−1 (mod p),
o` u p premier et a est une racine primitive de F p , c’est-` a-dire un ´ el´ ement de E tel que
a
k
≡ 1 (mod p),
k
p−1
≡ 1.
(Rappelons que F p (aussi appel´ e Z p au chapitre 7) est l’ensemble des entiers {0, . . . , p−1}
muni de l’addition et de la multiplication modulo p. F p est un corps si p est premier ;
ceci signifie (voir la d´ efinition 6.1 du chapitre 6) que l’addition et la multiplication sont
commutatives et associatives et ont chacune un ´ el´ ement neutre, que la multiplication est
distributive sur l’addition, que tout ´ el´ ement a un inverse additif et que tout ´ el´ ement non
nul a un inverse multiplicatif. L’existence d’un inverse multiplicatif pour tout ´ el´ ement
non nul est la propri´ et´ e qui nous int´ eresse : elle est d´ emontr´ ee ` a l’exercice 24 du chapitre 6, mais on peut l’admettre pour comprendre la suite.)
Prenons comme exemple le cas p = 7. Alors, 2 n’est pas une racine primitive, car
2
3 = 8 ≡ 1 (mod 7), mais 3 en est une, car
⎧
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩
3
2
≡ 2 (mod 7),
3
3
≡ 6 (mod 7),
3
4
≡ 18 ≡ 4 (mod 7),
3
5
≡ 12 ≡ 5 (mod 7),
3
6
≡ 15 ≡ 1 (mod 7).
La preuve qu’une racine primitive a existe toujours se trouve au th´ eor` eme 7.22 du
chapitre 7. ( `
A nouveau, vous pouvez tenir ce r´ esultat pour acquis et poursuivre votre
lecture.)
Ce g´ en´ erateur produit une suite p´ eriodique de p´ eriode exactement p − 1. Les g´ en´ erateurs lin´ eaires congruentiels sont employ´ es dans de nombreux logiciels et, par exemple,
on utilise souvent p = 2
31
− 1 et a = 16 807, mais ces g´ en´ erateurs ne sont pas jug´ es tr` es
fiables par les experts, car ils ne passent pas les tests statistiques (voir les exercices 2 et
4).
D’autres crit` eres entrent en ligne de compte, notamment des crit` eres ´ economiques.
Dans nombre de cas, on cherche ` a minimiser le temps de calcul et l’espace-m´ emoire.
On se contentera alors de g´ en´ erateurs de nombres al´ eatoires imparfaits du point de vue
statistique, mais suffisants pour les buts vis´ es.
251
a n = a n+M = a n+qN +r = a n+r .
Comme N est le plus petit entier tel que a n = a n+N , n´ ecessairement r = 0. Donc, N
divise M .
Exemple 8.3 Un g´ en´ erateur de nombres al´ eatoires tr` es populaire est le g´ en´ erateur
lin´ eaire congruentiel. Il g´ en` ere des nombres appartenant ` a E = {1, . . . , p − 1} par la
r` egle
x n = ax n−1 (mod p),
o` u p premier et a est une racine primitive de F p , c’est-` a-dire un ´ el´ ement de E tel que
a
k
≡ 1 (mod p),
k
p−1
≡ 1.
(Rappelons que F p (aussi appel´ e Z p au chapitre 7) est l’ensemble des entiers {0, . . . , p−1}
muni de l’addition et de la multiplication modulo p. F p est un corps si p est premier ;
ceci signifie (voir la d´ efinition 6.1 du chapitre 6) que l’addition et la multiplication sont
commutatives et associatives et ont chacune un ´ el´ ement neutre, que la multiplication est
distributive sur l’addition, que tout ´ el´ ement a un inverse additif et que tout ´ el´ ement non
nul a un inverse multiplicatif. L’existence d’un inverse multiplicatif pour tout ´ el´ ement
non nul est la propri´ et´ e qui nous int´ eresse : elle est d´ emontr´ ee ` a l’exercice 24 du chapitre 6, mais on peut l’admettre pour comprendre la suite.)
Prenons comme exemple le cas p = 7. Alors, 2 n’est pas une racine primitive, car
2
3 = 8 ≡ 1 (mod 7), mais 3 en est une, car
⎧
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩
3
2
≡ 2 (mod 7),
3
3
≡ 6 (mod 7),
3
4
≡ 18 ≡ 4 (mod 7),
3
5
≡ 12 ≡ 5 (mod 7),
3
6
≡ 15 ≡ 1 (mod 7).
La preuve qu’une racine primitive a existe toujours se trouve au th´ eor` eme 7.22 du
chapitre 7. ( `
A nouveau, vous pouvez tenir ce r´ esultat pour acquis et poursuivre votre
lecture.)
Ce g´ en´ erateur produit une suite p´ eriodique de p´ eriode exactement p − 1. Les g´ en´ erateurs lin´ eaires congruentiels sont employ´ es dans de nombreux logiciels et, par exemple,
on utilise souvent p = 2
31
− 1 et a = 16 807, mais ces g´ en´ erateurs ne sont pas jug´ es tr` es
fiables par les experts, car ils ne passent pas les tests statistiques (voir les exercices 2 et
4).
D’autres crit` eres entrent en ligne de compte, notamment des crit` eres ´ economiques.
Dans nombre de cas, on cherche ` a minimiser le temps de calcul et l’espace-m´ emoire.
On se contentera alors de g´ en´ erateurs de nombres al´ eatoires imparfaits du point de vue
statistique, mais suffisants pour les buts vis´ es.