A complexity chasm for solving univariate sparse polynomial equations over p-adic fields

2020/02/29 by J. Maurice Rojas, Rojas, J. Maurice, Yuyu Zhu +1
Computer Science · #Coding theory and cryptography #Polynomial and algebraic computation #Cryptography and Residue Arithmetic

paper · pdf · doi:10.48550/arxiv.2003.00314

Abstract

We reveal a complexity chasm, separating the trinomial and tetranomial cases, for solving univariate sparse polynomial equations over certain local fields. First, for any fixed field K∈\ℚ₂,ℚ₃,ℚ₅,…\, we prove that any polynomial f∈ℤ[x] with exactly 3 monomial terms, degree d, and all coefficients having absolute value at most H, can be solved over K in deterministic time O(log^O(1)(dH)) in the classical Turing model. (The best previous algorithms were of complexity exponential in log d, even for just counting roots in ℚ_p.) In particular, our algorithm generates approximations in ℚ with bit-length O(log^O(1)(dH)) to all the roots of f in K, and these approximations converge quadratically under Newton iteration. On the other hand, we give a unified family of tetranomials requiring Ω(dlog H) digits to distinguish the base-p expansions of their roots in K.

Related

• Root Repulsion and Faster Solving for Very Sparse Polynomials Over p-adic Fields
• Faster p-adic Feasibility for Certain Multivariate Sparse Polynomials
• Solving Degenerate Sparse Polynomial Systems Faster
• Solving Polynomial Equations Over Finite Fields
• Additive Complexity and the Roots of Polynomials Over Number Fields and p-adic Fields