Faster Polynomial Multiplication over Finite Fields
From MaRDI portal
Publication:3177879
DOI10.1145/3005344zbMath1426.68310arXiv1407.3361OpenAlexW1764552993MaRDI 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
Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Number-theoretic algorithms; complexity (11Y16) Polynomials over finite fields (11T06)
Related Items
On the complexity of integer matrix multiplication, Polynomial Multiplication over Finite Fields in Time \( O(n \log n \), Integer multiplication in time \(O(n\log n)\), Computing the Characteristic Polynomial of Endomorphisms of a finite Drinfeld Module using Crystalline Cohomology, Directed evaluation, Algorithms for simultaneous Hermite-Padé approximations, Fast algorithm of square rooting in some finite fields of odd characteristic, 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, Faster integer multiplication using plain vanilla FFT primes, Modular composition via factorization, 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, A probabilistic algorithm for verifying polynomial middle product in linear time, Unnamed Item, Accelerated tower arithmetic
