摘要
计算机通常被认为是一种通用的计算设备;也就是说,它被认为能够模拟任何物理计算设备,计算时间成本最多为多项式因子。如果把量子力学考虑在内,这一结论是否仍然成立也不清楚。以David Deutsch为首的几位研究人员开发了量子力学计算机的模型,并研究了它们的计算特性。本文给出了在量子计算机上寻找离散对数和因式分解整数的 Las Vegas 算法,该算法采用多个步骤,输入大小为多项式,例如要因式分解的整数的位数。这两个问题在经典计算机上通常被认为是困难的,并且已被用作几个提议的密码系统的基础。 (因此,我们给出了量子密码分析的第一个例子。)
1.引言
自从量子力学发现以来,人们发现量子力学中概率定律的行为是违反直觉的。由于这种行为,量子力学现象的行为与我们所熟悉的经典物理现象截然不同。费曼似乎是第一个提出这对计算有什么影响的人。他论证了为什么这种行为会使在经典(或冯·诺伊曼)计算机上模拟量子力学的计算成本过高。他还提出了使用基于量子力学原理的计算机来避免这个问题的可能性,从而含蓄地提出了相反的问题:通过在计算机中使用量子力学,您是否可以比在经典计算机上更有效地进行计算。 在量子力学和计算领域的其他早期工作由Benioff完成。虽然他并没有提出量子力学是否赋予了计算额外的能力,但他确实证明了可以通过量子过程的可逆幺正演化来模拟图灵机,这是量子计算的必要前提。 Deutsch是第一个给出明确的量子计算模型的人。他定义了量子图灵机和量子电路,并研究了它们的一些特性。
本文的下一部分讨论了量子计算与经典复杂性类别的关系。因此,我们将首先为那些没有此背景的读者简要直观地讨论复杂性类别。通常有两种资源限制了计算机解决大问题的能力:时间和空间(即内存)。算法分析领域将算法对这些资源的渐近需求视为问题大小的函数。当算法的步数增长为输入大小的多项式时,理论计算机科学家通常将算法归类为有效算法。可以通过有效算法解决的问题类别称为 。这个分类有几个很好的属性。一方面,它可以合理地反映算法在实践中的性能(尽管运行时间是输入大小的 10 次方的算法并不是真正有效的)。另一方面,这种分类在理论上很好,因为不同的合理机器模型产生相同的 类。我们将看到这种行为在量子计算中再次出现,其中量子机器的不同模型在运行时间上的差异不会超过多项式因子。
本文还讨论了其他计算复杂性类。其中一个是PSPACE,这些问题可以通过输入大小的内存多项式来解决。另一个重要的复杂度类是NP,直观上是指数搜索问题。这些问题可能需要搜索指数大小的空间来找到解决方案,但是一旦找到解决方案,就可以在多项式时间内验证解决方案(可能使用多项式数量的额外支持证据)。我们还将讨论另外两个传统的复杂性类。一个是 BPP,这是一种可以在多项式时间内用一个随机数生成器以高概率解决的问题。另一个是 ,如果可以有效地计算指数级多个项的总和(其中这些总和必须满足每个项在多项式时间内可计算的要求),那么这些问题可以在多项式时间内解决。这些类的关系如下:

BPP 和 NP 的关系是未知的。
在计算机中使用量子力学是否能使人获得更多的计算能力,这个问题尚未得到令人满意的回答。虽然这个问题在之前的研究中得到了解决,但没有说明如何在量子多项式时间内解决任何在 BPP 中无法解决的问题(一类可以在有界误差概率的多项式时间内解决的问题)。Bernstein和Vazirani的论文为计算复杂度的量子计算理论奠定了基础,促进了最近对这一问题的研究。这篇论文中包含的一个结果是一个预言问题(一个涉及“黑盒子”子程序的问题),它可以在量子图灵机上用多项式时间完成,而在经典计算机上需要超多项式时间。这是第一个迹象,除了没有人知道如何在没有指数减速的情况下在经典计算机上模拟量子计算机之外,量子计算可能比用随机数生成器扩大的经典计算获得大于多项式的加速。Simon改进了这一结果,他给出了一个更简单的oracle问题的构造,在量子计算机上需要多项式时间,而在经典计算机上需要指数时间。事实上,通过将Simon的预言视为一个子程序,这个结果就变成了一个有希望的问题,它在量子计算机上需要多项式时间,在经典计算机上看起来似乎非常困难。本文给出的离散对数“简单情况”的算法直接类似于simon算法,即组 替换为组 ;我是在看到Simon的论文后才发现这个算法的。
在Bernstein和Vazirani论文的另一个结果中,严格定义了一类特定的量子图灵机,并给出了一个通用的量子图灵机,它可以模拟该类的任何其他量子图灵机。不幸的是,这些量子图灵机是否能够模拟其他类的量子图灵机还不清楚,因此这个结果并不完全令人满意。Yao纠正了这种情况,证明了量子图灵机可以模拟多项式大小的量子电路,并且可以被这些量子电路所模拟,其速度最多为多项式。他进一步定义了具有 个头的量子图灵机,并表明这些机器可以在减速系数为 的情况下进行模拟。这似乎表明,这类问题可以在多项式时间内在这些机器上解决,可能具有有界概率 的误差,是相当稳健的。此类称为BQP,类似于经典的复杂性类BPP,这些问题可以在概率图灵机上用一个有界的误差概率来解决。此类BQP可以被认为是在量子图灵机上可有效解决的一类问题。
由于BPQ ,任何证明 BQP 严格大于 BPP 的非相对化证明都将暗示结构复杂性结果 尚未得到证明。鉴于这一困难,我想到了几种方法;一个是表明 将导致被认为是不同的经典复杂性类别的崩溃。第二种方法是证明与预言相关的结果。Bennett等人表明,相对于随机预言机, 并非如此。这一证明实际上表明量子计算机不能反转单向函数,而只能证明单向预言,即作为子程序给出的“黑盒”函数,不允许量子计算机查看内部。这种预言结果在过去一直具有误导性,尤其是在 的情况下。我们采用的第三种方法是在 BQP 中解决一些经过充分研究的问题,该问题没有多项式时间算法已知。这表明,量子干涉所赋予的额外功率至少很难使用经典计算来实现。 Bernstein 和 Vazirani 和 Simon也为 BPP 中未知的问题提供了多项式时间算法,但是这些问题是专门为此目的而发明的,尽管 Simon 的问题看起来并不人为,并且可以想象是有用的。
离散对数和整数因式分解是两个已被广泛研究但没有多项式时间算法已知的数论问题 。事实上,人们普遍认为这些问题很难,以至于基于密码系统 已经提出了关于它们的硬度的问题,并且基于因式分解的硬度的 RSA 公钥密码系统正在使用中。 我们证明了这些问题可以在 BQP 中解决。
目前,没有人知道如何建造量子计算机,尽管在量子力学定律下似乎是可能的。对于这种计算机的可能设计已经提出了一些建议,但是要建立这些计算机中的任何一个都将会有实质性的困难。即使可以建造小型量子计算机,但将规模扩大到足以进行有趣计算的机器可能会带来根本性的困难。 希望这篇论文能够激发对实际构建量子计算机是否可行的研究。
即使从未建造过量子计算机,这项研究也确实阐明了在经典计算机上模拟量子力学的问题。 对任意哈密顿量执行此操作的任何方法都必须能够模拟量子计算机。 因此,任何用于模拟最多多项式减速的量子力学的通用方法都将导致用于因式分解的多项式算法。
2.量子计算
在本节中,我们将简要介绍量子计算,强调我们将使用的属性。 对于更完整的概述,建议读者参考 Simon 的论文或早期关于量子计算复杂性理论的论文。
在量子物理学中,一个实验表现得好像它同时沿着所有可能的路径进行。每条路径都有一个复杂的概率振幅,这是由实验的物理性质决定的。实验中任何特定结果的概率与所有通向该结果的路径振幅和绝对值的平方成正比。为了对一系列路径进行求和,结果必须在所有方面都是相同的,即宇宙必须处于相同的状态。量子计算机的行为与此大致相同。 计算同时沿着所有可能的路径进行,并且每条路径都与一个复振幅相关联。 为了确定机器任何最终状态的概率,我们将到达该最终状态的所有路径的幅度相加,然后对该总和的绝对值求平方。
观察这个过程的一个等价的方法是想象机器在计算的每一步都处于某种状态的叠加状态。我们将态的叠加表示为

其中幅值 为复数,使得 ,并且每个 是机器的基本状态;在量子机器中,基本状态由磁带上写入的内容以及磁头的位置和状态定义。 在量子电路中,基态是由电路中某一级别的所有导线上的信号值来定义的。如果在某一特定步骤检查机器,则看到基状态 的概率为 ;然而,根据海森堡不确定性原理,在计算过程中看着机器会干扰其他的计算过程。
量子力学定律只允许状态的酉变换。一个酉矩阵的共轭转置等于其逆矩阵的矩阵,并且要求用酉矩阵表示状态变换可确保获得所有可能结果的概率加起来为 1。 此外,量子图灵机和量子电路的定义只允许局部酉变换,即对固定位数进行酉变换。
在这一点上,也许一个例子会提供信息。 假设我们的机器处于状态叠加状态

然后应用酉变换

到我们状态的最后两位。 也就是说,我们将向量 (2.2) 的最后两位分量乘以矩阵 (2.3)。 然后机器将进入状态叠加

请注意,如果我们从状态叠加开始,结果会有所不同

如果观察到它,它在任何特定配置中具有相同的概率。
我们现在给出一些有用的量子计算特性。 从量子物机或量子电路的定义来看,这些事实并不是立即显而易见的,它们对于构建量子机器的算法非常有用。
事实 1:当且仅当确定性计算是可逆的时,在量子计算机上可以执行确定性计算。根据可逆计算的结果,只要我们将输入 保留在机器上,我们就可以计算任何多项式时间函数 。 要擦除 并用 替换它,我们还需要 是一对一的,并且 可以从 在多项式时间内计算; 即 和 都是多项式时间可计算的。
事实2:任何多项式大小的酉矩阵都可以使用多项式的基本酉变换来近似,因此可以在量子计算机上以多项式时间进行近似。 此外,该近似值足够好,可以在计算结果中引入最多有界的错误概率。
3.构建酉变换
由于量子计算涉及酉变换,因此能够建立某些有用的酉变换是很有帮助的。本节我们将给出一些在量子机器上构建酉变换的技术,这将导致我们展示如何在多项式时间内构建一个特定的酉变换。 这些转换通常以矩阵形式给出,行和列都由状态索引。 这些状态将对应于计算机上的整数表示; 特别是,除非另有说明,否则行和列将从 0 开始索引。
我们将在本文中反复使用的一个工具是下面的酉变换,它的求和得到一个傅里叶变换。考虑一个数字 与 对于某个 , 的位数是多项式。我们将执行将状态 转换为状态

也就是说,我们应用其第 项为 的酉矩阵。 这种转换是我们算法的核心,我们称这个矩阵为 。 由于我们将使用 ,对于指数大小的 ,我们必须说明如何在多项式时间内完成这种转换。 事实上,我们只能对平滑数 执行此操作,即质因数较小的数。 在本文中,我们将处理对于某些固定 不包含大于 的素功率因数的平滑数 。 也可以在多项式时间内对所有平滑数 进行这种变换;Coppersmith 展示了如何使用本质上是快速傅立叶变换对 进行此变换,并且这大大减少了因式分解所需的运算次数。
如果我们知道一个因数分解 ,其中 ,并且 和所有 都是多项式大小的,我们将展示如何在多项式时间内通过组合 ,来构建变换 。为此,我们首先需要一个关于量子计算的引理。
引理 3.1 假设矩阵 是一个块对角线 酉矩阵,由沿对角线的 个相同的 矩阵 和其他任何地方的 组成。 进一步假设状态转换 可以在时间 上在量子图灵机上完成。 然后矩阵 可以在 时间内在量子图灵机上完成,其中 是一个常数。
我们将此矩阵 称为 的 个副本的直接和,并使用符号 。 该矩阵 是 和 的张量积,其中 是 单位矩阵。
证明:假设磁带上有一个数字 。 我们可以从 可逆地计算 和 。 此计算从磁带中删除 并将其替换为 和 。 现在 告诉 包含在哪个块中, 告诉该块中矩阵的哪一行是 行。 然后我们可以将 应用于 以获得 (在此过程中擦除 )。 现在,结合 和 以获得 给出了 应用于 的结果(具有正确的幅度)。 的计算需要 时间,其余的计算是 中的多项式。
我们现在展示如何获得 ,以获得平滑的 。 我们将 分解为多项式的单位变换的乘积,所有这些都可以在多项式时间内执行; 这使我们能够在多项式时间内构造 。 假设我们有 且 。我们要做的是表示 ,其中通过重新排列 的行和列我们得到 , 并且重新排列行和 的列我们得到 。 只要 和 的行和列的这些重新排列可以在多项式时间内执行(即,给定行 ,我们可以在多项式时间内找到它所在的行 )并且逆运算也可以在多项式时间,然后通过使用上面的引理和递归,我们可以在量子计算机上获得多项式时间的方式来执行 。
我们现在需要定义 和 并检查 。 要定义 和 ,我们需要一些初步定义。 回想一下 ,其中 和 互质。 令 。 令 为数 ,使得 且 。 根据中国余数定理,这个数是存在的,并且可以在多项式时间内计算出来。我们将行和列索引 分解如下: 、 和 。注意 定义中的不对称性。
现在我们可以定义 和 :

且

很容易看出 其中 因为我们需要 和 来确保 和 。 现在,

所以 。
我们现在将概述如何重新排列 的行和列,以获得矩阵 。 矩阵 可以放在块对角形式中,其中块由 索引(因为所有带有 的条目都是 )。令 。 在给定的块 内,条目是这样的

因此,如果我们重新排列该块中的行,以便它们通过 进行索引,我们将获得具有幅值 的变换 ; 即,由 项等于 的酉矩阵给出的变换,即 。矩阵 可以类似地重新排列以获得矩阵 。
我们还需要展示如何在多项式时间内找到介于 和 之间的平滑 。 实际上有更接近 的平滑 ,但这就是我们所需要的。 不知道如何在多项式时间内找到非常接近 的平滑数。
引理 3.2 给定 ,有一个多项式时间算法可以找到一个数 ,其中 ,使得没有大于 的素数除以 ,对于某个常数 与 无关。
证明 要找到这样的 ,将素数 相乘,直到乘积大于 。 现在,如果这个乘积大于 ,则将其除以保持数字大于 的最大素数。 这会产生所需的 。 在 和 之间总是存在一个素数,所以 。 素数定理和一些计算表明,最大的素数除法 的大小为 。
请注意,如果我们使用 2% 单位根的 Coppersmith 变换 ,我们设 ,其中 。
4.离散对数:简单案例
离散对数问题是:给定一个素数 p,乘法组的生成器 和一个 ,找到一个 使 。我们将首先给出在 是平滑的情况下在量子计算机上离散对数的多项式时间算法。 该算法与Simon论文中的算法类似,只是用 代替了组 。平滑情况本身并不是一个有趣的成就,因为在这种情况下已经有经典计算机的多项式时间算法; 然而,解释这种情况比解释离散对数或分解算法的一般情况更容易,并且由于这三种算法相似,这个例子将说明更复杂的算法是如何工作的。
我们将从磁带上的 开始我们的算法。(即,在我们机器的量子存储器中)。 我们试图计算 使得 。 因为我们永远不会删除它们,所以 是常数,我们将通过磁带的其他内容指定我们机器的状态。
该算法从统一“选择”数字 和 开始,所以这一步之后机器的状态是

该算法接下来可逆地计算 ,因此我们必须将值 和 保留在磁带上。 机器状态现在是

我们现在要做的是使用变换 来映射 与幅度 和 与幅度 。 正如上一节所讨论的,这是一个酉变换,并且由于 是平滑的,它可以在量子机器上的多项式时间内完成。这将使机器处于状态

我们现在计算机器在状态 和 时计算结束的概率。这个概率是机器可以产生这种状态的所有方式的总和平方的绝对值, 或者

其中所有 的和满足 。 这种情况源于这样一个事实,即计算路径只有在给出相同的 时才会产生干扰。 我们现在将方程 代入上述指数。 然后上面的总和减少到

然而,如果 上面的和是在一组 个单位根上均匀分布在单位圆周围,因此概率为 。如果 是 乘以相同的根,得到 ,所以概率是 。我们可以通过计算有 个状态 来检查这些概率加起来等于 ,因为有 个选择 和 个选择 。
因此,我们的计算产生了一个随机的 和相应的 。如果 和 是相对质数,我们可以通过除法得到 。因为我们是在所有可能的c中以相等的概率进行选择, 和 相对质数的机会是 ,其中 是欧拉 。很容易求出 。(实际上,限制 )因此,我们只需要大量的实验,在 上是多项式,就可以得到高概率的 。事实上,我们可以找到一组 ,使得 的每个质数因子中至少有一个是质数的,只要在预期的常数次内重复这个实验。这也给了我们足够的信息来得到 。
5.关于精度的说明
量子力学计算机振幅所需的精度位数可能是实用性的障碍。 可行和不可行之间普遍接受的理论分界线是多项式精度(即问题大小的对数位数)是可行的,而更多的则是不可行的。 这是因为在量子计算机上,相位角需要通过一些物理设备来获得,而以优于多项式精度的方式构建此类设备无疑是不切实际的。 事实上,即使是多项式精度也可能被证明是不切实际的; 但是,将其用作理论分界线会产生很好的理论性质。
因此,我们需要证明上一节中的计算只需要在幅度中使用多项式精度。 写下表达式 的行为似乎暗示我们需要指数精度,因为这个相位角是指数精度的。 幸运的是,情况并非如此。 考虑相同的矩阵 ,其中每一项 都替换为 。 每个正例,即导致 的情况,仍然会以几乎与以前一样大的概率发生; 我们不是添加具有完全相同相位角的 个幅度,而是添加具有几乎相同相位角的 个幅度,因此总和的大小只会减少一个常数因子。因此,算法将给出一个 ,其中 具有常数概率(而不是概率1)。
回想一下,我们通过最多将 矩阵 相乘来获得矩阵 。 此外, 中的每个条目最多是 项的乘积。 假设每个相位角在 中最多偏离 。 然后在产品中,每个相位角最多会偏离 ,这足以以恒定的成功概率执行计算。 一个类似的论点表明, 中幅度的大小可以偏离多项式分数。 类似的论点适用于离散对数的一般情况和因式分解,以表明在这些情况下,我们也只需要幅度的多项式精度。
我们仍然需要展示如何从精度有限的恒定大小的酉矩阵中构造 。 论点与上述大致相同,但我们不会在本文中给出它们,因为事实上,Bennett等人已经证明,对于量子图灵机上的任何计算,使用多项式精度来获得高概率的答案是足够的。
由于精度很容易成为量子计算实用性的限制因素,因此建议研究量子算法实际需要多少精度。 尽管 Bemstein 和 Vazirani 表明所需的精度位数永远不会超过量子计算机所采取的计算步骤数的对数,但在某些算法中它可能需要更少的精度。 有趣的悬而未决的问题是,是否有可能以低于多项式的精度进行离散对数或因式分解,以及是否可以在精度和时间之间进行权衡。
6.因式分解
因式分解的算法类似于离散对数的一般情况的算法,只是稍微简单一些。 我在离散对数的一般情况之前介绍了这个算法,以便按照复杂度增加的顺序给出本文中的三种算法。 对离散对数感兴趣的读者可以跳到下一节。
我们不是给出一个量子计算机算法来分解 ,而是给出一个量子计算机算法来寻找乘法组中元素 的阶数 ;即 的最小整数 。 从因式分解到元素的顺序有一个随机减少。
为了分解一个奇数 ,给定一个元素的阶数的计算方法,我们随机选择一个 ,找出 的阶数 ,并计算 。只有当 是奇数或 时,这才不能给出 的非平凡除数。使用这个判据,可以证明该算法找到一个概率至少为 的 因子,其中 是 的不同素数因子的个数。因此,只要 不是素幂,该方案就可以工作; 但是,使用经典方法可以有效地分解素数。
给定 和 ,要找到满足 的 ,我们执行以下操作。 首先,我们找到一个 的平滑 。 接下来,我们将机器置于表示数字 的状态的统一叠加中。 这使我们的机器处于状态

与离散对数的算法一样,我们不会在机器的状态中写入 ,因为我们从不改变这些值。
接下来,我们计算 。 由于我们将 和 保留在磁带上,因此可以可逆地完成。 这使我们的机器处于状态

然后我们执行傅里叶变换 ,将 映射到幅度 。 这使我们的机器处于状态

最后,我们观察机器。 仅观察 的值就足够了,但为了清楚起见,我们假设我们同时观察 和 。 我们现在计算我们的机器以特定状态结束的概率 ,其中我们可以假设 。对所有可能的方式求和达到这个状态,我们发现这个概率是

其中总和是所有 , ,使得 。 因为 的阶数是 ,所以这个和等效于所有满足 的 。 写作 ,我们发现上面的概率是

我们可以忽略 的项,因为它可以从总和中分解出来并且大小为 。我们也可以用 替换 ,其中 是与 同余,并且在 的范围内。 这给我们留下了表达式

现在我们将证明,如果 足够小,那么这个和中的所有幅度将几乎在相同的方向上,给出一个很大的概率。 如果 , 相对于 很小,我们可以使用变量 的变化,并用积分近似这个和

如果 ,这个量可以被证明为渐近下界为 ,因此至少有 。看到给定状态 的概率至少为 ,如果

也就是说,如果有一个

除以 ,重新排列得到

我们知道 和 。 因为 ,最多有一个分数 且 满足上述不等式。 因此,我们可以通过将 四舍五入到分母小于 的最接近的分数来获得最低项的分数 。 这个分数可以通过使用 的连续分数展开在多项式时间内找到,它通过分数找到 的所有最佳近似值。
如果我们有最低分数 ,并且如果 恰好与 互质,这将给我们 。我们现在将计算状态数 ,这使我们能够计算 这样。 与 互质的有 个可能值,其中 是欧拉的 函数。 这些分数 中的每一个都接近一个分数 ,其中 。 也有 个可能的值,因为 是 的阶。 因此,有 个状态 将使我们能够获得 。 由于这些状态中的每一个都以至少 的概率出现,因此我们以至少 的概率获得 。 使用 的定理对于某些固定的 ,这表明我们发现 至少有 时间的一部分,所以通过只重复这个实验 次,我们确信有很高的成功概率。
请注意,在排序算法中,我们没有使用乘法 的许多属性。 事实上,如果我们有一个置换 映射集合 到自身中,使得其 迭代 可以在 和 中以时间多项式计算,相同的算法将能够找到元素 在 下的阶, 即,最小 使得 。
7.离散对数:一般情况
对于一般情况,我们首先找到一个光滑的数字 ,使 接近 ,即 (见引理3.2)。
接下来,我们做与简单情况相同的事情,即统一选择 和 ,然后计算 。这样我们的机器就处于状态

和以前一样,我们使用傅里叶变换 ,发送 和 ,幅度为 ,给我们状态

请注意,我们现在有两个模数要处理, 和 。 虽然这使得追踪事情变得更加混乱,但我们仍然可以使用类似于简单案例的算法来获得 。 用 观察状态 的概率几乎和以前一样,

的和使 。我们现在利用这个关系

并代入上述表达式以获得幅度

这个幅度的平方的绝对值是观察到状态 的概率。 我们现在来分析这个表达式。 首先,可以从所有项中取出 的因子并忽略,因为它不会改变概率。 接下来,我们将指数分成两部分并分解出 以获得

其中

并且

这里的 是指 的余数,其中 。 我们将证明,如果我们得到足够“好”的输出,那么我们仍然可以推导出 ,而且,得到“好”的输出的机会是恒定的。 这个想法是,如果

其中 是最接近 的整数,那么当 在 到 之间变化时,Eq.(7.6)中的第一个指数项的相位最多只在单位圆的一半上变化。此外,如果

那么 总是最多 ,因此Eq.(7.6)中的第二个指数项的相位永远不会比 离 远。通过结合这两个观察,我们将表明,如果两个条件都成立,那么对应项对概率的贡献是显著的。此外,这两个条件将以恒定的概率成立,和一个合理的 的样本,其中条件(7.9)成立将允许我们推断 。
我们现在给出每个良好输出的概率的下界,即满足条件(7.9)和(7.10)的输出。我们知道当 取值为 到 时, 的相位取值为 到 ,其中

如式(7.9)所示。因此,式(7.6)中第一个指数的振幅在方向上的分量

至少为 。现在,根据条件(7.10)。由于第二个指数 ,相位最多可以变化 。应用这种变化的方式来最小化方向上的分量(7.12),我们得到这个方向上的分量至少是 。因为 ,从条件(7.9), ,把所有内容放在一起,得到同时满足条件(7.9)和(7.10)的状态 的概率至少为

或者至少是 。
我们现在将计算满足条件 (7.9) 和 (7.10) 的的成对数 。 使 (7.9) 成立的对 的数量正是可能的 的数量,因为对于每个 恰好有一个 使得 (7.9) 成立(将分数四舍五入到最接近的整数以获得这个 )。 (7.10) 成立的 的数量约为 。 因此,有 对 (c,d) 满足这两个条件。 乘以 ,它是可能的 的数量,得到大约 个状态 。将此计算与每个良好状态概率的下限相结合,我们得出获得任何良好状态的概率 状态至少为 ,或至少 (因为 )。
我们现在想从一对 中恢复 使得

其中这个方程是从条件 (7.9) 除以 得到的。 首先要注意的是, 上的乘数是分母为 的分数,因为 均分 。因此,我们只需要将 四舍五入到最接近 的倍数,并除以

找到一个候选 。为了证明这个实验只需要重复多项式次数来找到正确的 ,只需要更多的细节。 问题是我们不能除以一个与 不互质的数。
对于离散对数算法的一般情况,我们不知道 的所有可能值都是合理似然生成的;我们只知道其中的十分之一。这个额外的难度使得下一个步骤比前两个算法中相应的步骤更难。 如果我们知道 模除 的所有素数的余数,我们可以使用中国剩余定理在多项式时间内恢复 。 我们只能找到大于 20 的素数的余数,但通过一些额外的工作,我们仍然能够求出 。
我们所拥有的是每个好的 对的生成的概率至少为 ,并且至少十分之一可能的 位于好的 对中。由方程式 (7.15)可知,这些 通过四舍五入到 的最接近整数倍数,从 映射到 。此外,好的 正是 接近 的那些。因此,每个好的 都恰好对应于一个 。我们想证明,对于任何素数 除以 。一个随机的好 不太可能包含 。如果我们愿意接受算法的大常数,我们可以忽略20以下的素数幂;如果我们知道 模所有超过20的素数幂,我们可以尝试20以下素数的所有可能的残差,而运行时间只有(大)常数因子增加。因为至少有十分之一的 是好的 对,所以至少有十分之一的 是好的。因此,对于素数幂 ,随机的好的 可被 整除,概率最多为 。如果我们没有好的 ,那么拥有超过20的素数幂除以所有这些概率的概率最多是

其中总和是所有大于 20 且除以 的素数的总和。这个总和(在所有大于 20 的整数上)在 时收敛,并且随着 每进一步增加 1,该总和至少下降 2 倍; 因此对于一些大常数 它小于 。
回想一下,每个好的 是从任何实验中以至少 的概率获得的。 由于有 个好的 ,经过 160t 次实验,我们很可能会从所有好的 中等概率地获得 个好的 样本。 因此,我们将能够找到一组 ,使得除 的所有素数幂 与这些 中的至少一个相对素数。 对于每个小于 20 的素数 ,因此我们最多有 20 种余数模 的可能性,其中 是 的素数分解中素数 的指数。因此,我们可以尝试所有可能的余数模幂小于 20 的素数:对于每种可能性,我们可以使用中国剩余定理计算相应的 ,然后检查它是否是所需的离散对数。
该算法并没有使用 的很多性质,因此我们可以使用相同的算法来求其他域上的离散对数,例如 。 我们需要的是我们知道生成器的顺序,并且我们可以在多项式时间内乘以和取元素的逆。
如果要对这个算法进行编程(必须等到建立量子计算机之后),有很多方法可以提高本文中所示的效率。
致谢
我要感谢 Jeff Lagarias 在离散对数算法的第一个版本中发现并修复了一个严重错误。 我还要感谢Charles Bennett、Gilles Brassard、Andrew Odlyzko、Dan Simon、Umesh Vazirani 以及其他的作者,感谢他们进行富有成效的讨论,对本文的早期草稿进行更正和改进,以及本文所引用的参考文献。
---煤油灯科技victorlamp.com翻译整理---









