An Computational Algorithm for Polynomial Multiplication

Abstract

In field K, given two polynomials: a(x) = ^∑ _0≤i<n a_ixⁱ; b(x) = ^∑ _0≤i<n b_ixⁱ and m(x) = xⁿ – 1. This paper presents a computational algorithm for polynomial multiplication:

u(x) ≡ a(x)b(x) mod m(x) = ^∑ _0≤i<n u_ixⁱ.

The coefficients (u_i)_0≤i<n are determined based on convolution and using the Chinese remainder theorem.