Miller-Rabin-Test : Why can we be $100\%$ certain after $4$ tests for $p=13$?

Question

I have question about a homework.

The question is:

Why can we be $100\%$ sure after $4$ tests for the special case of $p=13$?

I don't get it. I have a formula that states, that every test increases certainty by $\left(\frac14\right)^k$, where $k$ is the number of tests. So after $4$ tests I get around $99.6\%$ certainty, not $100\%.$

Answer 1

Actually your 'formula' is a statement that says that a non-prime number passes the Miller-Rabin-Test for at most 1/4 of all possible bases. That would be no more than three for the number 13. That answers your question.

Answer 2

One way of thinking about it is that your $(1/4)^k$ is if you choose $k$ bases completely at random. But if you do this it is possible that you'll randomly pick the same base more than once, and of course this isn't optimal. So you can get a slightly better probability (than $(1/4)^k$) by making sure that you don't pick the same base twice.

If $p$ is large, this doesn't make much difference, since you're very unlikely to accidentally choose the same base twice anyway. But for small $p$, making sure you choose $k$ different bases can significantly improve the probability.