The degree of a polynomial is the greatest exponent with a nonzero coefficient. Polynomial routines store it alongside coefficients and update it whenever arithmetic changes the leading term. section 7.6 section 7.3
Degree controls the shape and termination of finite-field polynomial operations:
- Adding polynomials begins with the larger input degree, combines matching coefficients, and decreases the result degree when leading coefficients become zero. section 7.3
- Multiplying degree-n and degree-m polynomials creates intermediate coefficients through degree n+m before reduction modulo an irreducible polynomial. section 8.2
- Reduction limits field elements to degree at most k−1, then a final scan removes any newly zero highest coefficients. section 8.4.2
- Polynomial division compares remainder and divisor degrees, places quotient coefficients at their degree difference, and stops when the remainder degree is smaller. section 10.3
Degree tracking in multiplication
A multiplication routine allocates coefficients through degree n+m, computes each convolution coefficient, reduces terms at or above the modulus degree, and scans downward until the stored leading coefficient is nonzero. Omitting that final scan leaves an incorrect degree and can produce high-degree polynomials whose leading coefficients are zero. section 8.4.2 section 7.3
Listing 8.8 Multiply check maximum degree
while((mpz_cmp_ui(rslt->coef[rslt->deg], 0) <= 0) && (rslt->deg > 0)) #1
rslt->deg--;
for(i=0; i<=n+m; i++)
mpz_clears(coef[i], acf[i], bcf[i], NULL);
mpz_clear(tmp); #2
}
Inspect the cleanup loop that decreases the recorded degree while its highest coefficient is zero. section 8.4.2
