Randomized root finding over finite FFT-fields using tangent Graeffe transforms

DOI10.1145/2755996.2756647MaRDI QIDQ2819758zbMATH OpenOpenAlexFDO

Authors Bruno Grenet, Joris van der Hoeven, Grégoire Lecerf

Publication date 29 September 2016

Published in Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2755996.2756647

zbMATH Keywords

finite fieldsMathemagixpolynomial root finding

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Symbolic computation and algebraic computation (68W30)

Recommendations

• Deterministic root finding over finite fields using Graeffe transforms
• Implementing the tangent Graeffe root finding method
• Computing one billion roots using the tangent Graeffe method
• Taking roots over high extensions of finite fields
• A geometric approach to root finding in GT(q/sup m/)

Cited in

(10)

• A fast parallel sparse polynomial GCD algorithm
• On the computation of rational solutions of underdetermined systems over a finite field
• Deterministic root finding over finite fields using Graeffe transforms
• Implementing the tangent Graeffe root finding method
• Computing one billion roots using the tangent Graeffe method
• A generalized successive resultants algorithm
• Fast interpolation of multivariate polynomials with sparse exponents
• Sparse polynomial interpolation: faster strategies over finite fields
• Factoring sparse polynomials fast
• Optimizing the half-gcd algorithm

Describes a project that uses

Uses Software

• tangent Graeffe
• gmp
• FLINT
• Mathemagix
• NTL

This page was built for publication: Randomized root finding over finite FFT-fields using tangent Graeffe transforms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2819758)