Two variable polynomial congruences and capacity theory

2021/11/28 by Ted Chinburg, Chinburg, T., Falk, B. Hemenway +4
Computer Science · #11H06 #14H25 #Algebraic Geometry (math.AG) #Complexity and Algorithms in Graphs #Cryptography and Data Security #FOS: Mathematics #Number Theory (math.NT) #Polynomial and algebraic computation

paper · pdf · doi:10.48550/arxiv.2111.14180

openalex publication_date 2021/11/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We use capacity theory to analyze Coppersmith's method for finding small solutions of linear two variable polynomial congruences. We show that the method will succeed in a positive proportion of cases and fail in a different positive proportion of cases. We also bound the number of small solutions via capacity theory.

Related

• Cryptographic applications of capacity theory: On the optimality of Coppersmith's method for univariate polynomials
• The larger sieve and polynomial congruences
• Exponential sums and polynomial congruences in two variables: the quasi-homogeneous case
• Solutions to polynomial congruences in well shaped sets
• Linear Congruences in several variables with congruence restrictions