primes are fairly sparse so on average you have to generate quite a few random numbers to find a single prime
The density of primes is high enough that this really isn't a big problem. The prime number theorem says that the density of primes around N is roughtly 1/ln(N). So if you want to find a k-digit prime, you should expect to find one after k tries on average. (You can of course be clever and only consider odd numbers, and then you'll find one after k/2 tries on average). So Rabin-Miller takes O(k) time on k-bit numbers, and actually finding a prime takes O(k) tries on average. That's quite a good tradeoff actually.
I'm pretty certain this is how most modern crypto software generates RSA primes (guess and then check with Rabin-Miller). No, it's not super fast, but it's quite reasonable, and you usually only have to do it once.
| [reply] |
| [reply] |
Firstly, let me explain why random generating a prime
isn't that bad.
The first reason is the same as blokhead has mentioned,
that primes aren't so rare. As he has explained, if you
pick a random 31-bit number, it's a prime with 1/21
probability.
The second reason is that even when we don't pick a prime,
in most of the cases, it is divisable with a small prime,
and in this case, the primality tester algorithm should
return false very quickly.
Note that even before the R-M test, I divide the number
with the first eight primes (this should really be the
first 50 primes in real-world applications,
but then I wouldn't get much of the R-M
algorithm here) first thing I do.
Even without those divisions, the R-M test is correct,
so they wouldn't strictly be needed,
but it really helps finding a random prime number.
As a special case, blokhead notes that you can generate
a random even number. I do this, but it doesn't help much
as the primality tests test the parity of the number anyway.
(Update: it was stupid to say that I do this as I haven't
posted the code to generate a random prime. Anyway,
here it is:
end update)
Now let's look at whether building a table of large primes
is feasable, esp as spiritway has asked this too.
There are 5 million 8-digit primes, so if we really needed
five-digit primes, so we could build a table.
However, I'd only do this if you needed five-digit primes
very often. (demerphq's original application
was a random hash seed, so I don't think he needs it that
often.)
Also, if you need 9-digit primes or even primes less then
2^31, the table gets larger and larger.
| [reply]
[d/l] |
My original requirements were for primes with 7-8 digits, or more generally, those that can be represented by a long.
testing whether it's a prime and then generating tens and hundreds more until you accidentaly tramp over a prime sounds horribly inefficient to me.
Surprisingly it doesnt take very long at all for my particular task. But you are right it isn't efficient. But efficiency in this particular case is not required at all. If the program takes a few seconds then fine, but as it is it finishes in a heartbeat.
---
$world=~s/war/peace/g
| [reply] |
I expected slightly smaller "small primes" :-) And I stand corrected regarding the sparseness of primes. Thanks, you never stop learning :-)
(For a minute I thought whether it wouldn't be better to generate just one random number and then keep subtracting/incrementing until you find a prime, so that the algorithm is garanteed to finish, but that's not a good idea. Primes are not evenly distributed so some would come up more often than others.)
Jenda
|
XML sucks. Badly. SOAP on the other hand is the most powerfull vacuum pump ever invented. |
| [reply] |