TeXmacs 1.99.14发布。请看这篇导出到HTML的研究论文

假设关于算术级数中最小素数的假设被广泛接受，我们证明了两位整数可以在有限磁带数的图灵机上在时间上相乘；我们还证明了小于有限域上的次多项式可以在时间上一致相乘。

设表示确定性多带图灵模型中最多位的两个整数相乘的位复杂度[16]。类似地，让我们表示将两个次数多项式相乘的比特复杂度。这里是有限域的元素，所以对于一些素数和整数。为了计算，我们默许给出一个一元不可约的次数多项式，并且的元素用次数多项式表示。请注意，中的乘法也可以视为“无进位”的基数整数乘法。

和目前已知的最好界在[21]和[23]中得到。对于常量和，我们在那里证明了。

对于我们新结果的陈述，我们需要回顾一下“林尼克常数”的概念。给定两个整数和，我们定义。

我们称一个数为Linnik常数，如果。目前已知的最小的林尼克常数是由于Xylouris[57]。人们普遍认为，任何数字实际上都是林尼克常数；有关详细信息，请参阅第5节。

定理1.2是我们的主要结果。请注意，它隐含在输入的位大小方面。在文[22]中，我们证明了这个界实际上是无条件成立的，从而取代了定理1.1。由于定理1.1的证明很好地介绍了定理1.2的证明，而且比文[22]中无条件界的证明略短，因此我们决定将其包括在本文中。假设“在实践中”得到满足，也可以想象相应算法的变体可能导致更快的实际实现。

这篇配对论文[22]使用了本文中的一些技术，以及一个新的成分：高斯重采样。这项技术本质上利用了实数的性质，解释了为什么我们只能将其应用于整数乘法。相比之下，本文的技术可以与复数傅立叶变换和数论傅立叶变换结合使用。对于我们的演示，我们更喜欢第二种选择，众所周知，它也适用于实际实现[17]。定理1.2是否可以用一个无条件的界来代替仍然是一个悬而未决的问题。

在续集中，我们将重点从渐近复杂性的纯理论角度进行研究。鉴于过去的经验[17，26，32]，我们算法的变体实际上可能与机器实现相关，但这些方面将暂时搁置一边。

整数乘法。整数乘法的高效方法的发展可以追溯到数学史的开始。复杂的乘法算法在古代文明中就已为人所知，而对接近我们在学校学习的方法的描述则出现在中世纪晚期的欧洲。关于历史参考，我们参考[54，第二节5]和[41，6]。

第一种更有效的整数乘法是在1962年由Karatsuba[34，33]发现的。他的方法也是基于求值插值技术的一系列算法中的第一个。首先将输入的整数分成多段，取其为两个整数多项式的系数。这些多项式在几个精选的点处求值。该算法接下来在每个点递归相乘所获得的整数值。通过将乘积多项式的系数粘贴在一起，最终得到了想要的结果。这种将整数乘法简化为多项式乘法的方法也称为Kronecker分段[27，第2.6节]。

Karatsuba的原始算法将每个输入整数一分为二，然后使用三个评估点。这导致了算法的复杂性。Karatsuba的方法发表后不久，Toom[56]表明，使用更多的评估点可以获得更好的复杂性界限，Schönhage[47]和Knuth[35]进一步改进了这一点。

然后，开发高效的算法来进行所需的大量点集的求值和插值成为一个主要的瓶颈。库利和图基对快速傅立叶变换(FFT)的重新发现提供了克服这一问题的技术工具。对于Gauss[29]来说，FFT基本上已经是已知的，它可以被认为是一种特别有效的评估插值方法，用于特殊的评估点集合。考虑一个有主次单位根的环(详细定义见第2.2节；如果有，则可以取)。则FFT允许仅使用中的环运算在点处求值。如果在中是可逆的，则可以用相同的复杂度进行相应的插值。在给定的情况下，乘积也可以使用环运算来计算。

使用快速傅立叶变换进行整数乘法的想法独立于Pollard[45]和Schönhage-Strassen[49]。要做到这一点，最简单的方法是取AND，同时以有限精度近似元素。乘法本身是递归处理的，通过减少到整数乘法。这种方法与Schönhage和Strassen从[49]中提出的第一个算法相对应，他们表明它对所有人都是及时运行的。波拉德的算法更适合于，其中是形式中的质数。这个域确实包含本原的单位根，这种域上的FFT有时被称为数论FFT。Pollard没有分析他的方法的渐近复杂性，但可以证明，它对文中算法的递归使用导致了与Schönhage-Strassen的第一个算法类似的复杂性界限。

论文[49]还包含第二种方法，该方法可以达到更好的复杂性界限。该算法通常称为Schönhage-Strassen算法。它是这样算出来的，这里是费马数，用来作为中的单位的主次根。速度的提高是因为乘以的幂可以在线性时间内执行，因为它们对应于简单的移位和求反。

在被Fürer的算法[12]取代之前，Schönhage-Strassen算法保持了30多年的冠军地位。简而言之，Fürer设法结合了[49]中的两个算法的优点，以达到某个未指定常数的界(1.1)。在[25，第7节]中，已经证明了Fürer的原始算法的优化版本实现了。在一系列工作[25，18，19，21]中，提出了新的算法，其中，和。从配文[22]来看，我们现在知道了这一点。

从历史上讲，我们还注意到，在对和的最低可能值进行改进之前，往往会以适当的数论假设为模进行改进。在[25，第9节]中，我们证明了在假设存在“足够多的”Mersenne素数的情况下[25，猜想9.1]。当存在足够多的广义Fermat素数时，在[10]模上也得到了相同的结果。在[20]中，我们再次在假设欧拉函数在哪里的情况下得出结论。

多项式乘法。在很大程度上，更有效的多项式乘法算法的开发与整数乘法的进步是齐头并进的。Karatsuba和Toom[34，56]的早期算法，以及Schönhage-Strassen[49]的第二个算法，都是基于在或多或少一般的环上进行多项式乘法的日益有效的代数方法。

更准确地说，设为两个次多项式相乘所需的环运算的个数。对Karatsuba的整数乘法算法的直接改编产生了代数复杂度界限。

随后的方法通常需要温和的假设：由于Toom'；的算法使用了三个以上的评估点，其多项式模拟要求包含足够多的点。同样，Schönhage-Strassen乘法是基于“二进制”FFT的，因此要求在中是可逆的。Schönhage随后开发了他们方法的“三元”模拟，适用于特征为2的域上的多项式乘法[48]。一般(不一定是交换的)环的界是由Cantor和Kaltofen[8]得到的。

现在让我们来看看有限域上多项式乘法的比特复杂度，其中和是素数。使用Kronecker替换法，不难证明。

现在，可以使用Kronecker代换将小次多项式的乘法简化为整数乘法：首先将输入多项式提升为系数为in的整数多项式，然后在上求值。最终可以从这些评估的整数乘积中读出期望的结果。如果，这会让。

另一方面，对于，调整与图灵模型绑定的代数复杂性产生。

其中第一项对应于中的加/减，第二项对应于乘法。请注意，第一个术语在Large中占主导地位。(1.4)和(1.5)的组合也意味着。

在近40年的时间里，界(1.5)保持不败。由于Fürer的算法(类似于[49]的Schönhage-Strassen的第一个算法)本质上依赖于基场中合适的单位根的可用性，所以它不允许有直接的代数类比。特别地，形式为(1.2)的Fürer型边界的存在几年来一直是开放的。这个问题首先在[27]中得到解决，但是使用的算法与Fürer的整数乘法算法非常不同。在适当的数论假设下，在预印本[24]中也显示了人们可以采用的结果，这是随后在没有这些假设的情况下取得的结果[23]。

最后让我们注意到，从更好的乘法算法推导出更好的整数多项式乘法算法通常是例行公事。这些技术在[27，第8.1-8.3节]中有详细介绍。用两次多项式相乘的比特复杂度表示，这里显示了。

整齐划一地进入，并为之服务。利用有限域只包含有限个元素这一事实，在具有有限特征的环的情况下，推导代数复杂度的界也是例行公事。有关更多详细信息，请参阅[27，第8.4和8.5节]。

相关工具。为了证明定理1.1和1.2，我们将使用离散傅立叶变换(DFT)理论中的其他几个工具。首先，给定一个环和一个相互互素的复合整数，中国剩余定理产生同构。

这首先是在[1]中观察到的，我们将相应的转换称为CRT变换。上述同构还允许将长度的单变量DFT简化为长度的多变量DFT。这一观察更古老，是由于好[15]，而且独立于托马斯[55]。

离散傅立叶变换理论的另一个经典工具是Rader约化[46]：环上素数长度的DFT可以简化为计算长度的循环卷积，即环中的乘积。在第4节中，我们还将介绍此缩减的多变量版本。以类似的方式，可以使用Bluestein的线性调频变换[4]来将一般长度的DFT简化为相同长度的循环卷积。虽然FFT乘法是一种将多项式乘法减少到DFT计算的技术，但Bluestein的算法(以及Rader的素数长度算法)可以用于相反方向的缩减。特别地，定理1.2意味着有限域上长度的DFT可以在图灵机上及时计算。

Nussbaumer多项式变换[42，43]构成了我们新结果的另一个重要工具。与[49]中Schönhage-Strassen的第二个算法类似，其思想是在环上使用离散傅立叶变换(DFT)。这个环的性质是单位主根，乘以的幂可以在线性时间内计算。特别地，仅使用加法和减法就可以非常有效地计算长度的DFT。努斯鲍默的重要观察结果是，这种变换对于多维离散傅立叶变换的计算特别有趣(在[49]中，它们只用于单变量离散傅立叶变换)。现在，这些多维DFT的长度应该在每个方向上分开。根据Nussbaumer和Quandalle在[44，p.141]中的建议，可以使用雷达尔缩减和CRT变换来强迫这种情况。

为了证明定理1.1和1.2，我们使用了快速傅立叶变换理论中的一些众所周知的技巧。我们刚刚调查了这些相关工具；更多详细信息在第2、3和4节中提供。请注意，第2节的一部分包含我们从以前的论文[25，27]改编的材料，并包含在其中以方便读者。在第五节中，还将更详细地讨论关于小Linnik常数存在的假设，以及一些结果。在本文中，所有的计算都是在确定性多磁带图灵模型[16]中完成的，并且根据比特复杂度来分析执行时间。附录介绍了使用此模型时数据重排成本的技术详细信息。

整数乘法。我们在第6节证明了定理1.1。我们的新算法的主要思想是将整数乘法归结为在适当形式的代数中计算多元循环卷积

这里是2的幂，是算术级数中的前几个素数，这里是另一个2的幂与。设置时，我们选择这样一种方式，即存在一个主次单位根，这样就可以使用快速傅立叶乘法计算代数中的乘积。关于尺寸，事实证明我们可以采取，尽管更大的尺寸可以允许恒定系数的加速，只要能保持较小。

使用多元Rader变换，所需的离散傅立叶变换实质上归结为代数中多元循环卷积的计算。

通过构造，我们可以因数，这里是一个奇数，由于林尼克常数的假设，它很小。因为，我们注意到它包含一个原始的统一的第th个根。CRT变换允许我们将代数重写为。

现在重要的观察是，这可以被认为是和的统一的“快速”主根。这意味着可以使用具有离散傅立叶变换成为Nussbaumer多项式变换的特殊性质的多元傅立叶乘法来计算乘积。因为是2的幂，所以这些变换可以及时计算。此外，对于足够小的Linnik常数，中的“内乘法”的成本是可以掌握的，因此它只占总成本的很小一部分。

多项式乘法。为了证明定理1.2，我们以类似的方式进行，见第7节和第8节。考虑质数的情况就足够了。在第七节中，我们首先重点介绍了有特色的地面领域。这一次，需要将环替换为合适的扩展字段；特别是，我们定义了。更确切地说，我们取，这确保了和的统一的原始根的存在。

有限域的情况引起了一些额外的技术困难。首先，的元素的位大小指数大于的元素的位大小。这使得用于元素相乘的FFT方法效率不够高。取而代之的是，我们强加了两两互质的额外要求。这允许我们将中的乘法减少为中的单变量乘法，但要以上更强的假设为代价。

第二个技术困难涉及对的定义多项式(即次数上的不可约多项式)以及本原单位根的计算。对于我们选择作为Shoup[51，52]工作的函数，和都可以在线性时间内预先计算。

这种情况最终有其特殊的困难，所以我们在第8节中单独处理。由于不再是可逆的，所以我们不能使用2的幂的DFT长度。在Schönhage[48]之后，我们转而求助于“三进制”FFT，它变成了3的幂。更让人恼火的是，既然是必然的连为，这也意味着我们现在要走了。除了长度和之前的多变量循环卷积之外，这还会导致多变量长度的循环卷积，这需要单独处理。虽然定理1.2在When情形下的证明与When情形非常相似，但上述复杂性导致参数和系数环的选择发生了微妙的变化。因此，为方便读者，我们在第8条复制了第7条的大部分校样，并作了所需的适应化修改。

变种。定理1.1和1.2中的常数和并不是最优的：我们试图使证明尽可能简单。然而，我们的证明确实承认了两个值得强调的性质：

假设存在一个足够接近1的Linnik常数，就足以获得我们的主要复杂性界限。

多元傅立叶变换的维数可以保持有界，不需要随着维数的增加而增加。

有关如何优化可接受的Linnik常量阈值的一些想法，请参阅备注6.1和7.1。

我们的主要算法可以接受几种不同的算法。例如，在第6节中使用近似复数算术而不是模算术应该是相对简单的。由于中的单位原根特别简单，林尼克常数也可能变得稍好一些，但数值误差分析需要额外的注意。利用与[27，第8节]类似的思想，我们的有限域上多项式的乘法算法也可以适用于有限环上的多项式和更一般的正特征有效环。

另一个有趣的问题是，是否存在可能超越现有实现的实际有效的变体。显然，这需要进一步的微调，因为我们证明中的“疯狂”常量并不是由实际应用驱动的。然而，我们的方法结合了几个来自现有算法的想法，这些算法在实践中被证明是有效的。在整数乘法的情况下，这使我们比对于。

.