Faster polynomial multiplication over finite fields using cyclotomic coefficient rings
From MaRDI portal
Publication:2274408
DOI10.1016/j.jco.2019.03.004zbMath1423.12010OpenAlexW2927304297WikidataQ128101322 ScholiaQ128101322MaRDI QIDQ2274408
David I. Harvey, Joris van der Hoeven
Publication date: 19 September 2019
Published in: Journal of Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jco.2019.03.004
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (19)
Fast exact algorithms using Hadamard product of polynomials ⋮ Polynomial Multiplication over Finite Fields in Time \( O(n \log n \) ⋮ Root repulsion and faster solving for very sparse polynomials over \(p\)-adic fields ⋮ On the complexity exponent of polynomial system solving ⋮ Integer multiplication in time \(O(n\log n)\) ⋮ Fast algorithms for solving equations of degree \(\le 4\) in some finite fields ⋮ Orienteering with one endomorphism ⋮ Directed evaluation ⋮ Polynomial constructions of Chudnovsky-type algorithms for multiplication in finite fields with linear bilinear complexity ⋮ Univariate polynomial factorization over finite fields with large extension degree ⋮ Algorithms for simultaneous Hermite-Padé approximations ⋮ Derivation and Analysis of Fast Bilinear Algorithms for Convolution ⋮ Fast amortized multi-point evaluation ⋮ Counting invariant subspaces and decompositions of additive polynomials ⋮ Fast Gröbner basis computation and polynomial reduction for generic bivariate ideals ⋮ Asymptotics of 3-stack-sortable permutations ⋮ Unnamed Item ⋮ Amortized multi-point evaluation of multivariate polynomials ⋮ Polynomial modular product verification and its implications
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Even faster integer multiplication
- On distinguishing prime numbers from composite numbers
- On the deterministic complexity of factoring polynomials over finite fields
- On fast multiplication of polynomials over arbitrary algebras
- Fast multiplication of polynomials over fields of characteristic 2
- Fast multiplication of large numbers
- On the number of divisors of a natural number having the form \(p-1\)
- The Difference Between Consecutive Primes, II
- Modern Computer Algebra
- New algorithms for digital convolution
- Faster Polynomial Multiplication over Finite Fields
- Faster Integer Multiplication
- Searching for Primitive Roots in Finite Fields
- Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
- Faster integer multiplication using short lattice vectors
This page was built for publication: Faster polynomial multiplication over finite fields using cyclotomic coefficient rings
