[pycrypto] Distribution of prime numbers?
Ximin Luo
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
http://en.wikipedia.org/wiki/Riemann_Hypothesis#Distribution_of_prime_numbers
You could probably get away with using some variant of
http://en.wikipedia.org/wiki/Prime_number_theorem#Statement_of_the_theorem
or
http://en.wikipedia.org/wiki/Prime_number_theorem#The_prime-counting_function_in_terms_of_the_logarithmic_integral
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.
X
More information about the pycrypto
mailing list