只需要解决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) 
---->d*((a/d)^m mod (n/d)) *  (d^(m-2) mod (n/d))*d
分成两部分进行计算 
d*((a/d)^m mod (n/d)) 可以用1）解决，因为 a/d和n/d互质。
(d^(m-2) mod (n/d))*d继续递归解决。
粗糙的实现会超时，需要一些细节上的优化

• good (366) frkstyc 2005-12-07 19:11:45