1.2 Le test de Pollard (mesure de la période)

1.2.1 Algorithme du centre du carré (Neumann)

L'idée même d'utiliser une fonction déterministe pour engendrer une suite de nombres pseudo-aléatoires est due à J.v.Neumann (1946), et l'une des toutes premières méthodes examinées a été l'algorithme du "centre du carré". Partant d'un entier modulo , nous l'élevons au carré puis le réduisons à un nombre modulo en nous débarrassant des chiffres initiaux et terminaux. En considérant les nombres qui s'écrivent avec au plus chiffres dans une base fixée, c'est à dire en prenant , on obtient l'algorithme 1.

Si est adapté à la taille des mots machine, le calcul des quotients entiers (^1.1) et des restes euclidiens () s'obtient sans recours à des opérations de division : il suffit de calculer le produit en double précision et de décaler le résultat pour le ramener dans l'accumulateur. De même, le passage de c'est à dire d'un entier à un nombre peut se faire par un simple transtypage, et ne requiert donc pas une division effective en virgule flottante (). Ce générateur a donc la qualité d'être très rapide.

Mais un examen systématique des séquences obtenues conduit à un rejet absolu. En effet la longueur totale des suites obtenues est très courte, et la partie strictement périodique est encore plus courte. La figure 1.1 montre que pour , la plus longue séquence se compose de 36 termes, tandis que les parties strictement périodiques sont de longueur 1 ou 2 : les cycles attracteurs du processus étant et .

Figure 1.1: Les longueurs pour .

[Longueur totale][Longueur du cycle]

Pour , la situation n'est pas vraiment meilleure (figure 1.2). La plus grande séquence avant répétition que l'on puisse obtenir ne compte que 352 nombres. Et dans plus de deux cas sur trois, la longueur du cycle auquel le processus aboutit est inférieure ou égale à 7 !

Figure 1.2: Les longueurs pour .

[Longueur totale][Longueur du cycle]

L'examen (figure 1.3) du cas , montre que la très faible longueur des chaînes engendrées n'est pas un phénomène particulier à la base 2. Une des causes de ce mauvais comportement est la suivante. Supposons qu'une valeur vienne à tomber en dessous de . A l'étape suivante, nous obtenons : d'où et la suite débouche sur un cycle formé du seul nombre 0.

Figure 1.3: Les longueurs pour .

[Longueur totale][Longueur du cycle]

1.2.2 Générateurs congruentiels

Cette déconvenue "inattendue" causée par les générateurs quadratiques explique la généralisation des générateurs congruentiels, c'est à dire définis par le choix d'une valeur entière initiale (le "random seed") et par la récurrence , les nombres fournis par le générateur étant les quotients . On peut en effet calculer aisément la période d'un tel générateur.

Examinons les cas réellement utiles : et premier. L'intérêt du premier cas est évident car l'arithmétique modulaire se simplifie considérablement lorsque est égal à la taille du "mot machine" ou est une puissance de celui-ci. En pareil cas, le choix et racine primitive du groupe , qui comporte éléments, conduit à une période égale à (le choix du même et de ne donne que des nombres impairs, et conduit à une période divisée par 2). Prenant comme exemple (simpliste) et , on obtient :

Lorsque l'on choisit un module premier, le choix de est indifférent : on peut donc le prendre nul. La période maximale est assurée lorsque est une racine primitive du groupe qui comporte maintenant éléments. Cette période vaut alors . Prenant comme exemple (simpliste) et , on obtient :

Un exemple "réel" de ce procédé est le générateur lgm, proposé par Lewis, Goodman et Miller [73] en 1969. On part d'un nombre et l'on calcule ses successeurs par la récurrence , le nombre ayant été choisi (entre autres) pour être premier et le nombre ayant été choisi (entre autres) pour être une racine primitive de . On obtient l'algorithme 2 dans lequel contient les instanciations successives de l'entier .

1.2.3 L'algorithme de Pollard

Lorsque l'on est en présence d'un générateur non congruentiel, la détermination de sa période est un problème moins simple. Un algorithme immédiat à programmer consiste à utiliser une liste pour stocker au fur et à mesure les valeurs obtenues et à comparer chaque nouvelle valeur avec les précédentes. Comme la recherche dans une liste non triée est un processus proportionnel à la longueur de la liste, cet algorithme est en pour la place et en pour la durée...

Une amélioration consiste à utiliser une structure de données permettant des recherches et des insertions en temps logarithmique, permettant de passer à pour la durée. Mais en fait, il existe un algorithme, dû à Pollard, qui détermine la période d'une fonction avec une complexité en pour la durée et en pour la place !

Cet algorithme consiste à utiliser deux processus indépendants, l'un donnant les itérations et l'autre les itérations , avec initialement . On peut donc décrire le processus par deux cyclistes partant du même endroit, le second ayant une vitesse exactement double de la vitesse du premier. Leur trajet a la forme d'un : d'abord une partie rectiligne, puis une boucle. Il y aura forcément un moment où le second doublera le premier, qui aura alors parcouru la partie rectiligne et une partie de la boucle. La seconde fois où le second cycliste doublera le premier, ils auront parcouru un nombre entier de tours, à savoir un tour pour le premier, et deux pour le second : l'intervalle de temps séparant les deux événements permet donc une mesure de la longueur de la boucle (algorithme 3).

Par exemple, donne , montrant que ne serait pas un choix optimal du multiplicateur (en dehors du fait que est un choix évidemment défectueux du module). On peut ainsi obtenir la période associée à chacun des multiplicateurs possibles , conduisant à la table :

Il ne faudrait pas en conclure que la recherche d'un bon multiplicateur congruentiel requiert une durée en . Il existe en effet des algorithmes logarithmiques pour déterminer si un nombre est ou non une racine primitive d'un nombre premier donné à partir d'une factorisation de .

1.2.4 Période du générateur de Fibonnaci

Examinons maintenant le générateur défini par c'est à dire par une récurrence à la Fibonacci modulo . On obtient l'algorithme 4, qui significativement plus rapide qu'un générateur congruentiel, puisqu'il ne met pas en oeuvre de multiplications. Dans ce paragraphe, nous allons nous intéresser à la période de ce générateur, le reste de ses propriétés seront examinées plus en détail section 1.7.1.

Appelons la période de la suite modulo obtenue à partir de la condition initiale . Nous allons d'une part montrer que cette période vérifie et d'autre part indiquer comment choisir le module pour que cette période soit au moins égale à pour tout choix raisonnable de la condition initiale, c'est à dire tel que les trois nombres soient premiers dans leur ensemble.

Pour une condition initiale donnée , cette période est une fonction multiplicative, c'est à dire que implique

Il suffit donc de déterminer les pour , c'est à dire pour les nombres premiers et leurs puissances [7].

L'équation caractéristique de la récurrence est , dont le discriminant est . Il convient donc de distinguer le cas spécial , le cas où est un carré modulo (premier), imposant et le cas où n'est pas un carré modulo , soit ou .

Pour et , un examen direct donne . Ce résultat se retrouve en remarquant que l'équation caractéristique admet alors pour racine double, conduisant à . Comme le premier facteur est de période (lorsque ) et le second de période (Fermat), on retrouve effectivement la valeur expérimentale. Au passage, on remarque la sensibilité de la période aux conditions initiales : aurait donné une période .

Pour les premiers de la forme , le nombre est un carré modulo et l'équation caractéristique admet deux racines distinctes , conduisant à . Le théorème de Fermat montre alors que est un diviseur de . A titre d'exemple, pour , on obtient (par examen direct, ou en utilisant l'algorithme de Pollard) : et .

Pour les autres nombres premiers, soit ou , le nombre n'est un carré modulo et le polynôme est irréductible sur le corps . L'anneau quotient est donc un corps, à savoir le seul et unique corps ayant éléments, qui se note usuellement . Sur ce corps, l'équation caractéristique admet deux racines distinctes , et l'on obtient à nouveau . Dans cette écriture, et sont des quantités conjuguées, conduisant à un entier naturel pour valeur de .

Le théorème de Fermat montre alors que est un diviseur de . Et l'on a effectivement . Pour les premiers , il convient de remarquer que (formule de conjugaison de Frobénius) et que (produit des racines). On a donc et la période est donc un diviseur de . A titre d'exemple, pour , on obtient : et .

Passons maintenant aux pour , premier. Pour alléger les notations, nous écrirons . Posant , on a d'où . On a donc . Si nous supposons que n'est pas divisible par , on a . Nous allons montrer que l'on a alors .

Pour , on a . Pour impair, on a : . Nous avons donc multiple strict de et diviseur de : on en conclut . Ce résultat se généralise aux puissances supérieures. Posant () on obtient , conduisant à et donc à .

On a donc , , () ou (). On en déduit , cette valeur étant atteinte pour le choix et (par exemple) la condition initiale .

Le choix du module est particulièrement avantageux, à la fois parce que l'arithmétique modulo est aisément implémentable en machine et parce que la période est indépendante de la condition initiale du moment que celle-ci contient au moins un nombre impair.

Par contre, les modules , qui donnent toujours une période , et les modules , qui donnent une période au moins égale à se prêtent moins bien au calcul, tandis que certains modules premiers conduisent à de mauvaises périodes pour certaines conditions initiales : donne une période égale à !