Doubt on elliptic curve over a finite field and binary representation 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&gt;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.
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)&amp;=(x^2+x)\,x^2+(x^2+x)\\
&amp;=x^4+x^3+x^2+x\\
&amp;\equiv(x^4+x^3+x^2+x)+(x^4+x^2+x)&amp;\pmod{x^3+x+1}\\
&amp;\equiv x^3&amp;\pmod{x^3+x+1}\\
&amp;\equiv x^3+(x^3+x+1)&amp;\pmod{x^3+x+1}\\
&amp;\equiv x+1&amp;\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     &amp;\mathtt{000}&amp;\mathtt{001}&amp;\mathtt{010}&amp;\mathtt{011}&amp;\mathtt{100}&amp;\mathtt{101}&amp;\mathtt{110}&amp;\mathtt{111}\\
\hline
\mathtt{000}&amp;\mathtt{000}&amp;\mathtt{000}&amp;\mathtt{000}&amp;\mathtt{000}&amp;\mathtt{000}&amp;\mathtt{000}&amp;\mathtt{000}&amp;\mathtt{000}\\
\mathtt{001}&amp;\mathtt{000}&amp;\mathtt{001}&amp;\mathtt{010}&amp;\mathtt{011}&amp;\mathtt{100}&amp;\mathtt{101}&amp;\mathtt{110}&amp;\mathtt{111}\\
\mathtt{010}&amp;\mathtt{000}&amp;\mathtt{010}&amp;\mathtt{100}&amp;\mathtt{110}&amp;\mathtt{011}&amp;\mathtt{001}&amp;\mathtt{111}&amp;\mathtt{101}\\
\mathtt{011}&amp;\mathtt{000}&amp;\mathtt{011}&amp;\mathtt{110}&amp;\mathtt{101}&amp;\mathtt{111}&amp;\mathtt{100}&amp;\mathtt{001}&amp;\mathtt{010}\\
\mathtt{100}&amp;\mathtt{000}&amp;\mathtt{100}&amp;\mathtt{011}&amp;\mathtt{111}&amp;\mathtt{110}&amp;\mathtt{010}&amp;\mathtt{101}&amp;\mathtt{001}\\
\mathtt{101}&amp;\mathtt{000}&amp;\mathtt{101}&amp;\mathtt{001}&amp;\mathtt{100}&amp;\mathtt{010}&amp;\mathtt{111}&amp;\mathtt{011}&amp;\mathtt{110}\\
\mathtt{110}&amp;\mathtt{000}&amp;\mathtt{110}&amp;\mathtt{111}&amp;\mathtt{001}&amp;\mathtt{101}&amp;\mathtt{011}&amp;\mathtt{010}&amp;\mathtt{100}\\
\mathtt{111}&amp;\mathtt{000}&amp;\mathtt{111}&amp;\mathtt{101}&amp;\mathtt{010}&amp;\mathtt{001}&amp;\mathtt{110}&amp;\mathtt{100}&amp;\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&gt;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&gt;1$ then a coordinate is in its turn a &quot;set of coordinate&quot;.

Yes, that's a useful way of seeing it. An element of the field $\mathbb F_{p^k}$ is most naturally expressed as $k$ &quot;coordinates&quot; 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.