# What is the meaning of $F_{p^k}$ and the elliptic curve over it, $E(F_{p^k})$?

In pairing based cryptography, there will be the finite field $$F_{p^k}$$ where $$p$$ is prime number and $$k$$ is an integer. The elliptic curve is constructed on that finite field as $$E(F_{p^k})$$.

For example, let $$E$$ be an elliptic curve $$Y^2 = X^3 + aX + b$$ over $$F_{q^k}$$. What is the meaning of $$F_{q^k}$$ here? I only understand prime fields ($$F_q$$ where q is a prime number).

• There is an introduction in Wikipedia about Finite Fields, and this is a wide subject ( there are already 4K questions in math.se about it. If you are going to learn about more Finite Field, you should take a course or read a book about it. Nov 1 at 15:04

A finite field $$(\mathbb F,+,\cdot)$$ is a finite set $$\mathbb F$$ with two internal laws $$+$$ and $$\cdot$$, such that $$(\mathbb F,+)$$ is a commutative group with neutral noted $$0$$, and $$(\mathbb F-\{0\},\cdot)$$ is a commutative group with neutral noted $$1$$, and multiplication is distributive w.r.t. addition that is $$\forall A,B,C\in\mathbb F$$ it holds $$A\cdot(B+C)=(A\cdot B)+(A\cdot C)$$.

It can be shown that all finite fields with the same number of elements are isomorphic, that is we can map from one to another by a bijection $$\mathcal F$$ such that $$\mathcal F(A+B)=\mathcal F(A)+\mathcal F(B)$$ and $$\mathcal F(A\cdot B)=\mathcal F(A)\cdot \mathcal F(B)$$. We can thus talk about the finite field $$\mathbb F$$ with $$q$$ elements. It's often noted $$\mathbb F_q$$.

It can be shown that any finite field has a number $$q$$ of elements of the form $$q=p^k$$ for some prime $$p$$ and some $$k\in\mathbb N^*$$.

When $$k=1$$, the field $$(\mathbb F_p,+,\cdot)$$ is simply the ring of integers modulo $$p$$, that is $$(\mathbb Z_p,+,\cdot)$$.

For arbitrary $$k\in\mathbb N^*$$, we can think of the field $$(\mathbb F_{p^k},+,\cdot)$$ as the set of polynomials of degree up to $$k-1$$ and coefficients in $$\mathbb Z_p$$. That is, polynomials for an abstract variable $$x$$ with one coefficient in $$\mathbb Z_p$$ for each of the $$k$$ terms $$x^i$$ with $$i\in\{0,1\ldots,k-1\}$$. Addition in $$\mathbb F_{p^k}$$ is addition of polynomials. Multiplication in $$\mathbb F_{p^k}$$ is multiplication of polynomials followed by reduction modulo a particular reduction polynomial $$R(x)$$ of degree exactly $$k$$, and irreducible.

Equivalently, we can think of $$\mathbb F_{p^k}$$ as the set of $$p^k$$ tuples of $$k$$ elements of $$\mathbb Z_p$$, noted $$(a_0,a_1\ldots,a_{k-1})$$. Addition is defined by$$(a_0,a_1\ldots,a_{k-1})+(b_0,b_1\ldots,b_{k-1})=(a_0+b_0,a_1+b_1\ldots,a_{k-1}+b_{k-1})$$with the later additions carried in $$\mathbb Z_p$$, that is with reduction modulo $$p$$. If the tuple $$A$$ has $$a_i=1$$ and all the other terms $$0$$, and the tuple $$B$$ has $$b_j=1$$ and all the other terms $$0$$, then when $$i+j the tuple $$C$$ for $$A\cdot B$$ has $$c_{i+j}=1$$ and all the other terms $$0$$. When $$i+j=k$$, the tuple $$C$$ for $$A\cdot B$$ is a constant tuple $$(r_0,r_1,\ldots,r_{k-1})$$ independent of $$i$$ and $$j=k-i$$. That tuple is such that the polynomial $$R(x)=x^k-r_{k-1}\,x^{k-1}\ldots-r_1\,x-r_0$$ with coefficients in $$\mathbb Z_p$$ is irreducible, implying $$r_0\ne0$$. This constant tuple $$(r_0,r_1\ldots,r_{k-1})$$, or equivalently the polynomial $$R(x)$$, combined with the previously stated rules and properties of $$+$$ and $$\cdot$$, fully defines multiplication, and it's neutral $$(1,0\ldots,0)$$.

We can compute the tuple $$(c_0,c_1\ldots,c_{k-1})$$ for $$(a_0,a_1\ldots,a_{k-1})\cdot(b_0,b_1\ldots,b_{k-1})$$ as follows:

• $$(c_0,c_1\ldots,c_{k-1}):=(0,0\ldots,0)$$

• for $$i$$ from $$k-1$$ down to $$0$$

• $$m:=c_{k-1}$$
• for $$j$$ from $$k-1$$ down to $$1$$
• $$c_j:=m\cdot r_j+a_i\cdot b_j+c_{j-1}$$
• $$c_0:=m\cdot r_0+a_i\cdot b_0$$

with the computations in the last two lines carried in $$\mathbb Z_p$$, that is modulo $$p$$.

• I just want to add a small point: in the context of pairing based cryptography, the $k$ is usually the embedding degree. I.e. it's the smallest $k$ such that $n | q^k-1$ where $n$ is the number of points in the elliptic curve group. It's important to choose curves with small values of $k$ otherwise pairings are too expensive to compute. Nov 2 at 16:22

You can consider it's $$F_q[X]/(P(X))$$ with $$P$$ an irreducible polynomial of degree $$k$$ in $$F_q[X]$$.

It means the elements of the field can be seen are polynomials and when you do an addition or a multiplication, you are computing it modulo $$P$$.

Toy example: Let suppose $$q=2=k$$. We can take $$P=X^2 + X + 1$$ which is irreducible in $$\mathbb{Z}_2$$.

All elements are of the form: $$\alpha_0 + \alpha_1 X$$.

Let $$\alpha_0 + \alpha_1 X, \beta_0 + \beta_1 X$$ two elements of the field. $$\alpha_0 + \alpha_1 X + \beta_0 + \beta_1 X= (\alpha_0 + \beta_0) + (\alpha_1 + \beta_1) X$$

$$(\alpha_0 + \alpha_1 X) \cdot (\beta_0 + \beta_1 X)= (\alpha_0\beta_0) + (\alpha_1\beta_0 + \alpha_0\beta_1) X + \alpha_1\beta_1X^2$$. And because $$X^2 =X +1$$, it's equal to $$(\alpha_0 + \alpha_1 X) \cdot (\beta_0 + \beta_1 X)= (\alpha_0\beta_0+ \alpha_1\beta_1) + (\alpha_1\beta_0 + \alpha_0\beta_1 + \alpha_1\beta_1) X$$.

To compute the invert of $$(\alpha_0 + \alpha_1 X)$$, we have to solve the system: $$(\alpha_0x_0+ \alpha_1x_1)=1$$ and $$(\alpha_1x_0 + (\alpha_0+ \alpha_1)x_1)=0$$.

• Thank you, can you give an example that can simply explain $F_{q}[X]$ Nov 1 at 10:58
• @xiaojiuwo Is it clearer? Nov 1 at 11:09