问具有几百万位数的模数和指数的模幂的极快方法

EN

作为一项业余项目，我正在努力寻找真正大的素数。这方面的素数测试包含模指数计算，即a^e mod n。让我们将其称为modpow操作，以使解释保持简单。我想加速这个特别的计算。

目前我正在使用GMP的平头函数，但是它有点慢。我认为它太慢的原因，是因为对GMP的modpow的函数调用比对相同数量的称为PFGW的软件的完整的原始性测试要慢。(所以要明确的是，这只是GMP的modpow部分，而不是我正在比较的整个定制的原始测试例程)。PFGW在它的领域被认为是最快的，对于我的用例，它使用了一个布里哈特-莱默-塞尔弗里奇素数测试--它也使用了modpow过程--所以，PFGW在这方面更快不是因为数学上的聪明(如果我错了，请纠正我)。看来GMP的瓶颈是modpow操作。数字的一个示例运行时有20,000多位数:GMP的modpow操作大约需要45秒，PFGW在9秒内完成整个原始性测试(涉及一个modpow)。与更大的数字相比，两者之间的差别更大。GMP使用FFT乘法和蒙哥马利减少这一测试比较，见下面的评论。

我做了些调查。到目前为止，我知道modpow算法通过平方运算、整数乘法和模缩减来进行幂运算--这些我听起来都很熟悉。几种辅助方法可以改善整数乘法的运行时间：

• 蒙哥马利乘法
• FFT乘法

为了通过平方部分来改善幂运算的运行时间，可以使用有符号的数字表示来减少乘法次数(即位被表示为0、1或-1，而位串以这样的方式表示，使得它包含比它原来的基-2表示多得多的零--这通过平方来减少指数的运行时间)。

为了优化操作的模块化部分，我知道以下方法：

• 蒙哥马利还原

所以这里有一个十五万美元问题:在一个非常大的基数、指数和模数的情况下，是否有一个软件库可以有效地执行modpow操作？(我的目标是数以百万计的数字)如果您想建议一个选项，请尝试解释算法的内部工作情况，以数以百万的数字为基础，模数和指数，因为一些库使用不同的算法基于数字的数目。基本上，我正在寻找一个库，它支持上述技术(或者可能更聪明的技术)，并且在运行算法时应该执行得很好(至少比GMP更好)。到目前为止，我已经搜索、找到并尝试了GMP和PFGW，但是没有发现这些令人满意的东西(PFGW是快速的，但我只是对modpow操作感兴趣，并且没有直接的编程接口)。我希望这一领域的专家能够建议一个具有这些功能的库，因为似乎很少有人能够处理这些需求。

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