一个简单的算法题

jackyrong

昨天看到一道算法题，是说RSA加密的，大致的原理是，对于给定的三个正整数a,b,c，计算a的b次方除以C的余数。其中1<=a b<c<=32768

可以看到，如果用一般的直接算法，会设计到高精度乘法，十分麻烦，而经过查看数学书，可以看到同余方面有如下的性质，

    （x*y) mod  z=  (x*(y mod z)) mod z
比如 （3*9） mod 2=1
     而  (3*（9 mod 2)) mod 2=1

所以可以编制程序为
 d:=1;

 for i:=1 to b do
  d:=d*a mod c;
writeln(d);

即可解决问题，呵呵，可以看到数学的力量