?? bigint.cpp
字號:
for(i=Z.m_nLength-1;i>=len;i--)
Z.m_ulValue[i]=Z.m_ulValue[i-len];
for(i=0;i<len;i++)
Z.m_ulValue[i]=0;
}
X.Mov(X.Add(Z));
Y.Mov(Y.Sub(A.Mul(Z)));
}
return X;
}
CBigInt CBigInt::Div(unsigned long A)
{
CBigInt X;
X.Mov(*this);
if(X.m_nLength==1)
{
X.m_ulValue[0]=X.m_ulValue[0]/A;
return X;
}
unsigned __int64 div,mul;
unsigned long carry=0;
for(int i=X.m_nLength-1;i>=0;i--)
{
div=carry;
div=(div<<32)+X.m_ulValue[i];
X.m_ulValue[i]=(unsigned long)(div/A);
mul=(div/A)*A;
carry=(unsigned long)(div-mul);
}
if(X.m_ulValue[X.m_nLength-1]==0)
X.m_nLength--;
return X;
}
/****************************************************************************************
大數求模
調用形式：N.Mod(A)
返回值：N%A
思想：與大數除法相同的算法，只是返回的不是商而是余數
****************************************************************************************/
CBigInt CBigInt::Mod(CBigInt& A)
{
CBigInt X,Y;
unsigned __int64 div,num;
unsigned long carry=0;
unsigned i,len;
X.Mov(*this);
while(X.Cmp(A)>=0)
{
div=X.m_ulValue[X.m_nLength-1];
num=A.m_ulValue[A.m_nLength-1];
len=X.m_nLength-A.m_nLength;
if((div==num)&&(len==0))
{
X.Mov(X.Sub(A));
break;
}
if((div<=num)&&len)
{
len--;
div=(div<<32)+X.m_ulValue[X.m_nLength-2];
}
div=div/(num+1);
Y.Mov(div);
Y.Mov(A.Mul(Y));
if(len)
{
Y.m_nLength+=len;
for(i=Y.m_nLength-1;i>=len;i--)Y.m_ulValue[i]=Y.m_ulValue[i-len];
for(i=0;i<len;i++)Y.m_ulValue[i]=0;
}
X.Mov(X.Sub(Y));
}
return X;
}
unsigned long CBigInt::Mod(unsigned long A)
{
if(m_nLength==1)return(m_ulValue[0]%A);
unsigned __int64 div;
unsigned long carry=0;
for(int i=m_nLength-1;i>=0;i--)
{
div=m_ulValue[i];
div+=carry*0x100000000;
carry=(unsigned long)(div%A);
}
return carry;
}
/****************************************************************************************
從字符串按10進制或16進制格式輸入到大數
調用格式：N.Get(str,sys)
返回值：N被賦值為相應大數
sys暫時只能為10或16
****************************************************************************************/
void CBigInt::Get(CString& str, unsigned int system)
{
int len=str.GetLength(),k;
Mov(0);
for(int i=0;i<len;i++)
{
Mov(Mul(system));
if((str[i]>='0')&&(str[i]<='9'))k=str[i]-48;
else if((str[i]>='A')&&(str[i]<='F'))k=str[i]-55;
else if((str[i]>='a')&&(str[i]<='f'))k=str[i]-87;
else k=0;
Mov(Add(k));
}
}
/****************************************************************************************
將大數按10進制或16進制格式輸出為字符串
調用格式：N.Put(str,sys)
返回值：無，參數str被賦值為N的sys進制字符串
sys暫時只能為10或16
****************************************************************************************/
void CBigInt::Put(CString& str, unsigned int system)
{
if((m_nLength==1)&&(m_ulValue[0]==0)){str="0";return;}
str="";
CString t="0123456789ABCDEF";
int a;
char ch;
CBigInt X;
X.Mov(*this);
while(X.m_ulValue[X.m_nLength-1]>0)
{
a=X.Mod(system);
ch=t[a];
str.Insert(0,ch);
X.Mov(X.Div(system));
}
}
/****************************************************************************************
求不定方程ax-by=1的最小整數解
調用方式：N.Euc(A)
返回值：X,滿足：NX mod A=1
****************************************************************************************/
CBigInt CBigInt::Euc(CBigInt& A)
{
CBigInt M,E,X,Y,I,J;
int x,y;
M.Mov(A);
E.Mov(*this);
X.Mov(0);
Y.Mov(1);
x=y=1;
while((E.m_nLength!=1)||(E.m_ulValue[0]!=0))
{
I.Mov(M.Div(E));
J.Mov(M.Mod(E));
M.Mov(E);
E.Mov(J);
J.Mov(Y);
Y.Mov(Y.Mul(I));
if(x==y)
{
if(X.Cmp(Y)>=0)
Y.Mov(X.Sub(Y));
else
{
Y.Mov(Y.Sub(X));
y=0;
}
}
else
{
Y.Mov(X.Add(Y));
x=1-x;
y=1-y;
}
X.Mov(J);
}
if(x==0)
X.Mov(A.Sub(X));
return X;
}
/****************************************************************************************
求乘方的模
調用方式：N.RsaTrans(A,B)
返回值：X=N^A MOD B
****************************************************************************************/
CBigInt CBigInt::RsaTrans(CBigInt& A, CBigInt& B)
{
CBigInt X,Y;
int i,j,k;
unsigned n;
unsigned long num;
k=A.m_nLength*32-32;
num=A.m_ulValue[A.m_nLength-1];
while(num){num=num>>1;k++;}
X.Mov(*this);
for(i=k-2;i>=0;i--)
{
Y.Mov(X.Mul(X.m_ulValue[X.m_nLength-1]));
Y.Mov(Y.Mod(B));
for(n=1;n<X.m_nLength;n++)
{
for(j=Y.m_nLength;j>0;j--)Y.m_ulValue[j]=Y.m_ulValue[j-1];
Y.m_ulValue[0]=0;
Y.m_nLength++;
Y.Mov(Y.Add(X.Mul(X.m_ulValue[X.m_nLength-n-1])));
Y.Mov(Y.Mod(B));
}
X.Mov(Y);
if((A.m_ulValue[i>>5]>>(i&31))&1)
{
Y.Mov(Mul(X.m_ulValue[X.m_nLength-1]));
Y.Mov(Y.Mod(B));
for(n=1;n<X.m_nLength;n++)
{
for(j=Y.m_nLength;j>0;j--)Y.m_ulValue[j]=Y.m_ulValue[j-1];
Y.m_ulValue[0]=0;
Y.m_nLength++;
Y.Mov(Y.Add(Mul(X.m_ulValue[X.m_nLength-n-1])));
Y.Mov(Y.Mod(B));
}
X.Mov(Y);
}
}
return X;
}
/****************************************************************************************
拉賓米勒算法測試素數
調用方式：N.Rab()
返回值：若N為素數，返回1，否則返回0
****************************************************************************************/
int CBigInt::Rab()
{
unsigned i,j,pass;
for(i=0;i<550;i++){if(Mod(PrimeTable[i])==0)return 0;}
CBigInt S,A,I,K;
K.Mov(*this);
K.m_ulValue[0]--;
for(i=0;i<5;i++)
{
pass=0;
A.Mov(rand()*rand());
S.Mov(K);
while((S.m_ulValue[0]&1)==0)
{
for(j=0;j<S.m_nLength;j++)
{
S.m_ulValue[j]=S.m_ulValue[j]>>1;
if(S.m_ulValue[j+1]&1)
S.m_ulValue[j]=S.m_ulValue[j]|0x80000000;
}
if(S.m_ulValue[S.m_nLength-1]==0)
S.m_nLength--;
I.Mov(A.RsaTrans(S,*this));
if(I.Cmp(K)==0)
{
pass=1;
break;
}
}
if((I.m_nLength==1)&&(I.m_ulValue[0]==1))
pass=1;
if(pass==0)
return 0;
}
return 1;
}
/****************************************************************************************
產生隨機素數
調用方法：N.GetPrime(bits)
返回值：N被賦值為一個bits位（0x100000000進制長度）的素數
****************************************************************************************/
void CBigInt::GetPrime(int bits)
{
unsigned i;
m_nLength=bits;
begin:
for(i=0;i<m_nLength;i++)m_ulValue[i]=rand()*0x10000+rand();
m_ulValue[0]=m_ulValue[0]|1;
for(i=m_nLength-1;i>0;i--)
{
m_ulValue[i]=m_ulValue[i]<<1;
if(m_ulValue[i-1]&0x80000000)m_ulValue[i]++;
}
m_ulValue[0]=m_ulValue[0]<<1;
m_ulValue[0]++;
for(i=0;i<550;i++){if(Mod(PrimeTable[i])==0)goto begin;}
CBigInt S,A,I,K;
K.Mov(*this);
K.m_ulValue[0]--;
for(i=0;i<5;i++)
{
A.Mov(rand()*rand());
S.Mov(K.Div(2));
I.Mov(A.RsaTrans(S,*this));
if(((I.m_nLength!=1)||(I.m_ulValue[0]!=1))&&(I.Cmp(K)!=0))goto begin;
}
}?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -