Faster Polynomial Multiplication over Finite Fields
From MaRDI portal
Publication:3177879
DOI10.1145/3005344zbMath1426.68310arXiv1407.3361MaRDI QIDQ3177879
David I. Harvey, Joris van der Hoeven, Grégoire Lecerf
Publication date: 2 August 2018
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1407.3361
68Q25: Analysis of algorithms and problem complexity
68W30: Symbolic computation and algebraic computation
11Y16: Number-theoretic algorithms; complexity
11T06: Polynomials over finite fields
Related Items
Faster integer multiplication using plain vanilla FFT primes, Unnamed Item, Polynomial Multiplication over Finite Fields in Time \( O(n \log n \), Computing the Characteristic Polynomial of Endomorphisms of a finite Drinfeld Module using Crystalline Cohomology, Modular composition via factorization, On the complexity of integer matrix multiplication, Fast algorithm of square rooting in some finite fields of odd characteristic, A probabilistic algorithm for verifying polynomial middle product in linear time, Directed evaluation, Algorithms for simultaneous Hermite-Padé approximations, Deterministic computation of the characteristic polynomial in the time of matrix multiplication, Improved method for finding optimal formulas for bilinear maps in a finite field, Faster polynomial multiplication over finite fields using cyclotomic coefficient rings, Fast Gröbner basis computation and polynomial reduction for generic bivariate ideals, Fast multivariate multi-point evaluation revisited, Fast computation of approximant bases in canonical form, Fast Hermite interpolation and evaluation over finite fields of characteristic two, Accelerated tower arithmetic, Integer multiplication in time \(O(n\log n)\)
