使用Modulus计算大幂

Question

我目前正在处理一些事情，因此我需要计算如下内容的值

(65^17) mod 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