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?
