How do I generate a 160 bit prime number in java?
java, primes
Solution
`BigInteger.probablePrime(160, new Random())` generates a `BigInteger` that is almost certainly prime -- the probability that it is not a prime is less than the probability that you will get struck by lightning. In general, `BigInteger` already has heavily tested and optimized primality testing operations built in.
For what it's worth, the reason this won't take forever is that by the prime number theorem, a randomly chosen n-bit number has probability proportional to 1/n of being prime, so on average you only need to try O(n) different random n-bit numbers before you'll find one that's prime.
Problem
I want to generate a 160-bit prime number in java. I know that I'll have to loop through all the 160-bit numbers and for any number `n`, I'll have to check if they are divisible by any primes less than `sqroot(n)` or by any primality test like `Miller-Rabin test`. My questions are: Is there any specific library which does this? Is there any other (better) way to do this?