[pycrypto] Distribution of prime numbers?

don at amberfisharts.com don at amberfisharts.com
Mon Oct 26 03:37:32 CST 2009


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:


More information about the pycrypto mailing list