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:
- The points $(1,0)$ and $(1,1)$ share the same $x$-coordinate, and hence are each others negatives in the group $E(\Bbb{F}_2)$.
- Going through the usual process we see that the point doubling formula on $E(\overline{\Bbb{F}_2})$ reads
$$[2](x_0,y_0)=(x_0^4,y_0^4+1).$$ Here I denote by $\overline{\Bbb{F}_2}$ an algebraic closure of $\Bbb{F}_2$ (= a smallest field that contains all the extension fields $\Bbb{F}_{2^k}$, $k$ a positive integer). Ask, if you don't know how to derive the point doubling formula.
- Using that formula we see that $[2](1,0)=(1,1)$ and $[2](1,1)=(1,0)$. Further confirming the fact that $[4](1,0)=(1,0)$, so we must have $[3](1,0)=O$, all in line with the group being cyclic of order three.
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
- $[2]P=(x_0^4,y_0^4+1)$, and
- $-P=(x_0,y_0+1)$.
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):
- The group $E(\Bbb{F}_8)$ also has nine elements. The fields $\Bbb{F}_8$ and $\Bbb{F}_4$ intersect in $\Bbb{F}_2$, so only three of those are 3-torsion. Therefore this group is cyclic of order nine. We do observe that as $8-1=7$ the field $\Bbb{F}_8$ contains seventh roots of unity.
- The group $E(\Bbb{F}_{16})$ also has nine elements Because $16-1=15=3\cdot5$, this field contains roots of unity of orders $3$, $5$ and $15$. In particular, it contains $\Bbb{F}_4$ as a subfield. In fact all the points $(x,y)\in E$ with coordinates in $\Bbb{F}_{16}$ have their coordinates in the subfield. This is very rare.
- The group $E(\Bbb{F}_{32})$ has $33$ elements. That group is necessarily cyclic. The field contains roots of unity of order $31$.
- The group $E(\Bbb{F}_{64})$ has $81$ elements. By repeatedly applying the duplication formula and using the fact that $z^{64}=z$ for every element of $\Bbb{F}_{64}$ we see that $[8]P=-P$ for every element in this group, and hence this group is the 9-torsion part of $E(\overline{\Bbb{F}_2})$. We have the required Weil pairing taking values in $\Bbb{F}_{64}$. This is because $64-1=7\cdot9$, so the field contains ninth roots of unity. Also, as $64$ is a power of $8$, the field $\Bbb{F}_{64}$ contains $\Bbb{F}_8$ as a subfield. Therefore $E(\Bbb{F}_8)$ is a subgroup of $E(\Bbb{F}_{64})$.
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.
Best Answer
I was never up to speed with pairing based attacks (caveat reader), but you seem to have some wrong impressions, so I will try and fix some of them, and share my impressions.
We fix an integer $r$. This should be selected in such a way that $E(\Bbb{F}_q)$ has quite a bit of $r$-torsion. In other words, $G_1=E[r]\cap E(\Bbb{F}_q)$ is a relatively large subgroup of $E(\Bbb{F}_q)$. I guess the normal case is that $G_1$ is cyclic of order $r$, but that is probably not strictly necessary. Furthermore, the extension degree $k$ is chosen in such a way, that the group $G_2=E[r]\cap E(\Bbb{F}_{q^k})$ is relative large. Ideally $G_2$ contains all the $r$-torsion, but that need not be strictly true. The point is that $G_2$ should be significantly larger than $G_1$. As an abstract group $G_2\simeq C_r\times C_r$ in the ideal case, but it may still be useful to use the pairing attack as long as $G_2\simeq C_r\times C_d$, where $d$ is a large divisor of $r$. Of course, if $r$ is a prime, then we need $d=r$.
The DLP problem in $G_1$ is to determine the integer $m$ such that $P=mG$, where $P$ is a given point and $G$ is the known generator referred to in the specs of the cryptosystem.
Let $e(\ ,\ )$ be the Weil pairing. It is a mapping from $E[r]\times E[r]\to \mu_r$ (from the $r$-torsion of $E$ to a subgroup of units of the extension field). Here (ideally) $E[r]=G_2$ and the group of roots of unity $\mu_r$ is a subgroup of the multiplicative group $\Bbb{F}_{q^k}$. IIRC the condition $\mu_r\le\Bbb{F}_{q^k}^*$ is a necessary condition for $E[r]$ to be contained in $E(\Bbb{F}_{q^k})$.