## 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$$.

Ben Lynn blynn@cs.stanford.edu 💡