Polynomial multiplication expands two expressions, combines coefficients with equal powers, and produces an intermediate degree equal to the sum of the input degrees. In a finite-field extension, an irreducible polynomial serves as the modulus, reducing every result to degree at most n−1 and preserving the field size. section 8.2 section 8.7
For polynomials a = Σaᵢtⁱ and b = Σbⱼtʲ, calculate the product operationally:
- Compute each result coefficient with cₖ = Σaᵢbₖ₋ᵢ, treating coefficients outside either input range as zero. section 8.2
- Store coefficients through degree r+s, using arrays sized for the combined input degrees. section 8.4.2
- If the intermediate degree reaches the modulus degree, fold each higher coefficient into lower positions through a precomputed powers-of-t lookup table. section 8.3 section 8.4.2
- Trim trailing zero coefficients after reduction so the stored degree matches the actual result. section 8.4.2
A reusable reduction table
Given an irreducible polynomial tⁿ + aₙ₋₁tⁿ⁻¹ + ··· + a₀, set it to zero to obtain tⁿ = −aₙ₋₁tⁿ⁻¹ − ··· − a₀. Generate successive rows by multiplying by t, shifting coefficients, and replacing the highest power with row n. The resulting matrix is computed once and reused for polynomial products modulo that irreducible polynomial. section 8.2 section 8.3
Figure 8.1 Multiplication modulo a prime polynomial. Polynomial \(a\) times polynomial \(b\) gives polynomial \(c\)—each coefficient of \(c\) is multiplied with the corresponding row in the expansion matrix and then summed to find the result modulo the prime polynomial.
The expansion matrix shows how each coefficient of the unreduced product contributes to the final polynomial modulo the irreducible polynomial. section 8.2
