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?


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

  • $\begingroup$ 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. $\endgroup$ – Peter Oct 26 '16 at 11:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.