  For any fixed field $K\!\in\!\{\mathbb{Q}_2,\mathbb{Q}_3,\mathbb{Q}_5,
\ldots\}$, we prove that all polynomials $f\!\in\!\mathbb{Z}[x]$ with exactly
$3$ (resp. $2$) monomial terms, degree $d$, and all coefficients having
absolute value at most $H$, can be solved over $K$ within deterministic time
$\log^{7+o(1)}(dH)$ (resp. $\log^{2+o(1)}(dH)$) in the classical Turing model:
Our underlying algorithm correctly counts the number of roots of $f$ in $K$,
and for each such root generates an approximation in $\mathbb{Q}$ with
logarithmic height $O(\log^3(dH))$ that converges at a rate of
$O\!\left((1/p)^{2^i}\right)$ after $i$ steps of Newton iteration. We also
prove significant speed-ups in certain settings, a minimal spacing bound of
$p^{-O(p\log^2_p(dH)\log d)}$ for distinct roots in $\mathbb{C}_p$, and even
stronger repulsion when there are nonzero degenerate roots in $\mathbb{C}_p$:
$p$-adic distance $p^{-O(\log_p(dH))}$. On the other hand, we prove that there
is an explicit family of tetranomials with distinct nonzero roots in
$\mathbb{Z}_p$ indistinguishable in their first $\Omega(d\log_p H)$ most
significant base-$p$ digits.

Number Theory;Computational Complexity