Optimal polynomial collections for lattice attacks

Definitions and mathematical statement

The source asks for an optimal polynomial collection in multivariate lattice-based small-root methods. A typical instance has an integer polynomial $f\in\mathbb Z[x_1,\ldots,x_n]$, modulus $M\ge2$, and bounds $X_i>0$, and seeks \[ z\in\mathbb Z^n,\qquad |z_i|\le X_i,\qquad f(z)\equiv0\pmod M. \] This is an illustrative framework; the excerpt does not restrict the problem to one input polynomial or one modulus.

Such methods choose auxiliary polynomials $q_j$ with controlled modular vanishing at a sought root, form a lattice from their coefficient vectors after variable scaling by the $X_i$, and seek sufficiently short combinations to produce integer polynomial equations vanishing at that root. Monomial shifts, powers and modulus multiples are usual ingredients. The requested collection must be optimized for the intended instance and success criterion; finding short relations is distinct from proving that enough algebraically useful relations recover all required roots.

The source gives no admissible class of auxiliary polynomials, fixed lattice dimension or reduction budget, objective ordering, input family, or rigorous versus heuristic recovery criterion. Maximizing the root bounds, minimizing running time, minimizing lattice dimension, and maximizing practical success are different optimization problems. No universal maximizer or sharp threshold is defined without these specifications.

The summary says selection is currently guided by heuristics, mentioning the Jochemsz--May extended strategy, and reports no provably optimal general collection rule. No exact theorem or comparison criterion is supplied. The 2006 workshop problem and later open assessment remain source attributions pending primary-literature review.

Short English statement

Choose the best auxiliary polynomials for multivariate lattice small-root algorithms. The source does not specify the admissible collection, computational budget, or meaning of optimal, so the optimization target and success guarantees need to be fixed.

Sources

• Local registry: data/unsolvedmath/problems.json, permanent UnsolvedMath ID $8800027$, source code catalogue entry; supplied statement, background, and research summary, updated 2026-08-06. Attributed to Alexander May.
• IPAM, Workshop on Number Theory and Cryptography---Open Problems (2006), attachment 6222, PDF page 20, printed slide 15: https://www.ipam.ucla.edu/programs/workshops/workshop-i-number-theory-and-cryptography-open-problems/?tab=schedule. Supplied PDF/legacy-PPT visual audit accessed 2026-07-29; it reports 19 inspected surviving attachments.
• Jochemsz--May extended strategy is named by the summary without a full publication citation or precise optimality theorem.