2.7 Générateurs arithmétiques

2.7.1 Générateur uniforme de nombres factorisés

Terminons ce chapitre consacré à l'examen de générateurs variés par l'examen du problème suivant : nous nous proposons de construire, pour un donné, un générateur uniforme d'entiers factorisés appartenant à l'intervalle . Pour de petites valeurs de , il suffit d'utiliser un algorithme semblable à l'algorithme 11 pour engendrer les nombres en question, puis d'en chercher la décomposition en un produit de facteurs premiers en utilisant, par exemple, la routine Maple .

Mais une telle méthode devient rapidement impratiquable lorsque la taille de  augmente. En effet, les meilleurs algorithmes de factorisation ont une complexité en , conduisant à une explosion du temps de calcul comme le montre le tableau :

Il est donc souhaitable de selectionner les nombres voulus au moyen d'un processus qui donne en même temps leur factorisation. L'algorithme 37 (Bach, 1988) résoud la question de la façon suivante. On commence par sélectionner un facteur dans l'intervalle , selon une certaine loi, implémentée dans l'algorithme 40 (). Puis on sélectionne uniformément en utilisant récursivement l'algorithme et enfin on accepte ou on rejette le nombre obtenu selon un certain processus, de façon à ce que la loi de probabilité des nombres sélectionnés soit effectivement la loi uniforme.

Le coeur de l'algorithme est donc le processus de sélection des facteurs qui interviennent dans la décomposition des engendrés. Ce processus sera décrit au § 2.5.1. Mais avant il convient de rappeler quel est le fonctionnement des algorithmes permettant de déterminer rapidement, c'est à dire en un temps logarithmique, si un nombre est premier ou est une puissance d'un nombre premier (et cela indépendamment du fait que la factorisation reste un problème difficile pour les nombres qui ne sont pas de cette forme).

2.7.2 Premiers et puissances de premiers

Les différents algorithmes concernant la factorisabilité d'un nombre peuvent se ranger en deux catégories : les tests de composition et les tests de primalité. Un test de composition a pour objectif de détecter presque toujours si un nombre est composé, en fournissant alors une preuve de l'existence d'une décomposition (sans nécessairement en fournir une de façon explicite). Lorsqu'un tel test échoue, on a donc une forte probabilité pour que le nombre soit premier. Par contre, un test de primalité a comme objectif de déterminer avec certitude si un nombre est premier ou non : il s'agit donc d'obtenir une preuve de l'impossibilité d'une décomposition, et non pas une simple présomption.

L'intérêt des tests de composition vient de ce qu'ils sont nettement plus rapides que les tests de primalité. On dispose donc de deux stratégies : ou bien se contenter des tests de composition (en réglant le seuil de probabilité selon la marge d'erreur tolérable), ou bien utiliser systématiquement un test de primalité lorsque le test de composition a fait apparaître une forte présomption d'une telle primalité.

Pour illustrer ce qui vient d'être dit, considérons la liste des nombres premiers . Un nombre qui n'est pas dans cette liste et qui est divisible par un nombre de la liste est un nombre composé. Un pareil test ne nécessite pas divisions, mais seulement le calcul du pgcd de et du produit des membres de la liste, ce qui est plus rapide.

Pour les nombres , ce test est en fait un test de primalité, car est premier s'il n'a pas de diviseur premier . Pour les autres nombres, ce test est un test de composition, donnant de réponses positives. Il constitue les lignes 2 à 10 de l'algorithme 38.

Pour les de nombres restants, on utilise un algorithme dont le principe est le suivant : pour tout , on a (théorème de Fermat) la relation . On génère donc plusieurs dans cet intervalle et l'on rejette comme non-premier si l'un des est différent de . Il va de soi que les puissances modulo doivent être calculées par un algorithme spécial, et non pas par le calcul effectif de , suivi d'une division !

On peut malheureusement trouver des nombres composés qui ne sont pas détectés par ce test (nombres de Carmichel). Il convient donc de renforcer ce test de la façon suivante : on écrit avec et impair. L'un des nombres , , ..., doit valoir , et si ce n'est pas vrai dès le début, la première apparition du doit être immédiatement précédée par la valeur : tel est le test de Rabin-Miller (algorithme 38). En voici deux exemples :

On peut montrer que, pour composé, la proportion de qui n'entrainent pas le rejet de est faible (et cela d'autant plus que les petits nombres ont été éliminés par le crible d'Eratosthène) : de petites valeurs du facteur de répétition () permettent d'assurer une probabilité tout à fait satisfaisante.

Voyons maintenant comment détecter si un nombre est ou non une puissance d'un nombre premier (algorithme 39). On commence (lignes 2 à 8) par un crible fondé sur une tabulation préalable des , pour inférieur au plus grand envisagé et . S'il s'avère que faisait partie des de nombres qui passent à travers le crible, choisissons un nombre . Si avec premier, on a , et par théorème de Fermat, divise . On calcule donc le pgcd de et de (appelé en Maple, pour le distinguer du pgcd des polynômes). Si , il est clair que n'est pas de la forme cherchée (l. 13). Si est premier, il reste à vérifier que est bien une puissance de (l. 32 à 39).

Dans le cas où est un nombre composé, on recommence les tests précédents avec une nouvelle valeur de , et surtout en partant de , plutôt que du nombre originel. Dans le cas le plus fréquent, on assiste à une réduction rapide du nombre . Il reste à traiter le cas où est ou devient un nombre de Carmichel, et donc ne diminue plus lorsque l'on répète l'algorithme. La procédure utilisée l. 20 à 31 requiert des calculs de fonctions transcendantes, mais cela ne dégrade pas notablement les performances de l'algorithme, car il s'agit d'un cas peu fréquent.

2.7.3 L'algorithme de Bach

Revenons maintenant à l'algorithme de Bach. Commençons par remarquer que, pour des entiers avec , le nombre d'entiers contenus dans l'intervalle allant de (exclus) à (inclus) est exactement . Supposons que nous sachions sélectionner dans l'intervalle selon la loi . Rappelons que nous utilisons le signe (propto) et non le signe pour indiquer que les quantités données sont non pas égales, mais proportionnelles aux probabilités effectives (normaliser en divisant par la masse totale de la distribution ne sert pas à grand chose, à part compliquer les écritures).

Nous avons donc puisque le facteur sera (récurrence) choisi uniformément dans l'intervalle . On a donc et de là . Telle est donc la loi de probabilité des nombres obtenus à la ligne 6 de l'algorithme 37. Pour se ramener à la loi uniforme, il faut donc utiliser une méthode de tir : le nombre obtenu sera rejeté si le verdict fourni par une variable aléatoire uniforme est supérieur à . On remarquera que le taux de rejet est tres faible puisqu'il est visiblement inférieur à .

Il reste à examiner comment sélectionner les avec la bonne probabilité. En remarquant que est inférieur à , nous pouvons utiliser le processus de sélection suivant. Commençons par choisir uniformément un entier dans l'intervalle avec défini par . Posons alors , choisissons uniformément un entier dans et recommençons jusqu'à obtenir un inférieur ou égale à qui soit bien de la forme (ce que permet précisément de faire l'algorithme 39). La probabilité de sélection d'une valeur particulière de reste proportionnelle à .

Nous passons alors ces nombres à travers un processus de sélection : une valeur de sera rejetée si le verdict fourni par une variable aléatoire uniforme est supérieur au ratio des chances, c'est à dire ici à . On obtient l'algorithme 40.

Il reste à examiner la praticabilité de cet algorithme, c'est à dire la valeur moyenne du nombre d'essais qui seront nécessaires avant que puisse fournir une valeur de . La figure 2.14 illustre ce problème pour (valeur permettant d'avoir une figure lisible, mais ridiculement faible eu égard au domaine d'utilisation de l'algorithme). En gris, nous avons les chances de sélection d'un nombre sur le seul critère qu'il soit inférieur à , tandis qu'en noir nous avons les chances pour qu'un nombre soit choisi comme valeur de . Le rapport des deux surfaces est égal au facteur de tir c'est à dire à l'espérance du nombre d'essais nécessaires pour obtenir un succès.

Figure 2.14: Rapport des chances lors de la s'election d'un .

On a d'une part et d'autre part :

puisque la première somme et que la deuxième est de limite 1. On voit donc que , c'est à dire le nombre moyen d'essais nécessaire pour un succès, est majoré par une quantité équivalente à .

Un examen attentif du calcul précédent montre que cette quantité est en fait une bonne approximation de l'espérance du nombre d'essais. En effet, les nombres qui sont des puissances de premiers (avec ) sont rares en comparaison des nombres premiers eux mêmes. A titre d'exemple, nous avons explicitement calculé pour , et obtenu soit . A titre de comparaison, on a : .

Ces valeurs peuvent être retrouvées expérimentalement. La figure 2.15 rend compte de la répartition du nombre d'essais qui ont été nécessaires pour obtenir une suite de instanciations de . On constate que la courbe expérimentale correspond bien à une loi géométrique, et l'on trouve et ., tandis que le test du donne un score de .

Figure 2.15: Répartition du nombre déssais avant succès.