我正在寻找一种算法，允许我使用 n 和 d 32 或 64 位整数计算 (2^n)%d>.
问题是即使使用多精度库也不可能将 2^n 存储在内存中，但也许存在计算 (2^n)%d 的技巧仅使用 32 位或 64 位整数。
非常感谢。
最佳答案
看看 Modular Exponentiation algorithm .
这个想法不是计算2^n。相反，您可以在加电时多次降低模数 d。 That keeps the number small.
将方法与Exponentiation by Squaring结合起来，并且您可以仅在 O(log(n)) 步内计算 (2^n)%d。
这是一个小例子:2^130 % 123 = 40
2^1 % 123 = 2
2^2 % 123 = 2^2 % 123 = 4
2^4 % 123 = 4^2 % 123 = 16
2^8 % 123 = 16^2 % 123 = 10
2^16 % 123 = 10^2 % 123 = 100
2^32 % 123 = 100^2 % 123 = 37
2^65 % 123 = 37^2 * 2 % 123 = 32
2^130 % 123 = 32^2 % 123 = 40
关于c++ - 算法 C/C++ : Fastest way to compute (2^n)%d with a n and d 32 or 64 bit integers，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8963686/