[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
number theory
-----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-----