# How to find second subgroup for ECC Pairing?

Pretty new to ECC Pairings. I am trying to understand KZG Commitments from multiple sources. I found this blog beginner friendly and easier to understand. However, I'm stuck at ECC Pairings and having difficulty in order to completely understand it.

The blog mentioned:

• Input: 2 points ($$P$$ and $$Q$$) on 2 subgroups of the same curve ($$\mathbb{G}_1$$ and $$\mathbb{G}_2$$).
• $$\mathbb{G}_1$$ is a subgroup of points for the elliptic curve, which in the form $$y^2 = x^3 + b$$, and both $$x$$ and $$y$$ are simple integers ($$x,y ∈ F_p$$ )
• $$\mathbb{G}_2$$ is another subgroup of points for the same elliptic curve above (points satisfy the same equation as $$\mathbb{G}_1$$), but both $$x$$ and $$y$$ are elements of supercharged complex numbers ($$x,y ∈ F_{p^{12}}$$ ). $$x$$ and $$y$$ are in the format of $$w^{12} - 18 * w^6 + 82 = 0$$

I didn't understand how we can find generator for the second group $$\mathbb{G}_2$$ and why we need an extension field of $$F_{p^{12}}$$. Can you please help me understand with a simple example?

The generator for $$G_1$$ is point $$P$$ on Elliptic Curve $$E(F_p)$$. Assume the order of $$P$$ is $$m$$.

You have to find the smallest positive integer $$k$$ such that

$$p^k \equiv 1 \bmod m$$

$$k$$ is called as the embedding degree of the curve $$E(F_p)$$ with respect to $$m$$.

$$k$$ in your example is $$12$$

The point $$P \in E(F_p)$$ which satisfies $$mP=\mathcal O$$ is called a $$m$$-torsion point. The subgroup of all $$m$$-torsion points in $$E(F_p)$$ is called the $$m$$-torsion subgroup of $$F_p$$ & is denoted by $$E(F_p)[m]=\{P\in E:mP=\mathcal O\}$$. $$G_1$$ is this subgroup & $$P$$ is the generator.

Now since the extension field $$F_{p^k}$$ is bigger than $$F_p$$, $$E(F_{p^k})$$ may contain more $$m$$-torsion points than $$E(F_p)$$ (Note - $$k$$ is the embedding degree wrt $$m$$).

The biggest $$m$$-torsion group is found in the extension field $$F_{p^k}$$ i.e. going to a bigger extension field than $$F_{p^k}$$ doesn’t add any more m-torsion points. $$E(F_{p^k})[m]$$ is called the full $$m$$-torsion group.

• Next you have to compute the order of the elliptic curve of $$F_{p^k}$$. Let it be $$n$$.

i.e. $$n = \#E(F_{p^k})$$

Since the $$m$$-Torsion group of $$E(F_p)$$ is a subgroup of $$E(F_{p^k})$$, $$m$$ divides $$n$$ as per Lagrange’s Theorem.

• Choose a random point $$R \in E(F_{p^k})$$ such that $$R \notin E(F_p)$$

• Calculate $$Q=(\frac{n}{m})R$$. If $$Q= \mathcal O$$, then go back to previous step & chose another random point $$R$$. If it’s not $$\mathcal O$$, then it’s a point of order $$m$$ like shown below

$$Q = (\frac {n}{m}) R$$

So $$mQ = nR$$

Let $$r$$ be the order of $$R$$. By Lagrange’s Theorem, $$r$$ divides the order of $$E(F_{p^k})$$. i.e. $$r$$ divides $$n$$. So $$n$$ can be written as $$n=dr$$ for some $$d$$.

So $$mQ= drR$$.

Since $$rR = \mathcal O$$, $$drR = \mathcal O$$

So $$mQ = \mathcal O$$.

So the order of $$Q$$ is $$m$$. Let's call this subgroup of order $$m$$ as $$G_2$$. $$Q$$ is the generator for the subgroup $$G_2$$

The above is how you find the right extension field, the 2nd subgroup, the generator for the 2nd subgroup in a Weil Pairing.

You can read about Pairings, Weil Pairings, Embedding Degree etc from any Elliptic Curve text which covers pairings

• Mathematical Cryptography by Silverman et al

• Guide to Elliptic Curve Cryptography by Menezes, Vanstone et al

• Elliptic Curves by Lawrence Washington