高通路线上：精确算法与近似算法比较

本文主要探讨了精确算法在近似算法和精确求解短向量问题中的重要性，特别是与密码学紧密相关的格理论和算法。首先，关于近似算法，自1982年H. Lenstra、A. Lenstra和Lovasz提出著名的LLL算法以来，它在多项式时间内提供近似因子为\( \left(1 + \frac{24}{\epsilon}\right)^{\frac{1}{3}}n \)的短向量，对格理论和密码学有深远影响。后来，Schnorr通过分块约化扩展了LLL算法，降低了近似因子至\( \frac{n}{k^2} \)，而Gama和Nguyen在2008年的改进进一步将因子减小到\( \left(1 - \gamma k\right)^{-1}n^{1-\frac{k}{2}} \)。BKZ算法，由Schnorr和Euchner在1994年提出，随后Chen和Nguyen在2011年的更新版本中提高了效率并提供了精确模拟。 精确算法则分为确定性和随机算法两大类。早期的确定性算法如枚举算法，通过QR分解和Gram-Schmidt正交化方法求解，时间复杂度从最初的\( 2^{2n} \)逐渐优化到\( n^{2+o(n)} \)。其中，Kannan和Helfrich的工作做出了关键贡献。实际应用中，枚举算法常采用裁剪技术来改善效率，如Gama等人在2010年EUROCRYPT会议上提出的极端裁剪技术理论上降低了复杂度，但主项保持不变。Micciancio和Voulgaris在2010年提出的算法是当时理论上的最优确定性SVP和CVP求解方法，它巧妙地结合了相关向量和CVP问题，并利用格点的Voronoi细胞结构。 格密码学作为一个抗量子计算攻击的公钥密码体制，其发展涉及到多个交叉学科，包括格理论、计算复杂性理论、算法设计和密码分析。文章回顾了过去30年来在格困难问题求解、计算复杂性、格密码体制设计以及密码分析等方面的主要研究进展，展示了这些领域方法的渗透与融合。同时，文中也简要概述了一些对格密码学研究产生重要影响的经典格数学问题和研究方法。 关键词：格理论、密码分析、格密码体制、格困难问题、计算复杂性。