Typical probabilistic primality test (e.g. Miller-Rabin) tend to give definite outcome in case of composite number and iffy outcome in case of a prime number.
Are there iterated primality tests with the reverse propery, i.e. they either give definite answer that the number is prime or invite doing more iterations, and too many iterations means that the number is highly likely composite?
| Test | Outcome if number is prime | Outcome if number is composite |
|---|---|---|
| Typical test | Too many iterations | Likely a certificate of compositeness |
| ? | Likely a certificate of primeness | Too many iterations |
For a test to be good, probability of discerning primes from composites should approach 1 as number of iterations approach infinity, so trivial tests that check if a number is a particular class of known primes should not be considered good.