Função φ de Euler (Totiente)

Função phi de Euler φ(n)

A função totiente φ(n) conta os inteiros em [1, n] coprimos com n — sem fator primo em comum. Para um primo p, todo positivo menor é coprimo, então φ(p) = p − 1. A função é multiplicativa: quando gcd(m, n) = 1, vale φ(m · n) = φ(m) · φ(n). A partir da fatoração n = p₁^a₁ · p₂^a₂ · … obtemos a fórmula fechada φ(n) = n · ∏(1 − 1/pᵢ). Exemplo: φ(12) = 12 · (1 − 1/2) · (1 − 1/3) = 4 (os inteiros 1, 5, 7, 11). Para dois primos distintos, φ(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 calcula φ(n) = (p − 1)(q − 1) para derivar o expoente privado d ≡ e^(−1) (mod φ(n)).
• Teorema Chinês do Resto (CRT) — acelera a decriptação RSA trabalhando modularmente em p e q separadamente.
• Ordem multiplicativa — a ordem de qualquer elemento em (ℤ/nℤ)* divide φ(n).
• ECDSA e sistemas de logaritmo discreto usam a totiente para descrever o tamanho de grupos cíclicos.

Perguntas frequentes

Por que φ(n) é difícil sem a fatoração? Recuperar φ(n) só a partir de n é equivalente a fatorar n — o problema 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 — há sempre algum primo ímpar contribuindo com (p − 1) ou um fator 2 vindo de 2^k.

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