Two variable polynomial congruences and capacity theory

Abstract

Coppersmith's method for finding small solutions of multivariable congruences uses lattice techniques to find sufficiently many algebraically independent polynomials that must vanish on such solutions. We apply adelic capacity theory in the case of two variable linear congruences to determine when there is a second such auxiliary polynomial given one such polynomial. We show that in a positive proportion of cases, no such second polynomial exists, while in a different positive proportion one does exist. This has applications to learning with errors and to bounding the number of small solutions.