@inproceedings{ad868d6df259440c95cd40d8f4162ef2,
title = "The Frobenius FFT",
abstract = "Let Fq be the finite field with q elements and let ω be a primitive nth root of unity in an extension field Fqd of Fq. Given a polynomial P ∈ Fq[x] of degree less than n, we will show that its discrete Fourier transform (P(ω0);...; P(ωn-1)) ∈ Fnqd can be computed essentially d times faster than the discrete Fourier transform of a polynomial Q ∈ Fqd [x] of degree less than n, in many cases. This result is achieved by exploiting the symmetries provided by the Frobenius automorphism of Fqd over Fq.",
keywords = "Complexity bound, FFT, Finite field, Frobenius automorphism",
author = "\{Van Der Hoeven\}, Joris and Robin Larrieu",
note = "Publisher Copyright: {\textcopyright} 2017 Copyright held by the owner/author(s).; 42nd ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2017 ; Conference date: 25-07-2017 Through 28-07-2017",
year = "2017",
month = jul,
day = "23",
doi = "10.1145/3087604.3087633",
language = "English",
series = "Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC",
publisher = "Association for Computing Machinery",
pages = "437--444",
editor = "Michael Burr",
booktitle = "ISSAC 2017 - Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation",
}