[pycrypto] Distribution of prime numbers?
xl269 at cam.ac.uk
Mon Oct 26 02:17:33 CST 2009
Dwayne C. Litzenberger wrote:
> On Sun, Oct 25, 2009 at 11:00:54PM -0400, Dwayne C. Litzenberger wrote:
>> In other words: What is the a-priori probability of a number being
>> prime *before* we conduct any primality test?
> Approximations, lower, or upper bounds are all useful.
> I'm under the impression that the number of Rabin-Miller iterations needed
> to establish that a certain number is probably prime depends on the answer
> to this question.
The precise formula is a millenium prize problem; see
You could probably get away with using some variant of
which is more accurate but more expensive to calculate (or so I'd imagine).
Both formulas gives the total number of primes smaller than a given number, so
you'd have to do some further tweaks to get the "a-priori probability of a
number being prime *before* we conduct any primality test?", such as dividing
by x or something.
More information about the pycrypto