Modular composition via factorization
DOI10.1016/J.JCO.2018.05.002zbMATH Open1430.12003OpenAlexW2785230309WikidataQ129854256 ScholiaQ129854256MaRDI QIDQ722764FDOQ722764
Authors: Joris van der Hoeven, Grégoire Lecerf 
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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Polynomials over finite fields (11T06) Number-theoretic algorithms; complexity (11Y16) Polynomials in general fields (irreducibility, etc.) (12E05) Computational methods for problems pertaining to field theory (12-08)
Cites Work
- Powers of tensors and fast matrix multiplication
- Title not available (Why is that?)
- On fast multiplication of polynomials over arbitrary algebras
- Relax, but don't be too lazy
- Handbook of finite fields
- An introduction to the theory of numbers. Edited and revised by D. R. Heath-Brown and J. H. Silverman. With a foreword by Andrew Wiles
- Title not available (Why is that?)
- Boolean circuits versus arithmetic circuits
- Fast polynomial factorization and modular composition
- Fast Algorithms for Manipulating Formal Power Series
- Title not available (Why is that?)
- Modern computer algebra
- Fast computation of special resultants
- Deterministic root finding over finite fields using Graeffe transforms
- Probabilistic Algorithms in Finite Fields
- On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials
- Fast rectangular matrix multiplication and applications
- Computing Frobenius maps and factoring polynomials
- Title not available (Why is that?)
- Fast construction of irreducible polynomials over finite fields
- Subquadratic-time factoring of polynomials over finite fields
- Title not available (Why is that?)
- Fast construction of irreducible polynomials over finite fields
- Fast arithmetics in Artin-Schreier towers over finite fields
- On irreducible polynomials of certain types in finite fields
- Recurrent methods for constructing irreducible polynomials over \(\mathbb F_{q}\) of odd characteristics.
- Recurrent methods for constructing irreducible polynomials over \(\mathbb F_q\) of odd characteristics. II
- Taking roots over high extensions of finite fields
- A fast numerical algorithm for the composition of power series with complex coefficients
- Irreducibles and the composed product for polynomials over a finite field
- Composing power series over a finite ring in essentially linear time
- On \(p\)-adic differential equations with separation of variables
- Faster polynomial multiplication over finite fields
- Composition modulo powers of polynomials
- A fast algorithm for reversion of power series
- On the number of positive integers less than 𝑥 and free of prime divisors greater than 𝑥^{𝑐}
- Modular composition via factorization
Cited In (11)
- Accelerated tower arithmetic
- Simultaneous modular reduction and Kronecker substitution for small finite fields
- Modular composition modulo triangular sets and applications
- Modular composition via factorization
- On the complexity exponent of polynomial system solving
- Fast polynomial factorization and modular composition
- Composition modulo powers of polynomials
- Fast amortized multi-point evaluation
- Fast multivariate multi-point evaluation revisited
- Directed evaluation
- Univariate polynomial factorization over finite fields with large extension degree
This page was built for publication: Modular composition via factorization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q722764)
