3

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?

user93353
  • 466
  • 2
  • 18
  • You seem to be a bit confused about a few things. And also you are using $k$ for two different purposes. The $k$th roots of unity that emerges as values of the Weil pairing are elements of an extension field $\Bbb{F}p[\mu_k]$. For them to exist, we need that $p\nmid k$. In that case $\mu_k\subseteq \Bbb{F}{p^\ell}$, where $\ell$ is the (multiplicative) order of (the coset of) $p$ modulo $k$. – Jyrki Lahtonen Nov 02 '22 at 12:55
  • It then follows that the full $k$-torsion $E(\overline{\Bbb{F}p})[k]$ has coordinates in the field $\Bbb{F}{p^\ell}$. To understand the arithmetic in $\Bbb{F}{p^\ell}$ you need an irreducible polynomial $f(x)\in\Bbb{F}_p[x]$ of degree $\ell$, and then you can construct the field as the quotient ring $$\Bbb{F}{p^\ell}\simeq \Bbb{F}_{p}[x]/\langle f(x)\rangle.$$ In other words you multiply polynomials modulo $f(x)$, and then reduce their coefficients modulo $p$. – Jyrki Lahtonen Nov 02 '22 at 13:01
  • I advice strongly against thinking about $\Bbb{Z}_q$ here, because then you are likely to commit sins like do addition/multiplication modulo $q$, which is very wrong. When I used to implement finite fields with $q=2^\ell$ I also did use bitstrings to store the elements, but that was only because I knew how to interpret them. Addition is bitwise XOR rather than addition modulo $q$ etc. That won't be so simple when $p>2$. – Jyrki Lahtonen Nov 02 '22 at 13:04
  • @JyrkiLahtonen - re $\Bbb{F}{p^\ell}\simeq \Bbb{F}{p}[x]/\langle f(x)\rangle$ - so the extension field which contains the roots of unity is actually a field which isomorphic to $\Bbb{F}{p^\ell}$ rather than $\Bbb{F}{p^\ell}$ itself?. That actually answers one of my questions - `So is the group of kth roots of unity actually a group which is isomorphic to $F_{p^k}$. – user93353 Nov 02 '22 at 15:01
  • @JyrkiLahtonen - I have corrected the usage of k - please let me know if it's correct. I have also reworded my question considerably. Does it make sense now? – user93353 Nov 03 '22 at 08:18

1 Answers1

3

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.

Jyrki Lahtonen
  • 133,153
  • Wow! This is a beautiful answer. I understood the gist of your answer, but I may need a few days or more to drill down all the details. So I will mark it accepted only after that, so please don't mind that. Also, I am not a student, I am doing this for fun(?). I have already had some fun(?) with basics of EC, so I understand how the group operations on EC works. – user93353 Nov 03 '22 at 09:37
  • Also, I am not interested in divisors etc to construct the pairing as it's really too complex for me - I am regarding that as a black box. – user93353 Nov 03 '22 at 09:39
  • Oops. There were wrong $y$-coordinates matched with $x=\alpha$ and $x=\alpha+1$ in the example over $\Bbb{F}_4$. – Jyrki Lahtonen Nov 04 '22 at 04:10