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 20 en Z₂₇

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

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

---

Teorema de Euler

El Teorema de Euler dice: Sean a y m enteros con mcd(a , m) = 1, entonces

Este teorema sirve para reducir el exponente en una exponenciación modular siempre que:

• mcd(a , m) = 1
• φ(m) <= e

Para explicar su funcionamiento se usará el ejemplo anterior.

Se calcula φ(27) (Phi de Euler)

φ(27) = 18

Se expresa el exponente en términos de φ(27).

21 = 1*18 + 3
5²¹ = 5^{1*18 + 3} 5²¹ = 5^1*18 * 5³ 5²¹ = (5¹⁸)¹ * 5³

Como mcd(5 , 27) = 1 y φ(27) < 21 se puede aplicar el Teorema de Euler

5¹⁸ ≡ 1 mod 27

Se hace la sustitución.

5²¹ = (5¹⁸)¹ * 5³ 5²¹ ≡ 1¹ * 5³ mod 27 5²¹ ≡ 5³ mod 27

Ahora que el exponente se ha reducido se puede aplicar cualquier otro método de exponenciación modular.

5²¹ ≡ 5³ mod 27 5³ ≡ 17 mod 27

---

Referencias

1. Christof Paar, Jan Pelzl. (2010). Understanding Cryptography. Berlin Heidelberg: Springer.