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

• There are prime field-based curves, that is $F_p$ What you are asking is the finite field question. This might help. The hint is that $F_{p^m}$ is considered as a vector space over $F_p$ with $m$ dimension. Could your share your slides? Jan 4 at 16:45
• The wikipedia article has an explicit example of a/the finite field with 4 elements: en.wikipedia.org/wiki/Finite_field#Non-prime_fields Jan 4 at 17:39
• Welcome to Crypto Stack Exchange. I've added some paragraph breaks and math formatting to your question to make it easier readable – please check the changes, and feel free to roll back, or edit again if I made something wrong. Jan 5 at 1:00

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.

• Ok, you've been clear but just to be sure can you confirm the following? 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" (in your example belonging to {0,1}^3). And about the integer representation: what are you trying to tell me is that it is not convenient to represent an element of a F when m>1 because in that case I would have, for example, 110 XOR 111 = 101 becoming 6 XOR 7 = 5 that may result meaningless? Jan 4 at 22:42
• @user1108 "convenience" is relative. What the author meant here is that the "natural" ($+$ and $·$) operations on the integers modulo $p^m$ are not giving a field (they are a ring, but you have divisors of 0, so division is not unique), but the "normal" operations on polynomials modulo an irreducible polynomial to form a field (and up to isomorphism the only field of order $p^m$), so we don't need to define special operations here. XOR on integers mod $2^m$ is convenient enough, the multiplication is a bit more complicated to implement. Jan 5 at 0:58
• @user1108: I tried to clarify in updated answer (and changed primitive to irreducible as it should be).
– fgrieu
Jan 5 at 7:38
• Thanks @fgrieu. Now it's much clearer to me. I still would have a lot of questions about this marvelous branch of mathematics so I ask one more thing: can you suggest me a set (forgive me the joke) of reference (textbook and/or online handouts) that gather elliptic curves theory for cryptographer? I would enjoy them. Jan 5 at 10:58
• Thanks also to @PaŭloEbermann (apparently I cannot cite more than a user in a comment) Jan 5 at 11:00

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.