Exponenciación binaria (cuadrados repetidos).
Calcular potencias grandes módulo $n$, escrito como $a^b \pmod n$, es una operación fundamental en teoría de números y criptografía. Un enfoque simple —calcular $a^b$ directamente y luego dividir entre $n$— es imposible de hacer para exponentes grandes porque $a^b$ crece de forma exponencial y supera rápido los límites normales de los enteros. Pero la aritmética modular te permite hacer la operación de módulo en cada paso de la multiplicación. Como $(x \cdot y) \pmod n = ((x \pmod n) \cdot (y \pmod n)) \pmod n$, puedes mantener los resultados intermedios más pequeños que $n$ durante todo el cálculo.
El método más eficiente para calcular esto a mano o con algoritmos es la Exponenciación Binaria (también conocida como Repeated Squaring). Esta técnica usa la representación binaria del exponente $b$. En lugar de multiplicar $a$ por sí mismo $b$ veces (que toma mucho tiempo), calculas las potencias $a^1, a^2, a^4, a^8, \dots \pmod n$ elevando al cuadrado el resultado anterior sucesivamente. Cualquier entero $b$ se puede escribir como una suma de potencias de 2; por lo tanto, puedes escribir $a^b$ como el producto de términos específicos de esta secuencia. Esto reduce el número de multiplicaciones de $b$ a más o menos $\log_2(b)$.
Por ejemplo, para calcular $3^{13} \pmod{100}$, nota que $13 = 8 + 4 + 1$ (en binario es $1101_2$). Calculas $3^1, 3^2, 3^4, 3^8 \pmod{100}$ elevando al cuadrado, y luego calculas $3^{13} \equiv 3^8 \cdot 3^4 \cdot 3^1 \pmod{100}$. Este método es esencial para resolver problemas de AMC y AIME que piden los últimos dígitos de potencias grandes o encontrar restos de torres de exponentes.
1. La Propiedad Multiplicativa La base de la exponenciación modular es que puedes distribuir el módulo en la multiplicación: $$a \cdot b \pmod n = [(a \pmod n) \cdot (b \pmod n)] \pmod n$$ Esto implica que: $$a^2 \pmod n = (a \pmod n)^2 \pmod n$$
2. Descomposición por Exponenciación Binaria Si el exponente $b$ tiene la representación binaria $b = (d_k d_{k-1} \dots d_1 d_0)2$, lo que significa que $b = \sum{i=0}^k d_i 2^i$ donde $d_i \in {0, 1}$, entonces: $$a^b \equiv \prod_{i=0}^k (a^{2^i})^{d_i} \pmod n$$ Aquí, generas los términos $a^{2^i}$ de forma recursiva: $$a^{2^i} \equiv (a^{2^{i-1}})^2 \pmod n$$
3. Teorema de Euler (Reducción del Exponente) Aunque la exponenciación binaria sirve para calcular el valor, a menudo se usa primero el Teorema de Euler para reducir el tamaño del exponente $b$ si $b \ge \phi(n)$ y $\gcd(a,n)=1$: $$a^{\phi(n)} \equiv 1 \pmod n$$ Esto te permite simplificar el exponente: $$a^b \equiv a^{b \pmod{\phi(n)}} \pmod n$$ Nota: Si $n$ es primo, esto se simplifica al Pequeño Teorema de Fermat: $a^{p-1} \equiv 1 \pmod p$.
Teorema: Para enteros $a, b, n$ con $n > 0$, puedes calcular el valor $a^b \pmod n$ como el producto de los términos $a^{2^i}$ que corresponden a los bits encendidos en la representación binaria de $b$.
Demostración:
Define la representación binaria del exponente $b$ con los coeficientes $d_i \in {0, 1}$ de tal forma que: $$b = \sum_{i=0}^k d_i 2^i = d_0 2^0 + d_1 2^1 + \dots + d_k 2^k$$ donde $k = \lfloor \log_2 b \rfloor$.
Si sustituyes esta suma en la expresión de la potencia $a^b$: $$a^b = a^{\sum_{i=0}^k d_i 2^i}$$
Usando las leyes de los exponentes ($x^{y+z} = x^y x^z$), puedes separar la suma en el exponente como un producto de bases: $$a^b = \prod_{i=0}^k a^{d_i 2^i}$$
Como $d_i$ es $0$ o $1$:
Así que puedes escribir la congruencia módulo $n$: $$a^b \equiv \prod_{i=0, d_i=1}^k a^{2^i} \pmod n$$
Para encontrar los valores de $a^{2^i} \pmod n$, usa la relación recursiva que definimos al elevar al cuadrado el término anterior. Procede por inducción sobre $i$:
Por la propiedad multiplicativa de la aritmética modular, el producto de estos restos modulares es congruente al producto de los enteros módulo $n$. Por lo tanto, calcular las potencias $a^{2^i}$ mediante elevaciones al cuadrado sucesivas y multiplicar las potencias específicas donde $d_i=1$ te da el resultado correcto para $a^b \pmod n$.
$\square$