A polynomial function over a finite field represents a value as a sum of coefficient–power terms such as a_{k-1}x^{k-1}+...+a_1x+a_0, with every coefficient reduced modulo a field prime p. For an extension of degree k, the k coefficients provide p^k possible field elements. The variable x is an indexing symbol: coefficients distinguish elements rather than ordinary numeric inputs to evaluate. section 7.1
Figure 7.1 Finite field extension over prime numbers viewed as a clock (\(p=1187\), \(k=3\))
Use the clock-style view to connect k coefficient positions, each chosen modulo p, with the p^k elements of a finite-field extension. section 7.1
A practical representation stores an integer degree and a fixed-size coefficient array. Array index i holds the coefficient of x^i. Fixed capacity makes routines easy to follow, although it is not space-efficient for small embedded systems or sparse polynomials. Initialization creates every coefficient, and clearing releases every coefficient before a local polynomial is discarded. section 7.2
Listing 7.1 Polynomial structure
#define MAXDEGREE 32
typedef struct
{
unsigned long deg;
mpz_t coef[MAXDEGREE];
}POLY;
The structure makes the equation operational: deg records the highest active power, while coef[i] stores the matching coefficient. section 7.2
Addition aligns equal powers and adds their coefficients modulo p. If one input has a larger degree, its unmatched high-order coefficients are copied into the result. After addition, remove zero leading coefficients; otherwise the recorded degree can falsely describe the result. Subtraction negates every coefficient of the second polynomial and reuses addition. section 7.3 section 7.6
Adding unequal-degree polynomials
To add 37x^3+96x^2+7x+3 and 14x^2+83x+124 modulo 127, line up powers, sum each coefficient modulo 127, retain the x^3 coefficient from the first polynomial, and normalize the output degree if its leading coefficient becomes zero. section 7.1
Supporting routines keep polynomial arithmetic usable in larger algorithms:
- Copy a polynomial before manipulating an input, assuming the destination has already been initialized. section 7.4
- Compare only for equality by checking degree and every coefficient; ordering has no useful meaning in the cyclic modular setting. section 7.4
- Print coefficients as modular terms for debugging and direct checking in PARI/gp. section 7.4
- Generate random coefficients below the degree of the selected irreducible polynomial for later field-extension routines. section 7.4
These routines provide the data layer for finite-field extension operations. They support testing whether a polynomial is a quadratic residue and constructing elliptic-curve points whose coordinates and curve parameters are polynomials; point addition and multiplication then operate modulo both the field prime and an irreducible polynomial. section 12.2.4 section 13.2
