What is an extension field? Covered differently in math & in cryptography.

Question

In his book on Cryptography, Paar has this theorem

Theorem 4.3.1 A field with order m only exists if m is a prime power, i.e., m = p^n, for some positive integer n and prime integer p. p is called the characteristic of the finite field.

So here he says that the order has to be a prime power - He also has this as examples

This theorem implies that there are, for instance, finite fields with 11 elements, or with 81 elements (since 81 = 3^4) or with 256 elements (since 256 = 2^8, and 2 is a prime).

So he explicitly says that you can have a field with 256 elements - the order of a finite field needs to be a prime power & not necessarily a prime itself.

He then goes on to talk about extension fields - he says that if the order of the field is not a prime then it's called as an extension field.

In AES the finite field contains 256 elements and is denoted as GF(2^8). This field was chosen because each of the field elements can be represented by one byte. For the S-Box and MixColumn transforms, AES treats every byte of the internal data path as an element of the field GF(2^8) and manipulates the data by performing arithmetic in this finite field. However, if the order of a finite field is not prime, and 2^8 is clearly not a prime, the addition and multiplication operation cannot be represented by addition and multiplication of integers modulo 2^8. Such fields with m > 1 are called extension fields.

So as per this, I get the definition of an extension field as this - an extension field is any finite field where the order of the field is a prime power but not a prime itself.

However, when I look at books on abstract algebra, I see a totally different definition of extension fields which seem to be unconnected with what Paar says.

For e.g. from "Topics in Algebra" by Hernstein:

Let F be a field; a field K is said to be an extension of F if K contains F. Equivalently, K is an extension of F if F is a subfield of K.

So are Extension fields described in Cryptography different from those described in Algebra? But is Paar's description wrong? Or are the 2 definitions equivalent in some way?

Answer 1

The grammar of "extension field" is that it takes as input two fields, a smaller field $F$ and a bigger field $K$ into which $F$ embeds, so that we can say "$K$ is an extension of $F$." Paar is describing the way in which finite fields $\mathbb{F}_{p^n}$ arise as extension fields of prime finite fields $\mathbb{F}_p$; this is a special case of the general definition in algebra but Parr has not been maximally explicit about what the smaller field is.

The reason Parr wants to distinguish the $n \ge 2$ case is that, as he says, while $\mathbb{F}_p$ can be understood and calculated with very concretely as the integers $\bmod p$, the finite fields $\mathbb{F}_{p^n}, n \ge 2$ of prime power but not prime order cannot, and in particular are not isomorphic to the integers $\bmod p^n$, which do not form a field (exercise!).

In general, though, different groups of people often work with the same objects in different subareas of math, science, etc. and inevitably somewhat different terminology will spring up in each subarea. It happens sometimes. For example some people (cryptographers? engineers? programmers? I'm not sure) call finite fields "Galois fields" but a pure mathematician would find this terminology a little strange; "finite field" is the accepted terminology in pure mathematics universally as far as I know.

Answer 2

For any finite field $\Bbb F$ of order $p^m, m\gt1$, there is its prime subfield, generated by $1$, of order $p=\rm{char}\Bbb F$, of which $\Bbb F$ is an extension.

$\Bbb F$ will also be an extension of all the fields of order $p^n$, where $n|m$.

Perhaps this helps reconcile the treatments.

Answer 3

Paar is only concerned with finite fields in his book. It turns out that there is a finite field of $m$ elements only when $m$ is a power of a prime: $m = p^n$. And in that case, there is only one such field, up to isomorphism (i.e., if you have two such fields, you can match up the elements of one with the elements of the other in a way that preserves multiplication and addition, so the only differences between the two have nothing to do with being a field). We call this unique finite field $\Bbb F_m$.

Since $\Bbb F_m$ is a field, it contains a multiplicative identity $1$. If you keep adding $1$ to itself, you get new values. But there are only $m$ elements in $\Bbb F_m$, so you cannot keep getting new values forever. It has to repeat itself, and when it does, adding more $1$s just follows the same cycle. A little algebra then shows that in fact for some (real) integer $n$, adding $n$ copies of $1$ gives $0$. This is denoted by $n \cdot 1 = 0$, but note here that $n$ is an ordinary integer, while $1$ and $0$ are the elements of $\Bbb F_m$. This also means that for any element $\alpha \in \Bbb F_m, n\cdot \alpha = n\cdot(1\alpha) = (n\cdot 1)\alpha = 0$ by the distributive law.

The smallest non-zero $n$ for which $n\cdot 1 = 0$ is called the characteristic of the field. (This applies not only to finite fields but also to infinite fields. Only in that case it is possible (but not necessary) that $n\cdot 1$ is never zero. We say that such fields have "characteristic $0$", which you can just take as a convenient special definition - though mathematicians like to give a rather esoteric justification for it.) It turns out that $\Bbb F_{p^n}$ always has characteristic $p$.

Further if you take the subset $\{0, 1, 2\cdot 1, \ldots, (p-1)\cdot 1\}$ of $\Bbb F_{p^n}$, this set turns out to be closed under addition and multiplication and the taking of inverses. That is, it is a field itself. Since it has $p$ elements, it must be the field $\Bbb F_p$. Because $\Bbb F_p \subset \Bbb F_{p^n}$ using the same field operations, we say that it is a subfield of $\Bbb F_{p^n}$, or equivalently that $\Bbb F_{p^n}$ is an extension field of $\Bbb F_p$.

---

All of this is the theory and language that Paar needs. But it is just a building block on the way to his intent, so he is spending as little time on it has he can before diving into his subject. Because of this, he cuts corners.

Rather than give you the actual general definition of characteristic, he just tells you what it is for the fields of interest. And because the only extension fields he is interested in are $\Bbb F_{p^n}$ as an extension of $\Bbb F_p$, he shortens that terminology down as well. (In fact, $\Bbb F_{p^n}$ is an extension of $\Bbb F_{p^k}$ for any $k \mid n$, but Paar has no need of this.)

It is not that Paar is wrong. He is just speaking for his subject, not for all mathematics. He has chosen to borrow simplified versions of our conventional terminology for his own use. If he were writing as a mathematician, this might be frowned upon as confusing. But since he is in a different field, it is up to the other members of that field to say whether or not his terminology is a problem.

Answer 4

Paar uses “extension field” to mean nontrivial extension field, that is, an field that is an extension field of some field other than itself. In other words, he calls a field an “extension field” a field that has a proper subfield.

(It's possible that he'd prefer a different definition in general, perhaps to restrict to a finitely generated extension, but that doesn't make a difference for finite fields.)

Any field $F$ has a smallest subfield, which is the subfield generated by the empty set. It's the intersection of all the subfields of $F$. A field must contains the neutral element for addition $\bar 0$ and the neutral element for multiplication $\bar 1$, and $\bar 1+\bar 1$, $\bar 1+\bar 1+\bar 1$, etc. There are two cases for what this smallest subfield can look like.

• If there is a number $p \ge 1$ such that $p \bar 1 = \mathop{\underbrace{\bar 1+\bar 1+\bar 1+\ldots+\bar 1}}_\limits{\text{\(p\) terms}} = \bar 0$, take the smallest such $p$. $p$ must be prime, because if $p = q r$ with $p, q \ge 2$ such that $(q r) \bar 1 = \bar 0$ then $(q \bar 1) \cdot (r \bar 1) = \bar 0$ and therefore one of $q \bar 1$ or $r \bar 1$ is $\bar 0$. Addition and multiplication on $\{\bar 0, \bar 1, \bar 1+\bar 1, \bar 1+\bar 1+\bar 1, \ldots, (p-1)\bar 1\}$ coincides with the same operations in $\mathbb{Z}/p\mathbb{Z}$, and it follows that division also coincides and therefore $\{\bar 0, \bar 1, \bar 1+\bar 1, \ldots, (p-1)\bar 1\}$ is closed by division and is itself a field which is isomorphic to $\mathbb{Z}/p\mathbb{Z}$. The number $p$ must be prime, and is called the characteristic of the field.
• Otherwise, $\bar 0$, $\bar 1$, $\bar 1+\bar 1$, $\bar 1+\bar 1+\bar 1$, etc. are all distinct. In this case, the smallest subfield is isomorphic to $\mathbb{Q}$ (the rationals), and the field is said to have characteristic 0. Note that this cannot happen for a finite field, since $\{\bar 0, \bar 1, \bar 1+\bar 1, \bar 1+\bar 1+\bar 1, \ldots\}$ is an infinite subset.

I omit the proofs, which should be easy to find. Paar should prove these statements for the case of finite fields as lemmas before the theorem you cite.

A nontrivial extension field is therefore a field which is neither $\mathbb{Z}/p\mathbb{Z}$ nor $\mathbb{Q}$ (up to isomorphism). For a finite fields, the number of elements must be a prime power $p^n$, where $p$ is the characteristic. If $n = 1$ the field is $\mathbb{Z}/p\mathbb{Z}$, which doesn't have a proper subfield (as we saw above, no proper subset containing $1$ is closed even by addition alone ). If $n \gt 1$ the field is a proper extension of $\mathbb{Z}/p\mathbb{Z}$.

The reason why the terminology “field extension” is used even though it's redundant with “subfield” is that it is very common in algebra (but not so common in the study of finite fields) to construct fields by starting from a base field and adding elements to it. Formally, what's really happening is to start from a “large” field $L$ and a “small” field $K$ which is a subfield of $L$, and then consider fields generated by some subset $S$ of $L$, written $K(S)$ (with $L$ implicit).