Java probablePrime performance

Question

Javadoc on probablePrime:

Returns a positive BigInteger that is probably prime, with the specified bitLength. The probability that a BigInteger returned by this method is composite does not exceed 2-100.

My question is, how much performance does this gain by not guaranteeing a prime number, but making it almost certain? Also, is this performance difference really worth the minute chance of a bug occurring at some time in the future? Especially if the validity of encryption depends on this number being prime.

Answer 1

At the heart of probablePrime() is a series of Miller-Rabin tests (The number of rounds performed depends on the bit size of the number) combined with a Lucas-Lehmer primality test. The time complexity of these depend quite a bit on the rest of the BigInteger implementation. Taking in "slow" estimates from wikipedia would be O(k log(n)^3) and O(log(n)^3) respectively.

On the other hand, the AKS-primality test, without unproven conjectures, can run in Õ(log(n)^6).

So assuming your numbers are large enough, the probabilistic test can be quite a bit faster than a deterministic one. For anything large enough for cryptography the asymptotic behaviour is quite likely observable. Of course, the only way to find out for certain is to implement the modified AKS and time the results.

(k is the number of cycles in Mille-Rabin).

Answer 2

If you have this:

Especially if the validity of encryption depends on this number being prime

kind of constraint then you should not use probablePrime in my opinion. Because you cannot guarantee the correctness of your algorithm.

But if the probability of getting a non-prime is so low that is comparable for example to an SHA-1 collision probability then you are OK with it. (If git is ok with it so you are)

If you are using a pool of prime numbers in a given range then you can just pre-generate a list of prime numbers and put them in a lookup table. this will give you O(1) time complexity.