Do a primality classifier's residual errors fingerprint its algorithm — Fermat pseudoprimes for a Fermat-like test, no-small-factor composites for a sieve?

Status: open · laid 2026-09-27 · type: lead

Statement. Train a network to classify an integer n as prime or composite from its binary digits — no factorisation given, no arithmetic primitives, just the bit string. Whatever it learns will be wrong somewhere, and the probe's claim is that which n it is wrong on identifies the algorithm it found, because the two obvious algorithms fail on disjoint sets:

• A Fermat-like test — something computing a power residue, whose natural failure is a base-2 Fermat pseudoprime: a composite n with 2^(n−1) ≡ 1 (mod n). The first few are 341, 561, 645, 1105, 1387, 1729, 1905. A test of this shape calls exactly these prime and cannot do otherwise; the pseudoprimes are not hard cases for it, they are its definition of failure.
• A sieve — something detecting divisibility by small primes, whose natural failure is a composite with no small factor: semiprimes p·q with both factors large. It gets every pseudoprime in the list above right, because 341 = 11 · 31 and 561 = 3 · 11 · 17 have small factors and a sieve sees them.

So the error set discriminates, and it discriminates on objects that already have names. The measurement: the residual error rate on base-2 Fermat pseudoprimes against the rate on size-matched composites whose least prime factor exceeds some cut, both against the overall composite error rate. Enrichment on the first with none on the second, or the reverse.

The second question, about the learning curve rather than the errors. A sieve is built one prime at a time, and the accuracy attainable from divisibility by the primes up to p is a known density: screening by 2 alone settles half the composites, by 2 and 3 two thirds, and so on through the product over p of (1 − 1/p). So a network building a sieve should show a staircase, one step per small prime divisor it adds, with plateau heights predictable in advance from those sieve densities. That makes the curve a readout of which primes the network holds, and the prediction of the heights is a check on the reading rather than a fit to it.

Why a probe and not a case. The two branches are stated and the discriminating measurement is named, which is nearly a case — but the differential is not yet closed: a network may implement neither (memorising a bounded range is a third outcome, and the honest one for small n), and the sieve/Fermat pair does not exhaust what gradient descent might find. Closing the branch list, and fixing the range of n so memorisation is excluded by counting rather than by hope, is what would make it one.

No prediction and no falsifier are filed here — both are the human's (MANUAL.md, Decisions only you make).

Cross-refs. P-035 places this among the curve-shape readings. The staircase half is the discrete-prime analogue of P-027's singular-value staircase, where the plateau lengths rather than the heights are the readout.