Realizar la operación de elevar un número a una cierta potencia y después aplicarle la operación módulo puede ser algo fácil o difícil de hacer dependiendo tanto del exponente.

Por ejemplo:

Elevar 5 a la potencia 3 en Z₂₇

5³ = 125 ≡ 17 mod 27

es algo fácil de calcular porque el exponente es pequeño.

Ahora elevamos 5 a la potencia 21 en Z₂₇

5²¹ = 476,837,158,203,125 ≡ 17 mod 27

y notamos que se vuelve más difícil de hacer.

---

El método más simple para realizar una exponenciación modular basa su funcionamiento en el hecho de que no importa que tan grande sea la potencia, el resultado siempre será un número entre 0 y m - 1.

Para explicar este método se usará el ejemplo anterior.

1. Se toma la base y se escribe en forma de multiplicación.
5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5
2. Se toman los dos primeros números, se multiplican entre ellos y se calcula el módulo.
5 * 5 ≡ 25 mod 27
3. El 25 se coloca en lugar de los 2 primeros números.
25*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5
4. Se vuelven a tomar los dos primeros números, se multiplican entre ellos y se calcula el módulo.
25 * 5 ≡ 17 mod 27
5. El 25 se coloca en lugar de los 2 primeros números.
17*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5
6. Se repiten los pasos hasta que solo quede un número.
25*5 25 * 5 ≡ 17 mod 27 17
7. El número final es el resultado de la exponenciación modular.
5²¹ ≡ 17 mod 27