A multiplication table is a precomputed matrix that expands powers of t modulo an irreducible polynomial. Each row represents one power of t, and each column stores a coefficient in the underlying finite field. Polynomial multiplication can then reduce high-degree terms by combining their coefficients with the corresponding table rows. section 8.2 section 8.3
The table is prepared once for a chosen polynomial and then reused by multiplication routines:
- Normalize the input polynomial so its leading coefficient is 1, set the table degree, and release any previously allocated table. section 8.4.1
- Allocate a two-dimensional array with degree columns and twice the degree rows, then initialize every multiple-precision entry. section 8.4.1
- Place the coefficients of t^0 through t^(n-1) in the first n rows; each diagonal entry is 1. section 8.4.1
- Copy the relation for t^n from the normalized modulus, then generate later rows by shifting the previous row and adding a multiple of row n. section 8.4.1 section 8.3
For polynomials a = Σ a_i t^i and b = Σ b_j t^j, first compute each convolution coefficient c_k = Σ a_i b_(k−i). The resulting powers reach at most 2n−2; multiply each high-power coefficient by its table row and sum the columns to obtain the reduced product. section 8.2
Finite-field setup
A small extension-field program initializes the prime field with 43, finds x^2 + x + 3 as an irreducible polynomial, registers it, and calls poly_mulprep before polynomial multiplication. The resulting field elements have degree at most 1. section 13.3.1
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\) |
Use the coefficient matrix to inspect the rows for powers 0 through 2n−2 and follow how the modulus determines each reduction row. section 8.3
