MFIS-Lab2：求解模重复平方计算法
信息安全数学基础
课程实验报告
实验报告（二）
系 别： 网络空间安全系
班 级： secret!
姓 名： secret!
学 号： secret!
实验时间： 2023年10月25日
指导老师： secret!
一、实验内容
编程求解模平方计算法
二、实验目标
理解模平方计算法并会用c++编程求解，进一步改进优化
- 实验原理
- 实验设计
实验共分为主函数和4个自定义函数，
Longlong类型解释：
变量均定义为long long而不是一味的int的原因是，为了解决指数很大的情况，例如老师上课随机举例的日期如20231025等等，进而存放二进制表示的数组也要开大一些
自定义函数解释：
decToBin函数作用是将十进制数转换为二进制数
calcBit函数的作用是计算一个数的二进制位数
printBin函数的作用是打印存储在数组中的二进制数
calMod函数的作用是计算模幂运算
其中最核心的部分是calMod函数，按照模平方算法的思想进行代码实现，并输出时保证计算过程清晰可见
- 定义变量和函数
主函数：
long long类型变量：
指数exponent
底数base
二进制位数bit
模mod
二进制表示数组binary[32]
decToBin函数：
long long类型变量：
除2余数i
除2商j
二进制表示数组的下标k
calcBit函数：
long long类型：
十进制整数n
循环变量最终表示二进制位数i
printBin函数：
long long类型：
循环打印变量且为数组下标i
calcMod函数：
long long类型：
算法中的a不断迭代result
算法中的b不断迭代base
数组下标j
- 主函数
首先声明了变量exponent、base、bit和mod，以及一个存储二进制数的数组binary[]有32位。然后，函数打印欢迎信息和输入提示信息。接下来，函数使用scanf函数从用户输入中读取指数、底数和模数。然后，函数打印指数的二进制表示，并调用calcBit函数计算二进制位数，并调用printBin函数打印存储的二进制数。最后，函数调用calcMod函数进行模幂运算。函数返回0，表示程序正常结束。
- decToBin函数
此函数的作用是将十进制数转换为二进制数。函数参数是一个十进制数n和一个存储二进制数的数组binary[]作为参数。函数使用循环将十进制数n转换为二进制数，并将每一位二进制数存储在数组binary[]中。然后，函数使用循环打印二进制数，并在每4位之间插入一个空格。最后，函数返回0。
- calcBit函数
此函数的作用是计算一个数的二进制位数。函数的参数是十进制整数n。函数使用循环逐渐增加一个变量i的值，直到找到一个i，使得2的i次方大于n。然后，函数返回i。
其实还有一种方法，就是遍历已求得的二进制数组，找到最高位为1对应的数组下标，加1就是二进制位数，不同的是函数传参是binary数组而不是十进制整数n
- printBin函数
此函数的作用是打印存储在数组中的二进制数。函数的参数是存储二进制数的数组binary[]。函数使用循环打印数组中的每一位二进制数，并在每4位之间插入一个空格。最后，函数返回0。
- calMod函数
此函数的作用是计算模幂运算。函数的参数有指数exponent、底数base、模数mod、二进制位数bit和存储二进制数的数组binary[]。函数使用循环根据二进制数的每一位进行模幂运算，并打印每一步的计算过程。最后，函数返回计算结果。
具体的，函数严格模拟了模平方算法整个过程，刚开始令a取1，b取底数；如果二进制当前位为0，那么ai=a(i-1)，否则ai=a(i-1)*bi；bi=b(i-1)^2；直到计算完所有二进制位数，输出a的当前结果就是代求的余数结果
- 实验结果
- 教材2.5.6
计算12996^227(mod37909)
输入：227 12996 37909
输入解释：依次输入指数227、底数12996、模数37909
输出结果解释：
227的二进制表示是1110 0011共8位，倒序存储在数组中（二进制表示的低位对应数组低位），由此可知共循环计算8次，按照模平方算法，最后结果余数为7775。
- 作业2.5教材P89 24
计算3^1000000(mod 7)
输入：
1000000 3 7
输入解释：
依次输入指数1000000、底数3、模数7
输出结果解释：
1000000的二进制表示是1111 0100 0010 0100 0000共20位，倒序存储在数组中（二进制表示的低位对应数组低位），由此可知共循环计算20次，按照模平方算法，最后结果余数为5。
- 随机出题
计算1234^20231025(mod 56789)
输入：
20231025 1234 56789
输入解释：
依次输入指数20231025、底数1234、模数56789
输出结果解释：
20231025的二进制表示是1 0011 0100 1011 0011 0111 0001共25位，倒序存储在数组中（二进制表示的低位对应数组低位），由此可知共循环计算25次，按照模平方算法，最后结果余数为33926。
六、总结
本次实验用c++编程实现了模平方计算方法。自定义了几个辅助函数用于前期的处理准备，将指数十进制转为二进制，由于指数可能较大，所以用一个数组保存二进制的每一位，值得注意的是，需要倒序把放入数组中方便后续的模平方计算。代码严格按照模平方计算过程模拟实现。如果二进制当前位为0，那么ai=a(i-1)，否则ai=a(i-1)*bi；bi=b(i-1)^2；直到计算完所有二进制位数，输出a的当前结果就是代求的余数结果。