Arithmetic with Polynomials

• Polynomial product via classical, Karatsuba and Schönhage-Strassen FFT algorithms
• Polynomial quotient via classical and Karatsuba algorithms
• Pseudo quotient and remainder
• Modular exponentiation and inverse
• Modular composition over GF(q) (Brent-Kung)
• Norms
• Differentiation and integration
• Evaluation and interpolation
• Properties: prime, primitive, separable, permutation
• Properties: a unit, a zero-divisor, nilpotent

Magma employs asymptotically fast algorithms for performing arithmetic with univariate polynomials. These include two FFT-based methods for multiplication: the Schönhage-Strassen FFT method for situations where the coefficients are large compared with the degree, and the small-prime modular FFT with Chinese remaindering method for where the coefficients are small compared with the degree. These methods are applied to multiplication of polynomials over $\mbox{\bf Z}$, $\mbox{\bf Q}$, $\mbox{\bf Z}/m\mbox{\bf Z}$ and GF(q). For some coefficient rings, at least one of the FFT methods outperforms the Karatsuba method for polynomials having degree as small as 32 or 64; for each of the coefficient rings listed, the FFT method beats the Karatsuba method for degree 128 or greater. An asymptotically-fast division algorithm (which reduces division to multiplication) is also used for polynomials over all coefficient rings.