arXiv:2611.14334 · v1

$\mathsf{SVP}_\infty$ Is NP-Hard for Power-of-two Cyclotomic Ideals

$\mathsf{SVP}_\infty$ 在二的幂次分圆理想中是 NP-难的

首次提交 2026-11-11 00:57

版本更新 2026-11-11 00:57

雷达观测 2026-11-11 13:07

摘要

We prove that exact decision-$\mathsf{SVP}$ in the coefficient $\ell_\infty$-norm is $\mathsf{NP}$-complete for principal ideals and free modules of rank two over the cyclotomic rings $R_n=\mathbb{Z}[X]/(X^n+1)$, where $n$ ranges over powers of two. For each case, we give a deterministic polynomial-time many-one reduction from the Subset Sum problem. For an instance with $s$ positive input integers, the output lattice has dimension $O(s)$. A solution to the original Subset Sum instance can be recovered in polynomial time from any nonzero output lattice vector of norm at most the specified bound. We also transfer these reductions from $R_n$ to the power-of-two cyclic rings $S_{2n}=\mathbb{Z}[X]/(X^{2n}-1)$. This gives $\mathsf{NP}$-completeness of decision-$\mathsf{SVP}$ in the coefficient $\ell_\infty$-norm for principal ideals and free modules of any fixed positive rank over these rings.