Polynomial multiplication over finite fields: from quadratic to straight-line complexity (Q862343)

To obtain the coefficients of the product of two degree \(n\) polynomials, its known that \(2n\) multiplications/divisions are required for straight-line algorithms, if the polynomials belong to infinite fields. For finite fields, however, there is an additional problem because of the lack of elements. In this paper, the authors show that computing the coefficients of the product of two \(n\)-degree polynomials over finite fields by straight-line algorithms requires at least \(3n-o(n)\) multiplications/divisions.