8

作为一个爱好项目，我正在努力寻找非常大的素数。素数测试包含模幂计算，即 a^e mod n。让我们将其称为 modpow 操作以保持解释简单。我想加快这个特定的计算。

目前我正在使用GMP的mpz_pown函数，但是它有点慢。我认为它太慢的原因是因为对 GMP 的 modpow 的函数调用比对相同数量的名为PFGW的软件的全面素性测试要慢。（所以要清楚，这只是 GMP 的 modpow 部分，而不是我正在比较的整个自定义素数测试例程）。PFGW 被认为是该领域中最快的，对于我的用例，它使用Brillhart-Lehmer-Selfridge素数测试——它也使用 modpow 程序——所以 PFGW 在这方面更快并不是因为数学上的聪明（如果我在这里错了，请纠正我）。看起来 GMP 的瓶颈是 modpow 操作。具有超过 20,000 位数字的示例运行时：GMP 的 modpow 操作大约需要 45 秒，而 PFGW 在 9 秒内完成整个素数测试（涉及 modpow）。更大的数字使差异变得更加令人印象深刻。GMP 使用 FFT 乘法和蒙哥马利减少进行此测试比较，请参阅下面这篇文章的评论。

我做了一些研究。到目前为止，我了解到 modpow 算法通过平方、整数乘法和模约简来使用幂 - 这些对我来说听起来很熟悉。几个辅助方法可以提高整数乘法的运行时间：

为了通过平方部分来提高求幂的运行时间，可以使用有符号数字表示来减少乘法的次数（即位表示为 0、1 或 -1，并且位串以这样的方式表示：它包含比原始 base-2 表示更多的零 - 这通过平方减少了求幂的运行时间）。

为了优化运算的模部分，我知道这些方法：

所以这是150,000美元问题：在给定非常大的基数、指数和模数的情况下，是否有可用于有效执行 modpow 操作的软件库？（我的目标是几百万位数）。如果您想建议一个选项，请尝试解释算法的内部工作原理，以数百万位为基数、模数和指数的情况，因为一些库根据位数使用不同的算法。基本上我正在寻找一个支持上述技术（或者可能更聪明的技术）的库，并且它应该在运行算法时表现良好（嗯，至少比 GMP 更好）。到目前为止，我已经搜索、找到并尝试了 GMP 和 PFGW，但没有发现这些令人满意（PFGW 很快，但我只是对 modpow 操作感兴趣，并且没有直接的编程接口）。

编辑：使问题更简洁，因为它被标记得太宽泛。

4

2 回答 2

10

首先，重新。Answer 1 作者的评论“我不使用 GMP，但我怀疑当他们写他们使用 FFT 时，他们真的是指 NTT”——不，当 GMP 说“FFT”时，它表示浮点 FFT。IIRC 他们也有一些 NTT -based 例程，但对于 bignum mul 而言，这些例程与 FFT 没有竞争力。

一个经过良好调整的 FFT-mul 击败任何 NTT 的原因是，由于舍入误差累积而导致的每字精度的轻微损失被现代 CPU 产品的卓越浮点能力所弥补，尤其是考虑到利用 CPU 的矢量数学功能的高性能实现，例如 x86_64 系列，其当前迭代 - Intel Haswell、Broadwell 和 Skylake - 具有海量矢量浮点能力。（我没有在这方面引用 AMD，因为他们的 AVX 产品远远落后于英特尔；他们的高水位线大约是 2002 年，从那时起，英特尔每年都以越来越糟糕的方式击败他们。）原因GMP 在这方面令人失望的是，GMP 的 FFT 相对而言是垃圾。我非常尊重 GMP 编码器，但 FFT 计时是 FFT 计时，你不会因为努力而获得积分，或者例如有一个非常好的 bignum add。这是一篇详细介绍大量 GMP FFT-mul 改进的论文：

Pierrick Gaudry、Alex Kruppa、Paul Zimmerman：“Schönhage-Strassen 的大整数乘法算法的基于 GMP 的实现”[ http://www.loria.fr/~gaudry/publis/issac07.pdf]

这是从 2007 年开始的，但 AFAIK 在下面的片段中指出的性能差距并没有缩小；如果有的话，它已经扩大了。该论文非常适合详细介绍可以部署的各种数学和算法改进，但让我们切入金钱报价：

“一个为整数乘法实现复数浮点 FFT 的程序是 George Woltman 的 Prime95。它主要用于测试大型梅森数 2^p - 1 在 Great Internet Mersenne Prime Search [24] 中的素数。它使用用于乘法 mod a*2^n ± c 的 DWT，a 和 c 不太大，参见 [17]。我们使用我们的将 Prime95 版本 24.14.2 中的乘法模 2^2wn-1 与 n 字整数的乘法进行了比较SSA 在 Pentium 4 的 3.2 GHz 和 Opteron 250 的 2.4 GHz 上实现，见图 4。很明显，Prime95 大大超过了我们的实现，实际上通常在 10 倍以上Pentium 4，在 Opteron 上是 2.5 到 3 倍。”

接下来的几段是大量的面子旋转。（再说一次，我个人认识 3 位作者中的 2 位，他们都是计算数论领域的顶尖人物。）

请注意，上述 George Woltman 的 Prime95 代码在 20 年前首次亮相后不久就发现了所有世界纪录的素数，他的核心 bignum 例程以通用 API 化的形式提供，称为 GWNUM 库。您提到 PFGW 比 FFT-mul 的 GMP 快多少——这是因为 PFGW 使用 GWNUM 进行核心“繁重”算法，这就是 PFGW 中的“GW”的来源。

我自己的 FFT 实现，它具有通用 C 构建支持，但像 George 使用大量 x86 矢量数学汇编器在该 CPU 系列上实现高性能一样，在当前 Intel 处理器系列上比 George 的大约慢 60-70%。我相信这使它成为 x86 上世界上第二快的 bignum-mul 代码。例如，我的代码目前正在使用 30-Mdouble-length FFT（30*2^20 doubles）对大约 2^29 位的数字运行素数测试；因此每个输入字略多于 17 位。使用我的所有四个 3.3 GHz Haswell 4670 四核，每个 modmul 需要大约 90 毫秒。

顺便说一句，许多（如果不是大多数）世界顶级的 bignum-math 编码员都在 mersenneforum.org 上闲逛，我鼓励您查看它并向那里的更广泛（至少在这个特定领域）专家观众提问。我出现在与此处相同的句柄下；George Woltman 饰演“Prime95”，PFGW 的 Mark Rodenkirch 饰演“rogue”。

于 2015-09-25T03:40:41.970 回答
4

我根本不使用GMP，所以请记住这一点。

  1. 我宁愿使用 NTT 而不是 FFT 进行乘法运算

    它消除了舍入误差，并且与优化到同一点的我的FFT实现相比更快

    正如我提到的，我不使用 GMP，但我怀疑当他们写他们使用FFT时，他们真的是指NTT（有限域傅立叶变换）

  2. 你的测试和GMP素数测试的速度差异可能是由modpow调用引起的。

    如果对它的调用过多，则会导致堆/堆栈垃圾，从而大大减慢速度。特别是对于bignums. 尽量避免堆垃圾，因此从操作数中消除尽可能多的数据，并尽可能为频繁调用的函数返回调用。有时也有助于消除瓶颈调用，方法是直接将函数源代码复制到您的代码中，而不是仅使用局部变量的调用（或使用宏）。

    我认为GMP发布了他们的源代码，所以找到他们的实现modpow应该不会太难。你只需要正确使用它

  3. 只是为了清楚

    您正在使用像20000+十进制数字这样的大数字，这意味着~8.4每个数字的千字节。任何返回或非指针操作数都意味着将该数量的数据复制到堆堆栈或从堆堆栈复制。这不仅需要时间，而且通常会使CPU的CACHE无效，这也会降低性能。

    现在将它乘以算法迭代次数，你就得到了这个想法。在调整我的许多功能时遇到了类似的问题，即使使用的算法没有变化，bignum加速也通常超过10000% (倍)。100只是限制/消除堆/堆栈垃圾。

    所以我不认为你需要更好modpow的实现只是更好地使用它但是粗略的我可能是错的但没有你正在使用的代码很难推断出更多。

于 2014-07-22T08:03:46.067 回答