HNU信息安全数学基础实验二

一、实验内容

编程实现：模重复平方法（非伪码）。

二、实验目标

1. 理解模重复平方方法的算法原理及其应用场景。

2. 编写代码实现该算法，并能够正确处理大数幂次运算中的模运算。

3. 通过实验验证算法的正确性和效率，并能分析其在不同输入条件下的表现。

4. 培养编程解决问题的能力，巩固信息安全数学基础知识。

三、实验原理

模重复平方计算法定义：

设𝑛和𝑚是整数，计算𝑏𝑛(mod 𝑚)

将𝑛写成二进制形式：

其中𝑛𝑖∈{0,1}，𝑖=0,1,…,𝑘−1，

则𝑏𝑛(mod 𝑚)的计算可以归纳为：

这个计算方法叫做“模重复平方计算法”。

模重复平方计算法计算𝑏𝑛(mod 𝑚)最多作2⌊log2𝑛⌋+1次乘法和2⌊log2𝑛⌋+1次模运算。

四、实验设计

题目： 编程实现模重复平方法。

本题的编程思路依赖于课堂上所学的模重复平方法的步骤，即如下图所示：

基本思路：通过指数的二进制表示来逐位处理每一位。对于每个二次项的系数，如果系数ni为1，则将当前的幂次值bi乘到最终结果中；如果系数ni不为1，则当前结果ai等于上一轮结果ai-1。每处理一位后，幂次值将被平方并取模，以适应下一位的处理。

接下来，进行编程实现，代码如下：

#include <iostream>
#include <vector>
using namespace std;// 计算b^n % m的模幂函数
long long modExp(long long base,long long exp,long long mod){long long result=1; // 初始结果为1long long power=base; // 初始的幂次为base// 遍历指数的二进制表示while(exp>0){if(exp%2==1) {// 如果当前位是1，将当前幂次乘入结果result=(result*power)%mod;}// 更新幂次值(平方)并取模power=(power*power)%mod;// 处理下一位exp/=2;}return result;
}int main() {long long base,exp,mod;// 读取输入cout<<"请输入底数 (b): ";cin>>base;cout<<"请输入指数 (n): ";cin>>exp;cout<<"请输入模数 (m): ";cin>>mod;// 计算b^n % m的结果long long result=modExp(base,exp,mod);// 输出结果cout<<base<<"^"<<exp<<"mod"<<mod<<"="<<result<<endl;return 0;
}

代码中，首先定义底数base，指数exp和模数mod，获取输入后，使用函数modExp(base,exp,mod)来计算(b^n)%m的结果。

（代码中的变量都定义为long long类型，为了防止出现数据过大导致的溢出。）

代码的核心就是函数modExp()，我们用课堂上的一个例子来解释一下它的具体流程。

在这个例子中，我们要求12996227(mod 37909)的值。

// 计算b^n % m的模幂函数
long long modExp(long long base,long long exp,long long mod){long long result=1; // 初始结果为1long long power=base; // 初始的幂次为base// 遍历指数的二进制表示while(exp>0){if(exp%2==1) {// 如果当前位是1，将当前幂次乘入结果result=(result*power)%mod;}// 更新幂次值(平方)并取模power=(power*power)%mod;// 处理下一位exp/=2;}return result;
}

我们来看函数modExp()的具体实现。首先，定义结果变量result=1，即我们实例中的“令a=1”，然后定义初始幂次为base即实例中的b=12996。

接下来，由于指数227=1+2+25+26+27，此时它是>0的，因此先将它模2的结果与1比较。显然，227%2=1，说明20这一项前面的系数为1，因此，将当前幂次b乘入当前结果a并取余，得到新一轮结果a0。然后，更新当前幂次值b，将其平方后取模，即得到了新的幂次b1。

在第一次计算新结果和新幂次结束后，将指数227除以2，即二进制表达式变成了0+1+24+25+26即113=1+24+25+26，此时它仍>0，因此先将它模2的结果与1比较。113%2=1，从全局来看，这说明21这一项前面的系数为1，因此，将当前幂次b1乘入当前结果a0并取余，得到新一轮结果a1。然后，更新当前幂次值b1，将其平方后取模，即得到了新的幂次b2。

在第二次计算新结果和新幂次结束后，将指数113除以2，即二进制表达式变成了0+23+24+25即56=23+24+25，此时它仍>0，因此先将它模2的结果与1比较。56%2=0，从全局来看，这说明22这一项前面的系数为0，因此，新一轮结果a2就等于前一轮结果a1。然后，更新当前幂次值b2，将其平方后取模，即得到了新的幂次b3。

在第三次计算新结果和新幂次结束后，将指数56除以2，即二进制表达式变成了22+23+24即28=22+23+24，此时它仍>0，因此先将它模2的结果与1比较。28%2=0，从全局来看，这说明23这一项前面的系数为0，因此，新一轮结果a3就等于前一轮结果a2。然后，更新当前幂次值b3，将其平方后取模，即得到了新的幂次b4。

在第四次计算新结果和新幂次结束后，将指数28除以2，即二进制表达式变成了21+22+23即14=21+22+23，此时它仍>0，因此先将它模2的结果与1比较。14%2=0，从全局来看，这说明24这一项前面的系数为0，因此，新一轮结果a4就等于前一轮结果a3。然后，更新当前幂次值b4，将其平方后取模，即得到了新的幂次b5。

在第五次计算新结果和新幂次结束后，将指数14除以2，即二进制表达式变成了1+21+22即7=1+21+22，此时它仍>0，因此先将它模2的结果与1比较。7%2=1，从全局来看，这说明25这一项前面的系数为1，因此，将当前幂次b5乘入当前结果a4并取余，得到新一轮结果a5。然后，更新当前幂次值b5，将其平方后取模，即得到了新的幂次b6。

在第六次计算新结果和新幂次结束后，将指数7除以2，即二进制表达式变成了0+1+21即3=1+21，此时它仍>0，因此先将它模2的结果与1比较。3%2=1，从全局来看，这说明26这一项前面的系数为1，因此，将当前幂次b6乘入当前结果a5并取余，得到新一轮结果a6。然后，更新当前幂次值b6，将其平方后取模，即得到了新的幂次b7。

在第七次计算新结果和新幂次结束后，将指数3除以2，即二进制表达式变成了0+1即1=1，此时它仍>0，因此先将它模2的结果与1比较。1%2=1，从全局来看，这说明27这一项前面的系数为1，因此，将当前幂次b7乘入当前结果a6并取余，得到新一轮结果a7。

此轮处理结束后，将指数1除以2，得到0，这时回到while循环检查exp>0条件不满足，从而跳出循环，返回最终result值即a7，这就是我们要的答案。

以上过程与课堂实例过程一致，代码完全正确。