Lattice reduction for algebraic-number-theory problems

Definitions and mathematical statement

A number field is a finite extension $K/{\mathbb{Q}}$. Algorithmic problems in algebraic number theory may be presented through a defining polynomial, an order or integral basis, ideals, or algebraic elements, depending on the task. Lattice reduction takes a lattice basis and seeks another basis or short independent vectors satisfying specified geometric quality bounds.

An average-case computational problem includes an instance distribution $\mathcal D_\lambda$, not only a set of instances; its algorithmic guarantees concern quantities such as \[ \Pr_{x\sim\mathcal D_\lambda}[A(x)\text{ returns a correct answer}] \] and the relevant running-time measure. Micciancio's programme is to use lattice reduction together with average-case problems to solve computational problems in algebraic number theory.

The excerpt supplies no particular target problem, instance distribution, reduction, complexity bound, or success guarantee. Thus it calls for concrete algorithmic applications combining both ingredients, rather than asserting that one algorithm solves all algebraic number theory tasks. Average-case problems are not identified specifically as hard or easy here, and this is not automatically a worst-case-to-average-case cryptographic security reduction. The summary mentions factoring-related, unit and class-group computations as scattered examples; these are illustrative directions, not a mandatory exhaustive list or a precise supplied algorithm.

Short English statement

Develop algebraic number theory algorithms that combine lattice reduction with suitable average-case problems. This is a research programme; the target tasks, distributions, and desired guarantees are not specified.

Sources

• Local UnsolvedMath registry, permanent ID 8800075, source code catalogue entry; attributed to Daniele Micciancio; no proposal year supplied; update 2026-08-06.
• IPAM, Workshop on Number Theory and Cryptography --- Open Problems (2006), attachment 6240, PDF page 40: https://www.ipam.ucla.edu/programs/workshops/workshop-i-number-theory-and-cryptography-open-problems/?tab=schedule. Registry access date 2026-07-29; PDF and legacy-PPT visual audit. Provenance reports 19 attachments, 17 PDFs and two legacy PPT decks, with repetitions and solved definitions excluded. Present status and redistribution terms require review.
• The supplied summary describes isolated factoring-related, unit and class-group applications without exact references, and labels the broad programme open rather than claiming a single definitive theorem.