# Questions about a proof of the error-bound of the Miller-Rabin-Test

I am trying to understand a proof (from the German book "Einführung in die Kryptografie" by Johannes Buchmann) that there are at most $$(n-1)/4$$ non-wittnesses against the primality of $$n$$ in the Miller-Rabin algorithm that are coprime to $$n$$.

The Miller-Rabin test is stated in the following way:

Let $$s = max\{r \in \mathbb{N}: 2^r \text{ divides } n-1\}$$ and $$d = (n-1)/2^s$$. If $$n$$ is a prime number and if $$a$$ is a number coprime to $$n$$ then

$$a^d \equiv 1 \text{ mod } n \text{ (A) }$$

or there is a $$r$$ in the set $$\{0,1,\ldots,s-1\}$$ sucht that

$$a^{2^rd} \equiv -1 \text{ mod } n \text{ (B) }$$

The author gives the following proof:

Let $$n \ge 3$$ be an odd composite number. We want to estimate how many numbers $$a$$ \in$$\{0,1,\ldots,s-1\}$$ exist for which $$gcd(a,n-1) = 1$$ and both $$(A)$$ and $$(B)$$ hold. If there is no such $$a$$ we are finished, so let us suppose there is such a non-wittness $$a$$. We observe that if $$a$$ fulfills $$(A)$$ then $$-a$$ fulfills $$(B)$$. Let $$k$$ be the greatest value of $$r$$ for which $$gcd(a,n) = 1$$ and $$(B)$$ holds. We set $$m = 2^kd$$.

We set the prime factorisation of $$n$$ to $$n = \prod_{p | n} p^{e(p)}$$.

The author considers the following two subgroups of $$\mathbb{Z}_n^{\times}$$

$$J = \{ a + n\mathbb{Z} : gcd(a,n) = 1 \text{ and } a^{n-1} \equiv \pm 1 \text{ mod } n\}$$

$$K = \{ a + n\mathbb{Z} : gcd(a,n) = 1 \text{ and } a^{n-1} \equiv \pm 1 \text{ mod } p^{e(p)} \text{ for all primes p such that } p | n\}$$

$$L = \{ a + n\mathbb{Z} : gcd(a,n) = 1 \text{ and } a^{m} \equiv \pm 1 \text{ mod } n\}$$

$$M = \{ a + n\mathbb{Z} : gcd(a,n) = 1 \text{ and } a^{m} \equiv 1 \text{ mod } n\}$$.

We observe that $$M \subset L \subset K \subset J \subset \mathbb{Z}_n^{\times}$$. The author claims that every non-witness is an element of $$L$$. (Why?) He aims to prove the claim by showing that the index of $$L$$ in $$\mathbb{Z}_n^{\times}$$ is at least $$4$$.

Next the author says that the index $$(K:M)$$ is a power of $$2$$. (This is now clear to me thanks to Lord Shark the Unknown's answer here.) Then he argues that the index $$(K:L)$$ is also a power of $$2$$, say $$2^j$$. If $$j \ge 2$$ we are finished. So we will now examine what happens if $$j = 1$$ and $$j = 0$$.

If $$j = 1$$ then $$n$$ has two prime divisors.(Why?) So $$n$$ is not a Carmichael number and so $$J$$ is a true subgroup of $$\mathbb{Z}_n^{\times}$$, so the index of $$J$$ in $$\mathbb{Z}_n^{\times}$$ is at least $$2$$. Since the index of $$L$$ in $$K$$ is, by definition of $$m$$, also $$2$$ the index of $$L$$ in $$\mathbb{Z}_n^{\times}$$ is at least $$4$$.

If $$j = 0$$ then $$n$$ is a real prime power.(Why?) One can verify that in this case $$J$$ has exactly $$p-1$$ elements, namely exactly the elements of the subgroup of order $$p-1$$ in the cyclic group $$\mathbb{Z}_{p^e}^{\times}$$. Thus the index of $$J$$ in $$\mathbb{Z}_{n}^{\times}$$ is at least $$4$$, excepts for $$n=9$$. If $$n=9$$ one can verify the claim directly.

I am having trouble keeping track of the central theme of this proof. Could you please explain to me what the main idea behind this prove is and clearify the passages I have marked with an (Why?).