A CLASSIFICATION OF ALGORITHMS FOR MULTIPLYING POLYNOMIALS OF SMALL DEGREE OVER FINITE FIELDS

Abstract

It is shown that any optimal algorithm for computing the product of two degree-n polynomials over the q-element field, where n<=q, is based on the Chinese Remainder Theorem, with linear and quadratic polynomials presented as the moduli.