Failure depends on how many iterations you perform (n iterations = 2^-n chance of failure) and the values of the base you choose.
As I pointed out before, this probability is not correct. The trials are not independent, so you cannot just multiply them together.
I'm familiar with two other primality testing algorithms [...]: Lucas' and Lehmer's.
For some good information on primality testing, see A Course in Computational Algebraic Number Theory by Henri Cohen Chapter 9 is titled "Modern Primality Tests". I give you fair warning that you will not be able to understand this without significant effort. The Pocklington-Lehmer primality test is in Chapter 8 "Factoring in the Dark Ages". There's a very interesting result stated here, "There exists a probabilistic polynomial time algorithm which can prove or disprove that a given number N is prime". The result is by Adleman and Huang. (Yes, _that_ Adleman.) And for purposes of cultural literacy, the names are the Jacobi sum test, the elliptic curve tests, Goldwasser-Kilian, and Atkin (a development on G-K). Eric