Polynomial Multiplication

Definition

Polynomial multiplication is the operation of computing the product of two polynomials.

For polynomials $a(x)$ and $b(x)$, the result is

with multiplication defined over a particular coefficient domain and polynomial algebra.

Mathematical Domain

The operation may be defined over different coefficient domains and polynomial structures.

Examples include polynomial multiplication over integers, finite fields, modular integer rings, and quotient polynomial rings. Depending on the domain, the resulting polynomial may be retained in full or reduced according to a defining polynomial relation.

The kernel itself does not fix a particular coefficient domain, polynomial degree, modulus, quotient ring, or representation. These are defined by individual specifications.

Parameters Defined by Specifications

A specification narrows the general polynomial multiplication operation into a concrete computational problem by defining the relevant mathematical and interface parameters, such as:

• coefficient domain
• polynomial domain or quotient ring
• polynomial degree or size
• coefficient modulus or other arithmetic parameters
• reduction semantics
• input and output representation
• additional constraints required by the computation

Applications

Polynomial multiplication is a fundamental operation in many areas of computational mathematics and cryptography, including lattice-based cryptography, fully homomorphic encryption, post-quantum cryptography, coding theory, symbolic computation, and signal-processing-style polynomial arithmetic.