Exponentiation rapide

Exponentiation rapide

L'exponentiation rapide est un algorithme utilisé pour calculer rapidement, de grandes puissances entières. En anglais, cette méthode est aussi appelée square-and-multiply (« mettre au carré et multiplier »).

Sommaire

Écriture mathématique

La première façon de calculer une puissance np, est de multiplier n par lui-même p fois. Cependant, il existe des méthodes bien plus efficaces, où le nombre d'opérations nécessaires n'est plus de l'ordre de p mais de l'ordre de log(p), pour le logarithme en base 2.

Par exemple, si on écrit p=\sum_{i\leq d} a_i2^i pour a_i\in \{0,1\}, on constate que :

n^p=n^{a_0}(n^2)^{a_1}(n^{2^2})^{a_2}\dots (n^{2^d})^{a_d}

Il faut ainsi d opérations pour calculer tous les n^{2^i}, puis d opérations supplémentaires pour former le produit des (n^{2^i})^{a_i}. Le nombre d'opérations total est donc 2\cdot d, qui est bien de l'ordre du logarithme de p. Cette simple remarque algébrique conduit à l'algorithme présenté dans la section suivante.

Algorithme

Soit n un entier strictement supérieur à 1, supposons que l'on sache calculer pour tout x appartenant à l'ensemble des réels, toutes les puissances xk de x, pour tout k, tel que 1 \le k < n .

  • Si n est pair alors xn = (x2)n / 2. Il suffit alors de calculer yn / 2 avec y = x2.
  • Si n est impair et n>1, alors x^n = x\cdot(x^2)^{(n-1)/2}. Il suffit de calculer y(n − 1) / 2 avec y = x2 et de multiplier par x le résultat.

Cette remarque nous amène à l'algorithme récursif suivant qui calcule xn pour un entier strictement positif n:

\mbox{puissance}(x,\,n)=\left\{ \begin{matrix} x, & \mbox{si }n\mbox{ = 1} \\ \mbox{puissance}(x^2,\,n/2), & \mbox{si }n\mbox{ est pair} \\ x\times\mbox{puissance}(x^2,\,(n-1)/2), & \mbox{si }n >\mbox{2 est impair} \\ \end{matrix}\right.

En comparant à la méthode ordinaire qui consiste à multiplier x par lui-même n-1 fois, cet algorithme nécessite de l'ordre de O(lg n) multiplications et ainsi accélère le calcul de xn de façon spectaculaire pour les grands entiers.

La méthode fonctionne dans tout semi-groupe et est souvent utilisée pour calculer des puissances de matrices, et particulièrement en cryptographie, mais aussi pour calculer les puissances dans un anneau d'entiers modulo q. Elle peut être aussi utilisée pour calculer des puissances d'un élément dans un groupe, en utilisant pour les puissances négatives la règle : puissance(x, -n) = (puissance(x, n))-1.

Voir aussi

Liens externes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Exponentiation rapide de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Exponentiation Rapide — L exponentiation rapide est un algorithme utilisé pour calculer rapidement, de grandes puissances entières. En anglais, cette méthode est aussi appelée square and multiply (« mettre au carré et multiplier »). Sommaire 1 Écriture… …   Wikipédia en Français

  • Exponentiation Modulaire — En mathématiques, plus précisément en arithmétique modulaire, l exponentiation modulaire est un type d élévation à la puissance (exponentiation) exécutée modulo un entier. Elle est particulièrement utilisée en informatique, spécialement dans le… …   Wikipédia en Français

  • Exponentiation modulaire — En mathématiques, plus précisément en arithmétique modulaire, l exponentiation modulaire est un type d élévation à la puissance (exponentiation) exécutée modulo un entier. Elle est particulièrement utilisée en informatique, spécialement dans le… …   Wikipédia en Français

  • Exponentiation — Notation du résultat de l exponentiation de base a et d exposant b. En mathématiques, l’exponentiation est une opération binaire non commutative qui étend la notion de puissance en algèbre. Elle se note en plaçant l un des opérandes en exposant… …   Wikipédia en Français

  • Rapide — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « Rapide », sur le Wiktionnaire (dictionnaire universel) Rapide est un adjectif qui indique une vitesse… …   Wikipédia en Français

  • Rapides — Rapide Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Formule BBP — La formule BBP (ou Bailey Borwein Plouffe) permet de calculer le nème chiffre après la virgule de π en base 2 (ou 16) sans avoir à en calculer les précédents, et en utilisant très peu de mémoire et de temps. Elle a été obtenue le… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Exposant (mathématiques) — Pour les articles homonymes, voir Exposant. En mathématiques, l opération puissance consiste à multiplier un nombre a par lui même plusieurs fois de suite. Le nombre de facteurs intervenant dans cette opération est noté à la suite du nombre a en… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”