A finite field extension enlarges a prime field of size p to a field of size p^k, where k is the extension degree. Its elements are represented as polynomials in a symbol such as x, with coefficients reduced modulo p. A degree-k representation has k coefficients, giving p^k possible values. section 7.1 section 7.6
Polynomial arithmetic makes the enlarged field operational. Addition and subtraction combine coefficients of matching powers modulo p. For multiplication and inversion to remain field operations, an irreducible polynomial serves as the polynomial modulus; ordinary representatives are one degree below that defining polynomial. section 7.1 section 13.1
An implementation-oriented construction has these parts:
- Choose a prime base field p and an extension degree k, establishing p^k possible elements. section 7.1
- Store an element as a fixed-size polynomial with coefficients modulo p, tracking its degree carefully when leading coefficients become zero. section 7.0 section 7.6
- Select and test an irreducible polynomial of the required degree; it defines the reduction rule for polynomial multiplication and inversion. section 11.1 section 13.1
- Apply the polynomial routines to points and curves when elliptic-curve operations must run over the extension rather than only over the base field. section 13.2
A cubic extension over 1187
With p = 1187 and k = 3, the extension contains 1187^3 = 1,672,446,203 elements. One element can be indexed as a2x^2 + a1x + a0, with each coefficient chosen modulo 1187. For example, x^2 − 2x + 4 is stored using modular coefficients; a negative coefficient can be converted to its positive residue by adding 1187. section 7.1
A small powering check
Over a degree-two extension of the field modulo 43, defined using x^2 + x + 3, there are 43^2 = 1849 elements. Exponentiating a nonzero polynomial element to 1848 produces 1, illustrating the role of the extension-field size in power operations. section 9.3
Extensions are central to elliptic-curve pairings: curves over extension fields provide the point and value structures used by pairing computations. The embedding degree is the smallest k for which the extension-curve cardinality contains the required large prime factor. Security selection therefore considers both base-field size and extension-field size; a low extension can enable the MOV attack. section 13.1 section 6.3 section 14.1
Figure 13.1 Expanding a prime base field \(p\) to an extension field \(p^k\). Extension fields are required to compute pairings.
Visualize the base field p expanding into k polynomial-coordinate dimensions, producing the extension field p^k required for pairing computations. section 13.1
