计算通过一些与模

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 - ...如果数学不是你的强技能之一....}