計算2^n Mod m的最快方法，其中n和m是隨機整數

Question

當2^n除以m時，如果有任何可能的有效方法找到餘數，那麼我是在徘徊，其中n和m是隨機整數。是否有任何方程式，我將n和m分成餘數，還是必須遵循遞歸方法？ 請注意，我是初學者，我剛剛開始，所以可能不理解太複雜的東西。

在此先感謝。

Answer 1

Fermat's little theorem可以幫助你在情況米是質數：

如果p是一個素數，則對任意整數a，數量a^p − a是p的整數倍。

例如，如果a = 2和p = 7，2^7 = 128和128 − 2 = 7 × 18是7的整數倍。

Answer 2

乘法模運算是這樣的：

（A * B）％X =（（A％×）*（B％X））％×

這裏是C++代碼即：

#include <cstdio> 
#include <cstdlib> 

using namespace std; 

int powmod(int n, int m) { 
    int ret = 1; 
    for(int i = 0; i < n; ++i) 
    ret = ((ret % m) * (2 % m)) % m; // expression from above 
    return ret; // returns 2 to the power n modulo m 
} 

int main() { 

    int n, m; scanf("%d%d", &n, &m); 
    printf("%d\n", powmod(n, m)); 

    return 0; 
}