java - 用模数计算大幂

Question

我目前正在处理一些事情，我需要计算类似的值

(65^17) 模 3233 = *

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

我已经使用 BigIntegers（和内置的 modPow）编写了一个实现，但我想尽可能避免使用它们。

有没有替代方法可以避免使用 BigIntegers？

Answer 1

ifx = 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

Answer 2

Mitch Wheat 非常简洁但有点神秘的¹答案意味着这应该可以工作（伪代码）：

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

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

FWIW， usingMath.pow()不起作用的原因是它使用浮点算法计算 65 ^{17 。}的结果pow太大而无法精确表示为 a double，因此您会丢失一些最低有效数字；即数字“右手端”的那些。不幸的是，当您取模时，这些数字很重要。

---

^{1 - ...如果数学不是你更强的技能之一......}