Exponenciación binaria

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

Fundamentos

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

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

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

13789⁷²²³⁴¹ (mod 2345)

tomaría mucho tiempo y espacio de almacenamiento si el método ingenuo es usado: calcular 13789⁷²²³⁴¹ 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 13789⁷²²³⁴¹ = 13789(13789²)³⁶¹¹⁷⁰. Entonces, si se calcula 13789², 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

x¹³ = x^1101_bin

= x^{(1*2^3 + 1*2^2 + 0*2^1 + 1*2^0)}

= x^{1*2^3} * x^{1*2^2} * x^{0*2^1} * x^{1*2^0}

= x^{2^3} * x^{2^2} * 1 * x^{2^0}

= x⁸ * x⁴ * x¹

= (x⁴)² * (x²)² * x

= (x⁴ * x²)² * x

= ((x²)² * x²)² * x

= ((x² * x)²)² * x       → algoritmo necesita sólo 5 multiplicaciones en vez de 13 - 1 = 12

Algunos ejemplos más:

• x¹⁰ = ((x²)²*x)² porque 10 = (1,010)₂ = 2³+2¹, algoritmo necesita 4 multiplicaciones en vez de 9
• x¹⁰⁰ = (((((x²*x)²)²)²*x)²)² porque 100 = (1,100,100)₂ = 2⁶+2⁵+2², algoritmo necesita 8 multiplicaciones en vez de 99
• x^1,000 = ((((((((x²*x)²*x)²*x)²*x)²)²*x)²)²)² porque 10³ = (1,111,101,000)₂, algoritmo necesita 14 multiplicaciones en vez de 999
• x^1,000,000 = ((((((((((((((((((x²*x)²*x)²*x)²)²*x)²)²)²)²)²*x)²)²)²*x)²)²)²)²)²)² porque 10⁶ = (11,110,100,001,001,000,000)₂, algoritmo necesita 25 multiplicaciones
• x^{1,000,000,000} = ((((((((((((((((((((((((((((x²*x)²*x)²)²*x)²*x)²*x)²)²)²*x)²*x)²)²*x)²)²*x)²*x)²)²)²*x)²)²*x)²)²)²)²)²)²)²)²)² porque 10⁹ = (111,011,100,110,101,100,101,000,000,000)₂, algoritmo necesita 41 multiplicaciones

Véase también

• Exponenciación modular

Enlaces externos

• Method of repeated squaring en PlanetMath.

• Datos: Q864127