Association for Computing Machinery (ACM)

The Frobenius FFT

JORIS VAN DER HOEVEN ¹

Robin Larrieu ¹

Hide authors affiliations Show authors affiliations: 1 affiliation

CNRS & École polytechnique, Palaiseau, France |

Publication type: Proceedings Article

Publication date: 2017-07-23

Association for Computing Machinery (ACM)

DOI: 10.1145/3087604.3087633

Copy DOI

Abstract

Let Fq be the finite field with q elements and let ω be a primitive n-th 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)) ∈ Fqdn 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.

Found

Top-30

Journals

	1
Lecture Notes in Computer Science	Lecture Notes in Computer Science, 1, 20% Lecture Notes in Computer Science 1 publication, 20%
Applicable Algebra in Engineering, Communications and Computing	Applicable Algebra in Engineering, Communications and Computing, 1, 20% Applicable Algebra in Engineering, Communications and Computing 1 publication, 20%
	1

Publishers

	1 2
Springer Nature	Springer Nature, 2, 40% Springer Nature 2 publications, 40%
Association for Computing Machinery (ACM)	Association for Computing Machinery (ACM), 2, 40% Association for Computing Machinery (ACM) 2 publications, 40%
Institute of Electrical and Electronics Engineers (IEEE)	Institute of Electrical and Electronics Engineers (IEEE), 1, 20% Institute of Electrical and Electronics Engineers (IEEE) 1 publication, 20%
	1 2

We do not take into account publications without a DOI.
Statistics recalculated weekly.

Are you a researcher?

Create a profile to get free access to personal recommendations for colleagues and new articles.

Metrics

Publisher

Association for Computing Machinery (ACM)