La exponenciación binaria es un algoritmo utilizado para calcular de forma rápida grandes potencias enteras de un número
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.
El algoritmo está basado en las siguientes tres propiedades de la potencia: (1)
en la ecuación (3) se obtiene que
El siguiente algoritmo recursivo calcula
dado: Comparado con el método original de multiplicar
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.
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 Este método funciona en cualquier semigrupo, y es usado frecuentemente para calcular potencias de matrices.
Por ejemplo, la evaluación de 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.
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 Algunos ejemplos más: