SVP Is NP-Hard for Some Rank-2 Cyclotomic Modules

本文研究分圆环上的格问题计算复杂性。具体而言，作者证明了在二维全秩自由子模上，以 ℓ2-范数定义的判定型最短向量问题（SVP）是 NP-完全的。设 q 为模 4 余 3 的素数，ζ_q 为本原 q 次单位根，K=Q(ζ_q)，环 O_K=Z

历史摘要 · 未重新核验 · arXiv cs.CR