Cfrgtkky

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 + nmathbb{Z} : gcd(a,n) = 1 text{ and } a^{n-1} equiv pm 1 text{ mod } n}$

$K = { a + nmathbb{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 + nmathbb{Z} : gcd(a,n) = 1 text{ and } a^{m} equiv pm 1 text{ mod } n}$

$M = { a + nmathbb{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?).