问题标签 [modular-arithmetic]

作为一个爱好项目，我正在努力寻找非常大的素数。素数测试包含模幂计算，即 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 算法通过平方、整数乘法和模约简来使用幂 - 这些对我来说听起来很熟悉。几个辅助方法可以提高整数乘法的运行时间：

• 蒙哥马利乘法
• FFT 乘法

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

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

• 蒙哥马利还原

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

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

我在一些在线论坛上看到了以下面试问题。对此有什么好的解决方案？

获取5^1234566789893943的最后1000位

这个问题源于我几乎写在这个问题下面的评论，其中 Zack 正在计算大量模数的阶乘（为了这个问题，我们将假设它是素数）。Zack 使用传统的阶乘计算，在每次乘法时取余数。

我几乎评论说要考虑的替代方案是Montgomery multiplication，但仔细想想，我只看到这种技术用于加速同一个被乘数的多次乘法（特别是加快ⁿ mod p 的计算）。

我的问题是：蒙哥马利乘法可以用来加速n的计算！大 n 和 p 的 mod p？

我正在尝试在 Objective C 中实现 NTT（数论变换），但是在线发布的抽象数学文档缺少关键细节。我发现了以下关于 Stack Overflow 的现有问题，该问题声称包括 NTT 的工作（尽管不是最佳）实现： 模块化算法和 NTT（有限域 DFT）优化

我的问题是关于“W”的计算。“p”显然是一个选择的素数。然而，这个实现计算“W=(2^L) mod p”。“L”是一个预定义的常数，等于“0x30000000”，这绝对不是以 2 为底的幂。这与我发现的几个不同的数学摘要直接矛盾，这似乎表明“L”不仅应该是源数组中的元素（因此是基数 2 的幂），但也可以启动！显然我在这里遗漏了一些重要的东西。有人可以解决这个矛盾吗？此处“L”的值是如何选择的？更重要的是，给定一个不同的素数，如何确定“L”的对应值？

我有一个问题，我正在尝试基于 Diffie-Hellman 问题实现服务器和客户端之间的加密协议。

问题是当我尝试((t^RsRc) mod p)^(1/Rc mod q) 它时它没有给我(t^Rs) mod p。

我已经检查过了，即使我正在这样做 ((t^Rc) mod p)^(1/Rc mod q) t.modPow(Rc, p)).modPow(Rc.modInverse(q), p)也没有给我t。

这是我编写的用于计算乘法模逆（模 10^9+7）的 java 程序。但是对于大于 10 的数字，它会给出负数作为输出。无法弄清楚出了什么问题。

我在 Mathematica 中实现了一个算法，它使用 PowerMod 来找到模逆。我现在需要在 C 中实现这个算法，我决定使用 gmp 及其函数mpz_powm，这显然是做同样的事情。问题是，我没有得到相同的值。例如，在 Mathematica 上运行时，它会给出：

而mpz_pwm给出 16。并且：

而mpz_pwm给出 46。（我希望这些是足够的例子。）我还尝试了各种我设法在网上找到的模块化逆算法，它们也给出了不同的值。不过，我怀疑 Mathematica 是对的。有谁知道这里发生了什么？

N最近我阅读了扩展的euclid算法，MOD该算法用于找出一个数的模逆gcd(N,MOD)=1。

但是我对如何找到数字的模逆有疑问 if gcd(N,MOD)!=1？

我想计算组合C(n, k)，其中n和k可能非常大。我试图通过使用模逆来做到这一点，但即使对于小数字，它也没有给出正确的输出。谁能告诉我我错在哪里？

我有一个向量 n 值，如果它被认为具有环形拓扑，我想将它分成 n 组，每组 3 个相邻值。

我想做的是：

所以如果 n = 10 和 i = 1，组应该是 [vector(10); 向量（1）；向量(2)]

在大多数编程语言中，只使用 mod 运算符会非常简单，但是我无法使用 matlab 来解决这个问题，因为它不使用 0 作为向量的初始索引，所以如果 i = 1，那么 mod (i-1) = 0，这是一个非法的索引值。i = n 也是一个问题，因为 mod(n, n) = 0。

我在以下方面制定了一个非常hack-ish的解决方案：

但这很不雅，我觉得应该有更好的方法来做到这一点..

是否有一些运算符允许您对向量索引执行模运算？