AG 1, AG 3, AG 5, SWS, AG 4, RG1, MMCI   Info

AG Audience

English

45 Minutes

Saarbrücken

We present a new algebraic algorithm for computing the DFTs over arbitrary fields. It computes DFTs of infinitely many orders n in O(n log n) algebraic operations, while the complexity of the known FFT algorithms is Ω(n^{1.5}) for such n. Our algorithm is a novel combination of the classical FFT algorithms, and is never slower than any of the latter.

As an application we come up with an efficient way of computing DFTs of high orders in finite field extensions which can further boost fast polynomial multiplication. We relate the complexities of the DFTs of special orders with the complexity of polynomial multiplication.

gk-sek

--email hidden

passcode not visible

logged in users only