We explore a new form of DFT, which we call the Polynomial Transform. It functions over finite fields, and a size $n$ transform takes $O(n)$ operations. In the multitape Turing machine model, it allows us to multiply two $n$ bit numbers in time $n(k^{ \log^*{ n}} + \log{ p})$, where $k$ is a constant and $\log^*{ n}$ is the iterated logarithm. One important consequence is that the Network Coding Conjecture is false.
Categories: cs.DS cs.CC cs.DM math.NT