毕业设计（论文）-格基规约算法研究.doc

摘 要SHANDONG毕业设计说明书格基规约算法研究学 院： 理学院 专 业： 信息与计算科学 学生姓名： 学 号： 指导教师： 2012 年 6 月43全套设计加153893706摘 要格是数学上非常典型的一种线性代数结构，而且格上一些问题的困难性已经得到了许多学者的证明。格的理论研究中的重点主要是集中在了格基规约上，这同时也是密码学中密码系统的设计和分析中利用到格的一个重要工具。目前，在格的理论研究中，许多格的问题均可以通过格基规约来进行求解（因为是NP难问题，一般都只能近似求解）。在实践中，例如是在密码体制的设计和密码系统的破解中，对一些密码系统和密码方案的分析其实在本质上均可以等价成格基规约问题。因此研究格基规约问题不仅具有很高的理论价值，而且具有重要的实用价值。本文首先对格问题的背景和基础知识进行了学习和分析，然后研究了格中的困难问题，最后重点研究了常见的格基规约方法。研究了经典的Gram- Schnorr的经典格基规约算法，用C+语言将该经典算法实现，并用实例进行试验，验证该算法的质量。其次还用了遗传算法来实现格基规约，并用相同实例，将得到的结果进行比较。论文的重点放在格的困难问题上，由于目前计算机内部数据表示的一些局限性，使得大数的运算和大数格的运算称为困难问题，本文使用了NTL大数库进行辅助，在此基础上，分别实现了经典算法，LLL-FP浮点算法，BKZ-FP分块浮点算法，以及BKZ-QP分块四倍精度浮点算法，并使用相关实例进行实验，比较各算法的优越性。关键词：格；格基规约；LLL；NTL大数库全套设计加153893706AbstractThe lattice is mathematically a very typical of a linear algebraic structure, and the difficulty of some problems on the lattice has been proofed by many scholars. The studying of lattice of theoretical mainly focused in the the Lattice Basis Reduction, which is also an important tool at password system designing and analysising in cryptography that can take advantage of of the lattice. In the theoretical study of the lattice problem, many of the lattice can be solved by linear reduction (usually only can be approximate with the solution). In practice, for example, in cryptosystem designing and password cracking, the analysising of some of the password and password programs, in fact, are equivalented into Lattice Basis Reduction. The Researching of Lattice Basis Reduction do not only has a high theoretical value, but also has important practical value. In this peper, firstly, we present the background of lattice and the basic knowledge, the studying and analysising are focused on the difficult preblem of the lattice. And then we study some basic definitions of the lattice and basis with quasi-orthogonal, as well as Lattice Basis Reduction and the basic knowledge and basic theorems.we Study the classic Gram-Schnorr LLL classic algorithm and and validate the quality of the algorithm by using C + + with an examples to be tested. Secondly, we also use a genetic algorithm to achieve Lattice Basis Reduction, and with the same instance we can compare the quaelity of the results. This paper focus on the difficult problem of the lattice.For some limitations of the data representation inside the computer so that making the large numbers computing and lattice computing of large numbers the difficult problem.In this article, with the using of the NTL library auxiliary, we validate the quality of the algorithm by using the classical LLL algorithm LLL-FP floating-point arithmetic, the BKZ-FP block floating-point arithmetic, and the BKZ-QP block quadruple precision floating-point arithmetic with some examples to experiment, we can see the comparison of the queality of all the algorithms.Keywords: Lattice, LLL Lattice Basis Reduction, NTL Library全套设计加153893706目录摘 要IAbstractII第一章 引 言3课题的背景和意义3第二章 格问题的研究42.1 格问题的发展42.2格问题的算法发展42.2.1 精确算法42.2.2 近似算法52.3格问题的基础知识62.3.1低复杂度的格问题62.3.2高复杂度格问题6第三章格基规约73.1格基的正交性73.2格基的规约73.3格基规约的基本定义和定理8第四章格基规约算法104.1格基规约算法概述104.2 LLL格基规约104.2.1 基本定义104.2.2 基本性质114.3 经典的LLL格基规约算法134.3.1 低复杂度的LLL格基规约算法134.3.2使用实例进行实验174.3.3结果分析与结论184.4 遗传算法实现格基规约的算法194.4.1算法实现的概念194.4.2 遗传算法的实质194.4.3算法的步骤204.4.4 实例的实验20第五章 困难格问题的规约225.1高复杂度的格问题介绍225.2 NTL大数库的介绍225.3大数库的使用235.4几种变种规约算法的介绍245.4.1经典LLL算法：245.4.2 LLL-FP算法245.4.3 BKZ-FP算法255.4.4 BKZ-QP算法255.5高复杂度算法实现的原理255.6实例测试275.6.1低复杂度实例275.6.2高复杂度实例29第六章 结论32参考文献33致 谢34附录35第一章 引 言课题的背景和意义讨论格问题的最早出现要回溯到19世纪，当时的数论和密码被研究了很长的一段时间，那时候格在很多领域的应用主要是负面的，例如格被用来破解各种密码系统。然而Ajtai发表了他得里程碑式的论文，其利用格的难题来构造新的密码系统的观点让许多的学者产生了兴趣。这个算法和格的相关的理论从此时才真正的被开始应用到密码学的领域。在1990年，基于背包问题的密码系统被LLL的算法攻破。这一成果展开了格理论在密码分析学这一领域中的实际应用，并且同时更进一步的证明了 “单向函数假设”这一理论的不可靠性。1996年，在Coppersmith的论文中LLL算法被提出来用于求解整系数同余方程(仅当方程一定有足够小的解的时候)的算法。之后，Coppersmith的这一方法被学者们广泛的应用于对RSA密码体制的部分密钥泄露攻击以及低指数攻击等领域的应用中。在近年来格在许多领域都已经产生积极的作用。在对格问题的研究基础上，人们设计出了基于格困难问题(NP问题)的密码系统Shamir利用格基规约理论，用Lenstra的整数规划算法成功破解了Merkle-Hellman得基于背包问题的公钥密码方案，其理论也被成功的用于加密指数为3的RSA密码方案的研究中，以及利用其对NTRU进行分析和攻击。密码学界已经认定格问题是在计算困难问题时的新的源泉。除此之外，格的困难问题也可以用来设计公钥密码，可以用来抗量子攻击，如NTRU密码。这也是密码学发展的一个新方向。全套设计加153893706第二章 格问题的研究2.1 格问题的发展在1982年的时候，有三位伟大的数学家伦斯特拉（A.K.Lenstra），伦斯特拉（H.W.Lestra），洛伐兹（Jr.L.Lovasz）发明了算法。之后，算法被许多学者视为是对解决NP问题的一大突破，由于其简明性和广泛性的实际应用，很快被认为是20世纪后期中最重要的理论算法成果之一线性代数这一学科里面的一些基本理论表明：任何有限维欧氏空间都存在一个标准正交基，也就是说每一个基都是由两两正交的单位矢量组成。那么，是否每一个格都是有标准正交基的呢？然而，即使是对于2维格，也存在某种可能使得它不存在正交基。此时，格基规约的目标只能退而求其次。学者研究发现，对于任何一个格来说，总存在这样一个基，它离正交不远。（当然，要精确定义什么是离正交不远也是需要某种技巧的，截止到目前为止，我们只能说存在这样一个基，它是由足够短的格矢量组成，这便意味着至少在几何的意义上来说这样的一些矢量相互之间是离正交不远的）。世界上的第一个SVP算法就是Lagrange的规约算法，他使得该算法能够在二次方的时间内解决精确的二维SVP。而对于任意维格，都是有两类SVP算法：精确算法和近似算法。2.2格问题的算法发展2.2.1 精确算法这些算法可证明找到一个最短矢量，但他们是开销很大，运行时间至少是维数的指数次本质上，这些算法执行一个穷举搜索精确算法可分成两类：（1）多项式空间精确算法这些算法基于列举法，但是由于不等式限制了搜索的范围，当然也能找出所有长度小于M的非零的格的矢量。其中最好的具有确定行的算法是Kannan算法，该算法具有超过指数的最坏复杂度，其多项式运算的时间为。Schnorr引用了Pruning的技巧，将列举法与分块进行规约两者相结合，事实上是在分块的KZ规约算法中加入一个子过程，这个子过程是用列举算法实现的，由于该小技巧的使用，整个算法的实现速度上有了很大的提升。（2）指数控件精确算法。在（1）的基础上，这些算法会有更短的渐近的运算时间，可是还是有的空间复杂度。在这类算法中最有代表性的是AKS算法(Ajtai,Kumar,Sivakumar)，这些算法即使在最坏的情况下起运算时间也不会超过。后来Micciancio等人又提出了一个更加具有确定行的算法，该算法可以在的时间内解决CVP与SVP等问题。并且有多个AKS的变形，其时间复杂度达到。2.2.2 近似算法这类算法比精确算法实现的时间要短，最后输出的结果保证是短的格矢量，但不一定保证是最短的。该算法常输出整个的规约基，所以我们称之为格基规约算法。该算法中最为著名的就是Lenstra,Lenstra, 提出的算法，此算法可以在多项式的时间复杂度内解决近似因子是的SVP问题，这个算法本质上就是Hermite不等式的算法的变形。LLL算法出现后，研究的方向就集中在两个方面：（1）更快的算法。这个方向致力于获得在质量类可以接受类似于或者是更加差一点的规约基，当然，它只需要更少的运行时间，这里面的方法是利用的分治策略，或者是通过浮点算法也可以。因为当我们使用浮点数算术时，它可以加快格基规约的速度，然而同时也会带来更多大的浮点误差，这些误差很多时候就会让我们得到错误的结果，甚至使程序无法终止。因此，研究格基规约上的浮点运算的一些特性是非常有必要的。世界上首次得到正确的证明的浮点是由Schnorr提出来的，最近，一个比更加有效的浮点变形版是由Nguyen和Stehle这两位学者研究出来的。但就目前来说，最为流行的版本还是基于启发式的浮点算法。尽管利用常规的方法就可以证明它的安全性，但是有的时候基于启发式的算法会更加有效。1994年,一个非常重要的基于启发式的算法由Schnorr和Euchner提出来，一直延续到今天，这个基于启发式的算法依旧是很多浮点快速算法必不可少的基础。（2）更强的LLL算法。这种算法是以更长得运行时间为代价来获得比算法要更好更精确的近似因子。分块的规约方法其本质是在算法和HKZ算法两者取得中间方法，令分块的长度为,参数=1时，分块规约与HKZ规约是等价的；令分块的长度为2时，分块KZ规约就是变成了规约。目前最好的分块规约算法可以达到。不过这些算法在理论上没有学者证明其最短矢量界，并且它的时间复杂度也有可能回升亚指数的，不过这个算法在实际应用中能运行得很好。之后Gama和Nguyen实现了三个算法：算法，深插入的算法，分块的KZ规约算法，他们都是用NTL库实现的。而且实践证明，深插入的算法和分块KZ规约算法比算法的性能要好，且随着分块值k的增大，最终得到的规约基的质量就越好，当然，运行时间也增加了。综上可以看出，更快和更高质量这两者之间是互补的，所有的精确算法首先都需要用一个近似的算法（比如算法）来进行预处理，其中所有的分块算法都需要调用大量的低维格的精确算法来作为子过程进行处理。在实际中，大多采用基于启发式的算法，他们的运行时间提升了许多，不过理论上很难被证明。事实上，当维数，能够实用的只有近似算法。最后，以前人们大都认为格基规约算法的实际执行的效率可以比学者们可证明的理论界会更好。在上世纪80年代末，格问题计算的复杂性程度引起了许多人们的关注，主要是因为Ajtai发现了某种格的近似问题在最坏情况复杂度和平均情况下的复杂度之间的相互联系，这引起了理论密码学家与计算机复杂度的领域专家的兴趣。2.3格问题的基础知识2.3.1低复杂度的格问题格是离散的加子群。每个格都是由一些线性无关的向量产生的集合，称之为基。任意格都有无数个基，格基规约是一种在格的无数基中选择这样一个基矢量：其长度尽可能小，并且与基中其他矢量尽可能正交。格基规约理论有着悠久的历史，可以回溯到二次多项式的规约理论上。在Lenstra,Lenstra和a 个人的努力下，该工作达到了高峰，也就是著名的算法，它是第一个保证能够计算出包含近似短向量的格的基的多项式时间算法。此后，格基规约的方法有了进一步的发展（例如，Schnorr-Euchner的格基规约算法）并且在基础数学和计算科学的许多领域该工作被认为其价值是无可估量的。特别是格理论的进展使得想组合优化和加密这些领域被彻底改革。例如，格基规约理论技术已被用于攻击截断线性同余发生器，基于哈希散列函数的背包问题以及像Merkle-Hellman公钥密码体制的密码系统，RSA,GGH等。2.3.2高复杂度格问题 然而，尽管在理论上取得了巨大的进步，但是面向大型问题的实例，还是缺少一般化的格基规约的方法。因此，在实践中去进一步的进行改善和提高理论技术是非常重要的。在下面，我们提出了一种新的基于动态近似的启发式算法，它是为了提高改善Schnorr-Euchner的格基规约算法，也是在实践中应用最为广泛的一种格基规约算法。特别是这种新的启发式算法在大型问题例子的分解以及在例如用某些方法无法实现分解的问题上可以用我们提出的新算法解决，这拓展了Schnoorr-Euchner算法的适用性。格基规约第三章 格基规约3.1格基的正交性设是n位欧式线性空间中线性无关的向量，可以定义如下点集：我们称之为格，并称为格的一个基，由于是线性无关的，所以任一个格的矢量X可以用一组基的线性组合来表示，而且这种表示方式肯定是唯一，即有且仅有一种；但是如果X已经在格中，并且能够用以上的线性组合的形式来表出，那么系数均为正数。任意格矢量均能被唯一表示为基矢量的线性组合。由于用基表出得格是有意义的，格基本身就能用一个全为实数的系数矩阵来表示，因此我们可以非常方便的使用电脑来表示任何一个格。如果从代数的角度来看，格则是由d个生成元组成的阿贝尔群，我们认为它是的子群。我们研究格问题的中心问题集中在Shotrest Vector Problem（SVP问题），就是最短向量问题，它的定义如下：对于给定的一个格基B，要求找到这样的一个非零的格的矢量，使得满足一下条件：，其长度要达到最小值。（其中长度被定义为欧几里得长度）另一个集中点是Closest Vector Problem(CVP问题)，也就是最接近矢量问题。该问题对于给定的目标矢量和格基，要求找出最接近于该矢量的格点，即那组基。两个问题相比之下，CVP比SVP要更加难以解决。因为精确的SVP问题是属于NP问题，即多项式时间困难问题，但它在实际中需要的地方并不多，所以以下的近似SVP问题被提出。近似SVP问题的定义为：给定秩为d的格L基B，近似因子为，要求找出非零矢量，使得满足以下条件：。它可以简单记为apprSVP。截止到目前为止，已经能够证明apprSVP问题是NP难得当且仅当近似因子。3.2格基的规约下面给出一些格基规约的相关概念：对任何矢量集，是由生成的线性空间，或者称之为包含S的的最小子空间。如果设是格的一个格基，于是它的Gram行列式可以表示为是阶Gram矩阵。关于Gram行列式有一个很重要的在几何学上的解释，即当线性无关，矢量生成的平行多面体为：，则是该平行多面体的体积，可以记为。设表示半径是r中心在原点的n维开球，简记为。子空间，它的正交补可以表示为。用表示向量在上的投影，那么当时，当时，。当是一个格，则的秩被定义为的维数，当时格称为满秩格。和的线性子空间类似，格的基也补唯一。两者的不同点集中在，不是所有的最大线性无关矢量都能构成一个基。任意一个格都有无数格基。设为格的某一个格基，矩阵，任意个格矢量，矩阵为C，如果存在可逆的矩阵满足，并且，那么也是格的一个基。显然有无数格矩阵U满足条件。设是的子格，我们称是的本原子群，其中，且。同理，定义本源矢量，要求该组矢量可以扩充成的一个基。这个SVP问题一样，每一个格都存在最短非零矢量，且不唯一。Minkowshi给出了最短非零矢量的长度的定义，其定义为格的第一最小值。又由于定义第二短矢量不具意义，所以Minkowshi限定了最短矢量的定义为线性无关的格矢量。3.3格基规约的基本定义和定理定义3.1 逐次最小值（The successive minima） 格的第i个次最小值定义为包含i格线性无关，且中心在原点的格矢量的最小求半径。定理3.1（Minkowski凸体定理）设是其可测凸集，并且关于原点对称，且测度严格大于，则至少包含一个非零矢量。推论3.1 设是一个秩格，为相应的单位球的体积，Gamma函数可视为阶乘函数在实数情况下的扩展，则格包含一个非零矢量,能满足。以上表达式可以用另一种方式来表示为，故，我们可以得出的线性边界。该值可以让我们得到的上边界。定理3.2（Minkowski第二定理）令是一个秩格，则对于，总满足。即是对于基为的格总有，当其基的矢量相互正交的时候，最终结果才能取等号。定义3.2（正交亏损orthogonality defect）对于基是的格正交亏损可以定义为，其中等号成立的条件为初始的格基为正交基。综上，格基规约的最终目的其实就是找到规约基，也就是由相当短或者是几乎正交的格矢量组成的基。格基规约算法在数学和计算机，以及密码学等许多的领域具有非常高的研究价值。全套设计加153893706第四章 格基规约算法4.1格基规约算法概述首先,取我们用表示列向量的欧几里得长度，用Z表示中最接近的整数。 整数格的定义如下：，并且是线性无关的向量。我们称是k阶格的一个基。格的基对于单模转换来说是唯一的，比如说交换两个基向量，基向量同乘以-1，或是加某基向量的整数倍到另一基向量上。关于的格的行列式，其大小与基的选择是无关的。的亏缺被定义为。通常。如果B是一个正交基，则有。通过改进格的基的规约方式这个误差是可以被减小的，通过这种方式来构建出格中许多基中的一个基，这个基向量是尽量小的（通过欧几里得长度来衡量），并且与其他的基之间是尽量正交化的。下面要提到的所谓规约就是最为著名的格基规约中的一种方法。4.2 LLL格基规约4.2.1 基本定义定义3.3 对于基的格，它符合Gram-chmidt正交化后的，并且其Gram-Schmidt系数表示为（其中），如果下面的条件也满足的话，则我们称基为规约的： （1） （2）第一个性质是规约的规则。其中（2）里的恒定因子就是所谓的规约系数，这个系数可以被任何一个固定的实数代替，其中。该格基规约算法的质量，即是得到的格的基向量的正交化程度和长度的大小，这些可以被如下定理进行量化：定理3.3 令为一个格，而为的一个规约基。则如下估计成立： （3） （4）定义3.4 （矢量的欧几里德长度）对于维矢量的长度（Euclidean norm）定义为。定义3.5（连续最小值）在欧几里德长度定义的基础上，我们定义维格的一组基础性的常数值（successive minima）:可以包含格中个线性无关的向量的最小的圆的半径。其实质就是不小于个线性无关的向量的欧几里德长度的最小值。4.2.2 基本性质定理3.4 （Minkowski定理）对阶格的所有基中最短向量的长度有：且对于格的连续最小值有：Minkowski规约基可能存在，但并不是任何格均存在Minkowski规约基。其中其中是对进行Smicher正交化得到的。定义3.6 （Korkine-Zolotareff规约基）即KZ规约基：若格上的一组基，满足就称之为为KZ规约基。Gram-Schmidt正交化：该过程即是将一组有序的基投影到相互垂直的基上。若将正交向量构成的j-1实数空间看成是超平面的，则第j个基向量的Gram-schmidt正交化就是将朝超平面上投影，于是得到两个分量：和。使替换。因为与超平面是垂直的，所以是正交的。如下图：图 4.1关于格基规约算法还有以下命题：设是格的一个基，且是经过Gram-Schmidt正交化后的基。则其证明如下：设和分别是初始格基向量和进行Gram-Schmidt变换后的基构成的矩阵。则有，其中图 4.2且。定义3.7 设是格的一个基，且是经过Gram-Schmidt正交化后的基。基称为可规约的，当且仅当满足下列两个条件：（） 即是大小条件，（） 即是条件，且规约基的初始基满足：。4.3 经典的LLL格基规约算法4.3.1 低复杂度的LLL格基规约算法下面就给出格基规约算法低复杂度的格基规约算法。这个算法将给定的格的基转换为规约基，其工作原理如下：算法1：输入：一个格的基输出：规约基（1）计算（即各个基的长度的平方）和相应的，当时，使用Gram-Schmidt方法（2）（3）while() do （4）REDUCE()（5）if() then（6）SWAP（7）（8）else（9）for()do（10）REDUCE()（11）end do（12）（13）end if（14）end do用子程序SWAP来交换两个基向量和，而子程序REDUCE 被用来规约缩小因子，以达到的目的。对于任何有基的格，该基B的规约基都可以在多项式时间内计算出来。更确切的说，该算法运算执行的时间大小为，运算中个的这个整数的长度用2进制表示的大小为执行，其中。光从理论的角度上来看,尽管该算法运算起来有不错的性能和很好的表现,但在实践中基本上是无用的,为了保证在基中不发生什么错误，所以用于精确的长整数运算的子程序必须被使用，而该子程序运行太过缓慢（因而可以改变格）。Schnorr和Euchner取得了这种情况下的第一个重大改进（因而使得在实践中使用规约算法成为可能），他们使用了快速浮点算法和Gram-Schmidt系数来计算以得到整数格的近似解，从而重写了原算法，然而其他的算法都是通过使用确切的整数算法来计算的。此外，前面已经介绍过的为了避免和修正浮点算法中的错误的启发式算法，它在原始的算法的基础上提供了一种实际并且合理的变种算法，并且具有很好的稳定性。算法2.Schnorr-Euchner 输入：一个格的基输出：算法规约基（1）（2）（3）（4）APPROX_BASIS（5）while do（6）for do（7）ORTHOGONALIZE(m)（8）end do（9）for do（10）REDUCE（11）end do（12）ifthen（13）APPROX_VECTOR;（14）（15）end if（16）if（17）（18）（19）else（20）if（21）SWAP（22）（23）else（24）（25）end if（26）end if （27）end do 给定格B的每个基b在子程序APPROX BASIS和APPROX VECTOR的调用下分别向B逼近，并且是使用浮点运算，即一个近似的但是快速的数据类型。由于稳定的原因，和两个子程序ORTHOGONALIZE（用于计算Gram-Schmidt正交化过程）和REDUCE（用于计算规约过程）一样，主要算法中为了减小浮点错误的启发式算法是允许的。算法3：ORTHOGONALIZE（i）输入：i,基向量和，输出：，（1）（2）for()（3）if then（4）（5）else（6）（7）end if（8）（9）（10）end do （11）算法4：REDUCE输入：，输出：，其中(1) if() then (2)(3) if() then (4)(5) End if(6) (7) do(8) (9) End do(10) End if4.3.2使用实例进行实验下面给出一个小的实例进行演示，初始输入的格M是一个的矩阵，矩阵中的数值均为实数，且均为整数。输入矩阵如下：程序运行截图如下：图4.3程序运行结果截图如下：图4.44.3.3结果分析与结论经过规约后的基为：其中，初始基和经过规约后的基的行列式相同：哈德蒙德比率变化如下：，即最终得到的最短矢量为（7，-12，-8,4,19,9），规约前的基的最短矢量长度为，而，和精确的最短矢量长度26.062相差不算太大。显然，不论是运行的时间还是这个Schonorr-Euchner算法的稳定性都是强烈的依赖于使用的近似值的精确度。虽然高精度的近似意味着效率上的重大损失，但是如果精度太低，由于（累积的）浮点错误，虽然不会导致程序终止，但是会让程序进入死循环。因此，该算法任然缺乏效率，特别是对于大的格基或者大的输入基，因为必须使用高精度的近似值。为了克服这个问题，我们将在下面介绍一种新的启发式算法，这种算法允许浮点精度的动态适应，因此可以大大的减小相应的规约过程的运行时间。4.4 遗传算法实现格基规约的算法4.4.1算法实现的概念模式 ：模式表示基因串中某些特征位置相同的结构，它描述的是一个串的子集，在二进制编码的串中，模式是基于三个字符集（0,1，*）的字符串，符号*代表任意字符，即0或1。对于二进制编码串，当串长为时，共有个不同的模式，遗传算法中串的运算实际上是模式的运算。模式阶：模式H中确定位置的个数称为模式H的模式阶，记作O(H)，如O（101*1*1）=5。模式阶用来反映不同模式之间的确定性差异，模式阶数越低，模式的确定性越低，所匹配的样本个数就越多。定义距： 模式H中第一个确定位置和最后一个确定位置之间的距离称为模式的定义距，记作。如。 在遗传操作中，即使阶数相同的模式也会有不同的性质，定义距就反映了这种性质的差异。模式定理：在遗传算法选择、交叉、变异算子的作用下，具有低阶、短定义距以及平均适应度值高于种群品均适应度值的模式在子代中成指数增长。模式定理的数学公式表示为 (2-1)式中，-表示在t+1代种群中存在模式H的个体数目； -表示在t代种群中存在模式H的个体数目； -表示在t代种群中包含模式H的个体平均适应度； -表示在t代种群中所有个体的平均适应度； -表示个体的长度； -表示交叉概率； -表示变异概率。 模式定理是遗传算法的基本理论，保证了较优的模式（遗传算法的较优解）的数目呈指数增长，为解释遗传算法的机理提供了一种数学工具。4.4.2 遗传算法的实质传统的优化方法主要有3种：枚举法、启发式算法、和搜索算法，本文用到的是第一中优化方法，即枚举法。由于格基规约的过程等价于是找到输入格的一个最短基，这设计到线性代数里面的线性空间，其实就等于对输入格进行初等变换，将所有初等变换后的基的长度运算出来统计，并得出欧几里德长度最短的那个向量，就是最终得到的那个向量。唯一的问题在于变换的次数，即枚举的个数，这里，可以进行自己设定枚举的次数。由于该算法在进行初等变化的时候是随机进行的，所以，从概率学的角度上来说，一般都是枚举次数越多，最终的结果越精确。4.4.3算法的步骤步骤如下：（） 设V=为起始格基，并且相互之间是线性无关的。（） 令E为单位矩阵（阶），对E做三类初等变换，某行（列）乘以某数，某两行（列）相互交换，某行（列）加到另一行（列）上去。令初等变换后的单位矩阵为A。（） 令，其中V=，求出，并计算其中最短的那个向量及其长度。（） 循环2,3两个步骤N次，比较每次求出来的最短矢量的长度，从中找出长度最小的矢量，即为要求的格最短矢量。4.4.4 实例的实验如下，输入的格基为：程序运行如下：图4.5可以看到，和上一节输入的基相同，但最终出来的结果显示要比经典算法的结果要长，这里得到的基的长度为28.178，而经典算法的长度为26.74,。这是枚举了100次后运行的结果。可以看出，遗传算法和相比较，一般说来，经典算法得到的结果要更为精确，这是由于遗传算法算法本身的存在的随机性所决定的。困难格问题的规约第五章 困难格问题的规约5.1高复杂度的格问题介绍高复杂度的格基规约算法指的是高复杂度的NP问题，第一是初始输入的格基的维数较大，一般从几十到几千不等，所以运行的时间无法估量；第二 是初始输入的格基内部各元素本身就是大数，这些大数的位数也是从几十到几百位之间，大多超出了一般个人计算机的表示范围，因为现有的个人计算机一般都是32位机，或者是64位机，其能表达的数值的位数最多也只能达到32位和64位。所以高复杂度的格基规约算法要解决的问题有很多，集中的问题在以下几点：（） 计算机内部应该如何表示这些位数较长的大数（） 如何定义这些大数之间的加减乘除等四则运算（） 如何实现大型矩阵间的表示和运算鉴于以上提出的三点问题，可以使用Microsoft公司研发的NTL大数库来解决。5.2 NTL大数库的介绍下面首先将对该大数库进行简单的介绍：NTL库是一个高性能的，并且可以直接移植到C+中的大数库。它可以提供任意长度的整数的数据结构和运算，例如向量，矩阵，整数，多项式和有限域的运算，以及任意精度的浮点运算。由于NTL大数库提供了非常优异的大数运算，这让我们无需讨论其大数运算在计算机内部实现的细节，可以直接把NTL大数库当成是解决高复杂度格基规约问题的一个非常有力的工具。NTL是一种可以移植的C + +数论库，该库提供的数据结构和算法，在各种大数库中性能较高。NTL主要应用于操作签名领域,它能够简单地实现任意长度整数、向量、矩阵、多项式和有限的领域上的一些操作。NTL库提供了许多质量较高的算法：大整数的基本运算和高精度的浮点运算;在多项式时间内进行的整数和有限域的基本算术,多项式的因式分解、求最小多项式;格基规约算法,包括能够快速实现的Schnorr-Euchner算法,Korkin-Zolotarev、新Schnorr-Horner修剪启发式的块Korkin-Zolotarev;整数在有限域上和任意精度浮点数字的基本线性运算。NTL中的多项式时间算法是目前世界上最优秀的算法之一，它的运算速度非常快，因此在多项式时间算法以及椭圆曲线算法中常常被用来作为一个标准。NTL的另一个优点就是具有非常好的可移植性，它可以在许多的平台（windows 32/64位操作系统、Unix等）上使用，可以在许多的编程工具上使用。5.3大数库的使用下面我们来讲一下如何生成并调用NTL库（以WinNTL）：首先来介绍一下这个库（我们把库放在E:下）： Doc文件夹 介绍库中的类 Include文件夹 放置头文件 Src文件夹 放置源代码 Text文件夹 测试程序新建一个名为ntl的win32静态库，将src中的所有cpp文件（也可只选择自己要用到的文件）增加到工程，从工程里设置预处理器，即将头文件的路径名输入，然后生成库文件（生成的库文件在debug文件夹中）。下面可是对程序进行测试（正式使用中只需导入库，并设置预处理器的路径即可），同上文，我们将生成的ntl.lib文件以及用到的测试文件添加到工程，设置头文件的路径，然后进行组建即可。NTL库中的函数较为复杂，要想真正了解库的实现原理，还需要认真学习才行。下面介绍一下大数库的使用方式：（） 在NTL库的官方网址上下载库包（） 解压缩后找到其下述文件夹includeNTL中的config.h文件，在里面找到NTL_STD_CXX，对该处文本进行处理：将#if 1#define NTL_STD_CXX改成#if 0#define NTL_STD_CXX若没有修改这个地方，在运行程序时，会出现错误提示：floor is not a menber of std.（） 在C+上生成一个库文件，用于使用。先打开C+，然后做一下设置：图5.1注：上面提到的“c:mystuffinNTL-xxx”是NTL解压缩后的路径，“c:Progran FilesMicrosoftVisual StudioMyprojectsntl”是ntl这个project的路径，这两个路径都可以自己随意选择。如果需要使用release模式，那么需要在窗口左上角的下拉菜单里面选择release，并做相同的设置：Category: PreprocessorAdditionnal include directories: c:mystuffWinNTL-xxxincludeClick on OKBuildbuild ntl.lib经过以上步骤，在该文件目录下就已经产生了一个ntl.lib文件，将该文件复制出来，保存至创立的C+工程目录下，就可以在C+中调用了。该大数库中提供关于格的规约包括准确的算术运算（运行速度较慢但是记过精确）和浮点变种（运行速度很快但是得到的只是近似值）。5.4几种变种规约算法的介绍5.4.1经典LLL算法：Long LLL (ZZ& det2, mat_ZZ& B, mat_ZZ& U, long a, long b, long verbose = 0);其中B是一个的矩阵，可以视为M行N列的向量。M可以小于等于或是大于N，并且各行并比需要线性无关。矩阵B最终将被转变为规约基，并且返回值是矩阵B的第一行。ZZ是大数库内定义的一个大数类型，并且库中定义了其相应的加减乘除等运算。mat_ZZ是一个大数矩阵，对应的，大数库中也定义了其相应的各类矩阵运算。符号&是C+中的引用型，是为了在运算的过程中节省空间，只对数据本身做变换。a,b是限定规约过程中的，。5.4.2 LLL-FP算法LLL-FP算法，是浮点运算，该算法的运行速度很快，但是得到的只是近似值，不如算法那么精确。这可以显著的减少运行的时间，因此可以允许更大的块的大小，但是规约的效果不如前者理想。当然，prune的值越高以为着结果的效果越好，同时程序运行得越慢。当prune=0时，跃减被禁止。5.4.3 BKZ-FP算法BKZ-FP算法：该算法的功能除了应用了Block Korkin-Zolotarev规约，其余与上述算法的子程序的功能是等同的，我们在描述上只有在调用时语法上有差异。其中可选参数“BlockSize”可以指定规约过程中块的大小。该参数的值月大，就能产生更短的向量，但是程序运行的时间也会随着“BlockSize”成倍的增长。“BlockSize”的取值应该是介于2和矩阵B的行数。可选参数“prune”可以被设定为用来调用任何有积极效果的参数。大数库中推荐的值为：。5.4.4 BKZ-QP算法BKZ-QP变种:该算法使用quad_float的精度来计算Gram-Schmidt变换，但是在搜索阶段使用了双精度的规约算法。由于它使用的双精度精密计算，所以对于大多数的问题的期望值来说都足够了，并且比LLL-QP的速度要快。5.5高复杂度算法实现的原理为了防止由于必须使用高精度近似值儿产生的问题出现，该新的启发式算法的核心理念就是为了得到确切的表示则与最原始的格基规约算法一起运算，而近似值被计算出来表示为。R必须更加接近的时候B取代原来的B。该创新式算法的可行性是基于如下的定理：定理5.1 令为一个格，而为的一个规约基。a 的基，则如下成立： （5）证明。因为适用于正交化，且（Gram-Schmidt系数），其中，定义1成立时有如下结论：。尽管该元素的大小在规约阶段的过程中近似的变化，但是在整个规约过程中不可能使用同一个值，这就意味着r必须动态的随着时间改变，这是为了防止程序注销和结果不准确。因此，在用规约算法对基进行近似运算的开始之前（见算法2），首先要计算出输入的格的基中绝对值最大的那一个，然后用于给决定一个合适的值。该启发式算法，其核心是选择一个，使得它可以适应用于近似的那个数据类型，并且不会使得近似的元素变得太小。除此之外，鉴于APPROX_BASIS,APPROX_VECTOR和APPROX_VALUE在原始的Schnorr-Euchner算法（见选择2）中是简单的数据类型转换，为了能够实现动态近似的目的，他们还需要做以下调整：算法5：APPROX_BASIS输入：是精确的基输出：近似的基（1） for do（2） for do（3）（4） End do（5） End do和前面一样，表示近似值，表示转变后的值。算法6：APPROX_VECTOR 输入：为确定的向量输出：为近似的向量（1） for do （2）（3） End do（4）（5）（6） if then（7）（8） if then（9） fact=0（10） end if（11） APPROX_BASIS（12） End if的值（调整值）和的值（减少值）也都依赖于近似的数据类型。它们被用来动态的适应的值，并启发式的决定该近似元素不会变得太小以至于导致程序的跳出执行和不确定性。（对于近似元素，使用double类型双精度，和由=1E+52和=40来启发式的决定）。算法7：APPROX_VALUE输入：s,为一个确定的值输出：，为一个近似的值（1）接下来我们将给出测试结果来表明这个最新开发的启发式算法的效率。使用原始的Schnorr-Euchner算法，这些问题的实例无法实现规约，或者是只能在