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
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 > 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
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]\).