Randomized polynomial-time root counting in prime power rings

DOI10.1090/MCOM/3431MaRDI QIDQ5235106zbMATH OpenOpenAlexWikidataFDO

Authors Leann Kopp, Natalie Randall, J. Maurice Rojas, Yuyu Zhu

Publication date 7 October 2019

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

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

zbMATH Keywords

Las Vegas randomized algorithm

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Number-theoretic algorithms; complexity (11Y16) Computational number theory (11Y99) Finite rings and finite-dimensional associative algebras (16P10)

Abstract: Suppose $k,p!in!mathbbN$ with $p$ prime and $f!in!mathbbZ[x]$ is a univariate polynomial with degree $d$ and all coefficients having absolute value less than $p^k$. We give a Las Vegas randomized algorithm that computes the number of roots of $f$ in $mathbbZ/!left(p^{k}ight)$ within time $d^3(klogp{)}^{2+o(1)}$. (We in fact prove a more intricate complexity bound that is slightly better.) The best previous general algorithm had (deterministic) complexity exponential in $k$. We also present some experimental data evincing the potential practicality of our algorithm.

Recommendations

• Counting roots of polynomials over $\mathbb{Z}/p^2\mathbb{Z}$
• Fast computation of the roots of polynomials over the ring of power series
• Randomized NP-completeness for p -adic rational roots of sparse polynomials in one variable
• Detecting lacunary perfect powers and computing their roots
• On solving univariate sparse polynomials in logarithmic time

Cites work

• A new framework for computing Gröbner bases
• Algorithmic theory of zeta functions over finite fields
• Complex powers and asymptotic expansions. I. Functions of certain types.
• Computing zeta functions of nondegenerate curves
• Congruences, Trees, and 𝑝-adic Integers
• Counting (quickly) the number of solutions of equations in finite fields
• Counting roots for polynomials modulo prime powers
• Counting solutions to equations in many variables over finite fields
• Factoring modular polynomials
• Factoring polynomials over \(\mathbb Z_4\) and over certain Galois rings
• Factoring polynomials with rational coefficients
• Factorization of polynomials over \(\mathbb{Z}/(p^n)\)
• Fast polynomial factorization and modular composition
• Faster p-adic feasibility for certain multivariate sparse polynomials
• scientific article; zbMATH DE number 1643926 (Why is no real title available?)
• scientific article; zbMATH DE number 435565 (Why is no real title available?)
• scientific article; zbMATH DE number 5532114 (Why is no real title available?)
• scientific article; zbMATH DE number 51347 (Why is no real title available?)
• scientific article; zbMATH DE number 66069 (Why is no real title available?)
• scientific article; zbMATH DE number 66619 (Why is no real title available?)
• scientific article; zbMATH DE number 3460471 (Why is no real title available?)
• scientific article; zbMATH DE number 1305308 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 2000852 (Why is no real title available?)
• scientific article; zbMATH DE number 918133 (Why is no real title available?)
• scientific article; zbMATH DE number 3286953 (Why is no real title available?)
• Modern computer algebra
• Polynomial root finding over local rings and application to error correcting codes
• Primality proving via one round in ECPP and one iteration in AKS
• Single-factor lifting and factorization of polynomials over local fields

Cited in

(12)

• \#P-completeness of counting roots of a sparse polynomial
• Noisy polynomial interpolation modulo prime powers
• Root repulsion and faster solving for very sparse polynomials over \(p\)-adic fields
• On the coefficient-choosing game
• Counting and testing dominant polynomials
• Counting basic-irreducible factors \(\operatorname{mod} p^k\) in deterministic poly-time and \(p\)-adic applications
• Counting roots of polynomials over $\mathbb{Z}/p^2\mathbb{Z}$
• An effective description of the roots of bivariates mod pk and the related Igusa’s local zeta function
• Counting roots for polynomials modulo prime powers
• Solving polynomial systems over non-fields and applications to modular polynomial factoring
• A complexity chasm for solving univariate sparse polynomial equations over p-adic fields
• Solutions of a Polynomial Equation Modulo a Prime Power

This page was built for publication: Randomized polynomial-time root counting in prime power rings

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