毕业论文：格基规约算法研究

《毕业论文：格基规约算法研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、目录摘要IAbstractIV第一章引言6课题的背景和意义6第二章格问题的研究72.1格问题的发展72.2格问题的算法发展72.2.1精确算法72.2.2近似算法82.3格问题的基础知识92.3.1低复杂度的格问题92.3.2高复杂度格问题9第三章格基规约103.1格基的正交性103.2格基的规约103.3格基规约的基本定义和定理11第四章格基规约算法134.1格基规约算法概述134.2LLL格基规约134.2.1基本定义134.2.2基本性质144.3经典的LLL格基规约算法164.3.1低复杂度的LLL格基规约算法164.3.2使用实例进行实验204.3.3

2、结果分析与结论214.4遗传算法实现格基规约的算法224.4.1算法实现的概念224.4.2遗传算法的实质224.4.3算法的步骤234.4.4实例的实验23第五章困难格问题的规约255.1高复杂度的格问题介绍255.2NTL大数库的介绍255.3大数库的使用265.4几种变种规约算法的介绍275.4.1经典LLL算法：275.4.2LLL-FP算法275.4.3BKZ-FP算法285.4.4BKZ-QP算法285.5高复杂度算法实现的原理285.6实例测试305.6.1低复杂度实例305.6.2高复杂度实例32第六章结论35参考文献36致谢37附录38格基规约

3、算法研究摘要格是数学上非常典型的一种线性代数结构，而且格上一些问题的困难性已经得到了许多学者的证明。格的理论研究中的重点主要是集中在了格基规约上，这同时也是密码学中密码系统的设计和分析中利用到格的一个重要工具。目前，在格的理论研究中，许多格的问题均可以通过格基规约来进行求解（因为是NP难问题，一般都只能近似求解）。在实践中，例如是在密码体制的设计和密码系统的破解中，对一些密码系统和密码方案的分析其实在本质上均可以等价成格基规约问题。因此研究格基规约问题不仅具有很高的理论价值，而且具有重要的实用价值。本文首先对格问题的背景和基础知识进行了学习和分析，然后研究了格中

4、的困难问题，最后重点研究了常见的格基规约方法。研究了经典的Gram-Schnorr的厶厶厶经典格基规约算法，用C++语言将该经典算法实现，并用实例进行试验,验证该算法的质量。其次还用了遗传算法来实现格基规约，并用相同实例，将得到的结果进行比较。论文的重点放在格的困难问题上，由于冃前计算机内部数据表示的一些局限性，使得大数的运算和大数格的运算称为困难问题，本文使用了NTL大数库进行辅助，在此基础上，分别实现了经典厶厶厶算法，LLL-FP浮点算法，BKZ-FP分块浮点算法，以及BKZ-QP分块四倍精度浮点算法，并使用相关实例进行实验，比较各算法的优越性。关键词：格；

5、格基规约；LLL；NTL大数库AbstractThelatticeismathematicallyaverytypicalofalinearalgebraicstructure,andthedifficultyofsomeproblemsonthelatticehasbeenproofedbymanyscholars・ThestudyingoflatticeoftheoreticalmainlyfocusedinthetheLatticeBasisReduction,whichisalsoanimportanttoolatpasswordsystemdesign

6、ingandanalysisingincryptographythatcantakeadvantageofofthelattice.Inthetheoreticalstudyofthelatticeproblem,manyofthelatticecanbesolvedbylinearreduction(usuallyonlycanbeapproximatewiththesolution).Inpractice,forexample,incryptosystemdesigningandpasswordcracking,theanalysisingofsomeoft

7、hepasswordandpasswordprograms,infact,areequivalentedintoLatticeBasisReduction・TheResearchingofLatticeBasisReductiondonotonlyhasahightheoreticalvalue,butalsohasimportantpracticalvalue.Inthispeper,firstly,wepresentthebackgroundoflatticeandthebasicknowledge,thestudyingandanalysisingaref

8、ocusedonthed