bigint.cpp

RSA运算的大数库 语法简洁易懂 实用性强

		{
			Z.BI_Length+=len;
			for(i=Z.BI_Length-1;i>=len;i--)Z.BI_Value[i]=Z.BI_Value[i-len];
			for(i=0;i<len;i++)Z.BI_Value[i]=0;
		}
		X.Mov(X.Add(Z));
        Y.Mov(Y.Sub(A.Mul(Z)));
    }
    return X;
}

BigInt BigInt::Div(uint_32 A)
{
    BigInt X;
    X.Mov(*this);
    if(X.BI_Length==1){X.BI_Value[0]=X.BI_Value[0]/A;return X;}
    uint_64 div,mul;
    uint_32 carry=0;
    for(int i=X.BI_Length-1;i>=0;i--)
    {
        div=carry;
        div=(div<<32)+X.BI_Value[i];
        X.BI_Value[i]=(uint_32)(div/A);
        mul=(div/A)*A;
        carry=(uint_32)(div-mul);
    }
    if(X.BI_Value[X.BI_Length-1]==0)X.BI_Length--;
    return X;
}

/****************************************************************************************
大数求模
调用形式：N.Mod(A)
返回值：N%A
****************************************************************************************/
BigInt BigInt::Mod(const BigInt& A)
{
    BigInt X,Y;
	uint_64 div,num;
    uint_32 carry=0;
	usint i,len;
    X.Mov(*this);
    while(X.Cmp(A)>=0)
    {
		div=X.BI_Value[X.BI_Length-1];
		num=A.BI_Value[A.BI_Length-1];
		len=X.BI_Length-A.BI_Length;
		if((div==num)&&(len==0)){X.Mov(X.Sub(A));break;}
		if((div<=num)&&len){len--;div=(div<<32)+X.BI_Value[X.BI_Length-2];}
		div=div/(num+1);
		Y.Mov(div);
		Y.Mov(A.Mul(Y));
		if(len)
		{
			Y.BI_Length+=len;
			for(i=Y.BI_Length-1;i>=len;i--)Y.BI_Value[i]=Y.BI_Value[i-len];
			for(i=0;i<len;i++)Y.BI_Value[i]=0;
		}
        X.Mov(X.Sub(Y));
    }
    return X;
}

uint_32 BigInt::Mod(uint_32 A)
{
    if(BI_Length==1)return(BI_Value[0]%A);
    uint_64 div;
    uint_32 carry=0;
    for(int i=BI_Length-1;i>=0;i--)
    {
        div=BI_Value[i];
		div+=carry*0x100000000;
        carry=(uint_32)(div%A);
    }
    return carry;
}

/****************************************************************************************
从字符串按10进制或16进制格式输入到大数
调用格式：N.Get(str,sys)
返回值：N被赋值为相应大数
sys暂时只能为10或16
****************************************************************************************/
void BigInt::Get(string &str, usint system)
{
    int len=str.length(),k;   //len长度是有限制的，对1024位大数，system为16，即16进制时，长度应不超过256，10进制时不超过308
    Mov(0);
    /*****************
    len长度是有限制的，对1024位大数，system为16，即16进制时，长度应不超过256，10进制时不超过308
    *****************/
    //if(system==16&&len>256) len=256;
    //if(system==10&&len>308) len=308;  //做一个截取，防止过长而出错，如对程序进行扩充，如改变BI_MAXLEN，则此处要相应修改
    
    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 BigInt::Put(string &str, usint system)
{
    if((BI_Length==1)&&(BI_Value[0]==0)){str="0";return;}
	str="";
    string t="0123456789ABCDEF";
    int a;
    string temp;
    BigInt X;
    X.Mov(*this);
    while(X.BI_Value[X.BI_Length-1]>0)
    {
        a=X.Mod(system);
        temp=t.substr(a,1);
        str.insert(0,temp);
        X.Mov(X.Div(system));
    }
}

/****************************************************************************************
求不定方程ax-by=1的最小整数解
调用方式：N.Euc(A)
返回值：X,满足：NX mod A=1
****************************************************************************************/
BigInt BigInt::Euc(const BigInt& A) const
{
	BigInt 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.BI_Length!=1)||(E.BI_Value[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
****************************************************************************************/
BigInt BigInt::RsaTrans(const BigInt& A, const BigInt& B)
{
    BigInt X,Y;
	int i,j,k;
	usint n;
	uint_32 num;
	k=A.BI_Length*32-32;
	num=A.BI_Value[A.BI_Length-1];
	while(num){num=num>>1;k++;}
	X.Mov(*this);
	for(i=k-2;i>=0;i--)
	{
		Y.Mov(X.Mul(X.BI_Value[X.BI_Length-1]));
		Y.Mov(Y.Mod(B));
        for(n=1;n<X.BI_Length;n++)
		{          
			for(j=Y.BI_Length;j>0;j--)Y.BI_Value[j]=Y.BI_Value[j-1];
			Y.BI_Value[0]=0;
			Y.BI_Length++;
			Y.Mov(Y.Add(X.Mul(X.BI_Value[X.BI_Length-n-1])));
			Y.Mov(Y.Mod(B));
		}
		X.Mov(Y);
		if((A.BI_Value[i>>5]>>(i&31))&1)
		{
		    Y.Mov(Mul(X.BI_Value[X.BI_Length-1]));
		    Y.Mov(Y.Mod(B));
            for(n=1;n<X.BI_Length;n++)
			{          
			    for(j=Y.BI_Length;j>0;j--)Y.BI_Value[j]=Y.BI_Value[j-1];
			    Y.BI_Value[0]=0;
			    Y.BI_Length++;
			    Y.Mov(Y.Add(Mul(X.BI_Value[X.BI_Length-n-1])));
			    Y.Mov(Y.Mod(B));
			}
		    X.Mov(Y);
		}
	}
    return X;
}

/****************************************************************************************
拉宾米勒算法测试素数
调用方式：N.Rab()
返回值：若N为素数，返回1，否则返回0
****************************************************************************************/
int BigInt::Rab()
{
    usint i,j,pass;
    for(i=0;i<550;i++){if(Mod(PrimeTable[i])==0)return 0;}
    BigInt S,A,I,K;
    K.Mov(*this);
	K.BI_Value[0]--;
    for(i=0;i<5;i++)
    {
        pass=0;
        A.Mov(rand()*rand());
		S.Mov(K);
        while((S.BI_Value[0]&1)==0)
		{
            for(j=0;j<S.BI_Length;j++)
			{
			    S.BI_Value[j]=S.BI_Value[j]>>1;
			    if(S.BI_Value[j+1]&1)S.BI_Value[j]=S.BI_Value[j]|0x80000000;
			}
		    if(S.BI_Value[S.BI_Length-1]==0)S.BI_Length--;
			I.Mov(A.RsaTrans(S,*this));
			if(I.Cmp(K)==0){pass=1;break;}
		}
		if((I.BI_Length==1)&&(I.BI_Value[0]==1))pass=1;
		if(pass==0)return 0;
	}
    return 1;
}

/****************************************************************************************
产生随机素数
调用方法：N.GetPrime(bits)
返回值：N被赋值为一个bits位（0x100000000进制长度）的素数
****************************************************************************************/
void BigInt::GetPrime(int bits)
{
    usint i;
    BI_Length=bits;
    srand((unsigned)time(0)); 
begin:	
	for(i=0;i<BI_Length;i++)
	{
		BI_Value[i]=rand();
		if(BI_Value[i]&1)         //将最高位置为与最低位相同
			BI_Value[i]=BI_Value[i]|0x80000000;
	}
       BI_Value[0]=BI_Value[0]|1;   //BI_Value[0]最后一位为1，为零则为偶数了，不可能是素数。
	/*for(i=BI_Length-1;i>0;i--)   //大数整体左移一位
	{
		BI_Value[i]=BI_Value[i]<<1;  
		if(BI_Value[i-1]&0x80000000)
			BI_Value[i]++;
	}
	BI_Value[0]=BI_Value[0]<<1;
	BI_Value[0]++;  //最后一位补1，保证是奇数*/
    for(i=0;i<550;i++)
     {
    	if(Mod(PrimeTable[i])==0)
    		goto begin;
     }
    
    BigInt S,A,I,K;//以下为素数测试
    K.Mov(*this);
    K.BI_Value[0]--;
    for(i=0;i<5;i++)
	{
           A.Mov(rand()*rand());
	    S.Mov(K.Div(2));
	    I.Mov(A.RsaTrans(S,*this));
	    if(((I.BI_Length!=1)||(I.BI_Value[0]!=1))&&(I.Cmp(K)!=0))
	    	goto begin;
	}
}