From: nobody@jarthur.cs.hmc.edu
Date: Tue, 12 Apr 94 15:54:06 PDT
To: cypherpunks@toad.com
Subject: number theory
Message-ID: <9404122254.AA03798@toad.com>
MIME-Version: 1.0
Content-Type: text/plain


-----BEGIN PGP SIGNED MESSAGE-----

> I should point out that the standard argument that picking 'k'
> different values for 'a' and then calculating the probability as
> (1/2)^k is fallacious.  This would be true if the probabilities were
> independent, but they aren't.  There was a paper on this about five
> years ago whose awareness has not been yet widespread.  I no longer
> have the reference.

Okay, my memory has been jogged... is this a paper by Pomerance, "On
the distribution of pseudoprimes"?  He gave more precise estimates for
the number of base-2 pseudoprimes.  

With his more precise estimates, the chance of a 100 digit number
passing the base-2 pseudoprime test is about 1/10^13...

I think his work applies only to base-2 pseudoprimes, so my statement
concerning the error rate of Miller-Rabin is still correct: for s
iterations, the chance of failure is 2^-s.

-----BEGIN PGP SIGNATURE-----
Version: 2.3a

iQCUAgUBLar8xIOA7OpLWtYzAQEAmgP2NQx7a3woaZMgT5CeqOFrhqyRcYt3mAPd
9bnf+f19E4Il42e0xw9vQjOMyowB/IkATQf+//ADIFxhE9p+2MOpD8eDr9saGYOV
bVwV2/bWtzsHqjsbWRH27/5lEwFXerGfJNSc1ITkZFwp1QwpzmVvn6gkOZ2lf0AJ
/q3QneS7iw==
=2XH+
-----END PGP SIGNATURE-----