Éléments primitifs de Z/11Z
6 est un élément primitif de Z/11Z : les 10 restes sont différents dans la division euclidienne de 6k par 11, k variant de 1 à 10.
2 aussi, mais pas 3.
Cherchons tous les éléments primitifs de Z/11Z.
Sur Derive, on a
Les éléments primitifs de Z/11Z sont donc : 2, 6, 7 et 8.
De la même façon on peut déterminer les éléments primitifs de Z/13Z.
Il s’agit de : 2, 6, 7 et 11..
6 et 7 sont des éléments primitifs communs à Z/11Z et à Z/13Z.
On considère alors le reste dans la division euclidienne par 10 de l’entier relatif égal à la différence du reste de 6n dans la division par 11 et du reste de 7n dans la division euclidienne par 13, n étant un entier naturel non nul donné.
Les restes possibles sont donc les entiers compris entre 0 et 9.
La suite de ces restes présente-t-elle une période ?
Pour cela on fera varier n de 1 à 70.
L’écriture est peu explicite. On peut l’écrire sous forme de matrice :
La période est plus facile à trouver ici : la suite des nombres de la première ligne se retrouve à la dernière. la période est donc de 60.
On peut maintenant introduire des éléments supplémentaires que l’on notera s et t qui sont des entiers entre 1 et 10 pour s et entre 1 et 13 pour t.
On cherche alors la période de : mod(mod(s×6n,11)-mod(t×7n,13),10).
On peut écrire cette liste de terme sous la forme d’une fonction à deux variables :
ran(s,t)=mod(mod(s×6n,11)-mod(t×7n,13),10)
ou sous forme matricielle :
ran(s,t)=mod(mod(s×6i+10j,11)-mod(t×7i+10j,13),10),
avec i variant de 1 à 10 et j variant de 0 à 6.Sur Derive :
Sur la calculatrice l’instruction est identique si l’on remplace « vector » par « suite ».
On obtient par exemple :
|
|
|
|
|
|
Dans chaque cas la période est de 60 qui est égal à ((11-1)(13-1))/2.
Si l’on remplace modulo 10 par modulo 16 par exemple, cela ne change rien
Recommençons avec deux autres nombres premiers, par exemple 17 et 23 :
les éléments primitifs de Z/17Z sont :
Les éléments primitifs sont : 3, 5, 6, 7, 10, 11,12, 14.
On reprend le même calcul avec Z/23Z :
On trouve que les éléments primitifs sont : 5, 7,10, 11, 14, 15, 17, 19, 20, 21.
On construit comme précédemment la fonction :
Selon le résultat précédent nous nous attendons à une période de :
((23-1)(17-1))/2=(22×16)/2=176
On peut essayer avec s = 7 et t = 8.
On trouve :
Le 177ème terme.
Les nombres premiers choisis par Texas sont p = 231 - 85 et p’ = 231 - 249 avec comme éléments primitifs : a = 40014 et a’ = 40692.
La période est :
((231 - 85 - 1)(231 - 249 - 1))/2 = 2305842648436451838
Les valeurs de s et de t sont variables : il s’agit en fait des termes successifs de deux suites géométriques modulo p ou p’, de raisons respectives a et a’ et dont le premier terme est défini par l’initialisation.
Pour bien en comprendre le fonctionnement, donnons un exemple.
Supposons que l’on se donne deux nombres s1 et s2 comme termes initiaux des deux suites récurrentes que nous allons construire.
On a u0 = s1 et v0 = s2.
On aura alors u1 = mod(u0×a,p) et v1 = mod(v0×a’,p’).
Le premier nombre aléatoire calculé par la machine est alors : (mod(u1 - v1,p-1))/(p - 1).
Sur la TI-89 ou sur la TI-92, on peut modifier les valeurs de ces termes initiaux. Ils sont rangés dans les variables système seed1 et seed2.
On calcule les deux premiers termes des deux suites autres que les termes initiaux :
On remarque que la calculatrice modifie les deux variables systèmes avec les contenus des premiers termes des suites.
Regardons un coup plus loin.
On remarquera toutefois la légère différence dans les valeurs approchées (on peut penser que Texas ayant le même générateur sur les TI-83 et les TI-89 a choisi une précision de calcul correspondant à celle de la TI-83).
L’instruction IniNbrAl permet l’initialisation du générateur, c'est-à-dire des deux termes initiaux. Cette instruction n’a qu’un argument qui est un entier (on peut prendre un décimal comme argument, mais la calculatrice le remplace par sa partie entière).
Pour 0 et 1, on a :
Pour 2 et 10 par exemple :
Pour 59623 par exemple :
Reste à prouver que cela donne bien une distribution uniforme.
Mathématiquement c’est une autre histoire. On peut toutefois se donner une idée graphique de ce qui se passe.
On commence par un petit programme permettant le tracé de points dont les deux coordonnées sont des nombres aléatoires compris entre 0 et 1 :
Ce qui donne pour n=10000
Et sur la TI-83 :
Et la représentation graphique :
