Approximate common divisors via lattices

Henry Cohn, Nadia Heninger

We analyze the multivariate generalization of Howgrave-Graham's algorithm for the approximate common divisor problem. In the m-variable case with modulus N and approximate common d…