本文研究分圆环上的格问题计算复杂性。具体而言，作者证明了在二维全秩自由子模上，以 ℓ2-范数定义的判定型最短向量问题（SVP）是 NP-完全的。设 q 为模 4 余 3 的素数，ζ_q 为本原 q 次单位根，K=Q(ζ_q)，环 O_K=Z[ζ_q]。固定模秩为 2，但作为 Z-格，秩为 2(q-1)，随 q 增长。主要障碍是 O_K 作用下的封闭性：模块中任一非零向量蕴含其所有 O_K 标量倍，其中一些可能更短，从而干扰判定。作者提出三个关键思路克服该障碍：1) 将 Bennett-Peikert Reed-Solomon 格映射到主分圆理想，并利用 Wan 的点计数估计证明该理想的陪集含大量二进制系数表示；2) 基于二次高斯和的“检查器”将 X3C（精确覆盖三集）方程转化为规范化平方范数；3) 检查器与第二模坐标结合，利用理想陪集分离界限排除 O_K 作用产生的所有非预期向量。每个构造实例包含素数 q≡3 mod 4、两个非零行列式的积分生成元、以及一个整数平方阈值。该构造还通过多项式时间 Turing 归约给出 search-SVP 的 NP-难性。该工作属于密码学与计算复杂性理论交叉领域，对基于格的密码学（尤其 cyclotomic 结构）安全性分析有理论意义。适合对格基密码、计算复杂性理论、代数数论感兴趣的科研人员阅读。

本文提出一种求解最短向量问题（SVP）的随机化算法。SVP 是格密码学中的核心困难问题，其求解复杂度直接关系到基于格的密码方案（如 NTRU、LWE）的安全性评估。此前由 Aggarwal、Dadush、Regev 和 Stephens-Davidowitz 在 STOC'15 上给出的最佳算法需要 2^{n+o(n)} 的时间和空间。本文通过利用周期高斯函数在半最短向量处的 Hessian 矩阵特性，显著改进了复杂度：经典环境下时间复杂度为 2^{0.6039n+o(n)}，量子环境下为 2^{0.5411n+o(n)}，空间复杂度为 2^{0.5n+o(n)}。核心思想是：对于最短向量 v，在 v/2 处的 Hessian 矩阵存在一个与 v 方向接近的特征向量，借助预处理的有界距离解码（BDD）算法可以恢复 v。由于函数关于格 L 具有周期性，候选中点可由商格 L/2L 中的奇偶类索引。算法通过离散高斯采样估计对应 Hessian，从而搜索最短向量的奇偶类。作者还引入了随机子格陪集和多种采样技术来优化复杂度，这些优化方法本身可能具有独立价值。该论文属于理论算法研究，对格密码分析具有潜在影响，但当前仅基于摘要，尚未验证实验实现或实际攻击场景。