How to use the Fast Fourier Transform in Large Finite Fields

2011/01/15 by Petur Birgir Petersen, Petersen, Petur Birgir
Computer Science · Engineering · Mathematics · #11 #42 #68 and 94 #Advanced Wireless Communication Techniques #Coding theory and cryptography #Cryptography and Residue Arithmetic #FOS: Mathematics #Number Theory (math.NT) #math.NT #msc:11 #msc:42 #msc:68 #msc:94

paper · pdf · doi:10.48550/arxiv.1101.3001

arxiv created 2011/01/15 · openalex publication_date 2011/01/15 · arxiv updated 2011/01/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The article contents suggestions on how to perform the Fast Fourier Transform over Large Finite Fields. The technique is to use the fact that the multiplicative groups of specific prime fields are surprisingly composite.

Related

• Fast Fourier transform via automorphism groups of rational function fields
• Interesting Open Problem Related to Complexity of Computing the Fourier Transform and Group Theory
• Elliptic Curve Fast Fourier Transform (ECFFT) Part I: Fast Polynomial\n Algorithms over all Finite Fields
• Fast transforms over finite fields of characteristic two
• Discrete and Fast Fourier Transform Made Clear