?? ecdsa.cpp
字號(hào):
TempNum=TempNum-10;
rest2=1;
}
else
rest2=0;
result.AddHead(char(TempNum));
tempa=tempa->Prev;
}
if(rest2)
result.AddHead(char(rest2));
if(temp.Head!=NULL)
{
temp.End=temp.Head;
temp.Head=NULL;
}
tempb=NULL;
}
AdjustBigNum(result);
if (!flag)
{
result.Head->Num=char(int(result.Head->Num)*(-1));
}
return result;
}
/************************************************************************/
/* 將除法轉(zhuǎn)化為減法來(lái)處理,基本思想如下:
div=0;
while(a>=0)
{
a-=b;
div++;
}
div--;
這種方式直接處理效率很低,后來(lái)改進(jìn)為得到商的各位數(shù)字,將除數(shù)擴(kuò)大處理,
速度提高了很多,現(xiàn)在可以對(duì)整數(shù)的整除均可以進(jìn)行
*/
/************************************************************************/
BigInteger BigInteger::operator / (BigInteger BigNum2)//對(duì)/號(hào)進(jìn)行重載
{
BigInteger BigNum1,result(0);
bool flag=true;
BigNum1=*this;
if (int(BigNum1.Head->Num)*int(BigNum2.Head->Num)<0)
{
flag=false;
}
if (int(BigNum1.Head->Num)<0)
{
BigNum1.Head->Num=char(int(BigNum1.Head->Num)*(-1));
}
if (int(BigNum2.Head->Num)<0)
{
BigNum2.Head->Num=char(int(BigNum2.Head->Num)*(-1));
}
int cmp=Compare(BigNum1,BigNum2);
if (cmp==-1)
{
result.AddEnd(0);
}
else if (cmp==0)
{
result.AddEnd(1);
}
else
{
int n,t,i=0,k,sub;//BigNum1,BigNum2的長(zhǎng)度
Node *p1=BigNum1.Head;
Node *p2=BigNum2.Head;
while (p1)
{
n++;
p1=p1->Next;
}
while (p2)
{
t++;
p2=p2->Next;
}
sub=n-t;
BigInteger Bm1,Bm2=BigNum2;
BigInteger temp0(0),temp1(1),expand,temp2,temp3,temp;
/************************************************************************/
/* 對(duì)此情形的整除采用每步獲取商的各位數(shù)字的形式得到,余數(shù)小于0時(shí)退出 */
/************************************************************************/
while((!(Compare(BigNum1,Bm2)==-1)))
{
Bm1=BigNum1;//保存每步的被除數(shù)
expand=temp1;
n=t=0;
p1=BigNum1.Head;
p2=BigNum2.Head;
while (p1)
{
n++;
p1=p1->Next;
}
while (p2)
{
t++;
p2=p2->Next;
}
temp2=Transform(10);
temp3=Transform(n-t-1);
//先將除數(shù)擴(kuò)大10^(n-t-1)倍,商再擴(kuò)大這么多倍即可得到除數(shù)的最高位后添0的數(shù)值
if (n-t-1>0)
{
expand=temp2^temp3;
BigNum2=BigNum2*expand;
}
k=0;
while(int(BigNum1.Head->Num)>=0)
{
BigNum1=BigNum1-BigNum2;
k++;
}
k--;
temp=expand*Transform(k);
result=result+temp;
BigNum1=Bm1-BigNum2*Transform(k);//每步的余數(shù)代替被除數(shù)
BigNum2=Bm2;//恢復(fù)除數(shù)
}
}
AdjustBigNum(result);
if (!flag)
{
result.Head->Num=char(int(result.Head->Num)*(-1));
}
return result;
}
BigInteger BigInteger::operator % (BigInteger BigNum2)//對(duì)%號(hào)進(jìn)行重載
{
BigInteger BigNum1,temp,temp1(-1),result;
BigNum1=*this;
//為負(fù)則化為正處理,'+'只能對(duì)兩個(gè)正整數(shù)有效
while (int(BigNum1.Head->Num)<0)
{
BigNum1=BigNum1*temp1;//轉(zhuǎn)正
BigNum1=BigNum2-BigNum1;
}
temp=BigNum1/BigNum2;
result=BigNum1-(temp*BigNum2);
AdjustBigNum(result);
return result;
}
/************************************************************************/
/*底數(shù)和指數(shù)都是正數(shù),可以按模重復(fù)平方法的思路計(jì)算,只是計(jì)算過(guò)程中不用取余*/
/************************************************************************/
BigInteger BigInteger::operator ^ (BigInteger BigNum2)
{
int count=0;
BigInteger result(1),temp,temp2(2);
BigInteger &BigNum1=*this;
int b[200];
//將BigNum2轉(zhuǎn)換為二進(jìn)制
while(int(BigNum2.Head->Num))
{
temp=BigNum2%temp2;
b[count++]=int(temp.Head->Num);
BigNum2=BigNum2/temp2;
}
//按模重復(fù)平方法計(jì)算
for(int i=count-1;i>=0;i--)
{
result=result*result;
if(b[i])
result=result*BigNum1;
}
return result;
}
BigInteger BigInteger::operator = (BigInteger BigNum)//對(duì)=號(hào)進(jìn)行重載
{
if(this==&BigNum)
return *this;
this->~BigInteger();
Node *p;
TempNode=Head=End=NULL;
p=BigNum.Head;
while(p)
{
AddEnd(p->Num);
p=p->Next;
}
return *this;
}
CString disp(BigInteger BigNum)//輸出鏈表
{
CString str;
char s[2]={'\0','\0'};
Node *p=BigNum.Head;
while(p)
{
str+=itoa(int(p->Num),s,10);
p=p->Next;
}
str+="\r\n";
return str;
}
//a mod n 的逆,存在則返回逆，否則返回0
BigInteger Inv(BigInteger a,BigInteger n)
{
BigInteger b1(0),b2(1),d1(n),d2(a%n),temp,temp0(0);
if (int(a.Head->Num)<0)
{
a=a+n;
}
while (int(d2.Head->Num))
{
temp=b2;
b2=b1-(b2*(d1/d2));
b1=temp;
temp=d2;
d2=d1-((d1/d2)*d2);
d1=temp;
}
while (int(b1.Head->Num)<0)
{
b1.Head->Num=char(int(b1.Head->Num)*(-1));
b1=n-b1;
}
if (d1.Head==d1.End&&int(d1.Head->Num==1))
{
return b1%n;
}
else
return temp0;
}
//大整數(shù)的比較:a>b則返回1,相等返回0,a<b返回-1,只針對(duì)非負(fù)整數(shù)
int Compare(BigInteger BigNum1,BigInteger BigNum2)
{
int result=0;//初始化為相等
Node *temp1,*temp2;
temp1=BigNum1.End;
temp2=BigNum2.End;
while (temp1&&temp2)
{
if (int(temp1->Num)>int(temp2->Num))
{
result=1;
}
if (int(temp1->Num)<int(temp2->Num))
{
result=-1;
}
temp1=temp1->Prev;
temp2=temp2->Prev;
}
if (temp1)
{
result=1;
}
if (temp2)
{
result=-1;
}
return result;
}
//如果BigNum==0返回1，否則返回0
int Compare(BigInteger BigNum)
{
if (int(BigNum.Head->Num))
{
return 0;
}
else
return 1;
}
//隨機(jī)產(chǎn)生一個(gè)n位的大整數(shù)
BigInteger Rand(int n)
{
BigInteger result,temp1(1);
int number;
srand(unsigned(GetTickCount()+seed));
number=rand();//隨機(jī)產(chǎn)生種子
seed=number;
srand(number);//用種子初始化隨機(jī)發(fā)生器
number=1+rand()%9;//產(chǎn)生1-9的數(shù)字作為第一位
result.AddEnd(char(number));
n--;
while (n)
{
number=rand();
srand(number+seed);
number=rand()%10;
result.AddEnd(char(number));
n--;
}
seed=seed/2;
//調(diào)整使最后一位為奇數(shù)，利于后面產(chǎn)生素?cái)?shù)
if(int(result.End->Num)%2==0)
result=result+temp1;
return result;
}
/************************************************************************/
/* 隨機(jī)產(chǎn)生大整數(shù)Bignum以內(nèi)的大整數(shù),即0--BigNum-1之間
方法: 隨機(jī)生成一個(gè)相同位數(shù)的大整數(shù),再求模 */
/************************************************************************/
BigInteger Rand(BigInteger BigNum)
{
Node *p=BigNum.Head;
BigInteger result;
int length=0;//BigNum的位數(shù)
int num;
while (p)
{
length++;
p=p->Next;
}
srand(unsigned(GetTickCount()));
randmize=rand()%1500;//隨機(jī)產(chǎn)生種子
srand(randmize);
for(int i=1;i<=length;i++)
{
srand(randmize);//用種子初始化隨機(jī)發(fā)生器
randmize+=rand()%197;//保證種子不同
num=rand()%10;
result.AddEnd(num);
}
AdjustBigNum(result);
result=result%BigNum;
return result;
}
//將long型變量轉(zhuǎn)化為大整數(shù)BigInteger型
BigInteger Transform(long n)
{
BigInteger result;
int temp;
bool flag;
if (n<0)
{
flag=false;
n=-n;
}
while(n)
{
temp=n%10;//從個(gè)位開(kāi)始依次取各位的數(shù)字
result.AddHead(char(temp));
n=n/10;
}
if (!flag)
{
result.Head->Num=char(int(result.Head->Num)*(-1));//n為負(fù)數(shù)則轉(zhuǎn)化為負(fù)的大整數(shù)
}
return result;
}
//大整數(shù)a^m%n運(yùn)算,用模重復(fù)平方法求解
BigInteger Calculate_exp(BigInteger a,BigInteger m,BigInteger n)
{
int i;
int count=0;
BigInteger d(1),temp,temp2(2);
int b[400];
//計(jì)算m轉(zhuǎn)換為二進(jìn)制
while(int(m.Head->Num))
{
temp=m%temp2;
b[count++]=int(temp.Head->Num);
m=m/temp2;
}
//按模重復(fù)平方法計(jì)算
for(i=count-1;i>=0;i--)
{
d=d*d%n;
if(b[i])
d=d*(a%n)%n;
}
return d;
}
/************************************************************************/
/*素性檢驗(yàn)之前的篩選,即除以100以內(nèi)的小素?cái)?shù) */
/************************************************************************/
bool Select(BigInteger BigNum,int n)
{
int a[]={3,5,7,11,13,17,19,23,29,31,34,37,41,43,47,51,57,59,61,67,71,73,79,83,89,91,97};
if (int(BigNum.End->Num)%2==0)
{
return false;
}
int i=0;
BigInteger temp;
while (i<27&&i<n)
{
temp=Transform(a[i++]);
if (Compare(BigNum%temp))
{
return false;
}
}
return true;
}
/************************************************************************/
/* Rabin_Miller素性檢驗(yàn) */
/************************************************************************/
bool M_Rabin(BigInteger n,int k)
{
BigInteger t,b,r;
long s=0,i=3;
BigInteger nn,temp,temp0(0),temp1(1),temp2(2);
nn=n-temp1;
t=n-temp1;
if (Compare(n,temp2)==0||Compare(n,temp1+temp2)==0)
{
return true;
}
if (Compare(n,temp1)==0||Compare(n,temp2+temp2)==0)
{
return false;
}
temp=nn%temp2;
while (Compare(temp))
{
t=nn/temp2;
nn=nn/temp2;
s++;
temp=nn%temp2;
}
nn=n-temp1;
while (k)
{
b=temp2+Rand(n-temp2-temp2);//隨機(jī)選取2<=b<=n-2
r=Calculate_exp(b,t,n);
if (Compare(r,temp1)&&Compare(r,nn))
{
r=Calculate_exp(r,temp2,n);
i++;
while (Compare(r,nn)&&i<s+2)
{
r=Calculate_exp(r,temp2,n);
i++;
}
if (Compare(r,nn))
{
return false;
}
}
i=3;
k--;
}
return true;
}
//生成m位的偽隨機(jī)大素?cái)?shù)
BigInteger Produce_Prime(int m)
{
BigInteger result=Rand(m),temp2(2);
while (1)
{
if (!Select(result,2*m))
{
result=result+temp2;
}
else
{
if (!M_Rabin(result,5))
{
result=result+temp2;
}
else
return result;
}
}
}
//將一串?dāng)?shù)字轉(zhuǎn)化為大整數(shù)
BigInteger CStringToBignum(CString sub)
{
int length=sub.GetLength();
BigInteger result;
TCHAR c;
int num;
for(int i=0;i<length;i++)
{
c=sub[i];
num=c-'0';
result.AddEnd(num);
}
return result;
}
/////////////////////////////////////////////////////////////////////////////
// CECDSAApp message handlers
?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -