skip to content

A primality screen may pass a composite but never rejects a prime; what does that one-sided error let you conclude from each verdict?

level: middleimportance: must knowfreq 52%

answer

  1. one verdict is a proof
  2. Monte Carlo against Las Vegas
  3. compositeness has witnesses, primality does not
  4. fresh independent base every round
  5. a quarter per round, so 4^-k

basics

~20 s

A composite verdict is a proof and can be trusted outright; a prime verdict is only probable. One-sided error means the certainty lives on exactly one side, which is why repeating with fresh random bases drives the remaining doubt down multiplicatively.

solid answer

~40 s

The screen witnesses compositeness: when it rejects, it holds a concrete reason, so that verdict is certain. It never has a corresponding proof of primality, so passing means only that no witness was found with the bases it happened to draw. That is **one-sided error** — the class `RP` for the compositeness question, and `co-RP` for the primality question. Each independent round with a fresh random base fails to expose a composite with probability at most 1/4, so `k` rounds leave at most `4^-k`; at k = 40 that is about `8 x 10^-25`. Contrast a **Las Vegas** procedure (`ZPP`), which is never wrong at all and instead lets its running time be the random quantity, and a **Monte Carlo** two-sided procedure, where neither verdict is a proof.

code

pseudocode · 6 lines
pseudocode
function screen(candidate, rounds):
    for i from 1 to rounds:
        base = uniform_random_base(candidate)   // fresh draw each round
        if witness_relation_fails(candidate, base):
            return DEFINITELY_COMPOSITE        // proof found, stop
    return PROBABLY_PRIME                      // no witness among 'rounds' draws

go deeper

for a junior

Recall that a probabilistic check can be certain in one direction only, and that repeating it with new random choices is what shrinks the doubt on the other direction.

for a middle

Explain the asymmetry precisely: the rejecting verdict holds a witness and is certain, the accepting one is not, rounds are independent draws, and the residual error is the per-round rate raised to the round count.

for a senior

Show the operational consequences: choose a round count from a stated residual budget, keep the draws genuinely independent, and never let downstream code record the probabilistic verdict as an established fact.

for a principal

Own the trade itself. Decide whether the cheaper probabilistic screen or the deterministic test belongs in the pipeline, with the residual probability compared against the other failure rates the system already carries.

## Which side carries the certainty A randomized screen of this shape tests a candidate against a randomly drawn base and looks for an arithmetic relation that only a prime can satisfy. If the relation fails, the failure itself *is* the evidence: the candidate is composite, full stop, with no probability attached. If the relation holds, nothing has been proved — a composite can satisfy it for some bases, and those bases are exactly the ones the draw might have landed on. So the two verdicts are not symmetric, and saying so precisely is the whole answer: - **Reject (composite)** — certain. There exists a checkable witness and the run found it. - **Accept (probably prime)** — probabilistic. No witness was found among the bases drawn. ## Naming it: which class, in which direction The class of one-sided-error problems is `RP`: a problem is in `RP` when a polynomial-time randomized procedure accepts every yes-instance with probability at least 1/2 and accepts a no-instance with probability exactly zero. Pointing that at this setting requires care about which question you are asking. | question being decided | what a run can prove | class | |---|---|---| | Is the candidate composite? | a rejecting relation is a witness of compositeness | `RP` | | Is the candidate prime? | nothing is ever proved by a passing round | `co-RP` | Getting this backwards is the classic slip. The compositeness question is the one with witnesses, so it is the one in `RP`; primality is its complement and sits in `co-RP`. ## Amplification on one side is multiplication, not a concentration bound Because one verdict is a proof, you do not need a majority. Draw a fresh independent base, run again, and stop the moment any round rejects. The screen only errs if **every** round misses, so the failure probability is the per-round miss probability raised to the number of rounds. For a screen of this family, at most a quarter of the possible bases fail to expose a given odd composite, so a uniformly random base misses with probability at most 1/4: | rounds k | bound `4^-k` | |---|---| | 1 | 0.25 | | 10 | about 10^-6 | | 40 | about 8 x 10^-25 | The same independence caveat as always applies: rounds that reuse a base, or derive their bases from one another, are not independent rounds and the exponent is a fiction. ## Three guarantee shapes, kept apart 1. **Monte Carlo, two-sided.** Fixed running time, either verdict may be wrong, error bounded away from one half. The majority over independent repeats is the instrument. 2. **Monte Carlo, one-sided.** Fixed running time, one verdict is a proof. Repeat until the proof appears; error multiplies down. 3. **Las Vegas.** The answer is **never** wrong. The randomness moves into the running time, which becomes a random variable bounded only in expectation. The corresponding class is `ZPP`, and it is exactly the problems that are in both `RP` and `co-RP`: run the one-sided procedure for each direction alternately until one of them produces its proof. An equivalent way to picture a Las Vegas procedure is one allowed to answer "don't know", but never allowed to answer wrongly. That framing makes the cost obvious: you pay in time, not in correctness. ## The inclusions worth remembering Every deterministic polynomial-time procedure is trivially a randomized one that ignores its coins, and each shape above is a special case of the next, giving `P` inside `ZPP` inside `RP` inside `BPP`. Also `RP` sits inside `NP`, because an accepting run of a one-sided procedure is itself a certificate that a nondeterministic machine could have guessed. Whether `BPP` sits inside `NP` is not known. ## Why an engineer should care which side is certain The asymmetry decides what downstream code may assume. A rejected candidate can be discarded without a second thought. An accepted one carries a residual probability that has to be either driven below an explicit budget by adding rounds, or eliminated by a deterministic test — and a deterministic polynomial-time primality test does exist, so the randomized screen is a **cost** decision, not a necessity. The screen survives because its per-round work is far cheaper, and because `4^-40` is smaller than the probability that the machine mis-computes the deterministic answer anyway. The failure mode to watch for is a pipeline that treats the probabilistic verdict as if it were the certain one: logging "prime" as a fact, or dropping the round count to save time without recomputing what the residual probability became.

  • How does a Las Vegas procedure differ from this one?
    A Las Vegas procedure is never wrong; its running time is the random quantity, bounded only in expectation. This screen is the opposite trade: its running time is fixed by the round count, and the residual doubt sits in the accepting verdict. The problems with a Las Vegas procedure are exactly those with one-sided procedures in both directions.
  • If a deterministic polynomial-time primality test exists, why keep a randomized screen?
    Because polynomial time is not the same as cheap. The randomized rounds cost far less per candidate, and forty independent rounds leave a residual probability around 10^-24, which is below the rate of undetected hardware error. The choice is an explicit cost-against-certainty trade, not a gap in what is computable.
  • What breaks if the rounds share their random base?
    The multiplicative bound disappears. Rounds that reuse a base, or derive one base from another, repeat the same test, so a composite that survived the first round survives all of them. The reported error of the per-round rate to the power of the round count then describes an experiment that was never run.

saying these in an interview costs you the question

  • Says both verdicts of the screen are equally probabilistic
  • Puts the certainty on the prime side rather than the composite side
  • Thinks more rounds can eventually prove primality
  • Claims a randomized screen is needed because no deterministic test exists
  • Reuses one base across rounds and still quotes the multiplicative bound
  • Calls it Las Vegas although the answer can be wrong