Context
Random modular testing can be recast as a short existential certificate for nonzeroness.
Hypotheses and scope
- The circuit is division-free, has polynomial size, and uses integer constants of polynomial bit length.
Proof or evidence
A gate induction bounds the output bit length by 2^s times a polynomial in the circuit parameters, hence bounds the number of distinct prime divisors. More primes exist below a number with polynomially many bits, so one polynomial-bit prime does not divide a nonzero output. Verify primality and evaluate the circuit modulo that prime.
Verification notes
The proof uses Rosser--Schoenfeld's coarse prime bounds and Agrawal--Kayal--Saxena primality testing. Certificate size and modular gate evaluation are polynomial; a bounded audit found an escaping prime for 1,812 nonzero sample outputs.
Limitations
- The certificate proves nonzeroness; zero instances do not have the same kind of modulus witness.