用于计算非常非常大的正整数的功率函数的数位模 [英] Digit wise modulo for calculating power function for very very large positive integers

问题描述

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

  P，Q是正整数，数字upto 100000 
  

我想要的结果为

  result =（P ^ Q）modulo（10 ^ 9 + 7）
  

示例：

  P = 34534985349875439875439875349875 
 Q = 93475349759384754395743975349573495 
 Answer = 735851262 
  

我尝试使用诀窍：

 （P ^ Q）modulo（10 ^ 9 + 7）=（P * P * ...（Q次））modulo（10 ^ 9 + 7）
 
 （P modulo（10 ^ 9 + 7））*（P * P * ...（Q次））模））modulo（10 ^ 9 + 7）
  

由于P和Q都很大，

有没有任何有效的方式这样做或一些数字理论算法，我缺少？

提前感谢

解决方案

这是一种相当有效的方法：

1）计算p1 = P modulo 10 ^ 9 + 7

<2>计算q1 = Q modulo 10 ^ 9 + 6

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

Hi I am writing a code to calculate P^Q where

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

I want the result as

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

Example:

P = 34534985349875439875439875349875 
Q = 93475349759384754395743975349573495
Answer = 735851262

I tried using the trick:

 (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)

Since both P and Q are very large, I should store them in an array and do modulo digit by digit.

Is there any efficient way of doing this or some number theory algorithm which I am missing?

Thanks in advance

解决方案

Here is a rather efficient way:

1)Compute p1 = P modulo 10^9 + 7

2)Compute q1 = Q modulo 10^9 + 6

3)Then P^Q modulo 10^9 + 7 is equal to p1^q1 modulo 10^9 + 7. This equality is true because of Fermat's little theorem. Note that p1 and q1 are small enough to fit in 32-bit integer, so you can implement binary exponention with standard integer type(for intermidiate computations, 64-bit integer type is sufficient because initial values fit in 32-bits).

这篇关于用于计算非常非常大的正整数的功率函数的数位模的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！