How do I quickly generate a random prime number, that is for sure 1024 bit long?
+20
A:
Use a library function, such as OpenSSL. There's no need to write this yourself.
Mark Byers
2009-11-20 10:47:28
+2
A:
To trade memory for speed you could just generate them and store them in a list and then randomly pick one.
Edit: Naturally you can't generate them all so the best you could achieve is pseudo randomness at a high memory cost. Also this isn't good if you want it for security.
Jonas
2009-11-20 10:48:05
"generate them"? all of them!?!
Robin Day
2009-11-20 10:52:42
This would not be a good idea if the prime numbers are needed for security reasons, as is often the case.
Mark Byers
2009-11-20 10:53:36
Mark: Apart from the obvious problem of actually storing all 1024-digit primes, where is the problem with that? You'd be choosing a random prime anyway.
Joey
2009-11-20 11:00:11
No you're right. Edited the answer.
Jonas
2009-11-20 11:00:34
Johannes: Store them *all*? I hadn't assumed that was what Jonas meant. I assumed he meant store some small subset of them and then pick one at random. This would open a huge security hole if these primes are to be used in crypto.
Mark Byers
2009-11-20 11:08:58
+1
A:
1024 is a lot. Are you sure a pseudo-prime won't do? In java pseudo primes are a part of JDK
glebm
2009-11-20 10:50:35
-1, I think you are suggesting a probabilistic prime generator when you say pseudo prime. A pseudo prime is NOT a prime (i.e. it has divisors other than 1 and itself) although it has certain properties in common with primes, and a pseudo prime is no substitute for a prime, especially for cryptography. The fact that pseudo primes that pass probabilistic tests are rare, makes such tests good for randomly generated large numbers. But saying that the OPs needs maybe satisfied by a pseudo prime is obviously wrong. Java has a probabilistic prime check/generator, which is likely what you meant.
MAK
2009-11-20 11:19:03
+12
A:
Generate 1024 random bits. Use a random source that is strong enough for your intended purpose.
Set the highest and lowest bits to 1. This makes sure there are no leading zeros (the prime candidate is big enough) and it is not an even number (definitely not prime).
Test for primality. If it's not a prime, go back to 1.
Alternatively, use a library function that generates primes for you.
laalto
2009-11-20 10:52:32
Optionally - read up on primes distribution to assure yourself that this algorithm is feasible (i.e. won't need trillions of attempts).
Rafał Dowgird
2009-11-20 12:28:39
It won't need trillions of attempts: the density of primes is very approximately 1 in ln(x). In this case 1 in 710, but because he avoids even numbers 1 in 305. It will need trillions of trial divisions to prove it prime, unless you use a non-trivial primality test. And if you're going to need a non-trivial primality test, it's not clear to me why you wouldn't also use a non-trivial means of generating better candidates.
Steve Jessop
2009-11-20 16:55:34
Thanks, this was an initial idea. Though I wanted to know if there's a quicker solution.
gmile
2009-11-21 11:36:25
"Set the highest [and lowest] bit[s] to 1. This makes sure [there are no leading zeros] the prime candidate is big enough" - But that makes it not random, right? Doesn't this narrow down the interval of admissible values? Or is the question implicitly (I'm not expert in securty/encryption) "how to generate a 1024 bit random prime greater than 2^1023 + 1 (or greater than X)"?
d.
2010-01-21 15:37:54
True, you lose two bits-worth of randomness. So, you could start with the 1024 bits and prepend a '1' and append a '1' to make a 1026 bit number with 1024 bits of randomness. Of course that'll be a bit awkard on most machines made on this planet. In practice, no one is going to worry about losing two bits of randomness.
DarenW
2010-02-11 15:12:12