Lorsque l'on dispose d'un générateur effectivement aléatoire et uniforme
, on peut construire un générateur
effectivement aléatoire et uniforme de points dans 
par 
,
et même par 
si l'inter-dépendance des points obtenus n'est pas un objectif. Mais
si nous partons d'un générateur pseudo-aléatoire, il est tout à fait
possible que 
soit un générateur acceptable sur
sans que
soit utilisable comme générateur même médiocre dans .
Or le problème de la génération de points uniformément répartis dans un carré se pose de façon quasi inévitable, même pour résoudre des problèmes unidimensionnels. En effet la plupart des générateurs unidimensionnels non uniformes partent non pas d'un point aléatoirement réparti dans un segment donné, mais d'un point uniformément situé dans un carré. Tel est en particulier le cas pour les générateurs efficaces de variables réparties selon la loi normale.
Commençons par des remarques valables pour tout générateur pseudo-aléatoire,
les problèmes spécifiques aux générateurs congruentiels, les plus
utilisés, étant examinés par la suite. Du fait de sa nature essentiellement
finie et déterministe, un générateur est nécessairement périodique,
et la suite des points 
a évidemment
la même période. Si cette période est 
, chaque instanciation
dispose en moyenne d'un millionième de la place disponible.
On peut alors modéliser la situation en considérant les six premiers
chiffres décimaux de 
comme formant six variables iid, uniformément
réparties dans l'ensemble des chiffres, tandis que les chiffres suivants
de sont déterminés par la donnée des six premiers. Mais avec
un tel modèle, le nombre 
est totalement déterminé par
et donc par la donnée des six premiers chiffres de ce nombre.
Une seconde façon de modéliser la situation consiste à considérer
les trois premiers chiffres des deux nombres et
comme formant six variables iid, uniformément réparties dans l'ensemble
des chiffres, la connaissance de ces variables permettant de déterminer
les chiffres restants des deux nombres.
Ces deux modèles sont également valables, mais il est clair qu'il n'est pas possible de les utiliser simultanément. Il est également clair que la sémantique attachée à l'expression "générateur aléatoire uniforme de points dans un carré" relève du deuxième modèle et non du premier : il est donc important de ne pas réintroduire le premier par la petite porte.
Ainsi, la structure en réseau des générateurs congruentiels que nous
allons examiner dans le reste de cette section ne doit pas être mal
interprétée. Pour une période 
(cf figure 1.8)
une structure comme celle de gauche doit être rejetée car elle a des
effets à une distance 
, nettement supérieure à 
tandis que la structure de droite, faisant intervenir des distances
de cet ordre, est invisible sous les hypothèses d'utilisation
du générateur.
Après ces remarques générales, étudions plus en détail le cas des
générateurs congruentiels, c'est à dire définis par 
(pour 
) ou encore par 
(pour 
). Nous nous limiterons au cas où
est un nombre premier et 
une racine primitive, la période
du générateur étant alors 
.
Considérons les points : ce sont
les réductions modulo 
de points tous alignés sur la droite
du plan 
. Cette réduction modulaire
a pour effet de scinder cette droite en segments distants entre
eux de 
. La figure 1.6
en montre deux exemples : 
où les points se répartissent
sur 2 segments distants de 
, et 
où les points se répartissent sur 3 segments de pente 
et distants
entre eux de 
.
Lorsque le multiplicateur augmente, on constate que d'autres alignements
deviennent prépondérants. Ainsi, 
(figure 1.7,
à gauche) fait apparaître non seulement des alignements sur 
segments
de pente 
, distants entre eux de 
,
mais aussi sur 
segments de pente 
,
distants entre eux de 
ainsi que sur 
segments de pente 
,
distants entre eux de 
.
Il est aisé de montrer qu'un alignement principal ayant 
(fraction irréductible) pour pente comporte 
segments, distants
entre eux de 
. On constate également
que, pour chaque direction principale, il existe une direction conjuguée
telle que l'ensemble des intersections des deux réseaux de droites
se compose de l'origine et des points atteints par le générateur.
Ainsi, pour 
(figure 1.7, à droite),
voit-on apparaître les pentes 
et 
. Un calcul immédiat montre
que l'aire de la maille élémentaire déterminée par les réseaux formés
par les droites 
et 
et 
est 
.
On peut alors vérifier que 
,
et enfin que 
.
Pour résumer ce qui précède, on peut dire qu'en dimension 2 un générateur congruentiel engendre en tout premier lieu un réseau de points, cette structure étant pleinement apparente lorsque l'on utilise une période complète du générateur. On remarquera que cet état de fait n'est pas nécessairement apparent lorsque l'on se limite à l'utilisation d'une faible fraction de la période. Mais en tout état de cause, il est préférable de choisir un multiplicateur tel que le maximum de la distance réticulaire, c'est à dire le maximum de la distance entre deux droites d'une même direction principale, soit le plus petit possible.
Cette recherche de minimax se programme en deux étapes. Un premier
programme (algorithme 5) parcourt, pour un multiplicateur
donné , l'ensemble des dénominateurs 
possibles et trouve le plus petit numérateur 
qui lui soit associé,
en utilisant la fonction 
qui donne le
reste dans 
, c'est à dire 
tel que 
.
On remarquera que, pour des raisons de vitesse d'exécution, le problème
a été replacé par la recherche du minimum de l'inverse du carré
de la distance réticulaire, que l'on initialise par la valeur 
clairement supérieure à la quantité cherchée. Le mécanisme de seuil
(ligne repérée par 
) est un heuristique qui sera utilisé par
le second programme. En utilisation indépendante, on prend 
.
Ainsi a-t-on 
correspondant
à la fraction 
.
Le second programme consiste à essayer toutes les valeurs possibles
de 
et à conserver la meilleure.
L'algorithme proposé parcourt l'ensemble des racines primitives de
en utilisant la fonction Maple 
qui est telle que 
donne la
première racine primitive modulo strictement supérieure à .
Plusieurs moyens peuvent être employés pour accélérer cette recherche.
Une première technique, spécifique au problème posé consiste à remarquer
que les quatre nombres , 
, 
et 
sont simultanément racines primitives et ont
alors les mêmes réseaux associés. Cette remarque fait gagner un
facteur 4.
Une deuxième technique, commune à toutes les recherches de minimax,
consiste à arrêter la recherche du maximum associé à une valeur donnée
de dès que l'on a obtenu une valeur supérieure au meilleur (c'est
à dire plus petit) maximum déjà trouvé pour les valeurs précédentes
de . On aboutit à l'algorithme 6.
En troisième lieu, une remarque de caractère heuristique permet de
limiter grandement l'intervalle des valeurs à explorer pour .
Si le réseau réalisant le minimax était exactement un réseau carré,
sa maille aurait exactement pour longueur 
.
Or pour tout 
la distance réticulaire associée à
la pente est supérieure à : le maximum
associé à un tel étant encore supérieure, il est inutile de considérer
les .
En appliquant l'algorithme précédent au nombre premier ,
on trouve que le minimum du maximum (minimax) est atteint pour 
,
conduisant aux directions 
et 
et aux distances 
et 
. A titre de comparaison, 
.
Sur la figure 1.8, on constate la très nette différence
d'aspect entre le réseau correspondant à un multiplicateur primitif
"quelconque" (ici 
, avec une distance réticulaire 
)
et le réseau correspondant au minimax.
L'algorithme de minimax décrit au paragraphe précédent ne résout pas
complètement le problème du choix du meilleur multiplicateur pour
un module donné. En effet, la complexité de cet algorithme est quadratique
puisqu'il se compose de deux boucles imbriquées, la boucle intérieure
utilisée pour rechercher la distance réticulaire maximale ayant une
complexité en 
. Or, pour des raisons qui ont été exposées
par ailleurs, l'utilisation de grands modules (de l'ordre du carré
du nombre d'instanciations voulues) est souhaitable. Il est donc intéressant
de disposer d'un algorithme plus efficace.
Considérons le réseau à points entiers formé par l'ensemble des points
qui s'écrivent 
avec 
.
Une façon d'obtenir ce réseau est de paver le plan par des reproductions
du carré 
contenant les points 
du 1.6.2.
Une autre façon d'obtenir ce réseau est de constater qu'il est formé
des combinaisons linéaires à coefficients entiers (relatifs) des vecteurs
et 
. L'objectif est donc de
trouver le vecteur de plus petit module de ce réseau, la distance
réticulaire associée étant l'inverse de ce module.
Cette recherche peut être conduite efficacement en modifiant légèrement
un algorithme bien connu, à savoir l'algorithme d'Euclide de recherche
du pgcd. Cet algorithme modifié, qui est dû à Gauss, est le suivant.
Notons 
le produit scalaire de deux
vecteurs, et partons d'un couple donné de vecteurs 
. Si 
est le plus long des deux, permutons les deux vecteurs. Autrement
dit, imposons que 
.
Si est négatif, remplaçons
par 
. Autrement dit, imposons que l'angle entre les vecteurs
soit aigu. Prenons alors la partie entière approchée du quotient de
par 
,
soit 
. Si 
, le vecteur 
est plus court que
le vecteur 
, et nous recommençons avec le couple 
.
Si 
, il n'existe aucun vecteur 
(avec 
)
qui soit plus court que et la base est formée des vecteurs
ayant la longueur minimale : est donc le vecteur réalisant le
minimum de longueur. Comme cette longueur est l'inverse de la distance
séparant les droites réticulaires associées à la direction conjuguée
(qui est donc celle de ), cet algorithme de Gauss constitue bien
une autre méthode de recherche du minimax voulu.
Or la complexité de l'algorithme d'Euclide est logarithmique : la
recherche du multiplicateur réalisant le minimax réticulaire
pour un module donné est donc un problème en 
.
Dans l'algorithme 7, un vecteur (soit 
)
est représenté par un record composé de la liste de ses coordonnées
(accessible par 
) et de son carré scalaire (accessible
par 
). Comme son nom l'indique, dotprod
calcule le produit scalaire de deux listes.
L'existence d'une structure réticulaire pour les points engendrés
par les instanciations successives d'un générateur congruentiel se
manifeste encore plus fortement pour les dimensions supérieures à
2. Dans ce qui suit, nous nous limiterons à 
, mais la généralisation
à 
est immédiate.
Considérons donc points 
situés dans le cube 
,
et formons un réseau en pavant l'espace par des cubes égaux à ce cube
principal. Une base de ce réseau est fournie par les vecteurs 
,
et 
, et il
suffit d'appliquer successivement l'algorithme précédent à toutes
les paires de vecteurs de la base jusqu'à ce que plus aucune réduction
ne soit possible.
Dans l'algorithme 8, les permutations sont
utilisées en ordre décroissant, c'est à dire 
pour de façon à privilégier les vecteurs de plus petite longueur.
Et le résultat est conditionné sous la forme d'une matrice contenant
les vecteurs de la base réduite. Ainsi,
Un raisonnement de géométrie élémentaire montre que la distance réticulaire
maximale s'obtient en considérant le volume de la maille élémentaire.
On a 
.
On en déduit que la distance réticulaire (entre les points fournis
par le générateur, c'est à dire les points de 
)
est donnée par 
.
Nous donnons ci-dessous les carrés des distances réticulaires 
correspondant aux trois faces de la maille élémentaire des multiplicateurs
possibles (
) pour le module 
.
On voit sur cet exemple (simpliste) que le choix du multiplicateur doit être effectué avec soin.
]
[
[
]
[
