c++ - 用于计算非常大的正整数的幂函数的数字模数

Question

您好，我正在编写代码来计算 P^Q，其中

P, Q are positive integers which can have number of digits upto 100000

我想要的结果是

result = (P^Q)modulo(10^9+7)

例子:

P = 34534985349875439875439875349875 
Q = 93475349759384754395743975349573495
Answer = 735851262

我尝试使用这个技巧:

 (P^Q)modulo(10^9+7) = (P*P*...(Q times))modulo(10^9+7)

 (P*P*...(Q times))modulo(10^9+7) = ((Pmodulo(10^9+7))*(Pmodulo(10^9+7))...(Q times))modulo(10^9+7)

由于 P 和 Q 都非常大，我应该将它们存储在一个数组中并逐位取模。

是否有任何有效的方法来执行此操作或我缺少的一些数论算法？

提前致谢

Answer 1

这是一个相当有效的方法:

1)计算 p1 = P 模 10^9 + 7

2)计算 q1 = Q 模 10^9 + 6

3) 那么 P^Q 模 10^9 + 7 等于 p1^q1 模 10^9 + 7。这个等式是真的，因为费马小定理。请注意，p1 和 q1 足够小以适合 32 位整数，因此您可以使用标准整数类型实现二进制指数(对于中间计算，64 位整数类型就足够了，因为初始值适合 32 位)。