用模量计算大功率

Question

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

(65 ^ 17)mod 3233 =*

回答上述问题是2790,但是因为65 ^ 17比可由Math.pow返回的值越大它总是给错误的答案.

我已经使用BigIntegers(以及内置的modPow)编写了一个实现,但是如果可能的话我想避免使用它们.

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

Answer 1

if x = y (mod n) 和u = v (mod n) then 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