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

Averbuch, AmirKaminski, MichaelBshouty, Nader H.2008-02-272008-02-271991-06-01http://hdl.handle.net/1880/45743It 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.EngComputer ScienceA CLASSIFICATION OF ALGORITHMS FOR MULTIPLYING POLYNOMIALS OF SMALL DEGREE OVER FINITE FIELDSunknown1991-434-1810.11575/PRISM/30471