Counting roots for polynomials modulo prime powers

DOI10.2140/OBS.2019.2.191MaRDI QIDQ6165864zbMATH OpenOpenAlexWikidataFDO

Authors Qi Cheng, Shuhong Gao, J. Maurice Rojas, Daqing Wan

Publication date 2 August 2023

Published in Open Book Series (Search for Journal in Brave)

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

zbMATH Keywords

polynomialsprime powerroot counting

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Number-theoretic algorithms; complexity (11Y16) Solving polynomial systems; resultants (13P15)

Abstract: Suppose $p$ is a prime, $t$ is a positive integer, and $f!in!mathbbZ[x]$ is a univariate polynomial of degree $d$ with coefficients of absolute value $<!p^t$. We show that for any fixed $t$, we can compute the number of roots in $mathbbZ/(p^t)$ of $f$ in deterministic time $(d+logp{)}^{O(1)}$. This fixed parameter tractability appears to be new for $t!geq!3$. A consequence for arithmetic geometry is that we can efficiently compute Igusa zeta functions $Z$, for univariate polynomials, assuming the degree of $Z$ is fixed.

Recommendations

• Computing Igusa's local zeta function of univariates in deterministic polynomial-time
• Randomized polynomial-time root counting in prime power rings
• Counting roots of polynomials over $\mathbb{Z}/p^2\mathbb{Z}$
• Counting basic-irreducible factors \(\operatorname{mod} p^k\) in deterministic poly-time and \(p\)-adic applications
• scientific article; zbMATH DE number 2000852

Cites work

• \(p\)-adic numbers: An introduction.
• A new framework for computing Gröbner bases
• A new incremental algorithm for computing Groebner 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
• Counting (quickly) the number of solutions of equations in finite fields
• Counting solutions to equations in many variables over finite fields
• Deterministic root finding over finite fields using Graeffe transforms
• Factoring modular polynomials
• Factoring polynomials with rational coefficients
• Fast polynomial factorization and modular composition
• Faster p-adic feasibility for certain multivariate sparse polynomials
• Heuristics for the Brauer–Manin Obstruction for Curves
• scientific article; zbMATH DE number 1643926 (Why is no real title available?)
• scientific article; zbMATH DE number 5532114 (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 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?)
• On the deterministic complexity of factoring polynomials
• Polynomial root finding over local rings and application to error correcting codes
• Single-factor lifting and factorization of polynomials over local fields
• Sparse univariate polynomials with many roots over finite fields
• The complexity of the word problems for commutative semigroups and polynomial ideals

Cited in

(8)

• Noisy polynomial interpolation modulo prime powers
• Polynomials with roots mod \(p\) for all primes \(p\)
• scientific article; zbMATH DE number 1305308 (Why is no real title available?)
• Counting basic-irreducible factors \(\operatorname{mod} p^k\) in deterministic poly-time and \(p\)-adic applications
• Randomized polynomial-time root counting in prime power rings
• An effective description of the roots of bivariates mod pk and the related Igusa’s local zeta function
• Solving polynomial systems over non-fields and applications to modular polynomial factoring
• On algorithms to find \(p\)-ordering

This page was built for publication: Counting roots for polynomials modulo prime powers

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