Computational Complexity of Fourier Transforms Over Finite Fields

DOI10.2307/2006007zbMath0365.68053OpenAlexW4253447314MaRDI QIDQ4140387

Dilip V. Sarwate, Franco P. Preparata

Publication date: 1977

Full work available at URL: http://hdl.handle.net/2142/74080

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type (42A38) Convolution, factorization for one variable harmonic analysis (42A85) Theory of error-correcting codes and error-detecting codes (94B99) Arithmetic theory of polynomial rings over finite fields (11T55) Algorithms in computer science (68W99)

Related Items

The complexity of error-correcting codes, Inverting a Vandermonde matrix in minimum parallel time, Computational problems in the theory of finite fields, Discrete Weighted Transforms and Large-Integer Arithmetic, A flow model based on polylinking system, Finding the intersection of two convex polyhedra, Finite field towers: Iterated presentation and complexity of arithmetic., Authenticated hash tables based on cryptographic accumulators

Cites Work

• Fast multiplication of large numbers
• The use of finite fields to compute convolutions
• Properties of the Sequence 3 ⋅2 n + 1
• An Algorithm for the Machine Calculation of Complex Fourier Series
• The Fast Fourier Transform in a Finite Field
• Discrete Convolutions via Mersenne Transforms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item