Carmichael Function λ(n)

Carmichael Function, 카마이클 함수, reduced totient

정의

Carmichael function λ(n) 은 gcd(a, n) = 1 인 모든 a 에 대해 a^m ≡ 1 (mod n) 을 만족하는 최소 양의 정수 m.

핵심 성질: 항상 λ(n) | φ(n). 즉 Euler Phi 는 항상 유효하지만 tight 하지 않을 수 있음.

계산

• λ(1) = 1
• λ(2) = 1, λ(4) = 2
• λ(2^k) = 2^(k-2) for k ≥ 3
• λ(p^k) = p^(k-1)(p-1) for odd prime p
• λ(prod p_i^k_i) = lcm(λ(p_i^k_i))

응용

• RSA-CRT: 개인 키 지수 e^-1 mod λ(n) 이 정확한 exponent
• Order 문제: 임의 a 의 곱셈적 order 는 λ(n) 의 약수

참고

• Euler Phi Function
• Fermat’s Little Theorem