Carmichael Function Calculator
Calculate λ(n) - the smallest positive integer m such that a^m ≡ 1 (mod n) for all a coprime to n.
Enter a positive integer (max 1,000,000)
The Carmichael function λ(n), also known as the reduced totient function or least universal exponent function, finds the smallest positive integer m such that a^m ≡ 1 (mod n) for every integer a that is coprime to n.
Formula: For n with prime factorization n = 2^a × p1^k1 × p2^k2 × ... × pm^km, the Carmichael function is calculated as:
λ(n) = lcm(λ(2^a), λ(p1^k1), λ(p2^k2), ..., λ(pm^km))
For Prime Powers:
- λ(p^k) = p^(k-1) × (p - 1) for odd primes p
- λ(2) = 1
- λ(4) = 2
- λ(2^k) = 2^(k-2) for k >= 3
Relationship with Euler's Totient: The Carmichael function always divides Euler's totient: λ(n) | φ(n). They are equal for:
- n = 1, 2, 4
- n = p^k for odd prime p
- n = 2p^k for odd prime p
Applications: The Carmichael function is fundamental in modern RSA cryptography. While the original RSA paper used Euler's totient φ(n), modern implementations use λ(n) because it gives the smallest valid private exponent, making decryption more efficient.
Quick reference table for λ(1) through λ(20):
Note: For prime numbers p, λ(p) = φ(p) = p - 1. The difference between λ and φ becomes apparent for composite numbers like 8, 12, 15, 16, 20.
What is the Carmichael function?
The Carmichael function λ(n), also called the reduced totient function or least universal exponent function, gives the smallest positive integer m such that a^m ≡ 1 (mod n) for all integers a coprime to n. It's the exponent of the multiplicative group of integers modulo n.
How is the Carmichael function different from Euler's totient?
While Euler's totient φ(n) counts how many integers from 1 to n are coprime to n, the Carmichael function λ(n) finds the smallest exponent that works for all coprime bases. λ(n) always divides φ(n), and they're equal for prime powers p^k (except when p=2 and k>=3). For composite numbers, λ(n) is often smaller than φ(n).
Why is the Carmichael function important in cryptography?
The Carmichael function is crucial in RSA cryptography. Modern RSA implementations use λ(n) instead of φ(n) because it gives the smallest valid private exponent, making decryption more efficient. The security of RSA relies on the difficulty of computing λ(n) without knowing the prime factorization of n.
What is the formula for the Carmichael function?
For n = 2^a × p1^k1 × p2^k2 × ... (prime factorization), λ(n) = lcm(λ(2^a), λ(p1^k1), λ(p2^k2), ...). For odd prime powers: λ(p^k) = p^(k-1) × (p-1). For powers of 2: λ(2) = 1, λ(4) = 2, and λ(2^k) = 2^(k-2) for k >= 3.