用模量计算大功率

我目前正在研究一些我需要计算类似值的东西

（65 ^ 17）mod 3233 = *

上述问题的答案是2790，但是因为65 ^ 17大于Math.pow可以返回的值，所以它总是给出错误的答案。

我已经使用BigIntegers（以及内置的modPow）编写了一个实现，但是如果可能的话我想避免使用它们。

有没有其他方法可以避免使用BigIntegers？

如果x = y (mod n)且u = v (mod n)则xu = yv (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

什么米奇小麦的简洁但有点神秘的¹答案意味着这应该工作（伪代码）：

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

由于模运算的数学属性，您根本不需要使用BigInteger。

FWIW，使用Math.pow()不起作用的原因是它使用浮点运算来计算65 ¹⁷ 。 pow的结果太大而不能精确地表示为double ，所以你会丢失一些最不重要的数字; 即数字“右手端”的那些。不幸的是，当你取模数时，这些数字很重要。

^{1 – ……如果数学不是你更强大的技能之一……}