Exercise 3: Why a Single Fixed-Base Fermat Test Isn't Trustworthy — Possible Solution
====================================================================

THE PROBLEM WITH A SINGLE FIXED BASE
------------------------------
This chapter's own 341 example proved this concretely, not just in
theory: 341 is genuinely composite (341 = 11 x 31), yet testing it
with the fixed base a=2 gives 2^340 mod 341 = 1 - the test result
that's SUPPOSED to only happen for primes. If a crypto library
always tested with a=2 specifically, it would incorrectly accept
341 as "probably prime" every single time, with total certainty of
being wrong, not just some small chance of it.

This isn't a rare, hypothetical edge case either - Fermat
pseudoprimes to base 2 are a well-known, repeatedly rediscovered
category of numbers specifically BECAUSE base 2 is such a common
default choice, making a fixed-base test a genuinely bad idea in
practice, not just poor form.

WHY MULTIPLE RANDOM BASES FIX THIS
------------------------------
This chapter's own example already showed that switching to base
3, base 5, or base 7 immediately and correctly identified 341 as
composite - only base 2 happened to be fooled. A number that fools
one particular base is not guaranteed to fool a DIFFERENT randomly
chosen base as well - the specific mathematical relationship that
let 341 slip past base 2 doesn't carry over to unrelated bases.

Testing with several independently, randomly chosen bases means a
composite number would need to independently fool EVERY single one
of them to be wrongly accepted. Per this chapter's own framing, the
probability of that happening shrinks rapidly (exponentially) with
each additional round tested - a composite number surviving one
random base is a real but limited risk; surviving many independent
random bases simultaneously becomes vanishingly unlikely, without
ever needing to prove primality with total mathematical certainty
the way trial division does.

RESULT
------------------------------
A single fixed base is untrustworthy because a real, known
counterexample (341 with base 2) already defeats it completely and
deterministically. Multiple random bases work because fooling one
base doesn't imply fooling another, turning a real but limited risk
per test into a negligible one across many independent tests -
exactly the practical trade-off real crypto libraries rely on.

WHY THIS WORKS AS AN ANSWER
------------------------------
The explanation is grounded directly in this chapter's own verified
341 example rather than a generic statement about probability, and
distinguishes clearly between "one fixed base can be deterministically
wrong" and "many random bases are only vanishingly unlikely to all
be wrong together," which is the actual reasoning behind why
production systems use multiple rounds.