Exponenciación binaria

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

La exponenciación binaria es un algoritmo utilizado para calcular de forma rápida grandes potencias enteras de un número x dado. También es conocido como potenciación por cuadrados o elevar al cuadrado y multiplicar. Implícitamente utiliza la expansión binaria del exponente. Es de uso bastante regular en aritmética modular. Este algoritmo es similar al de la duplicación en la multiplicación.

Versión recurrente[editar]

Fundamentos[editar]

El algoritmo está basado en las siguientes tres propiedades de la potencia:

(1)x^1=x\,

(2)x^{a+b}=x^a\,x^b

(3)x^{a\,b}=\left(x^a\right)^b

Usando a=n-1 y b=1 en la ecuación (2) se sigue que x^n=x^{n-1}\,x. Tomando \textstyle a=\frac n 2 y b = 2 en la ecuación (3) se obtiene que x^n=\left(x^\frac n 2\right)^2.

Algoritmo[editar]

El siguiente algoritmo recursivo calcula x^n para un natural n dado:

x^n=\begin{cases} x & \mbox{si }n=1 \\ \left(x^{\frac n 2}\right)^2 & \mbox{si }n\mbox{ es par} \\ x\times x^{n-1} & \mbox{si }n\mbox{ es impar} \end{cases}

Comparado con el método original de multiplicar x por sí mismo n-1 veces, este algoritmo sólo utiliza O(log n) multiplicaciones y acelera el cálculo de x^n tremendamente; más o menos de la misma forma que el algoritmo de la multiplicación acelera una multiplicación sobre el método más lento de realizar una suma repetida.

Aplicaciones[editar]

La misma idea permite el cálculo rápido de potencias muy grandes en módulo. Especialmente en criptografía, es útil calcular potencias en el anillo de los enteros módulo q.

La idea puede ser usada también para computar potencias de números enteros en un semigrupo, usando la regla

Potencia(x, -n) = (Potencia(x, n))-1.

Este método funciona en cualquier semigrupo, y es usado frecuentemente para calcular potencias de matrices.

Por ejemplo, la evaluación de

13789722341 (mod 2345)

tomaría mucho tiempo y espacio de almacenamiento si el método ingenuo es usado: calcular 13789722341 y tomar el residuio cuando es dividido por 2345. Incluso usando un método más efectivo tomará tiempo considerable: elevar 13789 al cuadrado , tomar el residuo cuando se divide por 2345, multiplicar el resultado por 13789, y así sucesivamente. Este proceso realizará 722340 multplicaciones modulares. Este algoritmo está basado en la observación que 13789722341 = 13789(137892)361170. Entonces, si se calcula 137892, el cálculo completo tomaría 361170 multiplicaciones modulares. Ésta es una ganacia en un factor de dos. Pero como el nuevo problema sigue siendo similar al anterior, se puede aplicar la observación nuevamente, reduciendo a la mitad la cantidad, aproximadamente.

La aplicación sucesiva de este algoritmo es equivalente a descomponer el exponente (convirtiéndolo a base binaria) en una secuencia de cuadrados y multiplicaciones: por ejemplo

x13 = x1101bin
= x(1*2^3 + 1*2^2 + 0*2^1 + 1*2^0)
= x1*2^3 * x1*2^2 * x0*2^1 * x1*2^0
= x2^3 * x2^2 * 1 * x2^0
= x8 * x4 * x1
= (x4)2 * (x2)2 * x
= (x4 * x2)2 * x
= ((x2)2 * x2)2 * x
= ((x2 * x)2)2 * x       → algoritmo necesita sólo 5 multiplicaciones en vez de 13 - 1 = 12

Algunos ejemplos más:

  • x10 = ((x2)2*x)2 porque 10 = (1,010)2 = 23+21, algoritmo necesita 4 multiplicaciones en vez de 9
  • x100 = (((((x2*x)2)2)2*x)2)2 porque 100 = (1,100,100)2 = 26+25+22, algoritmo necesita 8 multiplicaciones en vez de 99
  • x1,000 = ((((((((x2*x)2*x)2*x)2*x)2)2*x)2)2)2 porque 103 = (1,111,101,000)2, algoritmo necesita 14 multiplicaciones en vez de 999
  • x1,000,000 = ((((((((((((((((((x2*x)2*x)2*x)2)2*x)2)2)2)2)2*x)2)2)2*x)2)2)2)2)2)2 porque 106 = (11,110,100,001,001,000,000)2, algoritmo necesita 25 multiplicaciones
  • x1,000,000,000 = ((((((((((((((((((((((((((((x2*x)2*x)2)2*x)2*x)2*x)2)2)2*x)2*x)2)2*x)2)2*x)2*x)2)2)2*x)2)2*x)2)2)2)2)2)2)2)2)2 porque 109 = (111,011,100,110,101,100,101,000,000,000)2, algoritmo necesita 41 multiplicaciones

Véase también[editar]

Enlaces externos[editar]