Two variable polynomial congruences and capacity theory

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.

arXiv comment15 pages