We prove an asymptotic lower bound of 3.52n nonscalar multiplications for (degree n — 1 by degree n-1) polynomialmultiplication in a model which allows only integers as scalars.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Hardware and Architecture
- Computational Theory and Mathematics
- Algebraic complexity
- lower bound
- polynomial multiplication