AG 1, MMCI   Info

AG Audience

English

45 Minutes

Saarbrücken

We study complexity of polynomial multiplication over arbitrary fields. We present a unified approach that generalizes all known asymptotically fastest algorithms for multiplication of polynomials by classifying fields where the coefficients of the polynomials are taken from by the hardness of attaching roots of unity to them. We show, that Schönhage-Strassen's (1971), Schönhage's (1976), Cantor Kaltofen's (1991) algorithms follow this approach. We then obtain algorithms requiring o(N\log N\log\log N) elementary arithmetic operations for multiplication of two degree N polynomials over certain fields which do not support FFT. We then put an argument that the O(N\log N\log\log N) bound is unlikely to be improved over generals fields if one considers algorithms relying on consecutive application of DFT in field extensions, what all the fastest algorithms currently do. An example of a 'tough' field for this approach is the field of rational numbers. We also explore the potential of known techniques to improve Schönhage-Strassen's upper bound over arbitrary fields of positive characteristic and discuss one particular conjecture, whose validity implies faster polynomial multiplication over arbitrary fields of positive characteristic.

This work is inspired by the recent improvement for a closely related problem of complexity of integer multiplication by Fürer and its modular arithmetic treatment due to De et. al. We develop several ideas introduced in these works. In particular, the conjecture for fields of positive characteristic is the result of an attempt to transfer the techniques used by De et. al. for faster integer multiplication to the largely similar problem of polynomial multiplication.

Christian Hoffmann

--email hidden

passcode not visible

logged in users only

Polynomial Multiplication, Fast Fourier Transform, Algebraic Complexity