Objectifs

Étant donné un exposant $e$, on souhaite calculer le plus efficacement possible $x^e, \forall x$, c'est-à-dire en minimisant le nombre de multiplications, pour gagner en temps d'exécution.

En effet, pour calculer $X^8$, on peut :

• Calculer $X \times X \times ... \times X$, ce qui fait 7 multiplications. La liste des exposants calculés est : 1, 2, 3, 4, 5, 6, 7, 8.
• Calculer :
  • $Y = X \times X$, ce qui correspond à $X^2$,
  • puis $Z = Y \times Y$, ce qui correspond à $X^4$,
  • enfin $T = Z \times Z$, ce qui donne le résultat.

L'écart se creuse très rapidement, entre la méthode naïve et les méthodes plus évoluées. Ainsi, pour calculer $X^{1024}, il faut

• 1023 multiplications, pour la méthode naïve,
• 10 multiplications pour la méthode dite exponentiation rapide.

Quand on sait que pour chiffrer, dans la méthode RSA, il faut élever notre message (un nombre) à la puissance "un grand nombre premier" (comprendre : un exposant de plusieurs centaines de chiffres), on comprend l'intérêt de racourcir le temps de calcul d'une puissance.

L'exponentiation rapide

Présentation

L'exponentiation rapide est une technique classique, utilisée en pratique, pour obtenir la puissance d'un nombre donné.

Cette exponentiation rapide itère, pour le calcul de $X^e$, les opérations suivantes :

• l'élévation au carré,
• la multiplication par $X$,

dans un ordre dépendant de l'écriture en base 2 de $e$.

L'algorithme

Plus précisément...

• On écrit $e$ en base 2,
• On enlève le premier 1 de cette écriture,
• On remplace alors, dans cette écriture,
  • les 0 par des $S$,
  • les 1 par des $SX$,

• On part du nombre $X$.
  • si la première lettre est $S$, on élève au carré (square)
  • sinon, on multiplie par $X$
• On recommence avec les lettres suivantes, jusqu'à la fin du mot.

Exemples

Premier exemple

15 s'écrit 1111 en base 2.

L'algorithme précédent aboutit au mot $SXSXSX$. Les étapes du calcul sont alors :

Le dernier résultat (res) contient donc la puissance recherchée, en seulement 6 opérations (contre 14, dans la méthode naïve).

La liste d'exposants est ici : 1, 2, 3, 6, 7, 14, 15.

Deuxième exemple

19 s'écrit 10011 en base 2, ce qui fournit le mot $SSSXSX$.

Après travail, la liste d'exposants est ici : 1, 2, 4, 8, 9, 18, 19.

On pourrait donc calculer $X^{19}$ en 6 multiplications.

Travaux pratiques

1. Réalisez une fonction qui réalise l'exponentiation rapide. On renverra un couple, comprenant :
   • Le résultat de l'exponentiation.
   • La liste des exposants.
2. Réalisez un graphe dans lequel on trouvera $n$ en abscisse, et le nombre de multiplications pour obtenir $X^n$ en ordonnées ($X$ est quelconque). On y représentera l'exponentiation naïve, et l'exponentiation rapide.
3. Faire un autre graphe, qui contiendra en ordonnée le temps d'exécution.

La meilleure exponentiation ?

Seulement, l'exponentiation rapide ne donne pas la méthode la plus rapide systématiquement. Par exemple, pour calculer $X^{15}$, on aurait pu procéder ainsi :

Soit 5 multiplications pour $X^{15}$, au lieu de 6 par la méthode dite exponentiation rapide. Une meilleure liste d'exposants pour $X^{15}$ est donc : 1, 2, 3, 6, 9, 15.

Vers les chaînes d'addition

Etude de l'exponentiation rapide

On rappelle que, dans la méthode d'exponentiation rapide de $X^e$, le nouveau terme est égal au terme précédent multiplié :

• par lui-même,
• ou par le premier terme.

On a donc, du point de vue des exposants :

$1 = a_1 < a_2 < ... < a_n = e$

avec

• $a_{i} = a_{i-1}+a_{i-1}$, dans le cas de l'élévation au carré,
• $a_i = a_{i-1}+a_1$, dans le cas d'une multiplication par $X$.

Par exemple, pour $X^{15}$ par exponentiation rapide, les exposants 1, 2, 3, 6, 7, 14, 15 sont bien de cette forme (pour passer d'un terme au successeur, soit on double, soit on rajoute 1).

Critique

On impose, par cette méthode, trop de restrictions aux listes d'exposants. Il nous suffit en effet d'avoir une liste d'exposants :

• partant de 1,
• arrivant à $e$,
• telle que tout nouvel exposant soit la somme d'exposants précédemment obtenus.

On veut que cette liste soit la plus petite possible, et évidemment qu'elle soit strictement croissante.

Faire intervenir le dernier exposant calculé pour obtenir le suivant semble alors légitime, vu que l'on souhaite atteindre $e$ rapidement.

On cherche donc des listes d'exposants de la forme

$1 = a_1 < a_2 < ... < a_n = e$

où

$a_{i+1} = a_i + a_j, j \leqslant i$

Par contre, imposer $j=i$ ou $j=1$ est une restriction inutile. La lever conduit à définir de nouveaux algorithmes d'exponentiation rapide, tels que les chaînes d'addition.

Premières idées de nouveaux algorithmes

Préliminaires

Faire une fonction qui teste si une liste $L$ d'exposants est correcte : chaque terme $a_{i+1}$ de la suite doit pouvoir s'écrire comme la somme de son prédécesseur, et d'un second terme apparu précédemment dans la liste. En d'autres termes, la fonction doit vérifier si l'on a

$\forall i \leqslant len(L)-1, \exists j \leqslant i-1, a_{i+1} = a_i + a_j, j \leqslant i$

Créez une fonction qui calcule $X^e$ à partir d'une liste d'exposants fournis en argument. On stockera, dans un dictionnaire, les termes intermédiaires obtenus avec leurs exposants associés : on en aura besoin pour les termes à venir.

Méthode exhaustive

La première idée qui peut nous venir à l'esprit, pour calculer $X^e$, est de tester toutes les possibilités. On peut, à ce niveau, choisir un premier angle d'attaque :

1. Dresser la liste de toutes les suites strictement croissantes de 1 à $e$.
2. Exclure, de cette liste, les suites qui ne sont pas des listes d'exposants de la forme $a_{i+1} = a_i + a_j, j \leqslant i$.
3. Retourner la liste de plus petite taille.

Ou procéder en s'inspirant d'une technique de type backtracking :

1. Partir de $a_0 = 1$.
2. Tant que $a_{i} \leqslant e$, faire $a_{i+1} = a_{i} + a_{i}$.
   • Si le dernier terme apparu est $e$, on a gagné, et l'on a fait à chaque fois le plus grand saut possible.
   • Si on dépasse $e$ sans l'atteindre, alors on prend le dernier $a_{i+1} = a_{i} + a_{i}$ calculé, que l'on remplace par $a_{i+1} = a_{i} + a_{i-1}$. Si on obtient $e$, c'est gagné, sinon on remplace $a_{i-1}$ par $a_{i-2}$.
   • Ce retour en arrière est effectué tant que l'on peut, et tant que l'on ne trouve pas exactement $e$.
   • Une fois toutes les possibilités testées avec le dernier des $a_i$, on passe (en cas d'échec), aux possibilités avec l'avant dernier des $a_i$, puis avec l'antépénultième, etc.

Utilisation du hasard

Une métaheuristique consiste à utiliser le hasard pour la génération de nouveaux algorithmes (Monte-Carlo, etc.) Une telle méthode de conception peut s'avérer fructueuse ; on va donc chercher à réaliser un algorithme d'exponentiation rapide basée sur l'utilisation du hasard.

Réalisons une fonction de génération aléatoire de la liste d'exposants. On trouvera en argument (de cette fonction) l'exposant $e$ à atteindre. On pourra tester les deux voies suivantes :

• Tirer aléatoirement une suite croissante d'exposants de 1 à $n$, et vérifier, avec la fonction de la section précédente, si cette suite est bien de la forme $a_{i+1} = a_i + a_j, j \leqslant i$.
• Construire une liste d'exposants $a_i$, tels quel :
  • Le premier terme $a_0$ est égal à 1,
  • $a_{i+1} = a_i + a_j$, où $j$ est un entier positif, inférieur à $i$, et choisi aléatoirement dans cet intervalle.

Une fois ces fonctions réalisées... Que pensez-vous de cette métaheuristique dans le cas qui nous intéresse ici ? Est-elle efficace ?

Vérifier expérimentalement que cette méthode n'est pas idéale :

1. Complétez le premier graphe, en ajoutant la taille des listes d'exposants obtenus.
2. Complétez le deuxième graphe, en mettant en ordonnée le temps d'exécution.

Conclusion ? Il faut chercher une methode plus efficace...

Les chaînes d'addition

Définition

Une chaîne d'addition (de Brauer) pour un exposant entier $e$ est une liste d'entiers $1 = a_1 < a_2 < ... < a_r = e$ où $a_i = a_{i-1} + a_k, k<i$

Exemples

Une chaîne pour l'exposant 15

Une chaîne d'addition pour l'exposant entier 15 peut être

• $a_1 = 1$,
• $a_2 = a_1 + a_1 = 2$,
• $a_3 = a_2 + a_2 = 4$,
• $a_4 = a_3 + a_3 = 8$,
• $a_5 = a_4 + a_3 = 12$,
• $a_6 = a_5 + a_2 = 14$,
• $a_7 = a_6 + a_1 = 15$.

D'où la chaîne : 1, 2, 4, 8, 12, 14, 15.

L'exponentiation rapide

Les listes d'entiers obtenues par la méthode d'exponentiation rapide sont, on l'a vu, de la forme : $1 = a_1 < a_2 < ... < a_r = e$ avec $a_i = a_{i-1} + a_k, k \in {1;i-1}$.

C'est donc un cas particulier de chaînes d'addition.

Résultats

Cas de l'exponentiation rapide

Dans le cas de l'exponentiation rapide, la longueur $l_n$ de la chaîne pour l'exposant $n$, se calcule en fonction du nombre $\nu_n$ de 1 dans l'écriture binaire de $n$, par la formule :

$l_n = \lfloor log_2(n) \rfloor + \nu_n - 1$

Par exemple, $15 = 1111_2$, donc $\nu_{15} = 4$, et $l_{15} = \lfloor log_2(15) \rfloor + 4 - 1 = 3+4-1 = 6$

De même, pour $19 = 10011_2$, $l_{19} = 4+3-1 = 6$.

On a vu que l'exponentiation rapide ne donne pas toujours la meilleure chaîne d'addition. Plus précisément, les meilleurs chaînes d'addition sont, dans le cas de l'exponentiation rapide, obtenues pour les entiers de la forme $2^n$, et les pires dans le cas $2^{n+1}-1$.

En effet, pour $n$ entier dans [$2^k, 2^{k+1} -1$], $log_2(n) = k$ reste fixe. Seul change donc, dans $l_n$, le nombre $\nu_n$ de 1, qui vaut 1 pour $2^n = 1000...0_2$, et $n+1$ pour $2^{n+1}-1 = 111...1_2$.

De manière plus générale, trouver la plus courte chaîne d'addition est un problème compliqué.

Le cas général

Les résultats restent à établir, quant à la longueur d'une chaîne minimale pour l'entier $n$. Par exemple, une conjecture de Sholz-Brauer, énoncée en 1937, et qui affirme que $l_{2^n-1} \leqslant n-1+l_n$, n'a toujours pas été démontrée.

Un algorithme génétique

Dans la pratique, puisqu'aucun résultat général ne peut fournir systématiquement la meilleure chaîne, on peut utiliser des techniques d'optimisation pour s'approcher des chaînes minimales. Nous donnons, dans ce qui suit, un exemple d'un tel algorithme...

Préliminaire

On suppose posséder une fonction générant aléatoirement une chaîne d'addition de $x$ à $e$. Par exemple, le pseudo-code suivant peut convenir :

  trouve = faux
  tant que trouve = faux
      L = [1]
      n = 1
      tant que L[n] < e
          choisir k dans [1, n]
          ajouter L[n] + L[k] à la liste L
          incrémenter n
      si L[n] = e, alors trouve = vrai
  retourner L

(D'autres algorithmes peuvent être trouvés.)

L'algorithme génétique

Métaheuristique

L'algorithme génétique est issu d'une analogie des processus d'évolution de Darwin.

On sélectionne aléatoirement $n$ individus, puis on boucle :

• tri en fonction d'un critère,
• mutation des $n-c$ moins bons individus,

jusqu'à obtenir un résultat satisfaisant.

L'algorithme

Une des applications possibles de cette métaheuristique à notre problème est :

1. Construire une population de $N$ chaînes d'addition différentes pour $e$.
2. Les trier suivant leur longueur.
3. Constituer une nouvelle population de $N$ chaînes d'addition pour $e$, constituée :
   • des meilleures chaînes de la population précédente,
   • de mutation de ces meilleures chaînes,
   • de nouvelles chaînes d'addition.

La mutation

La mutation d'une chaîne $1 = a_1 < a_2 < a_3 < ... < a_n = e$ consiste à :

• garder ses termes jusqu'au rang $a_{k-1}$
• remplacer $(a_k, ..., a_n)$ par $(a_k', ..., a_p')$, nouvelle chaîne, issue de la fonction ci-dessus, allant de $a_k$ à $e$ en un nombre éventuellement différent d'étapes.

Travaux pratiques

Programmez la recherche de chaînes d'addition par algorithme génétique.

On regardera l'évolution de la taille de la plus courte chaîne d'addition en fonction de différents paramètres de cet algorithme :

• le temps d'exécution,
• le nombre de chaînes que l'on mute, qui peut varier en fonction du temps,
• le nombre de nouvelles chaînes à apporter,
• le lieu de la mutation, qui peut être aléatoire, varier au cours du temps, ...

Une exploration des résultats, sous forme de graphes et de synthèse, est souhaitée. Une comparaison avec la technique d'exponentiation rapide est la bienvenue.

Enfin, cet algorithme peut être amélioré de différentes manières. Le faire est le bienvenu.