bigncal.cpp

大的整数运算

#include"stdafx.h"
#include"stdio.h"
#include"bigncal.h"
void BN_Reset(BNum *pbn)
{
	SWord i;

	for(i=0; i<2*WordPerBNum; i++)
		pbn->Data[i] = 0;
}

/*=====================================================================
     function:        out put the result
======================================================================*/
void BN_Print(BNum *pbn)
{
	SWord i;
	
	for(i = 2*WordPerBNum-1; i>=0; i--)
		printf("%08x ",pbn->Data[i]);
}

/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	function:	get bit length of BNum
	input:		pbn
	output:		bitlen
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/

SWord BN_GetBitlen(BNum *pbn)
{
	SWord i,j,k;	
	i = WordPerBNum-1;

	while(pbn->Data[i]==0)		
              i--;
	j = MSBOfWord;
	k=0;

	while(!(pbn->Data[i]&j))	
	{
		j=j >> 1;
		k++;
	}

	return WordLEN*(i+1) - k;	
}

/*=============================================
           funtion: get the first address of 
		   the large number
==============================================*/
SWord BN_GetAddr(BNum *pbn)
{
	SWord i = WordLEN-1;
	while(i>0)
	{
		if(pbn->Data[i]==0)
		    i--;
		else 
			return i;
	}
	return 0;
}

/*==============================================
	大整数加赋值
	pbnto=bn+bn2
===========================================*/
void BN_AddTo(BNum *pbn, BNum *pbn2, BNum *pbnto)
{

	SWord	i;
	DWord	carry=0;
	
	for(i=0; i<WordPerBNum; i++) 
	{
		carry = (DWord) pbn->Data[i] + (DWord) pbn2->Data[i] + carry;
		pbnto->Data[i] = (Word) carry;
	         carry = carry>>WordLEN;
	}
	
	pbnto->Data[i] = (Word) carry;
}
/********************************************************
                      大整数相乘
           re = bn1*bn2
           WordPerBNum = 16
*******************************************************/
void BN_Multiply(BNum *bn1,BNum *bn2,BNum *re)
{
	DWord temp;       //两数相乘的结果
	DWord  r0 = 0,r1 = 0,r2 = 0;   //暂时记录中间结果
	DWord  high = 0,low = 0;   //中间的结果高32位与低32位,即每次结果没有变化时的位
	SWord t,k = 0,i,j;
	t = WordPerBNum;
    SWord record1 = 0,record2 = 0;         //记录进位

	for(k = 0;k<=2*(t-1);k++)
	{
		for(i = 0;i<t&&i<=k;i++)
			for(j = 0;j<t&&(i+j)<=k;j++)
			{
				if((i+j) == k)
				{
					temp = ((DWord)bn1->Data[i])*((DWord)bn2->Data[j]);
					low = (Word)temp;
					high = temp>>WordLEN;
					(DWord)r0 = (DWord)r0+low;
					record1 = r0>>WordLEN;
					r0 = (Word)r0;
					(DWord)r1 = high+r1+record1;///////////////////////
					record2 = r1>>WordLEN;	
					r1 = (Word)r1;
					(DWord)r2 = r2+record2;
					r2 = (Word)r2;
				}
			}
			re->Data[k] = (Word)r0;
			r0 = r1;
			r1 = r2;
			r2 = 0;
			high = 0;
			low = 0;
	}
	re->Data[k] = (Word)r0;
}

/*==========================================================================
大整数相减，输入: bn1,bn2
            输出：bn_to
==========================================================================*/
BNum *BN_SubCore(BNum *bn1,BNum *bn2,BNum *bn_to)  //bn1是一个比bn2的数字
{
   for(int i = 0;i<2*WordPerBNum;i++)
		bn_to->Data[i] = 0;
	SWord length = BN_GetAddr(bn1);      //最高的位数所在的数组值
    DWord carry = 0;
	int temp = 0;
	for(int j = 0;j<=length;j++)
	{
		temp = (Word)bn1->Data[j]-(Word)bn2->Data[j]-carry;
		if((bn1->Data[j]<bn2->Data[j])||(bn1->Data[j]==bn2->Data[j])&&carry==1)
		{
			bn_to->Data[j] = (Word)(temp+0x100000000);
			carry = 1;
		}
		else
		{
			bn_to->Data[j] = (Word)temp;
			carry = 0;
		}
	}
	return bn_to;
}

int BN_ComPare(BNum *p1,BNum *p2)   //p1与p2比较，如果大于，返回2,= 返回1，小于返回0
{
	SWord length1,length2;
	length1 = BN_GetBitlen(p1);
	length2 = BN_GetBitlen(p2);
	if(length1>length2)
		return 2;
	else
		if(length1<length2)
			return 0;
		else 
		{
		    int	m = length1/WordLEN;
			for(int i = m;i>=0;i--)
			{
                if(p1->Data[i]>p2->Data[i])
				   return 2;
				else 
					if(p1->Data[i]<p2->Data[i])
					    return 0;
			}
			return 1;
		}
}

void BN_Sub(BNum *bn1,BNum *bn2,BNum *bn_to)
{
/*	SWord length1,length2;
	length1 = BN_GetBitlen(bn1);
	length2 = BN_GetBitlen(bn2);
	if(length1>length2)
		bn_to = BN_SubCore(bn1,bn2,bn_to);
	else
		if(length1<length2)
			bn_to = BN_SubCore(bn2,bn1,bn_to);
		else 
		{
		    int	m = length1/WordLEN;
			int i;
			for(i = m;i>=0;i--)
			{
                if(bn1->Data[i]>bn2->Data[i])
				{
					bn_to = BN_SubCore(bn1,bn2,bn_to);
					return;
				}
				else 
					if(bn1->Data[i]<bn2->Data[i])
					{
					bn_to = BN_SubCore(bn2,bn1,bn_to);
					return;
					}
			}
			if(i == -1)
				cout<<"the two number is equal!!!"<<endl;
		}*/
	int i = 0;
    i = BN_ComPare(bn1,bn2);
	if(i ==2)
	{
		bn_to = BN_SubCore(bn1,bn2,bn_to);
		return; 
	}
	else
		if(i==1)
		{
           bn_to = BN_SubCore(bn1,bn2,bn_to);
		   return;
		}
		else
		{
			bn_to = BN_SubCore(bn2,bn1,bn_to);
			return;
		}

}

void BN_MoveLeft(BNum *pbn)     //*2
{
	int i = 0,j = 0;
	int k = BN_GetAddr(pbn);
	__int64 temp[WordLEN] = {0};
	Word high = 0,low = 0;
	Word record = 0;        //记录相加后的进位
	while(j<=k)
	{
		temp[j] = (__int64)(pbn->Data[j]);
		j++;
	}
	i = k;
	while(i>=0)
	{
		temp[i] = temp[i]<<1;
		high =(Word)(temp[i]>>WordLEN);
		pbn->Data[i+1] = high+pbn->Data[i+1];
		pbn->Data[i] = (Word)(temp[i]);
     	i--;
	}
}

void BN_MoveRight(BNum *pbn)  //右移 = div2  前面先左移动31位
{
   int k = BN_GetAddr(pbn);
   Word temp = 0;
   int i = 0;
   while(i<=k)
   {
	   temp = pbn->Data[i+1]<<(WordLEN-1);
	   pbn->Data[i] = (pbn->Data[i]>>1)+temp;
	   i++;
   }
}

/*===========================================================
          赋值函数，将p1中的值传递给p2
============================================================*/
void BN_Pass(BNum *p1,BNum *p2)
{
	int i;
	for(i = 0;i<WordLEN;i++)
		p2->Data[i] = p1->Data[i];
}
/*===========================================================
            大数除法remind记录余数 result记录商
============================================================*/
void BN_Devide(BNum *p1,BNum *p2,BNum *rem,BNum *result)
{
	int i = BN_ComPare(p1,p2);
	if(i==0)
	{
		BN_Reset(result);
        BN_Pass(p1,rem);
		return;
	}
	else 
		if(i==1)
		{
           	BN_Reset(result);
			result->Data[0] = 0x1;
            BN_Reset(rem);
		}
		else
		{
			BN_Reset(result);
			BN_Pass(p1,rem);
			BNum *m,*s;
			BNum *tmp1,*tmp2;
			m = new BNum;
			s = new BNum;
			tmp1 = new BNum;
			tmp2 = new BNum;

			BN_Reset(tmp1);
			BN_Reset(tmp2);
			BN_Reset(m);
			BN_Reset(s);
			BN_Pass(p2,m);
			s->Data[0] = 0x1;         //初始化工作
			int temp = BN_ComPare(rem,m);
			while(temp==2)
			{
				BN_MoveLeft(m);
				BN_MoveLeft(s);
				temp = BN_ComPare(rem,m);
			}
			temp = BN_ComPare(rem,p2);
			int temp2 = BN_ComPare(rem,m);
			while(temp!=0)
			{
                temp2 = BN_ComPare(rem,m);
				while(temp2==0)
				{
					BN_MoveRight(m);
					BN_MoveRight(s);
					temp2 = BN_ComPare(rem,m);
				}
				BN_Sub(rem,m,tmp1);
				BN_Pass(tmp1,rem);
				BN_AddTo(result, s, tmp2);
				BN_Pass(tmp2,result);
				temp = BN_ComPare(rem,p2);
			}
		}
		
}

          /*获取e中得二进制得值*/
    /* 注意最开始时要取得e得位数*/
void BN_Transform(BNum *e,int eb[1024])
{
	int i;
	for(i = 0;i<1024;i++)
		eb[i] = 0;
	int k = BN_GetBitlen(e);
	Word tmp = 0x1;
	for(i = 0;i<k;i++)
	{
		eb[i] = e->Data[0]&tmp;
        BN_MoveRight(e);
	}
}
//eb中得数据全是0，1数字拉
/*模乘运算ModMul,A*B%n = bn_to*/
void ModMul(BNum *pb1,BNum *pb2,BNum *N,BNum *bn_to)
{
	BNum *re;
	BNum *result;
	re = new BNum;
	result = new BNum;
    BN_Multiply(pb1,pb2,re);
    BN_Devide(re,N,bn_to,result);
}

/*＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
             模幂运算M^e mod N = C
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝*/

void ModPower(BNum *M,BNum *e,BNum *N,BNum *C)
{
	int k = BN_GetBitlen(e);
    int eb[1024];
	BNum *bn;
	bn = new BNum;
	BN_Reset(bn);
	BN_Transform(e,eb);
    BN_Pass(M,C);         //把值先传过来
	for(int i = k-2;i>=0;i--)
	{
		ModMul(C,C,N,bn);
        BN_Pass(bn,C);
		BN_Reset(bn);
		if(1==eb[i])
		{
			ModMul(C,M,N,bn);
            BN_Pass(bn,C);
			BN_Reset(bn);
		}
	}
}