算法C/C++:用a和d 32或64位整数计算(2 ^ n)%d的最快方法

Question

我正在寻找一种算法,允许我(2^n)%d用n和d 32或64位整数进行计算.

问题是2^n即使使用多精度库也不可能存储在内存中,但是可能存在(2^n)%d仅使用32位或64位整数进行计算的技巧.

非常感谢你.

Answer 1

看一下Modular Exponentiation算法.

这个想法不是为了计算2^n.相反,您d在启动时会多次减少模数.这使数字变小.

与结合方法通过平方幂,并且可以计算(2^n)%d仅O(log(n))步骤.

这是一个小例子: 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