[pycrypto] Distribution of prime numbers?

[don at amberfisharts.com]

Hi,

On Sun, 25 Oct 2009 23:40:11 -0400, "Dwayne C. Litzenberger" <dlitz at dlitz.net> 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.

I don't think so. IIRC the probability of a number n being prime after k Rabin-Miller tests is 4^-k (or 2^{-2*k} for our base2 friends) independent of the size of n. And if you trust wikipedia that is an upper bound:
http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Accuracy_of_the_test

yours
//Lorenz