tor*_*edo 3 python modulo exponentiation modular-arithmetic
我的代码的瓶颈是对非常大的整数重复调用 pow(base,exponent,modulus)（numpy 不支持这么大的整数，大约 100 到 256 位）。但是，我的指数和模数始终相同。我可以以某种方式利用它来通过自定义函数加速计算吗？我尝试定义一个函数，如下所示（下面的函数用于一般模数和指数）。
然而，即使我在没有 while 循环和 if 语句的情况下对固定指数和模数的每个操作进行硬编码，它也比 pow 慢。
def modular_pow(self, base, exponent, modulus):
result = 1
base = base % modulus
while exponent > 0:
if (exponent % 2 == 1):
result = (result * base) % modulus
exponent = exponent >> 1
base = (base * base) % modulus
return result
另一种选择是如果我能以某种方式“矢量化”它。我必须计算大约 100000000 个不同基值的 pow。虽然这些值在我的脚本运行之间经常发生变化（因此查找表没有用），但我在运行时就会知道这些值（我可以立即计算它们）。
有任何想法吗？我通过使用 gmpy2 中的 mpz 数据类型获得了一些加速，但它仍然太慢。
好消息，坏消息。好消息是，当模数m固定时，就有办法加快计算速度a*b % m。搜索“巴雷特还原”和“蒙哥马利还原”。它们以不同的方式工作，通过预先计算与m此类相关的常量，这些常量% m可以通过乘法和移位来计算，而不需要除法。
坏消息：要找到余数，两种方法都需要（除了更便宜的运算之外）两次乘法。因此，除非乘法比除法便宜得多，否则他们不会总体支付费用。
\n因此，除非模数“真正”很大，否则它们通常会较慢 - 按照现代标准，“大约 100 到 256 位”仍然偏小，仅比本机 64 位机器整数宽几倍。像快速基于 FFT 的乘法之类的事情需要更大的整数才能得到回报。
\nCPython 的内置模块化 pow 已经在使用“二进制”方案，与您在 Python 中编码的内容类似，但更奇特（如果指数“足够大”，内置 pow 会将其视为在以 32 为底，每次循环迭代消耗 5 个指数位）。
\n在Python中快速实现蒙哥马利约简，并用蒙哥马利拼写替换代码中的模乘法，在modular_pow()模数增长到数万位之前，并没有比内置的更快。对于 256 位左右的输入，速度大约慢 3 倍。
这是一个混合包：Python 代码没有利用“base 32”技巧，这可以带来实质性的好处。但对于足够大的输入，CPython 使用比 na\xc3\xafve 更快的 Karatsuba 乘法，无除法 Montgomery 拼写可以从中受益（无论输入大小如何，CPython 的 int 除法都没有加速技巧，而 CPython' s 的内置模块化 pow 始终使用除法来求余数）。
\n所以，短期来说：据我所知，在 CPython 中没有任何明显的方法可以加快单个pow(a, b, c). 可能某些 C 编码的加密库有合适的东西，但我不知道。
但另一个好消息是你的问题是“令人尴尬的并行”。如果您有 N 个处理器，您可以为每个处理器提供 100000000/N 的输入，并且它们都可以全速并行运行。这将带来大约 N 倍的加速。
\n但坏消息是你的整数实际上并不“大”（它们足够小，我敢打赌你仍然可以使用内置 pow 每秒计算数千个模块化 pow），并且进程间通信成本可能会消失并行进行 N 次计算的好处。这完全取决于您如何获取输入以及您想要如何处理结果。
\n《应用密码学手册》(HAC)第 14 章本质上阐述了 gonzo 模幂算法的最新技术。
\n查看代码，GMP 已经实现了他们拥有的所有技巧。这包括我提到的内容（蒙哥马利约简，以及使用高于 2 的 2 次方基数来在每次循环迭代中消耗更多的指数位）。还有其他我没有提到的（例如，GMP 有一个特殊的内部平方例程，它比可能不等整数的一般乘积节省了周期）。总而言之，这是一座小山般的实现代码。
\n我想这就是为什么你没有得到更多答案的原因：在最坏的情况下，GMP 已经接近任何人曾经想出的最好方法了。对您而言，加速并不是真正引人注目，因为如前所述，您使用的整数实际上很小。
\n因此，如果您需要实现这一目标，那么使用 GMP 可能是最快的方法。如前所述，多处理是使用 N 个处理器获得理论 N 倍加速的明显方法，但也如前所述，您没有提及任何有关上下文的内容（这些输入来自何处或您需要对输出执行什么操作） 。因此，无法猜测这是否会给您带来回报。您需要的进程间通信越多，对潜在的多处理加速的损害就越大。
\n注意：您所做的正是 RSA 公钥密码系统所做的，尽管它们通常使用更大的整数。也就是说，你的“基数”就是他们的“消息”，而公共（或私有）RSA 密钥由固定指数和固定模数组成。只有基础（消息或加密位）在加密/解密实例中有所不同。对于给定的密钥，指数和模数始终相同。
\n许多世界级的数学家都研究了这个问题，世界级的黑客对算法进行了编码以达到最高速度。这就是为什么你应该放弃希望，因为 HAC 忘记提及有一种更快的方法;-)
\n与 RSA 的联系提醒我：RSA 解密在实践中并不是以“显而易见”的方式进行的。相反，私钥的持有者知道密钥模数的素因数分解（在 RSA 中，模数是两个不同但保密的大素数的乘积），并且可以使用它来显着加快求幂速度尊重该模数。
\n因此（无法猜测），如果您获取模实例的方式使得您可以有效地计算它们的素因式分解，那么当它们复合时，可以使用它来获得显着的加速。
\n不过，对于素数模而言，情况就不那么重要了。那么，唯一具有高度潜在价值的技巧是，对于p质数a且不能被整除p，
pow(a, b, p) == pow(a, b % (p-1), p)\n如果可以b远大于p。它之所以有效，是因为根据费马小定理，
pow(a, p-1, p) == 1\n对于p素数且不a能被整除p。例如，
pow(a, b, p) == pow(a, b % (p-1), p)\n对于复合模量，对其每个主要功率因数执行大致相同的操作，然后通过中国剩余定理将结果粘贴在一起。
\n如果您认为您的问题可以利用这一点来解决，请搜索“模幂中国余数”以找到许多好的说明。
\n