Exponenciación binaria

La exponenciación binaria es un algoritmo utilizado para calcular de forma rápida grandes potencias enteras de un número  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

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

Usando  y  en la ecuación  se sigue que . Tomando  y  en la ecuación  se obtiene que .

Algoritmo 
El siguiente algoritmo recursivo calcula  para un natural  dado:

Comparado con el método original de multiplicar  por sí mismo  veces, este algoritmo sólo utiliza O(log n) multiplicaciones y acelera el cálculo de  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 
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 residuo 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. Esta es una ganancia 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 
Exponenciación modular

Enlaces externos 

Algoritmos de precisión arbitraria
Exponenciales