# Deducing a bound of Miller-Rabin test

My question is somewhat the converse of this one. Basically, I want to proof that in the Miller-Rabin test the probability of passing the test given that the number n being test is not prime is bounded by $\frac{1}{4^k}$.

I found a proof in this Rabin's paper but I would like to simplify it. So you may assume the following theorem:

If more than a quarter of $b \in \mathbb{Z}_{n}^{*}$ pass Miller-Rabin test then all $b \in \mathbb{Z}_{n}^{*}$ do so.

How can I deduce the previous bound from this statement?

## 1 Answer

The theorem guarantees that at most $\frac{1}{4}$ of the bases coprime to the number $n$ (which has to be tested) pass the Miller-Rabin-test.

So, if we choose a random base, the probability that it passes the test, is at most $\frac{1}{4}$.

If we choose a random base $k$ times and the choices are independent, the probability is $p^k$, where $p$ is the probability that a single ranom base passes the test.

Since $p\le \frac{1}{4}$, we can conclude $p^k\le(\frac{1}{4})^k$.

• If we happen to choose a random base $a$ with $1<a<n$, which is NOT coprime to $n$, we have found a non-trivial factor of $n$ and do not need further tests. – Peter Oct 26 '16 at 11:49