Method and apparatus for multiplying polynomials with a prime number of terms

摘要

An efficient method and apparatus to compute a product of polynomials of degree n-1 where n is an arbitrary prime is provided. The total number of multiply operations and Arithmetic Logical Unit (ALU) operations to compute the product is minimized through the judicious use of polynomial evaluations at few points to decrease the number of multiplications while using only simple ALU operations.