This paper presents a new probabilistie primality test. Upon termination the test outputs "composite" or "prime", along with a short proof of correctness, which can be verified in deterministic polynomial time. The test is different from the tests of Miller [M], Solovay-Strassen [SSI, and Rabin [R] in that its assertions of primality are certain, rather than being correct with high probability or dependent on an unproven assumption.
No takes yet. Share an insight, caveat, or question.
Goldwasser et al. (1986) studied this question.
Synapse has enriched 2 closely related papers on similar clinical questions. Consider them for comparative context: