Proof of Lehmann's primality test

Question

I'm struggling to understand the details in the proof of Lehmann's primality test (Algorithm2 in the link).

Explanations, and a more incremental walkthrough in general would be very appreciated.

There are 2 Lemmas that the proof is based on:

Lemma 1:

1. First of all, why does it follow from the CRT that $ x\equiv a ~ (m_1) , x \equiv 1 ~ (m_2) $ ?

2. Second, if $ m=p^{\alpha} ,~ \alpha > 1$ then why is the order of the group $p^{\alpha - 1}\cdot (p-1)$ ?

3. Third, in theorem 1- the image of $f_{m-1, m}$ by definition of $f$ is simply $\\{a^{m-1}\\}$. They say that if it was the trivial subgroup (identity element only) then $p$ would divide $m-1$. I guess that's true because it would mean that the exponent of $a$ divides the order of the group, but I'm not sure why this completes the proof?

Lemma 2:

If the image of $f$ isn't contained in $G_3$ then there are some elements outside of $G_3$ that belong to $Im(f)$.

I understand that $G_3 \cap Im(f)$ is a subgroup of $Im(f)$, however why does it imply that half the elements of $Im(f)$ being in $Im(f) - G_3$ ?

Now, I understand the last claim about the kernel, however - how does this complete the proof, or even relevant to the statement we're trying to prove?

Many thanks in advance.

Answer 1

why does it follow from the CRT that $ x\equiv a \pmod{m_1}$ and $x \equiv 1 \pmod{m_2}$ ?

The CRT states that the reduction map $\Delta: \mathbf Z/m\mathbf Z \rightarrow \mathbf Z/m_1\mathbf Z \times \mathbf Z/m_2\mathbf Z$ is a bijection. The element $x$ in this proof was defined as the unique element such that $\Delta(x) = (a, 1)$.

EDIT: Why is this $x$ convenient? That's because $$\Delta(x^n) = (a^n, 1) = (-1, 1).$$ Since $-1 \neq 1$ in $\mathbf Z/m_1\mathbf Z$ or $\mathbf Z/m_2\mathbf Z$, we must have $x^n \not\equiv \pm 1 \pmod m$. Note that here, I'm assuming that $m$ is odd. That's only stated in theorem 1, but lemma 1 is false otherwise. For instance, the image of $f_{3, 6}$ or $f_{2, 10}$ is $\{\pm 1\}$.

if $ m=p^{\alpha}$ and $\alpha > 1$, then why is $|(\mathbf Z/m\mathbf Z)^\times| = p^{\alpha - 1}(p-1)$ ?

Recall that the class of an integer $x$ is invertible in the ring $\mathbf Z/m\mathbf Z$ iff $\gcd(x, m) = 1$. Therefore, $|(\mathbf Z/m\mathbf Z)^\times| = \phi(m)$, where $\phi$ is Euler's totient function. If you can't remember how to compute it, here's a quick argument. When $m = p^\alpha$, we are looking for integers that are not divisible by $p$. The nonnegative integers less than $p^\alpha$ that are divisible by $p$ are $$0,~ p,~ 2p,~ \dots,~ (p^{\alpha - 1} - 1)p,$$ so $$\phi(p^\alpha) = p^\alpha - p^{\alpha - 1} = p^{\alpha - 1}(p-1).$$

in theorem 1, the image of $f_{m-1, m}$ by definition of $f$ is simply $a^{m-1}$. They say that if it was the trivial subgroup (identity element only) then $p$ would divide $m-1$. I guess that's true because it would mean that the exponent of $a$ divides the order of the group, but I'm not sure why this completes the proof?

When you said the "exponent of $a$", did you mean the order of $a$ or the exponent of the group? The way I understood the argument in the proof was as follows:

The author is trying to show that the image of $f_{(m -1)/2, m}$ cannot be $\{\pm 1\}$ when $m = p^\alpha$, for some $\alpha > 1$. Since $$f_{m-1, m}(a) = (f_{(m-1)/2, m}(a))^2,$$ it suffices to show that the image of $f_{m - 1, m}$ is not trivial. Assume for a contradiction that $f_{m -1, m}$ has trivial image. Since $p$ divides $\phi(p^\alpha)$ and $(\mathbf Z/p^\alpha \mathbf Z)^\times$ is cyclic, there exists an element $a \in (\mathbf Z/p^\alpha\mathbf Z)^\times$ of order $p$. Since we assumed that $f_{m -1, m}$ has trivial image, we have $a^{m - 1} = 1$, implying that the order of $a$, which is $p$, must divide $m - 1 = p^\alpha - 1$ but that's not possible.

Note that, when $m$ is not a prime power, lemma 1 guarantees that the image of $f_{(m-1)/2, m}$ is not $\{\pm 1\}$.

I understand that $G_3 \cap Im(f)$ is a subgroup of $Im(f)$, however why does it imply that half the elements of $Im(f)$ being in $Im(f) - G_3$ ?

Let $H = G_3 \cap Im(f)$. Since $H \neq Im(f)$, it has index $j \geq 2$ in $Im(f)$, and there exist $$(j-1)|H| = \left(1 - \frac 1 j\right)|Im(f)|$$ elements in $Im(f)$ that are not in $H$. That's at least $|Im(f)|/2$ elements that are not in $G_3$.

Now, I understand the last claim about the kernel, however - how does this complete the proof, or even relevant to the statement we're trying to prove?

Let $k$ be as in their proof. We have a total of $k|Im(f)|$ elements in $G_1$. Let $S = Im(f) - G_3$. Then, $$|f^{-1}(S)| = k|S| \geq k~ \frac{|Im(f)|}{2} = \frac{|G_1|}{2}.$$

EDIT: answering your question in the comment:

To be specific, the part that if all $k$ elements we sampled are $-1$ or $1$ (and one of them is $-1$), then [$m$ is prime] with probability [at least] $1 - 2^{-k}$.

Specialize lemma 2 to the case when $G_1 = G_2 = (\mathbf Z/ m \mathbf Z)^\times$, $f = f_{(m-1)/2, m}$ and $G_3 = \{\pm 1\}$. By theorem 1 and the comment right after it, $m$ is not prime iff the image of $f$ is not contained in $G_3 = \{\pm 1\}$, in which case at least half the elements of $G_1 = (\mathbf Z/ m \mathbf Z)^\times$ are not taken to $\{\pm 1\}$ under $f$.