Deterministic root finding over finite fields using Graeffe transforms
From MaRDI portal
Let us consider the finite field \(\mathbb{F}_q\) with \(q=p^k\) elements where \(p\) is a prime number and \(k\geq 1\). Suppose that \(f\in \mathbb{F}_q[x]\) is a polynomial such that all its irreducible factors are linear with multiplicity one. In the paper under review, the authors propose new deterministic algorithms, based on Graeffe transforms for computing all roots of \(f\). Furthermore, they present a new algorithm for computing characteristic polynomial of multiplication endomorphisms in finite field extensions.
Recommendations
Cites work
- A Deterministic Algorithm for Factorizing Polynomials of Fq [X]
- A Gröbner free alternative for polynomial system solving
- A New Algorithm for Factoring Polynomials Over Finite Fields
- An improved algorithm for computing logarithms over<tex>GF(p)</tex>and its cryptographic significance (Corresp.)
- Comments on search procedures for primitive roots
- Deterministic polynomial factoring and association schemes
- Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p
- Even faster integer multiplication
- Extracting sparse factors from multivariate integral polynomials
- Factoring polynomials and primitive elements for special primes
- Factoring polynomials modulo special primes
- Factoring polynomials over finite fields using balance test
- Factoring polynomials over finite fields: A survey
- Factoring Polynomials Over Large Finite Fields
- Fast computation of special resultants
- Fast polynomial factorization and modular composition
- Fast separable factorization and applications
- Faster deterministic integer factorization
- Galois Groups and Factoring Polynomials over Finite Fields
- Generalized riemann hypothesis and factoring polynomials over finite fields
- Handbook of finite fields
- scientific article; zbMATH DE number 4065121 (Why is no real title available?)
- scientific article; zbMATH DE number 1273636 (Why is no real title available?)
- scientific article; zbMATH DE number 1936673 (Why is no real title available?)
- scientific article; zbMATH DE number 2151173 (Why is no real title available?)
- scientific article; zbMATH DE number 799779 (Why is no real title available?)
- scientific article; zbMATH DE number 3265895 (Why is no real title available?)
- Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
- New techniques for the computation of linear recurrence coefficients
- On fast multiplication of polynomials over arbitrary algebras
- On the deterministic complexity of factoring polynomials
- On the deterministic complexity of factoring polynomials over finite fields
- On the Efficiency of Algorithms for Polynomial Factoring
- Polynomial evaluation and interpolation on special sets of points
- Probabilistic Algorithms in Finite Fields
- Randomized root finding over finite FFT-fields using tangent Graeffe transforms
- Searching for Primitive Roots in Finite Fields
- Smoothness and factoring polynomials over finite fields
- Solving a Polynomial Equation: Some History and Recent Progress
- Subgroup Refinement Algorithms for Root Finding in GF(q)
- Tangent Graeffe iteration
- Tracking p-adic precision
- Using partial smoothness of p-1 for factoring polynomials modulo p
Cited in
(21)- On the complexity of the Lickteig-Roy subresultant algorithm
- Fast computation of generic bivariate resultants
- Computing Riemann-Roch spaces via Puiseux expansions
- Accelerated tower arithmetic
- On the complexity exponent of polynomial system solving
- On the computation of rational solutions of underdetermined systems over a finite field
- Randomized root finding over finite FFT-fields using tangent Graeffe transforms
- scientific article; zbMATH DE number 4065121 (Why is no real title available?)
- Subgroup Refinement Algorithms for Root Finding in GF(q)
- A Graph-Based Unified Technique for Computing and Representing Coefficients over Finite Fields
- A geometric approach to root finding in GT(q/sup m/)
- Implementing the tangent Graeffe root finding method
- Computing one billion roots using the tangent Graeffe method
- A generalized successive resultants algorithm
- Deterministic root finding in finite fields
- Character sums and deterministic polynomial root finding in finite fields
- Counting roots for polynomials modulo prime powers
- Root-Squaring for Root-Finding
- Efficient computation of Riemann-Roch spaces for plane curves with ordinary singularities
- Sparse polynomial interpolation: faster strategies over finite fields
- Modular composition via factorization
This page was built for publication: Deterministic root finding over finite fields using Graeffe transforms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q300881)
