算法C/C++：計算最快方式（2^N）與和d 32個或64位的整數

Question

％d

我尋找一個算法，允許我計算(2^n)%d與n和d 32或64位整數。

問題在於，即使使用多精度庫，也不可能將2^n存儲在內存中，但也許存在一種技巧，只能使用32或64位整數來計算(2^n)%d。

非常感謝。

Answer 1

看看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