Primality testing: guarantees, error bounds, and what to report

This page explains how we talk about primality tests in py-mathx-lab: what is guaranteed, what is probabilistic, and what must be recorded in experiment reports.

Core references: [Crandall and Pomerance, 2005, Rabin, 1980].

Deterministic vs probabilistic (project language)

A primality test can have different guarantees:

  • Deterministic: returns the correct answer for every input in its stated domain.

  • Probabilistic (one-sided error):

    • If it returns composite, that is always correct.

    • If it returns probably prime, that can be wrong with some probability.

Project reporting rule: every experiment that uses a probabilistic test must state:

  • “probabilistic vs deterministic” (and the domain if deterministic),

  • bases / rounds used,

  • a conservative error probability statement (when available),

  • and known counterexamples / failure modes when applicable.

(Practically: put this into out/e###/report.md as a short, explicit section.)

Fermat probable prime test (FPP)

For odd \(n>2\) and a base \(a\) with \(\gcd(a,n)=1\), Fermat’s congruence says:

\[ a^{n-1}\equiv 1\pmod n \quad\text{for prime } n. \]

If the congruence fails, \(n\) is composite (a witness was found).
If it passes, \(n\) is a Fermat probable prime to base \(a\).

Why Fermat alone is not reliable

There exist composite numbers that pass Fermat’s test for many bases. In particular, Carmichael numbers pass the test for all bases coprime to \(n\). So Fermat is best treated as a cheap pre-filter, not a strong claim of primality.

See Carmichael numbers.

Known counterexamples (Fermat)

  • \(341 = 11\cdot 31\) is a classic base-2 pseudoprime.

  • \(561 = 3\cdot 11\cdot 17\) is the smallest Carmichael number.

Miller–Rabin (strong probable prime test)

Write

\[ n-1=d\,2^s\quad (d\text{ odd}). \]
For a chosen base \(a\), Miller–Rabin tests a short chain of squarings modulo \(n\) and returns:

  • composite (a witness was found), or

  • strong probable prime to base \(a\).

Standard error bound (what you may claim)

For any odd composite \(n\), at most one quarter of bases \(a\in\{2,\dots,n-2\}\) can make \(n\) look prime to the Miller–Rabin test. Therefore, if you test \(k\) independent random bases,

\[ \Pr(\text{composite passes all }k\text{ rounds})\le 4^{-k}. \]
This is the classical Rabin bound. [Rabin, 1980]

Practical “deterministic” statements

Sometimes you will see statements like “Miller–Rabin is deterministic for 64-bit integers using a fixed base set.” Such claims depend on external results that specify an input range and a particular base set.

In this project:

  • If you use random bases, treat MR as probabilistic and report \(4^{-k}\).

  • If you use a fixed base list, report it as an engineering choice, and only call it deterministic if your documentation also cites a theorem covering your input range.

Pipeline viewpoint (how tests combine)

In experiments, primality tests often appear as components in a larger pipeline:

  1. Handle trivial cases: \(n<2\), even numbers, perfect squares.

  2. Trial division up to a small bound (fast removal of tiny factors).

  3. Miller–Rabin as a strong “probable prime” filter (with stated guarantee).

  4. If composite but no factor found: a factor-finding step (e.g. Pollard–\(\rho\)) and recursion.

See Semiprimes and Prime numbers refresher for context.

Report checklist (copy/paste into report.md)

Use a short section in out/e###/report.md that states:

  • Status: deterministic vs probabilistic

  • Method: Fermat / MR / combination

  • Bases / rounds:

    • fixed list (write the list), or

    • random rounds \(k\) (state how bases are sampled)

  • Error statement:

    • MR random rounds: \(P(\text{false prime})\le 4^{-k}\)

    • Fermat: no uniform bound; mention Carmichael numbers

  • Correctness cross-check:

    • compare decisions to a trusted reference on a CI-safe range

  • Known counterexamples / failure modes:

    • include at least one concrete counterexample when relevant (e.g. 341, 561)

References