4
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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? $\endgroup$
    – kelalaka
    Jan 4 at 16:45
  • 1
    $\begingroup$ The wikipedia article has an explicit example of a/the finite field with 4 elements: en.wikipedia.org/wiki/Finite_field#Non-prime_fields $\endgroup$
    – bmm6o
    Jan 4 at 17:39
  • $\begingroup$ 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. $\endgroup$ Jan 5 at 1:00
6
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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? $\endgroup$
    – user1108
    Jan 4 at 22:42
  • 2
    $\begingroup$ @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. $\endgroup$ Jan 5 at 0:58
  • $\begingroup$ @user1108: I tried to clarify in updated answer (and changed primitive to irreducible as it should be). $\endgroup$
    – fgrieu
    Jan 5 at 7:38
  • $\begingroup$ 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. $\endgroup$
    – user1108
    Jan 5 at 10:58
  • $\begingroup$ Thanks also to @PaŭloEbermann (apparently I cannot cite more than a user in a comment) $\endgroup$
    – user1108
    Jan 5 at 11:00
0
$\begingroup$

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.

$\endgroup$

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.