SVP Is NP-Hard for Some Rank-2 Cyclotomic Modules
本文研究分圆环上的格问题计算复杂性。具体而言，作者证明了在二维全秩自由子模上，以 ℓ2-范数定义的判定型最短向量问题（SVP）是 NP-完全的。设 q 为模 4 余 3 的素数，ζ_q 为本原 q 次单位根，K=Q(ζ_q)，环 O_K=Z
#svp
共收录 2 条相关情报。
← 返回所有主题Solving the Shortest Vector Problem in $2^{0.6039n}$ Time via Mid-point Hessian
本文提出一种求解最短向量问题（SVP）的随机化算法。SVP 是格密码学中的核心困难问题，其求解复杂度直接关系到基于格的密码方案（如 NTRU、LWE）的安全性评估。此前由 Aggarwal、Dadush、Regev 和 Stephens-D