Как в C / C ++ вычислить (a^b)%m, где b не умещается в 64 бита? Другими словами, есть ли способ вычислить указанное выше значение, используя b%m вместо b?
И есть ли какой-либо алгоритм, который может вычислить вышеуказанный результат за O(log(b)) или O(log(b%m)) время?
Согласно теореме Эйлера, если a и m взаимно просты:
ab mod m = ab mod phi(m) mod m
поэтому, если b велико, вы можете использовать значение b % phi(m) вместо b. phi(m) - это общая функция Эйлера, которую можно легко вычислить, если вы знаете разложение m на простые множители. .
После того, как вы уменьшили значение b таким образом, используйте возведение в степень возведением в квадрат для вычисления модульного возведение в степень в O(log (b % phi(m))).
a и m были взаимно простыми.
- person interjay; 13.07.2012
