I'm working through An Introduction to Mathematical Cryptography and one of the exercises asks

Suppose that we run the Miller–Rabin test N times on the integer n and that it fails to prove that n is composite. Show that the probability that n is prime satisfies (approximately)

Pr($n$ is prime $\mid$ the Miller–Rabin test fails $N$ times) $\geq 1 − \frac{ln(n)}{4^N}$.

This is assuming that the Miller-Rabin test is 75% accurate and that the probability $n$ is prime is $\frac{1}{ln(n)}$. I think by "failing on a number", they mean they identify the number as prime. (Fail to identify it as composite.)

Based on the assumptions, I find the following:

Let $n$ be "$n$ is prime" and $N$ be "The Miller-Rabin test fails $N$ times". Because the test always fails on a prime, $P(N \mid n)=1$. $P(n)=\frac{1}{ln(n)}$ as above, and $P(N \mid n^c)=(\frac{1}{4})^N$ because the test identifies a composite as prime $\frac{1}{4}$ of the time.

From this, I can use the fact that $P(n \mid N)=\frac{P(N \mid n)P(n)}{P(N \mid n)P(n) + P(N \mid n^c)P(n^c)}$ to find

$$ P(n \mid N)=\frac{\frac{1}{ln(n)}}{\frac{1}{ln(n)} + (\frac{1}{4^N})(1-\frac{1}{ln(n)})}\\ =\frac{\frac{1}{ln(n)}}{\frac{1}{ln(n)} + \frac{1}{4^N}-\frac{1}{4^Nln(n)}}\\ =\frac{\frac{4^N}{ln(n)}}{\frac{4^N}{ln(n)} + 1-\frac{1}{ln(n)}}\\ =\frac{4^N}{4^N + ln(n)-1}\\ $$

But that doesn't seem to get me anywhere. What am I missing here?


Just one step more, your last expression is

$$\frac{4^N}{4^N +\ln(n)-1}=1-\frac{\ln n -1}{4^N+\ln n -1}\geq 1-\frac{\ln n -1}{4^N}\geq 1-\frac{\ln n}{4^N}.$$

| improve this answer | |

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.