Função Totiente de Euler φ(n)

Função totiente de Euler

A função totiente φ(n) conta os inteiros em [1, n] coprimos com n — ou seja, sem fator primo em comum. Para um primo p, todo positivo menor é coprimo, então φ(p) = p − 1. A função é multiplicativa: se n = p₁^a₁ · p₂^a₂ · … é a fatoração em primos, então φ(n) = n · ∏(1 − 1/pᵢ). Exemplos: φ(12) = 12 · (1 − 1/2) · (1 − 1/3) = 4 (os inteiros 1, 5, 7, 11). Para dois primos distintos p ≠ q, φ(p · q) = (p − 1)(q − 1) — a identidade que sustenta o RSA. O teorema de Euler generaliza o pequeno teorema de Fermat: a^φ(n) ≡ 1 (mod n) sempre que gcd(a, n) = 1.

Onde a totiente aparece

• RSA — a geração de chaves escolhe primos p, q, calcula n = p · q e φ(n) = (p − 1)(q − 1), e deriva o expoente privado d ≡ e^(−1) (mod φ(n)).
• Ordem de elementos no grupo multiplicativo (ℤ/nℤ)* — que tem exatamente φ(n) elementos.
• ElGamal e outros sistemas baseados em logaritmo discreto dependem da estrutura de grupo descrita pela totiente.
• Contagem de frações irredutíveis com denominador n — existem exatamente φ(n) delas.

Perguntas frequentes

Por que φ(n) é difícil de calcular sem a fatoração? Porque depende dos fatores primos de n. Recuperar φ(n) a partir só de n é equivalente a fatorar n — o que sustenta a segurança do RSA.

Quanto é φ(1)? Por convenção φ(1) = 1: o único inteiro em [1, 1] é o próprio 1, e gcd(1, 1) = 1.

A totiente é sempre par para n > 2? Sim — todo n > 2 tem ao menos um fator (p − 1) com p ímpar ou contribui com um fator 2 vindo de 2^k.

Como se relaciona com a função de Carmichael? A função λ(n) de Carmichael é o menor expoente para o qual a^λ(n) ≡ 1; sempre divide φ(n) e costuma ser usada em implementações modernas de RSA no lugar de φ.