[pycrypto] Distribution of prime numbers?
don at amberfisharts.com
don at amberfisharts.com
Mon Oct 26 03:37:32 CST 2009
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
More information about the pycrypto
mailing list