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

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\%.$

• Speaking for myself, I am 100% certain for p=13 even before your first test :) – MooS Jul 24 '17 at 13:35
• – Shaun Jul 24 '17 at 13:38

• Where does $1/4$ comes from ? (see Rabin's paper) It seems it reduces the problem to $n = p_1^{k_1} p_2^{k_2}$ and look at $x^{\phi(n)/t}$ versus $x^{n-1}$ where $t = gcd(\phi(n),n-1)$ – reuns Jul 27 '17 at 9:28
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.