用模量计算大功率 [英] 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屋!