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?).


Your Answer

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

Browse other questions tagged or ask your own question.