Reducir exponentes usando mod φ(n).
Calcular potencias grandes módulo $n$, como $a^b \pmod n$ donde $b$ es extremadamente grande, es un problema fundamental en teoría de números y criptografía (es la base del algoritmo RSA). Hacer el cálculo directo es imposible por el tamaño tan enorme de los números. La técnica principal se basa en la naturaleza cíclica de la aritmética modular. Específicamente, la secuencia de potencias $a^1, a^2, a^3, \dots \pmod n$ tarde o temprano se vuelve periódica. Si identificas el periodo de esta secuencia, puedes reducir el exponente $b$ a un número mucho más pequeño y manejable sin cambiar el resultado final módulo $n$.
La herramienta principal para esta reducción es el Teorema de Euler. El teorema dice que si $\gcd(a, n) = 1$, entonces $a^{\phi(n)} \equiv 1 \pmod n$, donde $\phi(n)$ es la función phi de Euler (que cuenta cuántos enteros positivos menores o iguales a $n$ son primos relativos con $n$). Esto implica que las potencias de $a$ se repiten con un periodo que divide a $\phi(n)$. Por lo tanto, puedes reemplazar el exponente $b$ con su residuo al dividirlo entre $\phi(n)$. En otras palabras, el cálculo se reduce a encontrar $a^{b \pmod{\phi(n)}} \pmod n$.
Aunque la aplicación estándar requiere que $a$ y $