Deterministic root finding over finite fields using Graeffe transforms
From MaRDI portal
Publication:300881
DOI10.1007/s00200-015-0280-5zbMath1346.13056OpenAlexW2223609897MaRDI QIDQ300881
Bruno Grenet, Grégoire Lecerf, Joris van der Hoeven
Publication date: 29 June 2016
Published in: Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00200-015-0280-5
Symbolic computation and algebraic computation (68W30) Polynomials over finite fields (11T06) Polynomials, factorization in commutative rings (13P05)
Related Items
Implementing the Tangent Graeffe Root Finding Method, On the complexity exponent of polynomial system solving, Computing Riemann-Roch spaces via Puiseux expansions, On the computation of rational solutions of underdetermined systems over a finite field, Counting roots for polynomials modulo prime powers, Fast computation of generic bivariate resultants, On the complexity of the Lickteig-Roy subresultant algorithm, Modular composition via factorization, Accelerated tower arithmetic, A Generalised Successive Resultants Algorithm
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Even faster integer multiplication
- Factoring polynomials modulo special primes
- On the deterministic complexity of factoring polynomials over finite fields
- Factoring polynomials and primitive elements for special primes
- Smoothness and factoring polynomials over finite fields
- On fast multiplication of polynomials over arbitrary algebras
- Extracting sparse factors from multivariate integral polynomials
- New techniques for the computation of linear recurrence coefficients
- Polynomial evaluation and interpolation on special sets of points
- Fast separable factorization and applications
- Fast computation of special resultants
- Randomized Root Finding over Finite FFT-fields using Tangent Graeffe Transforms
- Handbook of Finite Fields
- Faster deterministic integer factorization
- Tracking -adic precision
- Using partial smoothness of 𝑝-1 for factoring polynomials modulo 𝑝
- Fast Polynomial Factorization and Modular Composition
- Generalized riemann hypothesis and factoring polynomials over finite fields
- A Deterministic Algorithm for Factorizing Polynomials of Fq [X]
- Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p
- Probabilistic Algorithms in Finite Fields
- A New Algorithm for Factoring Polynomials Over Finite Fields
- Searching for Primitive Roots in Finite Fields
- Subgroup Refinement Algorithms for Root Finding in $GF(q)$
- Galois Groups and Factoring Polynomials over Finite Fields
- On the Efficiency of Algorithms for Polynomial Factoring
- An improved algorithm for computing logarithms over<tex>GF(p)</tex>and its cryptographic significance (Corresp.)
- Solving a Polynomial Equation: Some History and Recent Progress
- Comments on search procedures for primitive roots
- Deterministic polynomial factoring and association schemes
- Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
- Factoring Polynomials Over Large Finite Fields
- Factoring polynomials over finite fields: A survey
- On the deterministic complexity of factoring polynomials
- A Gröbner free alternative for polynomial system solving
- Tangent Graeffe iteration