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