Search for a primality certificate for n, using seed to choose the
deterministic random sequence and budget to limit the work. Return a
certificate and search statistics, or an error explaining why search stopped.
Every .ok c result satisfies checkAt n c = true; failure to find a
certificate does not imply that n is composite.
The default policy admits inputs through 256 bits. native512Budget and
public512Budget explicitly select 512-bit search. For a theorem of
Mathlib's Nat.Prime n, use HexECPPTheory.Native or apply the companion's
soundness theorem to a kernel-checked checker equation.