26

Could you suggest a fast, deterministic method that is usable in practice, for testing if a large number is prime or not?

Also, I would like to know how to use non-deterministic primality tests correctly. For example, if I'm using such a method, I can be sure that a number is not prime if the output is "no", but what about the other case, when the output is "probably"? Do I have to test for primality manually in this case?

Thanks in advance.

Improve this question
1

3 Answers 3

Reset to default
12

The only deterministic, polynomial-time algorithm for primality testing I know of is the AKS primality test (http://en.wikipedia.org/wiki/AKS_primality_test). However, there are a lot of very good randomized primality tests that are fast and have extremely good probability of success. They usually work by finding whether the number is composite with exponentially good probability, so they'll either report that the number is composite or will require you to say "maybe" with very good confidence.

Improve this answer
5
  • 2
    When we say "with very good confidence", does it mean that the probability of getting a wrong output because of a system malfunction is higher than the probability of the algorithm producing the wrong answer? :-)
    – user500944
    Dec 20, 2010 at 20:42
  • 1
    @Grigory it depends on the algorithm you're using. Some will even allow you to specify your chances. Test ~50%, 75%, 90%, etc. The AKS that he specified will answer correctly 100% of the time, assuming it's coded correctly.
    – Mike M.
    Dec 20, 2010 at 20:45
  • @Grigory: "system malfunction"? Probabilities are involved because a "correct" algorithm would be slow, so you can check a much smaller set of values that would give you say 99.9% probability of right answer. What do you think non-deterministic term you've used means?
    – ruslik
    Dec 20, 2010 at 20:48
  • 5
    @ruslik: Grigory is essentially correct, you can set the "confidence" level of the probabilistic primality test so that the probability of a false positive -- declaring a number prime when it is in fact composite -- is so low that you are more likely to get a false positive from a system malfunction (e.g. a failed memory bit or register bit) than from the primality test.
    – President James K. Polk
    Dec 21, 2010 at 1:38
  • 1
    The question asks for the most efficient algorithm usable in practice - the AKS test is not usable in practice.
    – kaya3
    Apr 20, 2020 at 2:21
9

"Probably" actually means 1-ε, and ε gets as small as you need.

Most applications have some small yet nonzero probability of failing that is not connected to primality testing, for example

  • in cryptographic applications, an attacker luckily guessing the secret with, for example, a probability of 2^(-100)

  • a hardware failure (radiation-induced) randomly flipping some bit of your computer memory (maybe one that holds the output of your "deterministic" primality test

  • bugs (indeed, more probable than the other type of failures)

So pressing the ε to that order of magnitude will suffice in practice.

For example, OpenSSL, GnuPG of use non-deterministic primality test only. ``Probably'' you don't really want no deterministic test. But check what is available to you: If you have any libraries at hand, and they perform enough - go on and use them.

Improve this answer
3

If you're looking to find a random prime for use in RSA keys, you should use a probabilistic test initially. If the probability is high enough for your needs then stop there. If you must be certain, then once you find a large random probable-prime, verify it with AKS or another non-probabilistic test. This lets you check a lot of non-primes quickly while being certain when you think you've found one.

If you're trying to verify a specific existing number is prime then you should use one of the tests that answers with certainty. There are other non-polynomial-time tests too, use the one that is fastest in practice.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.