1
$\begingroup$

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).

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – kelalaka
    Nov 1 at 15:04
1
$\begingroup$

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<k$ 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$.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – user82867
    Nov 2 at 16:22
3
$\begingroup$

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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.