Every Prime Has a Succinct Certificate

To prove that a number n is composite, it suffices to exhibit the working for the multiplication of a pair of factors. This working, represented as af string, is of length bounded by a polynomial in log ₂ n. We show that the same property holds for the primes. It is noteworthy that almost no other set is known to have the property that short proofs for membership or nonmembership exist for all candidates without being known to have the property that such proofs are easy to come by. It remains an open problem whether a prime n can be recognized in only log ₂^α n operations of a Turing machine for any fixed α. The proof system used for certifying primes is as follows. Axiom. $(x,y,1)$. Inference Rules. \[ R_1 :(p,x,a),q (p,x,qa) x(p - 1)/q ≡ 1( p) and q | (p - 1). \]\[ R_2 :(p,x,p - 1) p xp - 1 ≡ 1( p). \] Theorem 1. pis a theorem≡ pis a prime. Theorem 2. pis a theorem⊃ phas a proof of4log ₂ plines.