A cache-friendly truncated FFT

DOI10.1016/j.tcs.2009.03.014zbMath1172.68065OpenAlexW2016287994MaRDI QIDQ1029334

David I. Harvey

Publication date: 10 July 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.03.014

zbMATH Keywords

fast Fourier transformpolynomial multiplication

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Numerical methods for discrete and fast Fourier transforms (65T50)

Related Items (8)

Fast transforms over finite fields of characteristic two ⋮ Accelerating the CM method ⋮ Congruent Number Theta Coefficients to 1012 ⋮ Fast Hermite interpolation and evaluation over finite fields of characteristic two ⋮ Irregular primes to 163 million ⋮ Counting points on smooth plane quartics ⋮ Irregular primes to two billion ⋮ Computing Hasse–Witt matrices of hyperelliptic curves in average polynomial time

Uses Software

• FLINT
• gmp
• Magma
• NTL
• SageMath
• zn_poly

Cites Work

• Fast multiplication of polynomials over fields of characteristic 2
• The Magma algebra system. I: The user language
• Fast multiplication of large numbers
• Fast polynomial transform algorithms for digital convolution
• Computing Hilbert class polynomials with the Chinese remainder theorem
• The truncated fourier transform and applications
• Computing L-Series of Hyperelliptic Curves
• Kedlaya's Algorithm in Larger Characteristic
• SAGE
• Irregular primes and cyclotomic invariants to 12 million

This page was built for publication: A cache-friendly truncated FFT