Doubt on elliptic curve over a finite field and binary representation

Question

I'm a programmer, i.e. agnostic to the mathemathics behind most of cryptographic scheme, but I'm trying to remediate. I'm writing this premise for any possible error or imprecision that I probably put in this question.

However, I'm studying Elliptic Curve and I got to Elliptic Curves over Finite fields topic. For what I understood an elliptic over a finite field $F$ are the points that fulfill the Weierstrass equation where coefficients and coordinates belongs to $F$.

So far I always thought of F as the integer modulo $p$ (with $p$ prime). Point addition, doubling must be thus performed modulo p and all the points that pop out along with the point at infinity form a cyclic group. Ok, I got this.

Now problems begin: reading some handouts that a professor of mine gave to me, I read two things that I couldn't figure out.

First, they say that the order of a finite field is always a prime power (and such a power is named extension degree that he denotes with $m$): of course I trust this result but I couldn't figure out a field of order, say, $4$, $8$, $9$ or $16$. What are examples of such fields?

Secondly, if $p=2$, $m>1$ and $q=p^m$ (binary field), they say that (I'm citing):

The elements of the a binary field of order $q=2^m$ cannot be represented as integers modulo $2^m$. A convenient way to represent them is by means of binary polynomials of degree less than m.

Why can't they be represented as integers modulo $2^m$? Any answers and/or reference is appreciated.

Answer 1

I couldn't figure out a field of order, say, 4, 8, 9 or 16. What are examples of such fields?

Let's do that with $8=2^3$.

• Elements of that field $\mathbb F_{2^3}$ will be assimilated to $3$-bit quantities, that is the set $\{\mathtt0,\mathtt1\}^3$, or equivalently polynomials of degree less than $3$ with binary coefficients, where e.g. $\mathtt{110}$ is the polynomial $x^2+x$, and $\mathtt{101}$ is the polynomial $x^2+1$.
• Our addition is bitwise exclusive-OR, or equivalently addition of polynomials, so that $\mathtt{110}\oplus\mathtt{101}=\mathtt{011}$, or equivalently $(x^2+x)+(x^2+1)=x+1$.
• For our multiplication we choose an irreducible_polynomial $P(x)$ of degree $3$ with binary coefficients (among two such polynomials, see this list of irreducible polynomials over GF(2) up to degree 11), e.g. $P(x)=x^3+x+1$; and we define multiplication as polynomial multiplication followed by reduction modulo $P(x)$. This simply tells that when in the product we get a term of degree $d\ge3$, we can get rid of it by adding the polynomial $x^{d-3}\,P(x)\ =\ x^d+x^{d-2}+x^{d-3}$. So for example $$\begin{array}{lll}(x^2+x)\,(x^2+1)&=(x^2+x)\,x^2+(x^2+x)\\ &=x^4+x^3+x^2+x\\ &\equiv(x^4+x^3+x^2+x)+(x^4+x^2+x)&\pmod{x^3+x+1}\\ &\equiv x^3&\pmod{x^3+x+1}\\ &\equiv x^3+(x^3+x+1)&\pmod{x^3+x+1}\\ &\equiv x+1&\pmod{x^3+x+1}\\ \end{array}$$ thus $\mathtt{110}\otimes\mathtt{101}=\mathtt{011}$.

The full multiplication table goes $$\begin{array}{c|cccccccc} \otimes &\mathtt{000}&\mathtt{001}&\mathtt{010}&\mathtt{011}&\mathtt{100}&\mathtt{101}&\mathtt{110}&\mathtt{111}\\ \hline \mathtt{000}&\mathtt{000}&\mathtt{000}&\mathtt{000}&\mathtt{000}&\mathtt{000}&\mathtt{000}&\mathtt{000}&\mathtt{000}\\ \mathtt{001}&\mathtt{000}&\mathtt{001}&\mathtt{010}&\mathtt{011}&\mathtt{100}&\mathtt{101}&\mathtt{110}&\mathtt{111}\\ \mathtt{010}&\mathtt{000}&\mathtt{010}&\mathtt{100}&\mathtt{110}&\mathtt{011}&\mathtt{001}&\mathtt{111}&\mathtt{101}\\ \mathtt{011}&\mathtt{000}&\mathtt{011}&\mathtt{110}&\mathtt{101}&\mathtt{111}&\mathtt{100}&\mathtt{001}&\mathtt{010}\\ \mathtt{100}&\mathtt{000}&\mathtt{100}&\mathtt{011}&\mathtt{111}&\mathtt{110}&\mathtt{010}&\mathtt{101}&\mathtt{001}\\ \mathtt{101}&\mathtt{000}&\mathtt{101}&\mathtt{001}&\mathtt{100}&\mathtt{010}&\mathtt{111}&\mathtt{011}&\mathtt{110}\\ \mathtt{110}&\mathtt{000}&\mathtt{110}&\mathtt{111}&\mathtt{001}&\mathtt{101}&\mathtt{011}&\mathtt{010}&\mathtt{100}\\ \mathtt{111}&\mathtt{000}&\mathtt{111}&\mathtt{101}&\mathtt{010}&\mathtt{001}&\mathtt{110}&\mathtt{100}&\mathtt{011}\\ \end{array}$$ The neutral for $\otimes$ is $\mathtt{001}$ that is the polynomial $1$. The distributive property and other commutative field properties follow from that for polynomials.

The elements of the a binary field of order $q=2^m$ cannot be represented as integers modulo $2^m$.

Actually it's OK to represent them as integers, and even convenient in some computer languages (perhaps our $\oplus$ is just the bitwise-XOR operator ^). But when $m>1$, addition and multiplication modulo $q=2^m$ give the ring $\mathbb Z_q$, which is essentially useless to build the field $\mathbb F_q$, for $\mathbb Z_q$'s addition and multiplication bear no relation with $\mathbb F_q$'s $\oplus$ and $\otimes$.

A convenient way to represent elements of the a binary field of order $q=2^m$ is by means of binary polynomials of degree less than $m$.

Indeed. That's what we did above.

---

Following comment

If $m=1$ then coordinates over elliptic curve are just scalars, whereas if $m>1$ then a coordinate is in its turn a "set of coordinate".

Yes, that's a useful way of seeing it. An element of the field $\mathbb F_{p^k}$ is most naturally expressed as $k$ "coordinates" each in $\{0,1\ldots,p-1\}$ when devising a general computer implementation of arithmetic in $\mathbb F_{p^k}$. The usual mathematical statement of the same thing is that such element is a polynomial of degree less than $k$, with coefficients in $\mathbb F_p==\mathbb Z_p$.

In the first part of the answer I have specialized to $p=2$, since the question mentioned binary in the title, but we can do the same for any prime $p$, and that makes polynomial notation shine: it implies the definition of addition, and of multiplication with the help of an irreducible polynomial.

Answer 2

It's more like a problem within abstract algebra rather than a problem within elliptic curves.

Integer modulo primepower $p^k$ would contain a zero divisor for k>1. Therefore, $\mathbb{Z}/p^k$ cannot be a field because you can't find, say, the multiplicative inverse of $p$. You could always consider $\mathbb{F}_{p^k}$ as $\mathbb{F_p}[x]/f(x)$ where $f(x)$ is some irreducible polynomial of degree $k$. Furthermore, whichever $f(x)$ you chose, they are always isomorphic.

There are many such polynomials. Exactly how many? Since $\mathbb{F}_{p^k}$ have order $p^k$ but they could possibly falls into lower extension degree. Write the prime factorization $k=\ell_1^{e_1}\dots \ell_r^{e_r}$. Say $c_d$ be the number of degree-d monic irreducible polynomial. Then we have $$ p^k-p=\#\mathbb{F}_{p^k}\setminus\bigcup_{d|k}\mathbb{F_{p^d}}=\sum_{d|k}d\cdot c_d $$ Using Mobius inversion, we easily obtain $$ k\cdot c_k=\sum_{d|k}\mu(d) (p^{k/d}-p). $$ You could therefore randomly pick one polynomial and then use algorithms such as Berlekamp's or Cantor-Zassenhaus to check that it is irreducible and resample if otherwise.