bigint.cpp

计算机信息的保密显得越来越重要。数据保密变换

    {
        M = Zero;
        Spls = A;
        return true;
    }

    static BigInt Out,Mod;
 
	Out = Mod = Zero;
    InitMulCache(B);
    for(int i=A.len-1,f,h,t,m; i>=0; )
    {
        if( !GetDivNext(Mod,A,B,i) )
            break;
        //用二分法找商
        h=1; t=BI_BASE-1;
        while( h<=t )
        {
            m = (h+t) >> 1;
            f = Cmp(MulCache[m],Mod);
            if( !f )
                break;
            if( f>0 )
                t = m-1;
            else
                h = m+1;
        }
        Out.bit[i+1] = f ? --h : m;

        if(f)
            Sub(Mod,Mod,MulCache[h]);
        else 
            Mod = Zero;
     }
    
    SetLen( Out,A.len-B.len);
	Spls = Mod;
	M = Out;

    return true;
}
/******************************************************************************/
//  名称：Add
//  功能：大数加法 ( C = A + B )
//  参数：
//	返回：成功返回true，否则返回false
/***************************************************************************/
bool CBigInt::Add(BigInt &C,BigInt &A,BigInt &B)
{
    static BigInt Out,*pa,*pb;

    if( A.len > B.len )
		pa=&A,pb=&B;
	else
		pa=&B,pb=&A;

	Out = *pa;

	for(UINT i=0,carry=0,j=pb->len,tmp; i<j; ++i)
    {
        tmp = pa->bit[i] + pb->bit[i] + carry;
        if( tmp > BI_BASE-1 )
        {
            tmp -= BI_BASE;
            carry = 1;
        }
        else
        {
            carry = 0;
        }
        Out.bit[i] = tmp;
    }

	if(carry)
    {
        while( Out.bit[i] == BI_BASE-1 )
        {
            Out.bit[i] = 0;
            CHECK( ++i < BI_MAXLEN );
        }
        CHECK( i < BI_MAXLEN );
        ++Out.bit[i];
        if( i == pa->len )
            ++Out.len;
    }

    C = Out;

	return true;
}
/******************************************************************************/
//	名称：Sub
//	功能：大数减法 ( C = A - B )
//  参数：
//	返回：成功返回true，否则返回false
//  备注：调用前保证A >= B，否则结果不对
/******************************************************************************/
bool CBigInt::Sub(BigInt &C,BigInt &A,const BigInt &B)
{
	if( &C != &A )
		C = A;

    for(int i=0,carry=0,j=B.len,tmp; i<j; ++i)
    {
        tmp = A.bit[i] - B.bit[i] - carry;
        if( tmp<0 )
        {
            tmp += BI_BASE;
            carry = 1;
        }
        else
		{
            carry = 0;
		}
        C.bit[i] = tmp;
    }
    
    if(carry)
    {
        while( !C.bit[i] )
        {
            C.bit[i] = BI_BASE-1;
            CHECK( ++i < BI_MAXLEN );
        }
        CHECK( i < BI_MAXLEN );
        --C.bit[i];
    }

	SetLen(C,C.len-1);

	return true;
}
/******************************************************************************/
//	名称：InitMulCache
//	功能：初始化乘法缓存 ( MulCache[i] = In*i )
//  参数：
//	返回：成功返回true，否则返回false
/******************************************************************************/
bool CBigInt::InitMulCache(BigInt &In)
{
    MulCache[1] = In;

	for(int i=2; i<BI_BASE; ++i)
	{
		CHECK( Add(MulCache[i],MulCache[i-1],In) )
	}

	return true;
}
/******************************************************************************/
//  名称：SetLen
//  功能：设置大数的长度
//  参数：
//	返回：
/***************************************************************************/
void CBigInt::SetLen(BigInt &BI,UINT start)
{
	for( int i=start; i>=0 && !BI.bit[i]; --i );

    BI.len = i+1;
}
/******************************************************************************/
//	名称：ShR
//	功能：大数逻辑右移
//  参数：
//	返回：成功返回true，否则返回false
/******************************************************************************/
bool CBigInt::ShR(BigInt &Out,BigInt &In,UINT len)
{
    CHECK( (In.len+len) <= BI_MAXLEN )
    
    if( !len )
	{
		if( &Out != &In )
			Out = In;
	}
    else if( In.len )
    {
        static BigInt Tmp;
		Tmp = Zero;
        memcpy(Tmp.bit+len,In.bit,In.len);
        Tmp.len = In.len + len;
		Out = Tmp;
    }

	return true;
}
/******************************************************************************/
//	名称：Cmp
//	功能：大数比较
//  参数：
//	返回：A>B 返回 1; A=B 返回 0; A<B 返回 -1
/******************************************************************************/
int CBigInt::Cmp(const BigInt &A,const BigInt &B)
{
    int i=A.len;

	if( (UINT)i > B.len )
	    return 1;
	if( (UINT)i < B.len )
	    return -1;

    for(--i; i>=0; --i)
    {
        if( A.bit[i] > B.bit[i] )
            return 1;
        if( A.bit[i] < B.bit[i] )
            return -1;
    }

    return 0;
}
/******************************************************************************/
//	名称：New
//	功能：产生一个大数
//  参数：
//	返回：
/******************************************************************************/
BigInt CBigInt::New(long n)
{
    int i=0;
    BigInt Out;

    memset(Out.bit,0,BI_MAXLEN);
    while(n)
    {
        Out.bit[i++] = n%BI_BASE;
        n /= BI_BASE;
    }
    Out.len = i;
    
    return Out;
}
/******************************************************************************/
//	名称：GetVal
//	功能：获取大数的值
//  参数：
//	返回：
/******************************************************************************/
long CBigInt::GetVal(const BigInt &In)
{
    CHECK( In.len )
    
    long n=0;

    for(int i=In.len-1; i>=0; --i)
    {
        n *= BI_BASE;
        n += In.bit[i];
    }

    return n;
}
/******************************************************************************/
//	名称：SetVal
//	功能：设置大数的值
//  参数：
//	返回：
/******************************************************************************/
void CBigInt::SetVal(BigInt &BI,long n)
{
    int i=0;

    BI = Zero;
    while(n)
    {
        BI.bit[i++] = n%BI_BASE;
        n /= BI_BASE;
    }
    BI.len = i;
}
/******************************************************************************/
//	名称：BuildBIFromByte
//	功能：由输入字节组构造一个大数
//  参数：
//	返回：构造成功返回true，否则返回false
/******************************************************************************/
bool CBigInt::BuildBIFromByte(BigInt &Out,const char *In,UINT len)
{
	CHECK( In && len<=BI_MAXLEN/4 )

    Out = Zero;
	CGfL::ByteToHalfByte(Out.bit,In,len);
    SetLen(Out,len<<1);

	return true;
}
/******************************************************************************/
//	名称：BuildBIFromHalfByte
//	功能：由输入半字节组构造一个大数
//  参数：
//	返回：构造成功返回true，否则返回false
/******************************************************************************/
bool CBigInt::BuildBIFromHalfByte(BigInt &Out,const char *In,UINT len)
{
	CHECK( In && len<=BI_MAXLEN/2 )

    Out = Zero;
	memcpy(Out.bit,In,len);
    SetLen(Out,len);

	return true;
}
/******************************************************************************/
//	名称：BuildBIFromStr
//	功能：由输入字符串构造一个大数
//  参数：len—字符串长度
//	返回：构造成功返回true，否则返回false
/******************************************************************************/
bool CBigInt::BuildBIFromStr(BigInt &Out,char *In,UINT len)
{
	CHECK( In && len<=BI_MAXLEN/2 )

    Out = Zero;
	CGfL::StrToHalfByte( Out.bit,In,len);
    SetLen(Out,len);

	return true;
}
/******************************************************************************/
//	名称：Rand
//	功能：产生随机大数
//  参数：len—随机大数的长度
//	返回：产生成功返回true，否则返回false
/******************************************************************************/
bool CBigInt::RandVal(BigInt &Out,UINT len)
{
    CHECK( len>0 && len<=BI_MAXLEN )

	Out = Zero;
    srand(GetTickCount());
    for(UINT i=0; i<len; ++i)
	{
        Out.bit[i] = rand()%BI_BASE;
	}

    Out.bit[0] |= 1;
    Out.bit[len-1] |= 1;
	Out.len = len;

	return true;
}
///////////////////////////////////////////////////////////////////////////////
// End of Files
///////////////////////////////////////////////////////////////////////////////