资源描述：
《毕业设计（论文）-格基规约算法研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、SHANDONGUNIVERSITYOFTECHNOLOGY毕业设计说明书格基规约算法研究学院：理学院专业：信息与计算科学学生姓名：学号：指导教师：2012年6月摘要格是数学上非常典型的一种线性代数结构，而且格上一些问题的困难性已经得到了许多学者的证明。格的理论研究中的重点主要是集中在了格基规约上，这同时也是密码学中密码系统的设计和分析中利用到格的一个重要工具。目前，在格的理论研究中，许多格的问题均可以通过格基规约来进行求解（因为是NP难问题，一般都只能近似求解）。在实践中，例如是在密码体制的设
2、计和密码系统的破解中，对一些密码系统和密码方案的分析其实在本质上均可以等价成格基规约问题。因此研究格基规约问题不仅具有很高的理论价值，而且具有重要的实用价值。本文首先对格问题的背景和基础知识进行了学习和分析，然后研究了格中的困难问题，最后重点研究了常见的格基规约方法。研究了经典的Gram-Schnorr的厶厶厶经典格基规约算法，用C++语言将该经典算法实现，并用实例进行试验,验证该算法的质量。其次还用了遗传算法来实现格基规约，并用相同实例，将得到的结果进行比较。论文的重点放在格的困难问题上，由于
3、目前计算机内部数据表示的一些局限性，使得大数的运算和大数格的运算称为困难问题，本文使用了NTL大数库进行辅助，在此基础上，分别实现了经典厶厶厶算法，LLL-FP浮点算法，BKZ-FP分块浮点算法，以及BKZ-QP分块四倍精度浮点算法，并使用相关实例进行实验，比较各算法的优越性。关键词：格；格基规约；LLL；NTL大数库AbstractThelatticeismathematicallyaverytypicalofalinearalgebraicstructure,andthedifficulty
4、ofsomeproblemsonthelatticehasbeenproofedbymanyscholars・ThestudyingoflatticeoftheoreticalmainlyfocusedinthetheLatticeBasisReduction,whichisalsoanimportanttoolatpasswordsystemdesigningandanalysisingincryptographythatcantakeadvantageofofthelattice.Inthe
5、theoreticalstudyofthelatticeproblem,manyofthelatticecanbesolvedbylinearreduction(usuallyonlycanbeapproximatewiththesolution).Inpractice,forexample,incryptosystemdesigningandpasswordcracking,theanalysisingofsomeofthepasswordandpasswordprograms,infact,
6、areequivalentedintoLatticeBasisReduction.TheResearchingofLatticeBasisReductiondonotonlyhasahightheoreticalvalue,butalsohasimportantpracticalvalue.Inthispeper,firstly,wepresentthebackgroundoflatticeandthebasicknowledge,thestudyingandanalysisingarefocu
7、sedonthedifficultpreblemofthelattice.Andthenwestudysomebasicdefinitionsofthelatticeandbasiswithquasi-orthogonal,aswellasLatticeBasisReductionandthebasicknowledgeandbasictheorems.weStudytheclassicGram-SchnoirLLLclassicalgorithmandandvalidatethequality
8、ofthealgorithmbyusingC++withanexamplestobetested・Secondly,wealsouseageneticalgorithmtoachieveLatticeBasisReduction,andwiththesameinstancewecancomparethequaelityoftheresults.Thispaperfocusonthedifficultproblemofthelattice.Forsomelimitationsofthedatare
