模幂 [英] Modular Exponentiation
问题描述
在C / C ++如何计算(A ^ B)%M
,其中 B
不适合64位?换句话说,有没有使用计算上述值的方法 B%M
而不是乙
?
In C/C++ how can I calculate (a^b)%m
where b
does not fit into 64 bits? In other words, is there a way of calculating the above value using b%m
instead of b
?
和是否有任何的算法,可以计算在上面的结果O(日志(B))
时间或 O(日志(B%M ))
时间?
And is there any algorithm that can compute the above result in O(log(b))
time or O(log(b%m))
time?
推荐答案
根据欧拉定理,如果 A
和 M
互素:
According to Euler's theorem, if a
and m
are coprime:
A 乙模m = A 乙MOD岛(M)模m
ab mod m = ab mod phi(m) mod m
因此,如果 B
大,则可以使用值 B%岛(M)
而不是 b
。 岛(M)
欧拉函数,它可以如果你知道的因式分解 M
很容易计算。
so if b
is large, you can use the value b % phi(m)
instead of b
. phi(m)
is Euler's totient function, which can be easily calculated if you know the prime factorization of m
.
一旦你以这种方式减少的值b
,使用通过幂平方来计算的模幂 O(日志(b%岛(M)))
。
Once you've reduced the value of b
in this way, use Exponentiation by squaring to compute the modular exponentiation in O(log (b % phi(m)))
.
这篇关于模幂的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!