A monic polynomial is a nonzero polynomial whose leading coefficient is 1. For example, t⁴ + 2t³ + t² + 3t + 5 is monic because its t⁴ coefficient is 1. section 8.2 section 8.7
Uses monic irreducible polynomials as moduli for polynomial arithmetic in finite-field extensions. Setting the modulus to zero lets multiplication replace powers at or above its degree with lower-degree terms, avoiding full polynomial division. section 8.2
Equation 8.1
\[t^n + a_{n-1}t^{n-1} + a_{n-2}t^{n-2}+\cdots+ a_1 t+a_0 \label{ply1}\]The modulus is written with a leading coefficient of 1; setting it equal to zero produces the reduction rule used for higher powers of t. section 8.2
A multiplication-table implementation proceeds as follows:
- Normalize the input polynomial if necessary so its leading coefficient becomes 1. section 8.4.1 section 8.5
- Allocate and initialize a two-dimensional table with 2n rows and n coefficient columns for a degree-n modulus. section 8.4.1
- Fill the first n rows with powers of t, placing 1s on the corresponding diagonal. section 8.4.1
- Copy the negative modulus coefficients into row n, then generate the remaining rows by shifting, multiplying, and adding. section 8.4.1
- Multiply coefficient products using cₖ = Σ aᵢbₖ₋ᵢ, then reduce higher-degree terms through the precomputed rows. section 8.2 section 8.7
Degree-four test polynomial
A test initializes C with degree 4 and coefficients C₄ = 1, C₃ = 2, C₂ = 1, C₁ = 3, and C₀ = 5, then calls poly_mulprep(C). The debug matrix begins with the four diagonal rows, followed by the negative modulus coefficients and generated reduction rows. section 8.5
