The Fast Fourier Transform in a Finite Field

DOI10.2307/2004932zbMath0221.12015OpenAlexW4212899991MaRDI QIDQ5625308

J. M. Pollard

Publication date: 1971

Full work available at URL: https://doi.org/10.2307/2004932

Mathematics Subject Classification ID

Finite fields and commutative rings (number-theoretic aspects) (11T99) Other transforms and operators of Fourier type (43A32) Primality (11Y11) Calculation of integer sequences (11Y55)

Related Items (34)

Even faster integer multiplication ⋮ Polynomial Multiplication over Finite Fields in Time \( O(n \log n \) ⋮ A fast algorithm for computing the number of magic series ⋮ Feedback shift registers, 2-adic span, and combiners with memory ⋮ Communication complexity of matrix computation over finite fields ⋮ Fractional Fourier, Hartley, cosine and sine number-theoretic transforms based on matrix functions ⋮ Precise deconvolution using the Fermat number transform ⋮ Integer multiplication in time \(O(n\log n)\) ⋮ Exact deconvolution using number-theoretic transforms ⋮ A class of functions with low-valued Walsh spectrum ⋮ An Elliptic Curve Cryptographic Processor Using Edwards Curves and the Number Theoretic Transform ⋮ A novel approach for defining a Hilbert number transform ⋮ A survey of elliptic curves for proof systems ⋮ Group character tables in discrete transform theory ⋮ Batched fully homomorphic encryption from TFHE ⋮ Fast norm computation in smooth-degree abelian number fields ⋮ A novel approach for computation of morphological operations using the number theoretic transform ⋮ Faster truncated integer multiplication ⋮ Finite field trigonometric transforms ⋮ Optimal Extension Field Inversion in the Frequency Domain ⋮ A note on discrete logarithms in finite fields ⋮ Discrete Weighted Transforms and Large-Integer Arithmetic ⋮ Algebraic complexities and algebraic curves over finite fields ⋮ Fast modular transforms ⋮ The eigenstructure of finite field trigonometric transforms ⋮ Another polynomial homomorphism ⋮ Efficient Multiplication of Somewhat Small Integers Using Number-Theoretic Transforms ⋮ Faster integer multiplication using plain vanilla FFT primes ⋮ Quantum circuits for high-degree and half-multiplication for post-quantum analysis ⋮ Group Convolutions and Matrix Transforms ⋮ Unnamed Item ⋮ An implementation of parallel number-theoretic transform using Intel AVX-512 instructions ⋮ Finite field transforms and symmetry groups ⋮ Computational Complexity of Fourier Transforms Over Finite Fields

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Primitive Trinomials of High Degree
• Matrix Multiplication and Fast Fourier Transforms
• Computing Multiplicative Inverses in GF(p)
• Three New Mersenne Primes and a Statistical Theory

This page was built for publication: The Fast Fourier Transform in a Finite Field