資訊工程大學
實驗報告
2016學年第一學期報告題目：
課程名稱： 學B
：
專 業：
學 号：
：
一、概述
要求：自定義一種乘法，給出平方乘算法的軟體實作。
二、思路
平方乘算法是實作的一種快速算法，算法描述如下：
輸入和正整數；
輸出:
預處理: 求出比特數的二進制表示，即
主算法:
Step 1 置 ;
Step 2 從i = m-1到i = 0, 依次執行:
(1) y← y2;
(2)當ei = 1時, 執行.
Step 3 輸出 y.
三、采取的方案
使用者輸入n的值後程式将n存在無符号整形變量MO中之後的每次運算隻需要對MO取餘數即可簡化了計算的空間複雜度算法的目标是計算下一步程式會提示使用者輸入xe，儲存在無符号整形變量中
之後将ToEr函數實作結果儲存在32]中。接下來利用上述算法的思想對平方乘進行運算通過Alu函數實作結果傳回到無符号整形變量c中最後輸出結果c四取得的成果
程式運作執行個體計算26(mod163):
與Windows 10 自帶的電腦進行結果比對結果正确
五、心得體會我對算法有了更加深入的了解個人編的小程式也得到了應用作業中有很多模平方乘的題我通常是利用自己的程式跑一遍就得到了答案
本程式比較簡單乘法雖然比N小但依然很大否則不能保證RSA的安全性
改進的思路根據教員在課上講的可以使用unsigned int 數組進行大數的存放一個元素存附錄
#include
void ToEr(unsigned int e,unsigned int d[],unsigned int &num) // 變為二進制
{
int a;
a = e % 2;
num++;
//cout<
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<
cin>>MO;
cout<
cout<
cout<
cin>>x;
cout<
cin>>e;
ToEr(e,d,num);
//cout<
c=Alu(x,d,num,MO);
cout<