Modular composition via factorization
From MaRDI portal
Publication:722764
DOI10.1016/j.jco.2018.05.002zbMath1430.12003OpenAlexW2785230309WikidataQ129854256 ScholiaQ129854256MaRDI QIDQ722764
Grégoire Lecerf, Joris van der Hoeven
Publication date: 27 July 2018
Published in: Journal of Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jco.2018.05.002
Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Polynomials in general fields (irreducibility, etc.) (12E05) Polynomials over finite fields (11T06) Computational methods for problems pertaining to field theory (12-08)
Related Items
On the complexity exponent of polynomial system solving, Directed evaluation, Univariate polynomial factorization over finite fields with large extension degree, Fast amortized multi-point evaluation, Modular composition via factorization, Fast multivariate multi-point evaluation revisited, Accelerated tower arithmetic
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Deterministic root finding over finite fields using Graeffe transforms
- Fast arithmetics in Artin-Schreier towers over finite fields
- Modular composition via factorization
- A fast numerical algorithm for the composition of power series with complex coefficients
- On fast multiplication of polynomials over arbitrary algebras
- Composing power series over a finite ring in essentially linear time
- Fast rectangular matrix multiplication and applications
- Irreducibles and the composed product for polynomials over a finite field
- Relax, but don't be too lazy
- Recurrent methods for constructing irreducible polynomials over \(\mathbb F_{q}\) of odd characteristics.
- Computing Frobenius maps and factoring polynomials
- Fast computation of special resultants
- Recurrent methods for constructing irreducible polynomials over \(\mathbb F_q\) of odd characteristics. II
- Boolean circuits versus arithmetic circuits
- Handbook of Finite Fields
- Taking roots over high extensions of finite fields
- Modern Computer Algebra
- On p-Adic Differential Equations with Separation of Variables
- Faster Polynomial Multiplication over Finite Fields
- Fast Polynomial Factorization and Modular Composition
- Powers of tensors and fast matrix multiplication
- Probabilistic Algorithms in Finite Fields
- Fast Algorithms for Manipulating Formal Power Series
- Subquadratic-time factoring of polynomials over finite fields
- Composition Modulo Powers of Polynomials
- A fast algorithm for reversion of power series
- On irreducible polynomials of certain types in finite fields
- On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials
- On the number of positive integers less than 𝑥 and free of prime divisors greater than 𝑥^{𝑐}
- Fast construction of irreducible polynomials over finite fields
- Fast construction of irreducible polynomials over finite fields
