Reducir exponentes usando mod p-1.
Calcular potencias grandes módulo $p$, como encontrar el residuo de dividir $a^n$ entre un número primo $p$, es un problema fundamental en la teoría de números y la criptografía. Cuando el exponente $n$ es mucho más grande que el módulo $p$, hacer el cálculo directo es prácticamente imposible. La técnica para resolver esto se basa en la naturaleza cíclica de las potencias en la aritmética modular. Específicamente, el Pequeño Teorema de Fermat te dice que para un primo $p$ y un entero $a$ que no sea divisible entre $p$, las potencias de $a$ se repiten con un periodo de $p-1$.
Esta idea te permite reducir el exponente $n$ módulo $p-1$. En lugar de calcular $a^n$, puedes calcular $a^r$, donde $r$ es el residuo de dividir $n$ entre $p-1$. Esto simplifica muchísimo el problema, transformando un exponente gigante en un número más chico que $p$. Esta técnica es esencial en las olimpiadas de matemáticas para encontrar las últimas cifras de números grandes y evaluar torres de exponentes masivas. También sirve como la base matemática para el algoritmo de cifrado RSA.
La intuición detrás de esto es que, mientras la base $a$ vive en el "reloj" de tamaño $p$ (aritmética módulo $p$), el exponente vive en un "reloj" de tamaño $p-1