近年来,学术界对量子计算机的研究逐渐深入,大素数分解问题(Prime Factorization)和离散对数问题(Discrete Logarithm)因此开始变得不再那么困难。然而,当今广泛使用的公钥密码体制的安全大都依赖于这两个问题的困难性,因此,设计抗量子计算机攻击的“后量子时代”密码体制吸引了密码学界越来越多的研究兴趣。在已经提出的几种“后量子时代”密码体制中,格密码体制逐渐成为近年来顶级密码会议和期刊上的研究热点。最短向量问题(Shortest Vector Problem,简称SVP)是格理论(或者说,数的几何)中最重要的问题之一,几种基于格的公钥密码体制(Lattice-Based Cryptography)的安全性都依赖于最短向量问题(SVP)问题的困难性。本文围绕最短向量问题(SVP)展开深入研究,提出了格中短向量在BKZ约化基下的y-稀疏表示,然后利用这种短向量表示的稀疏性提出了解决最短向量问题(SVP)的若干算法,包括SVP遗传算法,SVP模拟退火算法,SVP分段枚举算法,以及SVP随机采样算法。本文的创新点主要包括:?首先,本文提出了在BKZ约化基下的格中短向量的整数y-稀疏表示,同时通过理论证明得到格中短向量的这种表示中各个整数分量的上界及其稀疏性;这种格中短向量的稀疏性具有独立的研究价值。?其次,本文首次将“遗传算法”和“模拟退火算法”等计算智能(Computational Intelligence)的思想应用于最短向量问题(SVP),通过马尔科夫分析和实验验证,这两种算法在解决最短向量问题(SVP)方面收到良好的效果。?最后,本文基于格中短向量的y-稀疏表示提出了分段的概念,利用分段情况下的短向量稀疏表示中非零分量个数的升序排列,提出了SVP分段枚举算法。实验显示,与当前著名SVP枚举算法相比,这种SVP分段枚举算法是目前较为快速而有效的SVP枚举算法。