-----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-----