計算通過一些與模

Question

我目前工作的大國，由此我需要計算像

（65^17）模3233的東西值= *

回答上述問題是2790，但是因爲65^17大於Math.pow可以返回的值，它總是給出錯誤的答案。

我已經寫了一個使用BigIntegers（和內置的modPow）的實現，但我想盡可能地避免它們。

是否有避免使用BigIntegers的替代方法？

Answer 1

如果x = y (mod n)和u = v (mod n)然後x.u = y.v (mod n)（其中 '' 表示乘法）

重複的本申請中使用，以減少65^17 MOD 3233，

例如

65 * 65 (mod 3233) = 992 

65 * 992 (mod 3233) = 3053 

3053 * 65 (mod 3233) = 1232 
. 
. 
. 

事實上，我們可以縮短這一點，因爲我們計算65^4 (mod 3233) = 1232

所以，

65^8 (mod 3233) = 1232 * 1232 (mod 3233) = 1547 

65^16 (mod 3233) = 1547 * 1547 = 789 

最後，

65^17 = 789 * 65 (mod 3233) = 2790 

Answer 2

什麼米奇小麥的奇妙簡潔而略帶神祕的答案意思是我s表示這應該工作（僞代碼）：

res = 1 
    for i in 1 to 17: 
     res = (res * 65) mod 3233 

你並不需要使用的BigInteger在所有的這一點，因爲模運算的數學特性的。

FWIW，使用Math.pow()不起作用的原因是它使用浮點運算計算65 。 pow的結果太大，無法精確表示爲double，因此您將丟失一些最低有效位;即數字的「右手邊」上的那些。不幸的是，這些數字很重要，當你採取模數。

---

^{1 - ...如果數學不是你的強技能之一....}