Pseudoprimes & Primality Testing

561 = 3 × 11 × 17 — plainly composite. Yet Fermat's primality test, the most natural one, declares it 'probably prime' for almost every base you try. It's a Carmichael number: a composite that wears a prime's costume. Catching these impostors is essential, because RSA and every crypto system must pick real primes — and the difference between 'probably' and 'definitely' is exactly where attackers slip in.