我們如何計算大的除數和指數的模運算？

Question

實施例：

（30000000^30000000）模40000000 =？

我一直在使用指數的歐拉理論和性質，但仍然無法得到答案 任何人都知道如何通過理論和簡單的計算器來計算？

我的審判是由費馬小定理減少3000的指數，但指數仍然過大的計算器來計算。

Answer 1

您可以使用減半平方法進行功率計算，並在每一步中減少中間結果以給定除數爲模。

您也可以使用負餘得到稍小的中間結果。還需要注意的是，n = 40000000 = 4 * 10^7 = 2^9 * 5^7是一個合數，所以Euler的總體函數給出了phi（n）= 2^8 * 4 * 5^6 = 16 * 10^5 = 160000。現在先減小指數mod phi（n）-1。

最後這個方法只有當你知道除數的分解工作。

Answer 2

# b^e (mod m) 
function powerMod(b, e, m) 
    x := 1 
    while e > 0 
     if e % 2 == 1 
      x := (b * x) % m 
     b := (b * b) % m 
     e := floor(e/2) 
    return x