英语原文共 9 页，剩余内容已隐藏，支付完成后下载完整资料

---

在本次演讲中(1)我们将描述一个关于最短路径算法（SVP）的近似算法。这种算法，由A. K. Lenstra，H.W. Lenstra，Jr.和L. Lovasz于1982年开发，通常被称为LLL算法，给出一个的近似比，其中n是点阵的维数。在许多应用中，该算法适用于常数n，在上诉算法下，就会得到一个常数逼近因子。

在1801年，高斯给出一个算法，此算法是在两个维度下解决SVP问题。在某些方面，LLL算法是高斯算法一般化到更高维下的结果。1987年，Schnorr提出一种改进的SVP算法，该改进算法得到一个稍次指数，即：。

LLL算法在计算机科学的许多领域都有所应用。其中的一些我们将在下面的讲座中进行说明。下面便是这些应用的简要说明：

1. 在整数和有理数条件下的多项式的因子分解，例如：-1的因子为x-1和x 1。
2. 得出一个数的极小多项式，来很好的近似这个数，例如: 1.414213得出-2=0；0.645751得出 4x-3=0。
3. 寻找整数关系。一组实数{}如果存在这样一组整数{}使它们有如下关系=0其中并不是所有=0，举个例子，arctan(1)asymp;0.785398, arctan()asymp;0.197395，arctan() asymp;0.004184，事实证明整数关系存在arctan(1) - 4 arctan(1/5) arctan(1/239) = 0(这种相等关系被称之为Machinrsquo;s公式)
4. 整数规划。这是个公知的NP完全问题，使用LLL算法，我们可以得到一个具有固定变量的整数规划的多项式时间的解决方案。
5. 对最近问题（CVP）以及其他的晶格问题的近似。
6. 在密码分析中的各种应用（即：打破密码协议）。例如:有许多基于密码协议的背包问题的攻击手段，而且还有关于RSA的特殊的攻击方法，如低公共指数攻击。

为简单起见，我们描述LLL算法的满秩格；很容易去掉此限制。此外，我们描述的仅适用于范式，扩展到其他范式是已经被证明出来的。

现在让我们描述LLL算法，这个论述分三个阶段：

1. 建立一个LLL的规约基;
2. 提出一种算法来得出这个基
3. 分析它的所需用时。
4. 规约基

我们首先回顾一下施密特正交化过程。

要求1：给出n个线性无关向量对这n个向量进行施密特正交化被定义成以下形式：=-，这里的=

要求2:如果下面成立的话，一个基于B={}是的规约基:

1．，

2.。

备注1：从一个基变为规约基总是可以实现的，其实这也就是LLL可以达成的事情。

备注2：考虑这种情况是非常必要的。这个算法适用于。

备注3：定义2中的第二个特性也可以写成：

=

其中第二个等式遵循从到是正交的，它遵循下面：

使用这种方式，这第二个特性读取“是不如短的”。

为了更好的了解这个定义，考虑到归一化正交基施密特矢量在此基准下，B可以表示为

在这里我列双显示在这个标准正交基的坐标。在一个LLL规约基德基础上保证的定义的第一个条件，任何非对角线元素的绝对值至多为写在对角线元素上的同一行中的值的一半。这可以写成

这里||表示这个坐标的绝对值至多为||。第二属性考虑到上诉矩阵的2X2子矩阵是在左上角的索引(i,i).

然后第二属性要求该矩阵的第二列是几乎只要它满足它的第一列。让我们从提到的Schnorrrsquo;s算法改进LLL算法。本次第二特性KXk将被K2替换，规约基的一个重要特性是：它的第一矢量相对较短，就像下一个定义的中所提到的一样。

引理1 令是LLL的一个规范基。然后||||(L)

备注4 从sigma;=得出||||(L)。

证明：从所有基，(L)，我们得到

这里的最后一个等式是基于=。然后，对于所有i，

因此，||||(L)

证明5 LLL的规约基有很多不错的性能，一些在作业中提及。

引理2 提供我们对SVP的一个近似方法。假设我们可以从我们给出的基里生成一个LLL的规约基，那么我们可以返回作为我们的答案。从我们得到一个对的近似，下文中我们将介绍怎么把任意一个基转换成LLL的规约基。

1. LLL算法

输入：点阵基

输出：LLL规约基从L(B)

开始：计算

还原步骤：

for i=2 to n do

for j=I-1 to 1 do

其中

交换步：

If then

goto start

输出：

备注6 我们使用代表把数值近似到最接近的整数，例如：[3.3]=3,[3.8]=4.

让我们在此过程中给出一些重要的意见。很容易看出交换步骤采用LLL规约基的第二条属性。如果该算法可以终止，那么输出必须满足第二条件。这个还原部满足第一条件。目的去看清这里，我们看整个还原步，这里的斯密特基没有发生变化（因此向量，不需要从新进行计算）。所以我们只要对对（igt;j;a）进行列计算。这个操作不会影响施密特正交。在外层循环第i次迭代中，还原步骤可以确保对在上的投影对于任何jlt;i最大值是。这个操作通过减去i列的向右取整乘以j列，这样第j个坐标绝对值至多为。注意内环从i-1到1是非常重要的。

为了演示还原步骤，让我们写的B通过归一化的施密特获得正交基。考虑，例如：这个外部循环的第i次迭代和内循环的j=2的迭代。然后在这样一点上，矩阵B的形式如下：

在此迭代中，我们从第i列减去第二列的某些整数倍去让第i列的绝对值最多为。同样的，在内层循环中的最后一次迭代中国我们从的i列减去第一列的某些整数倍。

引理3（正确性）如果LLL程序像上诉过程终止，通过输入然后它的输出是LLL点阵的规约基。

证明：我们需要证明LLL算法的输出是L(B)的一个基且它满足LLL规约基的两个属性。这个规约基的第二属性被执行是在交换步之中。这个算法确实是一个L(B)的一个基的原因是我们仅仅对列进行了操作（igt;j;a）。

我们接下来说明还原步之后，满足。首先，注意整个还原步骤，施密特基不会改变，现在考虑，并且考虑在内循环的第j列外循环的第i列。然后||可以被写成

=||

这里在还原步的定义下的第一个等式和在下的最后一个不等式。

1. 分析这个运行时间

我们的分析包含2个步骤。首先我们结合这个迭代次数。第二，我们结合一次迭代的运行时间。我们表明，该算法的总运行时间是输入大小的多项式时间。一个粗略的下界给出是M:=max{n,log()}(因为每一个n矢量都至少需要一个字节表示，并且一个范数r的矢量至少需要log r 字节去表示)，下面，我们将说明这个算法的运行时间是以M的多项式的形式。

引理4 迭代次数时与M的多项式。

证明：我们第一步是去定义一个函数映射一个点阵基到一些正数。这个函数可以被认为是一个“点位功能”。

引理5B={}是点真的基。这个B的点位，记为被定义为：

其中,被定义为由 生成的点阵

备注7 注意更多的权重被给到了第一个矢量。

我们的目的是要表明，不是太大并且它还会迅速衰减。由于 ，的初始值可以通过（）来限定。注意，此值的对数是以M的多项式。

在还原步骤中，不会改变，因为施密特基是不会改变的。现在我们考虑这个交换步。假设被换成。对于所有的，不会发生改变 ，仅仅会发生改变。让,分别表示和的新值 ，我们得到：

其中最后一个等式是根据交换步的条件得到。

如上所示，在每次迭代中，衰减通过一个乘法因子。令是的初始值。因为是一个非0整数，并且至少为1，这就意味着我们可以约束从以上次数的迭代以：

对于任何常数这就是以M的多项式。

备注8 一个有点繁琐的计算表明，即使对于，这都比任何常数都更接近于1，它的运行时间是多项式时间。对于的近似因子是。这种近似因子本质上最好的一个可以用LLL算法获得。对于更好的近似因子，需要应用Schnorrrsquo;s算法。

引理6 每次迭代的运行时间是M的多项式时间。

证明：不难看出，每次迭代我们仅仅执行算术运算（即，加法，减法等）的多项式次数。因此，在证明的其余部分，这足以证明在每次迭代中产生的数字可以表示成比特多项式。

为了证明这位什么是必要的，考虑用重复平方法，给出一个数x,对其平方n次,即使算术运算的数仅仅是n，用来表示的这个数迅速增大到了。因此，算法（比特的操作的测定）的实际时间是n的指数。

我们建立约束使用这两种要求的迭代中出现的数字。这第一个问题是施密特矢量，这是一个简单的约束，在还原步中它们不会发生改变，这第二个问题是基础基。

依据2 这个施密特矢量可以在以M的多项式时间内计算出来，而且，对于每一个1，我们可以得到和。
备注9 注意注意施密特矢量的两种特性意味着他们可以表示成M的空间多项式形式。这个规范的约束意味着每一个关于的坐标至多含有绝对值的数量。因此。我们知道分母不能比还大。因此，每个坐标位至多需要个字节并且他们共有。因此的初始值是以M的多项式并且之后它只能衰减，我们得到的施密特矢量可以表示成以M的空间多项式。

证明:施密特矢量基德计算可以表示成如下形式：因为，我们可以写成，其中。我们真在寻找这样一组满足是与都正交。对于每一个可以被写成：

因此，我们获得以下包含i-1个变量的i-1元方程组：

在一个多项式时间内是可以解决这个方程组的。

对于第二个条件，注意使用克莱姆法则我们可以写成：

因此对于一些有理数的分母是。这意味着特别是当是整向量时。

现在我们说明是不是很大。显而易见，

并且：

第一个等式可以得出下面是由于：。

在接下来的解释中，我们说明这个矢量基不会变的太大。这是必要的因为这些矢量基可能在还原步中改变(事实上，矢量可能变长在还原步过程中)。我们首先结合在第外循环i次迭代完成后的各个的长度（例如：当矢量衰减时）。然后我们结合第i次外循环时的长度。为了观察矢量我们仅仅添加一个矢量（jlt;i）。这些矢量将会衰减，为此我们首先结合这些方法。

依据3 所有的矢量在一个迭代期可以表示成M的多项式形式。

证明：首先，我们说明了，再还原步之后，的长度不会很长，对于每一个：

都有：

这第一个等式成立是因为是正交的。这第一个约束为的不等式在证据3中已被证明，并且正在使用。

我们约束这个范数意味着每一个坐标哦含有至多个整数，只意味着它可以表示成个字节。我们的仍然是个整形的矢量在衰减过程中---他们这样输入，我们通过增添整数去改变他们的值。这意味着在还原步后，我们可以证明这个在M多项式组空间里。

最后，我们需要说明在还原步之后，这个是不会太大的。考虑到一个矢量，他是受控于还原步的内循环过程。

其中第一个不等式通过使用柯西-施瓦兹不等式和四舍五入操作后定义如下，并且第二个不等式使用依据2。为此有：

其中第一个不等式有如下的三角不等式，通过约束为，并且这第三个不等式通过限制约束在还原步之后的的长度。事实上，在还原步的，矢量(jlt;i)，他们已经完成在还原步中，所以我们可以使用这个约束。内环在至多n次内循环迭代之后，这个范数已经增长一个因子至多。这用M的多项式组当让可以表示。

通过依据2和依据3我们得出我们可以通过多多项式字节数来表示一个多项式数。这样，在每次迭代中，我们都执行算术运算的多项式数，证明了这个引理。

备注10我们唯一使用这个其中jlt;i，是在证明引理3的额时候，对于这个剩余的证明，用较弱的条件就已经足够了。这表明，我们可以提高时间通过只对连续连续矢量进行还原操作以便获得较弱的状态。在修改的算法中迭代次数仍然是多项式，因此我们上诉所有的参数保持不变。然而，现在我们尚不清楚这个改进的算法是否仍会运行在多项式时间内，因为

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[146339]，资料为PDF文档或Word文档，PDF文档可免费转换为Word