模幂 [英] 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屋！