java - 用模数计算大幂

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