title: Exponenciación binaria
text: # 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.
  
  # Exponenciación binaria
  ## 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}$.
  
  # Exponenciación binaria
  ## Versión recurrente
  ### 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.
  
  # Exponenciación binaria
  ## 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$^{722341}$ (mod 2345)
  tomaría mucho tiempo y espacio de almacenamiento si el método ingenuo es usado: calcular 13789$^{722341}$ 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$^{722341}$ = 13789(13789$^2$)$^{361170}$. Entonces, si se calcula 13789$^2$, 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$^{13}$ = x$^{1101bin}$
      = 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$^8$ * x$^4$ * x$^1$
      = (x$^4$)$^2$ * (x$^2$)$^2$ * x
      = (x$^4$ * x$^2$)$^2$ * x
      = ((x$^2$)$^2$ * x$^2$)$^2$ * x
      = ((x$^2$ * x)$^2$)$^2$ * x   → algoritmo necesita sólo 5 multiplicaciones en vez de 13 - 1 = 12
  Algunos ejemplos más:
  * x$^{10}$ = ((x$^2$)$^2$*x)$^2$ porque 10 = (1,010)$_2$ = 2$^3$+2$^1$, algoritmo necesita 4 multiplicaciones en vez de 9
  * x$^{100}$ = (((((x$^2$*x)$^2$)$^2$)$^2$*x)$^2$)$^2$ porque 100 = (1,100,100)$_2$ = 2$^6$+2$^5$+2$^2$, algoritmo necesita 8 multiplicaciones en vez de 99
  * x$^{1,000}$ = ((((((((x$^2$*x)$^2$*x)$^2$*x)$^2$*x)$^2$)$^2$*x)$^2$)$^2$)$^2$ porque 10$^3$ = (1,111,101,000)$_2$, algoritmo necesita 14 multiplicaciones en vez de 999
  * x$^{1,000,000}$ = ((((((((((((((((((x$^2$*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 10$^6$ = (11,110,100,001,001,000,000)$_2$, algoritmo necesita 25 multiplicaciones
  * x$^{1,000,000,000}$ = ((((((((((((((((((((((((((((x$^2$*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 10$^9$ = (111,011,100,110,101,100,101,000,000,000)$_2$, algoritmo necesita 41 multiplicaciones