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

发布于:2021-09-22 02:47:37

信息工程大学 实验报告 (2015-2016 学年第一学期)
报告题目: 课程名称: 任课教员: 专 学 姓 业: 号: 名: *方乘算法 密码学 B

二 O 一五年十二月三十一日

一、课程概述
目的:培养学员的编程能力,理解算法原理。 要求:自定义一种乘法,给出*方乘算法的软件实现。

二、设计思路
*方乘算法是实现 输入 输出: 预处理: 求出 比特数 的二进制表示,即 和正整数 ; 的一种快速算法,算法描述如下:

主算法: Step 1 置 ;

Step 2 从 i = m-1 到 i = 0, 依次执行: (1) y← y2; (2)当 ei = 1 时, 执行 Step 3 输出 y. .

三、采取的方案
使用 C 语言进行编程,为简化输入输出语句,调用了 C++的 cin、cout 函数。预处理时加入了 iostream.h 包。 程序支持用户自己定义乘法运算,即模 n 乘法。 用户输入 n 的值后,程序将 n 存在无符号整形变量 MO 中。之后的每 次运算,只需要对 MO 取余数即可,这样可以减小计算结果,简化了计算

的空间复杂度。如果不取模,当计算结果大于 232 时,C 语言就无法存放, 会出现溢出。 算法的目标是计算 符号整形变量中。 之后将 e 转化为二进制数, 通过 ToEr 函数实现。 ToEr 函数采用除以 2, 取余的算法进行十进制数向二进制转化,利用了递归的思想,简化了代码。 计算结果保存在 32 位无符号整形数组 d[32]中。接下来利用上述算法的思 想对*方乘进行运算,通过 Alu 函数实现。结果返回到无符号整形变量 c 中。最后输出结果 c。 ,下一步程序会提示用户输入 x、e,储存在无

四、取得的成果
程序运行实例:计算 9526(mod163):

与 Windows 10 自带的计算器进行结果比对,结果正确。

五、心得体会
通过本次实验,我对*方乘算法有了更加深入的理解,在公钥密码算 法学*的过程中,个人编的小程序也得到了应用。RSA 公钥密码体质的作 业中有很多模 n *方乘的题,我通常是利用自己的程序跑一遍,就得到了 答案。 本程序比较简单,经过教员的指导,一个学时就已经编完。但是没有 实现对大模数的*方乘。模数 n 是储存在一个无符号整形变量中,无符号 整形变量的最大值是 232,如果模数大于这个数,本算法就无能为力。在 真正的 RSA 算法中,我们要选定一个大合数 N,进行模 ?(N )乘法。?(N )虽 然比 N 小,但依然很大,否则不能保证 RSA 的安全性。所以本人的*方乘

算法在应用上有一定的局限性,只能进行小模数的乘法运算。 改进的思路:根据教员在课上讲的,可以使用 unsigned int 数组进行 大数的存放,一个元素存 32 位二进制数。这样两个元素组成的数组就可以 存放 64 位的数,随着数组中元素的增加,数的范围可以达到很大。但是本 人能力有限,之前也没有接触到这方面的知识,如何对一个数组链接成的 大数进行运算,成了一个难点。在之后的学*中,本人会逐渐探索,改进 算法。

六、附录
程序代码: #include <iostream.h>

void ToEr(unsigned int e,unsigned int d[],unsigned int &num) { int a; a = e % 2; num++; // cout<<a<<endl; d[num] = a; e /= 2 ; if (e!=0) ToEr(e,d,num); }

// 变为二进制

unsigned int Alu(unsigned int x,unsigned int d[],unsigned int num,unsigned int MO) //运算 { int a,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; } return c; }

void main() { unsigned int x,e,c,num,MO; unsigned int d[32]; num=0; cout<<"首先需要定义模 n 乘法,请输入 n:"; cin>>MO; cout<<"本程序定义为 mod"<<MO<<"乘法运算。"<<endl; cout<<"y=x^e 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<<"^"<<e<<" mod"<<MO<<" = "<<c<<endl;}


相关推荐

最新更新

猜你喜欢