-----BEGIN PGP SIGNED MESSAGE----- Well, I'm the person posting all the number theory stuff anonymously. Well, not too anonymously since I am signing each post... ;) I thought I'd try out Matt Ghio's service. I'm not sure exactly what will happen, but hopefully you will able to reply to this message and reach me! Anyway, I got my copy of "Elementary Number Theory and its Applications" by Kenneth Rosen just now, and checked Miller-Rabin primality testing, and pseudoprime primality testing. Eric pointed out some recent work (by Pomerance I presume) and it does indeed junk the notion that for pseudoprime testing, the failure rate is 2^-n, n being the number of trials. However, Miller-Rabin isn't susceptible (it uses strong pseudoprime testing) - and what it even better is the latest bound is 4^-k! That is, if you pick k integers and perform M-R on n for each, the chance a composite will pass is less than (1/4)^k. And, there is no analogy of a Carmichael number for strong pseudoprimes. So I guess the bottom line is M-R is the way to go. -----BEGIN PGP SIGNATURE----- Version: 2.3a iQCVAgUBLas39YOA7OpLWtYzAQETVQP/YzHMudKp/ehgcG0MkBeoyhQsItAlAvXL VVj2VN2ac7KjlqtyP/Frjq+6s/T0ai4MhojboaWKBJfuUvZT1hBj0c0PvkaHVeiQ H1eJpEXEqbFoouRX/M7ZYLmwfeJenKn0th408gJBf6yDHwdv9dyo7//Hhd/GreWJ K+9nHl4k3kU= =9zRl -----END PGP SIGNATURE-----