Polynomial Multiplication over Finite Fields in Time \( O(n \log n \)
From MaRDI portal
Publication:5066949
DOI10.1145/3505584zbMath1493.11157WikidataQ114071088 ScholiaQ114071088MaRDI QIDQ5066949
David I. Harvey, Joris van der Hoeven
Publication date: 31 March 2022
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/3505584
68W30: Symbolic computation and algebraic computation
11Y16: Number-theoretic algorithms; complexity
11T06: Polynomials over finite fields
68M07: Mathematical problems of computer architecture
Related Items
Computing modular polynomials and isogenies of rank two Drinfeld modules over finite fields, A strategy to optimize the complexity of Chudnovsky-type algorithms over the projective line, Beating binary powering for polynomial matrices, HyperPlonk: Plonk with linear-time prover and high-degree custom gates, Simple Codes and Sparse Recovery with Fast Decoding, Amortized multi-point evaluation of multivariate polynomials
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Even faster integer multiplication
- Gauss and the history of the fast Fourier transform
- On fast multiplication of polynomials over arbitrary algebras
- Fast multiplication of polynomials over fields of characteristic 2
- On finding primitive roots in finite fields
- PRIMES is in P
- Relax, but don't be too lazy
- Faster polynomial multiplication over finite fields using cyclotomic coefficient rings
- Faster arithmetic for number-theoretic transforms
- Multiplikation großer Zahlen
- Fast multiplication of large numbers
- Integer multiplication in time \(O(n\log n)\)
- Fast Integer Multiplication Using Modular Arithmetic
- Modern Computer Algebra
- Fast Polynomial Multiplication over F 2 60
- Fast polynomial transform algorithms for digital convolution
- New algorithms for digital convolution
- Modern Computer Arithmetic
- On the least prime in an arithmetic progression and estimates for the zeros of Dirichlet L-functions
- Faster Polynomial Multiplication over Finite Fields
- New Algorithms for Finding Irreducible Polynomials Over Finite Fields
- Faster Integer Multiplication
- Searching for Primitive Roots in Finite Fields
- Computation of Convolutions and Discrete Fourier Transforms by Polynomial Transforms
- A lower bound for the least prime in an Arithmetic progression
- Fast integer multiplication using generalized Fermat primes
- Implementing Fast Carryless Multiplication
- Faster integer multiplication using plain vanilla FFT primes
- Zero-Free Regions for Dirichlet L-Functions, and the Least Prime in an Arithmetic Progression
- Multivariate power series multiplication
- An Algorithm for the Machine Calculation of Complex Fourier Series
- Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
- The Fast Fourier Transform in a Finite Field
- Faster integer multiplication using short lattice vectors
