算法 C/C++：计算 (2^n)%d 的最快方法，其中 n 和 d 是 32 位或 64 位整数。

Question

我正在寻找一种算法，允许我使用32或64位整数计算n和d的(2^n)%d。

问题在于，即使使用多精度库，也无法在内存中存储2^n，但可能存在一种技巧，可以仅使用32或64位整数计算(2^n)%d。

非常感谢。

- Vincent

Answer 1

看一下模指数算法。

其思路是在求幂的过程中，不计算2^n，而是多次对模数d进行取模操作。这种方法可以保证结果较小。

将该方法与平方取幂算法结合起来，就能够只用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

- Mysticial

---

是的，你说得对。考虑到我的背景，我应该更清楚这一点...哈哈 - Mysticial