Carmichael Numbers & λ(n) — the true group exponent, and why a lone Fermat test lies

The Carmichael function λ(n) is the smallest exponent with a^{λ(n)} ≡ 1 (mod n) for every a coprime to n — the TRUE exponent of the multiplicative group (Z/nZ)^*, and it always divides φ(n) (often strictly). A Carmichael NUMBER is a composite n that fools Fermat's test — a^{n-1} ≡ 1 (mod n) — for *every* base a coprime to n, not just some; the classic public example is 561 = 3·11·17.

The signal that gives it away

- The challenge hands you p, q (or a factored N) and asks for the minimal RSA private exponent d, or the source code computes d from something other than φ(N). That's the tell that λ(N) — not φ(N) — is the exponent actually in play, since d ≡ e^{-1} mod λ(N) is both correct and canonical (RSA only strictly needs e·d ≡ 1 mod λ(N), and modern implementations increasingly compute it this way rather than via φ(N)). - Exponent arithmetic in the challenge appears to "wrap around" (cycle back to the same value) at a period *smaller* than φ(n) — that period is λ(n), and treating φ(n) as the true group order will silently overcount. - A number the challenge treats as prime, or that a target library only validated with a^{n-1} ≡ 1 (mod n) for a single (or a handful of) bases, is composite and squarefree with an unusual number of prime factors — a candidate Carmichael number planted to trip up naive primality checks. - Korselt's criterion is the structural fingerprint if you're reverse-engineering *why* a given composite passes Fermat universally: n is Carmichael iff n is squarefree and, for every prime p | n, (p-1) | (n-1). It follows that Carmichael numbers are always odd and always have at least 3 distinct prime factors (never exactly two) — so a two-factor RSA-style modulus n = pq can never itself be a Carmichael number, but a modulus deliberately built from 3+ small primes can be.

How to exploit it

1. Compute λ(n) from the factorization: λ(n) = lcm over all prime-power factors p^e of λ(p^e), where λ(p^e) = p^{e-1}(p-1) for odd p, and the 2-power case is special: λ(2)=1, λ(4)=1, λ(2^e)=2^{e-2} for e≥3. 2. For the two-prime RSA case this collapses to λ(N) = lcm(p-1, q-1), which is smaller than φ(N) = (p-1)(q-1) by a factor of gcd(p-1, q-1) — use it whenever a challenge wants the *smallest* valid private exponent, or when d derived from φ(N) doesn't match a d the challenge expects. 3. Reduce any exponent mod λ(n) before big computations: a^k ≡ a^{k mod λ(n)} (mod n) for a coprime to n — this is the general form behind cutting down huge exponents in modular-exponentiation-heavy challenges, and it's the *tight* reduction (φ(n) also works but can leave the exponent needlessly larger). 4. Working reference implementation (uses sympy.factorint, generalizes past the RSA n=pq case to any n): ```python from math import gcd from functools import reduce from sympy import factorint

def lam(n): def lp(p, e): if p == 2: return 1 if e <= 2 else 2(e - 2) return p(e - 1) * (p - 1) vals = [lp(p, e) for p, e in factorint(n).items()] return reduce(lambda a, b: a * b // gcd(a, b), vals, 1) `` 5. To CONSTRUCT or recognize a Carmichael number from scratch (e.g. a challenge that plants one as a fake "prime"), search for squarefree products of small primes p_1...p_k (k≥3) satisfying Korselt: (p_i - 1) | (product - 1) for every i. Verifying candidate n` against this criterion is far cheaper than factoring it blind if you already suspect the shape. 6. Route detection of a suspected Carmichael number to Miller–Rabin — see Primality Testing — confirming a number is prime without factoring it — rather than iterating more Fermat bases; a single strong-test round already distinguishes it from a true prime with overwhelming probability, because Miller-Rabin checks the structure of n-1's factorization on the exponentiation path, which Fermat's test ignores entirely.

What does NOT work

- Trusting a lone Fermat test, or even a handful of extra bases. By definition a Carmichael number passes a^{n-1}≡1 for *every* a coprime to it — adding more random bases doesn't help, because none of them are witnesses. You need a test (Miller–Rabin) that checks something Fermat's test structurally cannot see. This is the single most field-tested pitfall: any "primality check" in challenge source that only does modular exponentiation, no square-root-of-unity check, is exploitable by a planted Carmichael number. - Assuming `d` computed from `φ(N)` will be "the" private exponent a challenge expects. If the challenge's reference solution used λ(N), the two d values can differ (d_φ ≠ d_λ) even though both satisfy e·d ≡ 1 in their respective moduli — decrypting with the wrong one silently fails or gives garbage, and it's easy to lose time assuming a bug elsewhere. - Two-prime RSA moduli can never be Carmichael numbers themselves (Korselt requires ≥3 distinct prime factors) — don't waste time checking a textbook n=pq for the Carmichael property; if a challenge modulus does pass a suspiciously weak primality check, look for a third hidden factor, not a two-factor Carmichael construction. - Using `φ(n)` as if it were the definitive group exponent when reasoning about periods/cycles. φ(n) is only an upper bound on the true exponent; if you use it to predict when something (a keystream, a repeated value, an oracle response) should cycle, you'll be wrong by exactly the factor φ(n)/λ(n) and may conclude "no periodicity" when there is one.

Related

Euler's Totient — the RSA key-math backbone, and why it's not the exponent you want to leak Primality Testing — confirming a number is prime without factoring it RSA Fundamentals — the routing hub: which artifact points to which attack