1
$\begingroup$

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

$\endgroup$

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.