sab*_*ari 2 c exponentiation modulus
在C/C++我怎样才能计算(a^b)%m其中b不适合64位？换句话说,有没有办法用b%m而不是b？来计算上述值.
(a^b)%m
b
b%m
是否有任何算法可以在O(log(b))时间或O(log(b%m))时间计算上述结果？
O(log(b))
O(log(b%m))
int*_*jay 8
根据欧拉定理,如果a并且m是互质的:
a
m
ab mod m = ab mod phi(m) mod m
所以如果b很大,你可以使用值b % phi(m)而不是b.phi(m)是欧拉的函数,如果你知道的是素数因子分解,可以很容易地计算出它m.
b % phi(m)
phi(m)
一旦你b以这种方式减小了值,就可以通过平方来计算模幂运算O(log (b % phi(m))).
O(log (b % phi(m)))
归档时间：
13 年，5 月 前
查看次数：
1439 次
最近记录：