C语言实现平方乘算法实验报告Word下载.doc
《C语言实现平方乘算法实验报告Word下载.doc》由会员分享，可在线阅读，更多相关《C语言实现平方乘算法实验报告Word下载.doc（6页珍藏版）》请在冰点文库上搜索。
二O一五年十二月三十一日
一、课程概述
目的：
培养学员的编程能力，理解算法原理。
要求：
自定义一种乘法，给出平方乘算法的软件实现。
二、设计思路
平方乘算法是实现的一种快速算法，算法描述如下：
输入和正整数；
输出:
预处理:
求出比特数的二进制表示，即
主算法:
Step1置;
Step2从i=m-1到i=0,依次执行:
（1）y←y2;
（2）当ei=1时,执行.
Step3输出y.
三、采取的方案
使用C语言进行编程，为简化输入输出语句，调用了C++的cin、cout函数。
预处理时加入了iostream.h包。
程序支持用户自己定义乘法运算，即模n乘法。
用户输入n的值后，程序将n存在无符号整形变量MO中。
之后的每次运算，只需要对MO取余数即可，这样可以减小计算结果，简化了计算的空间复杂度。
如果不取模，当计算结果大于232时，C语言就无法存放，会出现溢出。
算法的目标是计算，下一步程序会提示用户输入x、e，储存在无符号整形变量中。
之后将e转化为二进制数，通过ToEr函数实现。
ToEr函数采用除以2，取余的算法进行十进制数向二进制转化，利用了递归的思想，简化了代码。
计算结果保存在32位无符号整形数组d[32]中。
接下来利用上述算法的思想对平方乘进行运算，通过Alu函数实现。
结果返回到无符号整形变量c中。
最后输出结果c。
四、取得的成果
程序运行实例：
计算9526（mod163）:
与Windows10自带的计算器进行结果比对，结果正确。
五、心得体会
通过本次实验，我对平方乘算法有了更加深入的理解，在公钥密码算法学习的过程中，个人编的小程序也得到了应用。
RSA公钥密码体质的作业中有很多模n平方乘的题，我通常是利用自己的程序跑一遍，就得到了答案。
本程序比较简单，经过教员的指导，一个学时就已经编完。
但是没有实现对大模数的平方乘。
模数n是储存在一个无符号整形变量中，无符号整形变量的最大值是232，如果模数大于这个数，本算法就无能为力。
在真正的RSA算法中，我们要选定一个大合数N，进行模乘法。
虽然比N小，但依然很大，否则不能保证RSA的安全性。
所以本人的平方乘算法在应用上有一定的局限性，只能进行小模数的乘法运算。
改进的思路：
根据教员在课上讲的，可以使用unsignedint数组进行大数的存放，一个元素存32位二进制数。
这样两个元素组成的数组就可以存放64位的数，随着数组中元素的增加，数的范围可以达到很大。
但是本人能力有限，之前也没有接触到这方面的知识，如何对一个数组链接成的大数进行运算，成了一个难点。
在之后的学习中，本人会逐渐探索，改进算法。
六、附录
程序代码：
#include<
iostream.h>
voidToEr（unsignedinte,unsignedintd[],unsignedint&
num）//变为二进制
{
inta;
a=e%2;
num++;
// cout<
<
a<
endl;
d[num]=a;
e/=2;
if（e!
=0）ToEr（e,d,num）;
}
unsignedintAlu（unsignedintx,unsignedintd[],unsignedintnum,unsignedintMO）//运算
inta,b,c,i;
b=x;
c=1;
for（i=1;
i<
=num;
i++）
{
a=d[i];
if（a==1）{c*=b;
c%=MO;
b=b*b%MO;
}
returnc;
voidmain（）
unsignedintx,e,c,num,MO;
unsignedintd[32];
num=0;
cout<
"
首先需要定义模n乘法，请输入n：
;
cin>
>
MO;
本程序定义为mod"
MO<
乘法运算。
cout<
y=x^emod"
请输入x：
cin>
x;
请输入e：
e;
ToEr（e,d,num）;
num<
c=Alu（x,d,num,MO）;
结果为y="
x<
^"
e<
mod"
="
c<
升级会员 