Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

   
 
 

 

Randomized polynomial-time root counting in prime power rings


Authors: Leann Kopp, Natalie Randall, J. Maurice Rojas and Yuyu Zhu
Journal: Math. Comp. 89 (2020), 373-385
MSC (2010): Primary 11Y16, 11Y99, 16P10
DOI: https://doi.org/10.1090/mcom/3431
Published electronically: April 9, 2019
Full-text PDF
View in AMS MathViewer New

Abstract | References | Similar Articles | Additional Information

Abstract: Suppose $ k,p\!\in \!\mathbb{N}$ with $ p$ prime and $ f\!\in \!\mathbb{Z}[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 $ \mathbb{Z}/\!\left (p^k\right )$ within time $ d^3(k\log p)^{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.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y16, 11Y99, 16P10

Retrieve articles in all journals with MSC (2010): 11Y16, 11Y99, 16P10


Additional Information

Leann Kopp
Affiliation: Department of Mathematics, Auburn University, 221 Parker Hall, Auburn, Alabama 36849
Email: LHK0002@auburn.edu

Natalie Randall
Affiliation: Department of Mathematics, Austin College, 900 N. Grand Avenue, Sherman, Texas 75090
Email: natgrandall@gmail.com

J. Maurice Rojas
Affiliation: Department of Mathematics, Texas A&M University, 3368, College Station, Texas 77843-3368
Email: rojas@math.tamu.edu

Yuyu Zhu
Affiliation: Department of Mathematics, Texas A&M University, 3368, College Station, Texas 77843-3368
Email: zhuyuyu@math.tamu.edu

DOI: https://doi.org/10.1090/mcom/3431
Received by editor(s): September 15, 2018
Received by editor(s) in revised form: January 4, 2019, and January 19, 2019
Published electronically: April 9, 2019
Additional Notes: The first and second authors were partially supported by NSF REU grants DMS-1757872 and DMS-1460766.
The third author is the corresponding author
The third and fourth authors were partially supported by NSF grant CCF-1409020, and NSF REU grants DMS-1757872 and DMS-1460766.
Article copyright: © Copyright 2019 by the authors