C语言实现平方乘算法实验报告

1、信息工程大学实验报告（2015-2016学年第一学期）报告题目： 平方乘算法 课程名称： 密码学B 任课教员： 专 业： 学 号： 姓 名： 二O一五年十二月三十一日一、课程概述目的：培养学员的编程能力，理解算法原理。要求：自定义一种乘法，给出平方乘算法的软件实现。二、设计思路平方乘算法是实现y=xe的一种快速算法，算法描述如下：输入:  x和正整数e；输出: y=xe预处理: 求出m比特数e的二进制表示，即em-1,em-2,e0且满足e=i=0mei2i主算法: Step 1 置 y = 1; Step 2 从i = m-1到i = 0, 依次执行: （1） y y2;

2、 （2）当ei = 1时, 执行yy×x. Step 3 输出 y.三、采取的方案使用C语言进行编程，为简化输入输出语句，调用了C+的cin、cout函数。预处理时加入了iostream.h包。程序支持用户自己定义乘法运算，即模n乘法。用户输入n的值后，程序将n存在无符号整形变量MO中。之后的每次运算，只需要对MO取余数即可，这样可以减小计算结果，简化了计算的空间复杂度。如果不取模，当计算结果大于232时，C语言就无法存放，会出现溢出。算法的目标是计算y=xe，下一步程序会提示用户输入x、e，储存在无符号整形变量中。之后将e转化为二进制数，通过ToEr函数实现。ToEr函数采用除以2

3、，取余的算法进行十进制数向二进制转化，利用了递归的思想，简化了代码。计算结果保存在32位无符号整形数组d32中。接下来利用上述算法的思想对平方乘进行运算，通过Alu函数实现。结果返回到无符号整形变量c中。最后输出结果c。四、取得的成果程序运行实例：计算9526（mod163）:与Windows 10 自带的计算器进行结果比对，结果正确。五、心得体会通过本次实验，我对平方乘算法有了更加深入的理解，在公钥密码算法学习的过程中，个人编的小程序也得到了应用。RSA公钥密码体质的作业中有很多模n平方乘的题，我通常是利用自己的程序跑一遍，就得到了答案。本程序比较简单，经过教员的指导，一个学时就已经编完。但

4、是没有实现对大模数的平方乘。模数n是储存在一个无符号整形变量中，无符号整形变量的最大值是232，如果模数大于这个数，本算法就无能为力。在真正的RSA算法中，我们要选定一个大合数N，进行模乘法。虽然比N小，但依然很大，否则不能保证RSA的安全性。所以本人的平方乘算法在应用上有一定的局限性，只能进行小模数的乘法运算。改进的思路：根据教员在课上讲的，可以使用unsigned int 数组进行大数的存放，一个元素存32位二进制数。这样两个元素组成的数组就可以存放64位的数，随着数组中元素的增加，数的范围可以达到很大。但是本人能力有限，之前也没有接触到这方面的知识，如何对一个数组链接成的大数进行运算，成

5、了一个难点。在之后的学习中，本人会逐渐探索，改进算法。六、附录程序代码：#include <iostream.h>void ToEr(unsigned int e,unsigned int d,unsigned int &num) / 变为二进制int a;a = e % 2;num+;/cout<<a<<endl;dnum = a;e /= 2 ;if (e!=0) ToEr(e,d,num);unsigned int Alu(unsigned int x,unsigned int d,unsigned int num,unsigned int M

6、O) /运算int a,b,c,i; b = x;c = 1;for(i=1;i<=num;i+)a=di;if(a=1) c *= b;c %= MO; b = b*b%MO;return c;void main()unsigned int x,e,c,num,MO;unsigned int d32;num=0;cout<<"首先需要定义模n乘法，请输入n："cin>>MO;cout<<"本程序定义为mod"<<MO<<"乘法运算。"<<endl; cout<<"y=xe mod"<<MO<<endl; cout<<"请输入x：" cin>>x;cout<<"请输入e："cin>>e;ToEr(e,d,num);/cout<<num<<endl; c=Alu(x,d,num,MO);cout<<"结果为y = "<<x&