摘    要线性方程组是代数学中最基础也是应用最广泛的研究对象之一。对于一个格上线性方程组求近似解就相当于求解一个已知格上的SVP问题或CVP问题。

本文首先简要介绍了有关格的一些基本概念和有关性质，然后从格上困难问题的计算复杂性研究、LLL格基约简算法、基于格理论的公钥密码体制三个方面回顾了该领域这些年来的一些研究方法和主要研究成果。

随着量子计算的发展，许多目前被广泛使用的传统的公钥密码体制岌岌可危，而基于格理论的公钥密码体制已被证明可以抵挡量子计算攻击。但是就公钥密码的发展历史和研究现状来看，基于格的公钥密码在效率上需要进一步提升，在安全性上需要深入的分析，在功能上仍然需要进一步拓展。89637

The system of linear equations is one of the most fundamental and the most widely studied objects in algebra。 For a linear system of equations on a lattice, the approximate solution is equivalent to solving the SVP or CVP on a given lattice。源Q于W优E尔A论S文R网wwW.yOueRw.com 原文+QQ75201,8766

In this paper, firstly, we introduce some basic concepts and properties of lattices。 Then we review main research methods and results about this field over three aspects which are the difficult problem of lattice research on computational complexity, LLL lattice reduction algorithm and public key cryptosystem based on lattice theory in these years。 

With the development of quantum computing, many of the widely used traditional public key cryptosystems are at stake。 Fortunately, the public key cryptosystem based on lattice theory has been proved to be able to resist the attack of quantum computing。 However, the efficiency of the public key cryptography based on lattice needs to be further improved, the security needs to be further analyzed, and the function needs to be further expanded in terms of the development history and research status of public key cryptography。

毕业论文关键词：格上困难问题； LLL格基约简算法； 公钥密码学

Keyword: difficult problem of lattice; LLL algorithm; cryptography

目录

摘    要 2

目录 3

一、引言 4

二、格的基本概念和相关性质 5

三、格上的计算性难题 6

四、LLL格基约简算法来自优Y尔L论W文Q网wWw.YouERw.com 加QQ7520~18766 的基本概念 9

五、LLL格基约简算法的研究进展 11

六、格理论在密码学中的一些应用 12

参考文献 15

致谢 17

一、引言

线性方程组是代数学中最基础也是最重要的研究对象之一，早在古代中国经典数学著作《九章算术》中便已经对线性方程组的解法进行了比较完整的论述，并且在工程和科学领域的许多问题可以转化为对线性方程组的求解，应用十分广泛。

对于一个通常意义下（在域上）的线性方程组，我们已经有很多种方法可以解决它，如高斯消去法、克莱姆法则等等，都可以很快的求解一个线性方程组。然而在实际应用中，有时需要在格上求解一个线性方程。由于格是一个离散的加法子群，此时想要求解一个线性方程组就要比在域上复杂得多。事实上，至今为止还没有一种算法可以在格上快速且精确地求解一个线性方程组，所以我们退而求其次，想要先求出一个格上线性方程组的比较优的近似解。这个问题可以转化为格上的计算性难题：SVP问题或CVP问题，也就是说想要求解一个格上线性方程组，就相当于求解一个已知格上的SVP问题或CVP问题。而SVP问题和CVP问题都已被证明是NP-hard。论文网