Root repulsion and faster solving for very sparse polynomials over \(p\)-adic fields

DOI10.1016/j.jnt.2022.01.013zbMath1498.11241arXiv2107.09173OpenAlexW3186184273WikidataQ114156579 ScholiaQ114156579MaRDI QIDQ2167518

Yuyu Zhu, J. Maurice Rojas

Publication date: 25 August 2022

Published in: Journal of Number Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2107.09173

zbMATH Keywords

iteration\(p\)-adicNewtontrinomialapproximateroot countingHensel

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Polynomials (11S05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Estimating the number of roots of trinomials over finite fields
• Faster \(p\)-adic feasibility for certain multivariate sparse polynomials
• Single-factor lifting and factorization of polynomials over local fields
• A Wronskian approach to the real \(\tau\)-conjecture
• Sharp bounds for the number of roots of univariate fewnomials
• On the deterministic complexity of factoring polynomials over finite fields
• On fast multiplication of polynomials over arbitrary algebras
• Zeros of sparse polynomials over local fields of characteristic \(p\)
• Factoring modular polynomials
• On finding primitive roots in finite fields
• Metric estimates and membership complexity for Archimedean amoebae and tropical hypersurfaces
• On the distance between the roots of a polynomial
• A refinement of Müller's cube root algorithm
• Root separation for trinomials
• Faster polynomial multiplication over finite fields using cyclotomic coefficient rings
• Explicit Chabauty-Kim for the split Cartan modular curve of level 13
• Sparse univariate polynomials with many roots over finite fields
• Polynomial root finding over local rings and application to error correcting codes
• An inequality for the discriminant of a polynomial
• Primality proving via one round in ECPP and one iteration in AKS
• Recherches sur la méthode de Graeffe et les zéros des polynômes et des séries de Laurent
• Integer multiplication in time \(O(n\log n)\)
• Fast Integer Multiplication Using Modular Arithmetic
• Modern Computer Algebra
• Fewnomial systems with many roots, and an Adelic Tau Conjecture
• Sub-linear root detection, and new hardness results, for sparse polynomials over finite fields
• Roots of sparse polynomials over a finite field
• Fast Polynomial Factorization and Modular Composition
• A near-optimal algorithm for computing real roots of sparse polynomials
• On the Complexity of Familiar Functions and Numbers
• Adleman-Manders-Miller Root Extraction Method Revisited
• Complexity of OM factorizations of polynomials over local fields
• Randomized polynomial-time root counting in prime power rings
• Using zeta functions to factor polynomials over finite fields
• Computational Complexity
• P-adic logarithmic forms and group varieties III
• Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
• Numbers of solutions of equations in finite fields
• On the Number of Solutions of Some Trinomial Equations in a Finite Field
• On the statistical properties of Diffie-Hellman distributions
• Zeta functions of nondegenerate hypersurfaces in toric varieties via controlled reduction in \(p\)-adic cohomology

This page was built for publication: Root repulsion and faster solving for very sparse polynomials over \(p\)-adic fields