Faster Coppersmith root methods

Definitions and mathematical statement

For an integer polynomial $f\in{\mathbb{Z}}[x_1,\ldots,x_t]$, coordinate bounds $B_i>0$, and possibly a modulus $N\ge2$, a small modular root is an integer tuple satisfying \[ f(x_1,\ldots,x_t)\equiv0\pmod N, \qquad |x_i|\le B_i, \] whereas an integer-root problem requires the exact equation $f(x_1,\ldots,x_t)=0$. Coppersmith-type methods construct lattices of auxiliary polynomials, reduce a lattice basis, and extract roots under suitable size and algebraic hypotheses.

May asks to improve their running time. A valid speed comparison must keep the polynomial class, modulus/height parameters, root bounds, success guarantees, and output task fixed. Finding one root, all roots, or certifying absence can have different costs, and the output size must be counted. Increasing the provable root-size range is a separate improvement from reducing time for the same range.

For example, a benchmark could fix monic univariate inputs of degree $d$ and a root range parameterized below the usual $N^{1/d}$ scale before comparing bit complexity. Multivariate modular or integer-root methods require their own dimension, root-box, and algebraic-independence conditions; a polynomial-time guarantee for a standard univariate setting is not a blanket guarantee for arbitrary multivariate systems.

The source specifies no baseline running-time formula, dimension/degree regime, coefficient encoding, smallness threshold, output requirement, or deterministic/randomized cost model. It therefore poses an algorithm-improvement programme rather than one numerical complexity inequality. The supplied research summary reports incremental lattice-dimension and reduction improvements and no verified definitive general asymptotic improvement. Its reference to an unsettled optimum does not imply that the original request demands a proven optimal algorithm.

Short English statement

Speed up Coppersmith-type small-root algorithms while preserving their input class, recoverable root bounds, and correctness guarantees. The baseline and complexity parameters need specification before an improvement can be assessed.

Sources

• Local UnsolvedMath registry, permanent ID $8800024$, exact source code catalogue entry, "Faster Coppersmith root methods." Proposer Alexander May.
• IPAM Workshop on Number Theory and Cryptography --- Open Problems (2006), attachment 6222, recorded PDF page 18, printed slide 13; https://www.ipam.ucla.edu/programs/workshops/workshop-i-number-theory-and-cryptography-open-problems/?tab=schedule. Recorded access 2026-07-29; pdf-and-legacy-ppt visual-audit extraction.
• Supplied OPEN-TRIAGE research summary names Coppersmith and LLL-based methods but provides no complete algorithm references, exact runtime bound, or matching improvement theorem.