Se considera el anillo Z_m, es decir, el conjunto de enteros {0 , 1 , ... , m-1}. Se está interesado en el problema de conocer cuántos números en este conjunto con coprimos con m. Esta cantidad es dada por la función Phi de Euler, la cual se define como sigue:

El número de enteros en Z_m coprimos a m es denotado por φ(m).

Por ejemplo:

Sea m = 6. El conjunto asociado es Z₆ = {0 , 1 , 2 , 3 , 4 , 5}.

mcd(0 , 6) = 6
mcd(1 , 6) = 1 *
mcd(2 , 6) = 2
mcd(3 , 6) = 3
mcd(4 , 6) = 2
mcd(5 , 6) = 1 *

Ya que hay dos números en el conjunto que son coprimos a 6, sean 1 y 5, la función phi toma el valor de 2, es decir φ(6) = 2.

Para números pequeños no supone ningún problema, pero para números grandes tomaría mucho tiempo en calcular el mcd entre m y todos los valores de Z_m.

Propiedades de Phi de Euler:

1. Si p es primo ⇒ φ(p) = p - 1.
2. Si p es primo ⇒ φ(p^e) = p^e * (1 - 1/p).
3. Sea m = a * b. Si MCD(a , b) = 1 ⇒ φ(a * b) = φ(a) * φ(b).
4. Sea m = p₁^e₁ * p₂^e₂ ... p_k^e_k ⇒ φ(m) = m * (1 - 1/p₁ ) * (1 - 1/p₂ ) ... (1 - 1/p_k ).

Por ejemplo:

Propiedad 1.

Sea m = 19 ⇒ φ(19) = 19 - 1 = 18

Propiedad 2.

Sea m = 81 = 3⁴ ⇒ φ(3⁴) = 3⁴ * (1 - 1/3) = 54

Propiedad 3.

Sea m = 5 * 4. MCD(5 , 4) = 1 ⇒ φ(5 * 4) = φ(5) * φ(4) = (5-1)*(2²*(1-1/2)) = 8

Propiedad 4.

Sea m = 360 = 2³ * 3² * 5 ⇒ φ(360) = 360 * (1 - 1/2) * (1 - 1/3 ) * (1 - 1/5 ) = 96

---

Referencias

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