An algebraic LLL algorithm

Definitions and mathematical statement

Let $K$ be a number field, $\mathcal O$ an order in $K$, and $I$ an ideal or fractional ideal. Through the real and complex embeddings of $K$, $I$ gives a Euclidean lattice of rank $[K:{\mathbb{Q}}]$, with a norm/complex-coordinate weighting that must be specified. This is a standard ideal-lattice setting; the source does not fix the field, order, norm, or admissible ideals.

For comparison, an ordinary LLL-reduced ${\mathbb{Z}}$-basis uses Gram--Schmidt vectors $b_i^*$ and coefficients $\mu_{ij}$, size reduction $|\mu_{ij}|\le1/2$, and a Lovász condition such as \[ \delta\|b_i^*\|^2\le \|b_{i+1}^*\|^2+\mu_{i+1,i}^2\|b_i^*\|^2, \qquad\tfrac14<\delta<1. \] The problem asks to develop an algebraic analogue exploiting ideal-lattice structure, rather than treating the input only as an unstructured integer basis.

The source does not state which algebraic representation or allowed operations replace the integer-basis operations, what reduction conditions should be achieved, or what approximation, complexity, and structure-preservation guarantees are required. An ideal need not be principal, so a proposed algebraic basis convention must distinguish ideals from free modules and explain which class it handles. No restriction to principal, cyclotomic, or maximal-order ideals is silently imposed.

Thus the target is an algorithmic research program: specify and realize a genuinely structure-using reduction notion and prove the intended guarantees. The ordinary LLL display explains the comparison only; it is not a theorem that its guarantees automatically carry over to an unspecified algebraic construction.

Short English statement

Design an LLL-like reduction method that uses the multiplication and arithmetic structure of ideal lattices, with explicit reduction and performance guarantees. The intended algebraic representation and field class are missing.

The supplied summary reports ideal/module-lattice techniques and speedups, naming Nguyen--Stehlé and Lee--Lee--Yoo, but supplies no exact algorithms or theorems matching this request. Its reference to algebraic/RLWE reductions does not by itself identify a basis-reduction procedure. The partial-progress label and 2006 problem are retained with current primary-literature audit required.

Sources

• Local UnsolvedMath registry, permanent ID 8800069, source code catalogue entry, "An algebraic LLL algorithm," proposed by Daniele Micciancio. Dataset curation and metadata: Ulam AI and UnsolvedMath Contributors, CC BY 4.0.
• IPAM, Workshop on Number Theory and Cryptography --- Open Problems (2006), Attachment 6240, PDF page 37, schedule locator https://www.ipam.ucla.edu/programs/workshops/workshop-i-number-theory-and-cryptography-open-problems/?tab=schedule; pdf-and-legacy-ppt visual-audit extraction, accessed 2026-07-29.
• Nguyen--Stehlé and Lee--Lee--Yoo are named in the supplied summary without complete references or exact ideal/module reduction results.
• Source provenance reports inspection of 17 PDFs and two legacy PPT decks among 19 surviving attachments, excluding repetitions and solved definitions; this is supplied provenance, not a new inspection claimed here.
• Current primary-literature status audit and redistribution terms NEEDS_REVIEW for the publicly accessible author/publisher copy, separately from the dataset licence.