模重复平方解题过程

问：求5^16（mod113）,用模重复平方或平方乘方法，求大神给出解答过程

1. 答：5^16（mod113）=5*125^5（mod113）≡5*12^5（mod113）=60*144^2（mod113）
   ≡60*31^2（mod113）=60*961（mod113）=60*57（mod113）=3420（mod113）
   ≡30（mod113）

问：C语言 一个数学程序求解释

1. 答：x[32]也是存放结果的。
   模重复平方法求的是a^m%n
   当m=13，即二进制的 1101 = 1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0时，最终结果
   ans =a^m % n
   = a^(1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0) %n
   = [a^(1 * 2^3)] * [a^(1 * 2^2)] * [(a ^ (0 * 2^1)] * [a ^ (1 * 2^0)] % n
   也就是说，从低到高，在第 i 位的时候，将a^(bin[i] * 2^i) %n 乘到结果中即可。这里可以稍微变换一下：仅当bin[i] == 1的时候，将a^(2^i) % n乘进去即可。所以这里可以用一个辅助的变量 b 来保存 a^(2^i) % n，在每次迭代的过程中 b = b^2 % n 。
2. 答：将m转换为二进制输出 调用函数to_binary()实现
   第二个计算a的n次方

问：模重复平方法怎么计算的？那个b1≡b^2(modm)怎么算的？

1. 答：MOD用法及意义是：a≡b(modc)的意思是a和b除以c后余数相同读作a与b同余，mod为c例如：amodb=c说明:a除以b余数为c。再比如说2的100次方的个位是什么，可写成2^100≡6。（mod10）特别是进制，用“mod”来代表几进制。modn读作“模n”