Método para calcular eficientemente a^e mod m para enteros a, exponente e (no negativo o representado en binario) y módulo m, combinando el cuadrado repetido con reducción modular para mantener pequeños los valores intermedios.

Principio

Usar la descomposición binaria (o ventana deslizante) del exponente para efectuar cuadrados sucesivos y multiplicaciones selectivas, aplicando reducción modular tras cada operación para evitar el crecimiento exponencial de los intermedios.

Demostración

Calcular 2^20 mod 17. Como 2^4 = 16 ≡ −1 (mod 17), 2^20 = (2^4)^5 ≡ (−1)^5 = −1 ≡ 16 (mod 17). El cuadrado repetido produce 2, 4, 16, 1, ... con reducción en cada paso.

Aplicación incorrecta

Realizar la exponenciación en precisión completa antes de reducir (provoca desbordamiento) o usar multiplicación repetida ingenua para exponentes enormes sin descomposición, lo que hace el cálculo inviable.

Consecuencia

Bien utilizado, permite calcular potencias modulares grandes rápidamente con complejidad logarítmica en e, habilitando cifrado, verificación de firmas y rutinas de primalidad.

Inversión

La inversión es intentar recuperar el exponente o la base a partir de la potencia modular (logaritmo discreto), un problema inverso difícil en muchos grupos; la exponenciación modular es fácil, su inversa suele ser difícil.

Límite

Aplica a la exponenciación en Z/mZ y, en general, en grupos finitos; exponentes negativos requieren inversos modulares (existencia ligada a que sean coprimos). No resuelve logaritmos discretos ni exponenciación no modular.

Tensión semántica

Contrasta con la exponenciación simple seguida de reducción (equivalente en teoría pero impráctica) y con la exponenciación en aritmética real donde la reducción no aplica; frecuentemente se confunde con protocolos de exponenciación segura.

Síntesis

La exponenciación modular es la secuencia controlada de cuadrados y multiplicaciones con reducción inmediata, guiada por la representación binaria del exponente para calcular eficientemente a^e mod m.