Given a modular polynomial equation f(x_1,…,x_n)equiv 0 pmod N and the associated lattice-based Coppersmith method, determine the optimal asymptotic region of exponents (beta_1,…,beta_n) for which roots satisfying |x_i|≤ N^beta_i can be recovered as N→∞, and prove matching upper and lower bounds for the method in general.

Coppersmith small-root problem

The problem concerns the general limits and optimization of Coppersmith’s lattice-based method for finding small modular polynomial roots. Recent results address narrower multivariate, implementation, and bound-analysis questions rather than proving a general theorem or giving a counterexample.

Known results

A 2016 capacity-theory paper proves that broad auxiliary-polynomial constructions cannot generally improve Coppersmith’s univariate root-size exponent $1/d$ to $1/d+\epsilon$ .

2026 specialized improvements

A 2026 ePrint paper reports improved multivariate bounds and lower sample and lattice-dimension requirements in selected cryptanalytic problems, including a heuristic claim about a Boneh et al. conjecture; it does not address the general problem. A separate August 2026 report formulates bound analysis as linear programming and obtains improvements in several specialized settings, explicitly without solving the general problem.

Current status (as of August 2026): The general Coppersmith small-root problem has no reported proof, counterexample, or claimed resolution; only specialized improvements are established or claimed.

Coppersmith small-root problem

Progress summary

Primary source

Additional references

Solutions 0