Prime Field Extension

Given some prime number $p ∈ P$, a natural number $m ∈ N$, and an irreducible polynomial $P ∈ F_p[x]$ of degree $m$ with coefficients from the prime field $F_p$, a prime field extension $(F_{p^m} , +, ·)$ is defined as follows:

1. The set $F_{p^m}$ of the prime field extension is given by the set of all polynomials with a degree less than $m$:

$$F_{p^m} = \{a_{m−1}x^{m−1} + a+{m−2}x^{m−2} + . . . + a_1x + a_0 | a_i ∈ F_p\}$$

1. The addition law of the prime field extension $F_{p^m}$ is given by the usual addition of polynomials:

$$+ : F_{p^m} × F_{p^m} → F_{p^m} , (\sum_{j=0}^{m}a_j x^j, \sum_{j=0}^{m}b_j x^j) \to \sum_{j=0}^{m}(a_j + b_j) x^j$$

1. The multiplication law of the prime field extension $F_{p^m}$ is given by first multiplying the two polynomials, then dividing the result by the irreducible polynomial $P$ and keeping the remainder:

$$\cdot : F_{p^m} × F_{p^m} → F_{p^m} , (\sum_{j=0}^{m}a_j x^j, \sum_{j=0}^{m}b_j x^j) \to (\sum_{n=0}^{2m}\sum_{i=0}^{n}a_i b_{n - i} x^n) \mod P$$

1. The neutral element of the additive group $(F_{p^m} , +)$ is given by the zero polynomial $0$. The additive inverse is given by the polynomial with all negative coefficients. The neutral element of the multiplicative group $(F^∗_{p^m} , ·)$ is given by the unit polynomial $1$. The multiplicative inverse can be computed by the Extended Euclidean Algorithm.

This field is of characteristic $p$, since the multiplicative neutral element $1$ is equivalent to the multiplicative element $1$ from the underlying prime field, and hence $\sum_{j=0}^p 1 = 0$. Moreover, $F_{p^m}$ is finite and contains $p^m$ many elements, since elements are polynomials of degree < $m$, and every coefficient $a_j$ can have $p$ many different values. In addition, we see that the prime field $F_p$ is a subfield of $F_{p^m}$ that occurs when we restrict the elements of $F_{p^m}$ to polynomials of degree zero.

It can be shown that the fields for different choices of $P$ are isomorphic, which means that there is a one-to-one correspondence between all of them. As a result, from an abstract point of view, they are the same thing. From an implementations point of view, however, some choices are preferable to others because they allow for faster computations.

Any field $F_{p^m}$ constructed in the above manner is a field extension of $F_p$. To be more general, a field $F_{p^{m_2}}$ is a field extension of a field $F_{p^{m_1}}$ if and only if $m_1$ divides $m_2$. From this, we can deduce that, for any given fixed prime number, there are nested sequences of subfields whenever the power $m_j$ divides the power $m_{j+1}$:

$$F_p \subset F_{p^{m_1}} \subset ... \subset F_{p^{m_k}}$$

Sage example:

TODO