| 摘要 | 第3-4页 |
| Abstract | 第4-5页 |
| 主要符号对照表 | 第9-11页 |
| 第1章 引言 | 第11-18页 |
| 1.1 选题背景与研究意义 | 第11-14页 |
| 1.2 国内外研究进展 | 第14-16页 |
| 1.3 本文主要内容和结构安排 | 第16-18页 |
| 第2章 预备知识 | 第18-27页 |
| 2.1 格 | 第18-19页 |
| 2.2 格基的Gram-Schmidt正交化 | 第19-20页 |
| 2.3 LLL约化基和LLL算法 | 第20-22页 |
| 2.4 BKZ约化基和BKZ算法 | 第22-24页 |
| 2.5 马尔科夫过程 | 第24-27页 |
| 第3章 格中短向量的y-稀疏表示 | 第27-35页 |
| 3.1 格向量的y-表示 | 第27-28页 |
| 3.2 几个有用的定理 | 第28-29页 |
| 3.3 BKZ约化基的几个性质 | 第29-31页 |
| 3.4 格中短向量的y-稀疏表示： 另一种观点下的格向量 | 第31-34页 |
| 3.5 小结 | 第34-35页 |
| 第4章 最短向量问题的遗传算法 | 第35-58页 |
| 4.1 遗传算法概述 | 第35-38页 |
| 4.2 使用y-稀疏表示对格中向量编码的长度上界估计 | 第38-40页 |
| 4.2.1 格中最短向量的y-稀疏表示的各个分量上界 | 第38-39页 |
| 4.2.2 格中向量的编码和解码方式 | 第39-40页 |
| 4.3 SVP遗传算法的算法描述 | 第40-47页 |
| 4.3.1 将格向量编码为染色体 | 第40-41页 |
| 4.3.2 SVP遗传算法的基本操作 | 第41-42页 |
| 4.3.3 SVP遗传算法的描述 | 第42-47页 |
| 4.4 SVP遗传算法的收敛性证明 | 第47-50页 |
| 4.5 SVP遗传算法的启发式改进 | 第50-53页 |
| 4.5.1 局部搜索技术 (local search) | 第50-51页 |
| 4.5.2 启发式剪枝技术 (heuristic pruning) | 第51-52页 |
| 4.5.3 并行实现 | 第52-53页 |
| 4.6 实验结果 | 第53-56页 |
| 4.7 小结 | 第56-58页 |
| 第5章 最短向量问题的分段枚举算法 | 第58-70页 |
| 5.1 y-稀疏表示的几个重要的观察结果 | 第58-62页 |
| 5.2 SVP分段枚举算法描述 | 第62-66页 |
| 5.2.1 概述 | 第62-64页 |
| 5.2.2 Phase Enumeration()和Phase Enumeration Bottom() | 第64-66页 |
| 5.3 实验结果 | 第66-68页 |
| 5.4 小结 | 第68-70页 |
| 第6章 最短向量问题的模拟退火算法 | 第70-85页 |
| 6.1 模拟退火算法概述 | 第70-72页 |
| 6.2 SVP模拟退火算法描述 | 第72-77页 |
| 6.2.1 算法概述 | 第72-73页 |
| 6.2.2 模拟退火： Simulated Annealing() | 第73-75页 |
| 6.2.3 扰动过程： Perturb() | 第75-77页 |
| 6.3 模拟退火算法的收敛性证明 | 第77-80页 |
| 6.3.1 数学模型： 一个非齐次马尔科夫链 | 第77-79页 |
| 6.3.2 收敛性证明 | 第79-80页 |
| 6.4 一种多项式时间复杂度的实际SVP模拟退火算法 | 第80-81页 |
| 6.5 实验结果 | 第81-83页 |
| 6.6 小结 | 第83-85页 |
| 第7章 最短向量问题的随机采样算法 | 第85-91页 |
| 7.1 SVP随机采样算法的描述 | 第85-88页 |
| 7.1.1 算法概述 | 第85-86页 |
| 7.1.2 随机采样过程： Ramdom Sampler() | 第86-88页 |
| 7.2 实验结果 | 第88-89页 |
| 7.3 小结 | 第89-91页 |
| 第8章 结论与未来研究计划 | 第91-94页 |
| 8.1 结论 | 第91-92页 |
| 8.2 未来研究计划 | 第92-94页 |
| 参考文献 | 第94-99页 |
| 致谢 | 第99-101页 |
| 个人简历、在学期间发表的学术论文与研究成果 | 第101页 |
