用模量计算大功率 [英] Calculating Large Powers with Modulus

问题描述

我目前正在研究某些东西，因此我需要计算类似

I am currently working through something whereby I need to calculate the values of something like

(65 ^ 17)mod 3233 = *

(65^17) mod 3233 = *

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

The answer to the above problem is 2790, however because 65 ^ 17 is larger than the values that can be returned by Math.pow it always gives the wrong answer.

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

I have written an implementation using BigIntegers (and the built in modPow), but I want to avoid them if at all possible.

是否有避免使用BigIntegers的替代方法?

Is there an alternative way that avoids the use of BigIntegers?

推荐答案

如果x = y (mod n)和u = v (mod n)然后x.u = y.v (mod n)(其中."表示乘法)

if x = y (mod n) and u = v (mod n) then x.u = y.v (mod n) (where '.' denotes multiplication)

此方法的重复应用用于减少65 ^ 17 mod 3233，

Repeated application of this is used to reduce 65^17 mod 3233,

例如

65 * 65 (mod 3233) = 992

65 * 992 (mod 3233) = 3053

3053 * 65 (mod 3233) = 1232
.
.
.

实际上，我们可以缩短此时间，因为我们已经计算了65^4 (mod 3233) = 1232

In fact we can shorten this because we have calculated 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

这篇关于用模量计算大功率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！