Balasubramanian-Koblitz Theorem

We show that the Weil and Tate pairing are interchangeable for elliptic curves for embedding degrees greater than 1.

Theorem: Let $E$ be an elliptic curve defined over $\mathbb{F}_q$ and suppose $r$ is a prime dividing $N = \#E(\mathbb{F}_q)$, and that $r$ does not divide $q - 1$. Then $E(\mathbb{F}_{q^k})$ contains $r^2$ points of order $r$ if and only if $r$ divides $q^k - 1$.

Proof: It is well-known that if $E(\mathbb{F}_{q^k})$ contains $E[r]$ then $r | q^k -1$, even without assuming $r$ divides $N$ or $r$ does not divide $q-1$.

Let $\Phi$ denote the Frobenius map. Consider the subgroup $T$ of $E[r]$ consisting of all points of trace zero, that is

\[ T = \{ Q | Q \in E[r], \mathrm{tr} Q = O \} \]

The group $T$ may be explicitly constructed using the map $P \mapsto P - \Phi(P)$. Now we have $\Phi(T) = T$, and also $T$ is not contained in $E(\mathbb{F}_q)$ since we are assuming $k \gt 1$.

Hence $T$ is an eigenspace of $\Phi$, but not the $1$-eigenspace. Since the eigenvalues of $\Phi$ are $1$ and $q$, we see that $T$ must be the $q$-eigenspace of $\Phi$ and hence

\[ \Phi^k(Q) = q^k Q = Q \]

since $r | q^k - 1$. Thus $T$, like $E(\mathbb{F}_q)$ is fixed under $\Phi^k$, and since these groups are linearly independent they generate all of $E[r]$, implying that all of $E[r]$ is fixed under $\Phi^k$. Hence $E[r] \subset E(\mathbb{F}_{q^k})$∎

Example

Here is a curve where the Tate pairing can be used but the Weil pairing cannot. Let $r = 3$. Let $E$ over $\mathbb{F}_{19}$ be given by $Y^2 = X^3 + X + 6$. We may use the Tate pairing since $\mathbb{F}_{19}$ contains the cube roots of unity. However, the group of points of $E(\mathbb{F}_{19})$ is a cyclic group of order 18, so the Weil pairing cannot be used. It turns out that we must go to $\mathbb{F}_{19^3}$ to get all of $E[3]$.