Faster polynomial multiplication over finite fields

DOI10.1145/3005344zbMATH Open1426.68310arXiv1407.3361OpenAlexW1764552993MaRDI QIDQ3177879FDOQ3177879

Authors: 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)

Abstract: Let p be a prime, and let M_p(n) denote the bit complexity of multiplying two polynomials in F_p[X] of degree less than n. For n large compared to p, we establish the bound M_p(n) = O(n log n 8^(log^* n) log p), where log^* is the iterated logarithm. This is the first known F"urer-type complexity bound for F_p[X], and improves on the previously best known bound M_p(n) = O(n log n log log n log p).

Full work available at URL: https://arxiv.org/abs/1407.3361

Recommendations

• Faster polynomial multiplication over finite fields using cyclotomic coefficient rings
• Multiplicative complexity of polynomial multiplication over finite fields
• Polynomial multiplication over finite fields in time \(O(n\log n)\)
• STACS 2005
• On the complexity of multiplication in finite fields

zbMATH Keywords

algorithmFFTfinite fieldcomplexity boundpolynomial multiplication

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Polynomials over finite fields (11T06) Number-theoretic algorithms; complexity (11Y16)

Cited In (31)

• Fast algorithm of square rooting in some finite fields of odd characteristic
• Fast Hermite interpolation and evaluation over finite fields of characteristic two
• Accelerated tower arithmetic
• Dense Arithmetic over Finite Fields with the CUMODP Library
• Faster polynomial multiplication via multipoint Kronecker substitution
• Polynomial evaluation over finite fields: new algorithms and complexity bounds
• Improved method for finding optimal formulas for bilinear maps in a finite field
• On the complexity of integer matrix multiplication
• On fast multiplication of polynomials over arbitrary algebras
• Modular composition via factorization
• Faster polynomial multiplication via discrete Fourier transforms
• Faster polynomial multiplication over finite fields using cyclotomic coefficient rings
• Deterministic computation of the characteristic polynomial in the time of matrix multiplication
• Integer multiplication in time \(O(n\log n)\)
• Faster integer multiplication using plain vanilla FFT primes
• Polynomial multiplication over finite fields in time \(O(n\log n)\)
• Algorithms for simultaneous Hermite-Padé approximations
• A probabilistic algorithm for verifying polynomial middle product in linear time
• Fast polynomial multiplication over \(\mathbb{F}_{2^{60}}\)
• Multiplication
• Threshold encryption with silent setup
• Fast Gröbner basis computation and polynomial reduction for generic bivariate ideals
• Fast multivariate multi-point evaluation revisited
• Directed evaluation
• Polynomial Multiplication over Binary Fields Using Charlier Polynomial Representation with Low Space Complexity
• Polynomial multiplication over finite fields: from quadratic to straight-line complexity
• Multiplicative complexity of polynomial multiplication over finite fields
• Computing the Characteristic Polynomial of Endomorphisms of a finite Drinfeld Module using Crystalline Cohomology
• Low-Weight Polynomial Form Integers for Efficient Modular Multiplication
• Fast Multiplication for Skew Polynomials
• Fast computation of approximant bases in canonical form

This page was built for publication: Faster polynomial multiplication over finite fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177879)