摘  要

    LLL(Lenstra,Lenstra,Lovasz)是最经典的格基规约算法。而以LLL算法为基础的变体数不胜数,其目的都是为了优化。LLL算法虽然不能保证给出格的最短向量,但却成功地在多项式时间内找到了不超过最短向量的倍的短向量,而且往往在实际应用时效果很好。主要研究内容有瘦三角形和晶格减少，整数编程，椭球法和多项式因式分解。LLL算法思想源于 Lagrange, Gauss, Hermite, Ko-rkine- Zolotareff 等的二次型理论及 Minkovski 的数的几何理论。在密码分析方面的应用,LLL算法研究格基规约攻击分析中格构造的方法和RSA攻击格构造方法。

目    录

 

一、引言

二、LLL算法的历史

三、LLL算法的研究

（一）、 瘦三角形和晶格减少

（二）、整数编程

（三）、椭球法

四、LLL算法的实现

（一）、多项式因式分解

（二）、 LLL条款

五、LLL算法在密码学中的应用

（一）、 RsA攻击格构造方法研究

（二）、格基规约攻击分析中格构造的方法

六、结论

参考文献

 

 

致谢