Probabilistic Primality Tests

Question

I know most primality tests are probabilistic, but doesn't that pose a major problem to security like RSA that depend on the prime numbers always having no smaller factors? And if you can repeat the tests enough times to ensure that the number is prime, then would it be correct to say it's not probabilistic anymore?

Answer 1

If you take N random bases and the number passes the test, the probability that is composite is at most

$$\frac{1}{4^N}$$

So, if you take 100 random bases, there is no practical doubt about the primality.

In practice, it is even better.

If you take a random number N (mostly done in practice) and a random number M with 1 < M < N and the number passes the test with just this one base M, the probability, that N is composite, is vanishing small for, lets say, a 200-digit number. Look at the prime-page of Chris Caldwell under "probable prime - how probable"

Moreover, if a number passes the test for several bases, it is likely to be easy to factor (because it is a pseudoprime for several bases, likely a carmichael number).

But theoretically, the prime is not proven.

If you want to be absolutely sure, take the adleman-pomerance-rumely test which proves the primality and is feasible even for 1000-digit numbers.

Answer 2

The probability of a composite being misdetected as prime can be rendered lower than the probability of a hardware error, so for practical purposes the difference is meaningless: regardless of whether you use a probabilistic or deterministic test, the probability of error will be the probability of a hardware error.