The Weil Pairing maps 2 points from the $m$-torsion subgroup of an Elliptic Curve over a Finite Field to an extension field of the Finite Field.
Let $E$ be an elliptic curve over $F_p$ where $p$ is prime. Let $k$ be the embedding degree of the curve with respect to $m$. So the Weil pairing is a map from $E(F_p)$ to a subgroup of the multiplicative group of $F_{p^k}$.
Let $G$ be the group of all mth roots of unity. If $m$ does not divide $p-1$, it's possible to contruct the Weil Pairing which is a map $e_m$ such that $e_m(P, Q) \mapsto G$
$G$ is a unique subgroup of $F_{p^k}$.
My understanding of extension fields is as below.
An extension field $F_p^k$ with $k \ge 2$ would be such that the elements would be the polynomials in $F_p[z]$ each of degree less than $k$.
$F_{p^k} = \lbrace a_{k−1}z^{k−1} +a_{k−2}z^{k−2} + ···+a_{2}z^2 +a_{1}z +a_0 : a_i ∈ Fp \rbrace$.
I don't see any complex numbers in the extension field. So I am unable to understand how the group of all mth roots of unity is a subgroup of the extension field $F_{p^k}$
The roots of unity are $\in \mathbb C$. You can add complex numbers to a Ring $\mathbb R$ by having a ring extension $\mathbb R[i]$. I don't understand how complex numbers exist in $F_{p^k}$.
So is the group of mth roots of unity actually a group which is isomorphic to a subgroup of $F_{p^k}$? Or does $F_{p^k}$ actually contain complex numbers? If the group of mth roots (i.e. $G$) is only isomorphic to a subgroup & not an actual subgroup of $F_{p^k}$, then which subgroup of $F_{p^k}$ is it isomorphic to?
Best Answer
The main confusion seems to be that you think there is only one kind of roots of unity, namely the complex ones. You need to dispose of this idea.
Depending on how familiar you are with the language and concepts of abstract algebra, my answer may become progressively more difficult to follow towards the end. Posting it anyway with the hope that it will get you started.
The multiplicative group of the field $\Bbb{F}_{p^k}$ has $p^k-1$ elements. By Lagrange's theorem from the first course covering algebraic structures this means that every non-zero element $z\in\Bbb{F}_{p^k}$ satisfies the equation $z^{p^k-1}=1$. This means that $z$ is a root of unity of order that is some factor of $p^k-1$. In other words, a root of unity is an element $z$ of any field with the property that $z^m=1$ for some integer $m>1$.
You seem to have a particular interest on elliptic curves and their torsion subgroups. In order to add some meat to this post let me discuss, as a toy example, the elliptic curve $E$ $$ y^2+y=x^3+1 $$ defined over the smallest field $\Bbb{F}_2$. Quick testing shows that the curve has three points with coordinates in $\Bbb{F}_2$, namely the points $(1,0)$, $(1,1)$ and the point $O$ at $\infty$. As the only group with three elements is cyclic, it follows that under the EC addition $E(\Bbb{F}_2)\simeq C_3$. Let's make the further observations:
So the first kind of torsion we meet with the curve $E$ is 3-torsion. Unfortunately the group $E(\Bbb{F}_2)$ is cyclic, so the Weil pairing on $E(\Bbb{F}_2)$ is trivial. This is because we always have $e(P,P)=1$ and $e(P,[2]P)=e(P,P)^2$. To get a non-trivial Weil pairing on the 3-torsion of $E$, we need to go to an extension field. The smallest such field is $\Bbb{F}_4=\Bbb{F}_2[T]/\langle T^2+T+1\rangle$, as $T^2+T+1$ is the only irreducible quadratic polynomial in $\Bbb{F}_2[T]$. Denoting the usual coset by $\alpha=T+\langle T^2+T+1\rangle$ we end up with the description $$ \Bbb{F}_4=\{0,1,\alpha,\alpha+1\}, $$ where the addition is determined by the characteristic, and the multiplication by the minimal polynomial $T^2+T+1$, implying that $\alpha^2+\alpha+1=0$. As consequences of that relation we have $\alpha^2=\alpha+1$ and hence also $\alpha^3=\alpha^2+\alpha=2\alpha+1=1$. In particular, $\alpha$ and its square $\alpha+1$ are both third roots of unity.
By another quick count we see that the points on $E(\Bbb{F}_4)$ are, in addition to the points of $E(\Bbb{F}_2)$, the points $$(0,\alpha),\ (0,\alpha+1),\ (\alpha,0),\ (\alpha,1),\ (\alpha+1,0)\ \text{and}\ (\alpha+1,1).$$ An easy way to see this is that if $x\in\{\alpha,\alpha+1\}$, then $x^3+1=1+1=0$, and if $y\in\{\alpha,\alpha+1\}$, then $y^2+y=1$.
What about the group structure of $E(\Bbb{F}_4)$? We saw that there are altogether nine points in this group. It turns out that they are all 3-torsion! I designed this toy example to make this happen. A way to see this is the following. If $P=(x_0,y_0)\in E(\Bbb{F}_4)$, then by our duplication formula we have
Because every non-zero element $z\in\Bbb{F}_4$ satisfies the equation $z^3=1$, every element (including zero) satisfies the equation $z^4=z$. Applying this to $x_0$ and $y_0$ shows that for all $P\in E(\Bbb{F}_4)$ we have $$[2]P=-P.$$ Therefore $[3]P=0$ for all $P\in E(\Bbb{F}_4)$.
It follows that the $E(\Bbb{F}_4)$ is exactly the 3-torsion subgroup of $E(\overline{\Bbb{F}_2})$. So there we get a non-trivial Weil pairing.
If you extend the field further then (proving these requires more work):
I have not included example calculations of Weil pairing. The reason is that I recall having seen at least two different definitions. And, as those calculations quickly become a bit involved, I don't want to pick one and then learn that you are using a different one. Feel free to try your hand at calculating a few on $E(\Bbb{F}_4)$. You will be needing the addition formula also. Consult your course notes for that.