只需要解决a^m mod n怎么计算，m非常大。
1）如果d=gcd(a,n)等于1，那么由欧拉定理得到原式等于a^(m mod Euler(n)) mod n
Euler()是欧拉函数；
2）d不等于1,那么原式等于((a/d)^m*d*d^(m-1)) mod n
---> ((a/d)^m*d  mod n ) * ( d^(m-1) mod n)  mod n )
分成两部分进行计算 d*((a/d)^m mod (n/d)) 可以用1）解决，因为 a/d和n/d互质。
d^(m-1) mod n  = (d^(m-2) mod (n/d))*d继续递归解决。
粗糙的实现会超时，需要一些细节上的优化。

 

• Re:终于找到正确方法了. (346) zhucheng 2005-12-07 17:31:18
  • good (366) frkstyc 2005-12-07 19:11:45
• 请教:这一步该如何证明呢?? d^(m-1) mod n = (d^(m-2) mod (n/d))*d (47) CowXX 2009-05-27 20:21:41