An irreducible polynomial is a nonconstant polynomial with no factorization into smaller nonconstant polynomial factors over the chosen finite field. It is also called a prime polynomial when used as a modulus: it plays the role that a prime number plays for integer arithmetic. Irreducibility depends on the coefficient modulus, so the same formula can be irreducible for one field prime and reducible for another. section 8.0 section 8.1
Same polynomial, different field
The polynomial x² + 13x + 1 has no factors modulo 1187, but modulo 43 it factors as (x + 25)(x + 31). Therefore it can define an extension over the first field prime but not the second. section 8.1
A degree-k irreducible polynomial defines a field extension with p^k elements when coefficients are taken modulo the prime p. Set its defining equation f(t)=0 to reduce every high power of t to a polynomial of degree below k. For example, x² + 13x + 1 = 0 modulo 1187 gives x² = −13x − 1; repeated substitution reduces x³, x⁴, and all later powers. section 7.6 section 8.1
Use an irreducible polynomial operationally as follows:
- Choose a polynomial whose degree matches the required extension degree, then make it monic so its leading coefficient is 1. section 8.7 section 11.0
- Treat it as the fixed polynomial modulus for multiplication, inversion, and division of extension-field values. section 8.7 section 10.2
- Precompute coefficient rows for powers of t; multiplication can then reduce terms of degree k or higher through table lookup and accumulation. section 8.3 section 8.7
- Test candidates before relying on them. A Ben-Or-based search tries trinomials and rejects a candidate when gcd tests expose a factor. section 11.1 section 11.2
Table 8.1 Powers of \(\boldsymbol{t}\) expanded modulo irreducible polynomial
| Coefficient index | |||||
| Power | \(n-1\) | \(n-2\) | \(\cdots\) | \(1\) | \(0\) |
| \(0\) | \(0\) | \(0\) | \(\cdots\) | \(0\) | \(1\) |
| \(1\) | \(0\) | \(0\) | \(\cdots\) | \(1\) | \(0\) |
| ⋮ | ⋮ | ⋮ | \(\cdots\) | ⋮ | ⋮ |
| \(n\) | \(-a_{n-1}\) | \(-a_{n-2}\) | \(\cdots\) | \(-a_1\) | \(-a_0\) |
| \(n+1\) | \(a_{n-1}^2-a_{n-2}\) | \(a_{n-1}a_{n-2}-a_{n-3}\) | \(\cdots\) | \(a_{n-1}a_1-a_0\) | \(a_{n-1}a_0\) |
| ⋮ | ⋮ | ⋮ | \(\cdots\) | ⋮ | ⋮ |
| \(2n-2\) | \(c_{n-1}\) | \(c_{n-2}\) | \(\cdots\) | \(c_1\) | \(c_0\) |
The table makes reduction concrete: the defining polynomial supplies row k, and each later row is produced by multiplying the preceding expansion by t and reducing again. section 8.3
This fixed modulus is infrastructure, not merely a test condition. It determines the representation of extension-field elements, which have at most k coefficients after reduction, and it is prepared once before repeated arithmetic. Extension-field elliptic-curve and pairing routines use the resulting polynomial arithmetic alongside reduction modulo the base field prime. section 8.7 section 13.1
Tiny extension-field setup
Over the prime 43, x² + x + 3 is used as an irreducible polynomial, producing an extension with 43² = 1849 elements. A polynomial-power test reduces values modulo this polynomial; raising a sample element to power 1848 yields 1. section 9.3 section 13.3.1
