0

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.

Arthur
  • 199,419
Vi0
  • 331
  • --Maybe I've got in in reverse. I meant the test with properties opposite to Miller-Rabin (and related) tests.-- Re-checked the wiki about primality tests - they all tend to stop iterating when they think the number is composite, not when they think that the number is prime. – Vi0 Jul 16 '22 at 16:44
  • 2
    If there were such a test, it would be much more convenient than Rabin-Miller, so it would be in universal use. Therefore there is no such test. – TonyK Jul 16 '22 at 16:47
  • A composite number is usually quickly detected to be composite , but primality proofs are time consuming in general. So, there won't be such a test. – Peter Jul 16 '22 at 21:05

0 Answers0