Bit complexity of polynomial GCD on sparse representation

DOI10.1090/MCOM/4054MaRDI QIDQ6927793zbMATH OpenFDO

Authors Qiao-Long Huang, Xiao-Shan Gao

Publication date 18 September 2025

Published in Mathematics of Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1090/MCOM/4054

zbMATH Keywords

finite fieldbit complexitysparse interpolationmultivariate polynomial GCD

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Symbolic computation and algebraic computation (68W30) Number-theoretic algorithms; complexity (11Y16)

Cites work

• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• A fast parallel sparse polynomial GCD algorithm
• A fast parallel sparse polynomial GCD algorithm
• Computing sparse GCD of multivariate polynomials via polynomial interpolation
• Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
• Diversification improves interpolation
• Early termination in sparse interpolation algorithms
• Fast construction of irreducible polynomials over finite fields
• Greatest common divisors of polynomials given by straight-line programs
• On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors
• Randomness efficient identity testing of multivariate polynomials
• Sparse interpolation of multivariate rational functions
• Sparse polynomial interpolation based on diversification
• Subresultants and Reduced Polynomial Remainder Sequences
• The EEZ-GCD algorithm

This page was built for publication: Bit complexity of polynomial GCD on sparse representation

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