2021/02/02 by Caleb Robelle, Robelle, Caleb, J. Maurice Rojas +3
Computer Science · Mathematics · #Algebraic Geometry (math.AG) #Coding theory and cryptography #Combinatorics #Computational Complexity (cs.CC) #Cryptography and Data Security #Cryptography and Residue Arithmetic #FOS: Computer and information sciences #FOS: Mathematics #Geometry #Mathematical analysis #Mathematics #Number Theory (math.NT) #Point (geometry) #Prime (order theory) #Prime power #Variable (mathematics) #cs.CC #math.AG #math.NT
paper · pdf · doi:10.48550/arxiv.2102.01626
18 pages, no figures. Submitted to a conference. Comments and questions welcome!
arxiv created 2021/02/02 · openalex publication_date 2021/02/02 · arxiv updated 2021/02/03 · openalex created_date 2021/02/15 · openalex updated_date 2026/07/28
Let k,p∈ ℕ with p prime and let f∈ℤ[x1,x2] be a bivariate polynomial with degree d and all coefficients of absolute value at most pk. Suppose also that f is variable separated, i.e., f=g1+g2 for gi∈ℤ[xi]. We give the first algorithm, with complexity sub-linear in p, to count the number of roots of f over ℤ mod pk for arbitrary k: Our Las Vegas randomized algorithm works in time (dklog p)O(1)√(p), and admits a quantum version for smooth curves working in time (dlog p)O(1)k. Save for some subtleties concerning non-isolated singularities, our techniques generalize to counting roots of polynomials in ℤ[x1,…,xn] over ℤ mod pk. Our techniques are a first step toward efficient point counting for varieties over Galois rings (which is relevant to error correcting codes over higher-dimensional varieties), and also imply new speed-ups for computing Igusa zeta functions of curves. The latter zeta functions are fundamental in arithmetic geometry.