mynumber1.cpp

rsa源代码

///////////////////////////////////////////////////////////////
//                        MyNumber.cpp                       //
///////////////////////////////////////////////////////////////
#include "Iostream.h"
#include "math.h"
#include "assert.h"
#include "MyNumber.h"
#include "stdlib.h"
#include "string.h"
#include "time.h"
#define lo(x) ((x)&0xffff)
#define hi(x) (((x)&0xffff0000)>>16)
#define hl(x) (((x)&0xffff)<<16)


///////构造和析构函数////////
MyNumber::MyNumber()
{
	bit_len = 0;
	fuhao   = true;
	for(int i=0;i<MAX_LEN;i++)data[i]=0;
}

MyNumber::MyNumber(unsigned int n)
{
	fuhao = true;
	data[0]  = n;
	bit_len = 32;
	while((bit_len>1)&&((n>>(bit_len-1)) == 0))bit_len--;
	for(int i=1;i<MAX_LEN;i++)data[i]=0;
}

MyNumber::MyNumber(MyNumber&num)
{
	fuhao = num.fuhao;
	bit_len = num.bit_len;
	for(int i =0;i<=(bit_len-1)/32;i++)data[i] = num.data[i];
	for(;i<MAX_LEN;i++)data[i]=0;
}

MyNumber::~MyNumber()
{
//	delete [] data;
}

/////////辅助函数////////////
void MyNumber::setlength(int len)
{
	if(len == 0)
	{
		bit_len = 0;
		fuhao = true;
		return;
	}
	fuhao  = true;
	bit_len = len;
	for(int i = 0;i<=(bit_len-1)/32;i++)data[i] = 0;
}

void MyNumber::Mstr(char n[],MyNumber &m)
{
	int len=strlen(n),i,j,k=0;
	m.fuhao = true;
	m.bit_len = len*8;
	i=(len-1)/4;
	m.data[i]=0;
	for (j=(len-1)%4;j>=0;j--) 
		m.data[i]=(unsigned int)n[k++]+(m.data[i]<<(8));
	for(i=i-1;i>=0;i--)
	{
		m.data[i]=0;
		for (j=3;j>=0;j--) 
			m.data[i]=(unsigned int)n[k++]+(m.data[i]<<(8));
	}
	for(i=(len-1)/4+1;i<MAX_LEN;i++) m.data[i]=0;
//	m.standardize();
}

void MyNumber::Strm(MyNumber m,char s[])
{
	int len=m.bit_len/8,i,j,k=0;
	if (m.bit_len%8) len++;
	i=len/4;
	for (j=len%4-1,k=j;j>=0;j--) 
	{
		s[j]=m.data[i]&0xff;
		m.data[i]=m.data[i]>>(8);
	}
	k++;
	for(i=i-1;i>=0;i--)
	{
		for (j=3;j>=0;j--) 
		{
			s[k+j]=m.data[i]&0xff;
			m.data[i]=m.data[i]>>(8);
		}
		k+=4;
	}
	s[k]=0;	
}


int MyNumber::getdata(int index_0based)
{
	if( (index_0based<0)||(index_0based>=bit_len) )
	{
		cout<<"MyNumber.getdata() out of boundary!"<<endl;
		return -1;
	}
	int pos = index_0based/32,bitpos = index_0based%32;
	return (data[pos]&(1<<bitpos))!=0;
}

int MyNumber::getlength()
{
	return bit_len;
}

void MyNumber::display()
{
	MyNumber b(*this),c;
	if(fuhao == false)cout<<"-";
	unsigned int *dat,k=10;
	int j,i = (bit_len-1)/32;
	dat=new unsigned int [bit_len/3+1];
	for (i=0;i<=bit_len/3;i++) dat[i]=0;
	i=0;
	while (b>0)
	{
		c=b%k;
		dat[i]=c.data[0];
		b=b/k;
		i++;
	}
	for(j=i-1;j>=0;j--) cout<<dat[j];
}

void MyNumber::standardize()
{
	int i=MAX_LEN-1;
	bit_len = MAX_LEN*32;
	while (data[i]==0&&i>0) 
	{ i--;bit_len=bit_len-32;}
	while( (bit_len>1)&&(getdata(bit_len-1)==0) )bit_len--;
	if(bit_len == 1)
		if(data[0] == 0)fuhao = true;
}

ostream&operator<<(ostream&out,MyNumber&num)
{
	num.display();
	return out;
}

MyNumber MyNumber::operator=(MyNumber&num)
{
	if(this == &num)return (*this);
	fuhao   = num.fuhao;
	bit_len = num.bit_len;
	for(int i=0;i<=(bit_len-1)/32;i++)
		data[i] = num.data[i];
	for(;i<MAX_LEN;i++)
		data[i] = num.data[i];
	return (*this);
}

MyNumber MyNumber::operator=(unsigned int n)
{
	fuhao = true;
	data[0]  = n;
	bit_len = 31;
	while((bit_len>1)&&((n>>(bit_len-1)) == 0)) bit_len--;
	for(int i=1;i<MAX_LEN;i++) data[i]=0;
	return (*this);
}

MyNumber MyNumber::abs()
{
	MyNumber Result = *this;
	Result.fuhao = true;
	return Result;
}

/////////逻辑运算函数///////
bool MyNumber::operator>(MyNumber num)
{
	if(fuhao!=num.fuhao)return fuhao;
	if(fuhao == true)
	{
		if(bit_len!=num.bit_len)return bit_len>num.bit_len;
		for(int i = (bit_len-1)/32;i>=0;i--){
			if(data[i]!=num.data[i])return data[i]>num.data[i];
		}
		return false;
	}	//else if(fuhao == false)
	if(bit_len!=num.bit_len)return bit_len<num.bit_len;
	for(int i = (bit_len-1)/32;i>=0;i--)
	{
		if(data[i]!=num.data[i])return data[i]<num.data[i];
	}	//end for的情况两数相等//
	return false;
}

bool MyNumber::operator==(MyNumber num)
{
	if(fuhao != num.fuhao)return false;
//	if(bit_len!= num.bit_len)return false;
	for(int i=(bit_len-1)/32;i>=0;i--)
		if(data[i]!=num.data[i])return false;
	return true;
}

bool MyNumber::operator>=(MyNumber num)
{
	return ((*this)==num||(*this)>num);
}

bool MyNumber::operator!=( MyNumber num)
{
	return !((*this)==num);
}

bool MyNumber::operator<(MyNumber num)
{
	return !((*this)>num||(*this)==num);
}

bool MyNumber::operator<=(MyNumber num)
{
	return ((*this)<num||(*this)==num);
}

bool MyNumber::operator>(int n)
{
	MyNumber temp = n;
	return (*this)>temp ;
}

bool MyNumber::operator==(int n) 
{
	MyNumber temp = n;
	return (*this) == temp;
}

bool MyNumber::operator>=(int n)
{
	MyNumber temp = n;
	return (*this) >= temp;
}

bool MyNumber::operator!=(unsigned int n) 
{
	MyNumber temp = n;
	return (*this) != temp;
}

bool MyNumber::operator<(unsigned int n) 
{
	MyNumber temp = n;
	return (*this) < temp;
}

bool MyNumber::operator<=(int n)
{
	MyNumber temp = n;
	return (*this) <= temp;
}

MyNumber MyNumber::operator<<(const int off)////////左移位操作/////
{
//	int of=off;
	MyNumber Result=(*this);
	if(off<0){
		cout<<"operator << bad off!"<<endl;
		return Result;
	}
	if(off==0)return Result;

	Result.setlength(bit_len+off);
	int add = off/32,mod = off%32;
	unsigned int  mid = 0,cf = 0;
	for(int j =0;(j<MAX_LEN)&&(j<=(Result.bit_len-1)/32);j++)
	{
		mid = data[j];
		mid = (mid<<mod)+cf;
		Result.data[j+add] = mid;
		cf = data[j]>>(32-mod);
	}
	if (cf>0) 
	{
		Result.data[j+add]=cf;
		cout<<"cf>0......\n";
	}
	Result.standardize();
	return Result;
}

/////////算术运算函数//////////
MyNumber MyNumber::bitadd( MyNumber&num)
{
	MyNumber Result;
	unsigned int mid=0,cf=0,limit,i;
	if (bit_len>=num.bit_len) limit=bit_len;
	else limit=num.bit_len;
	Result.bit_len=limit;
	limit=(limit-1)/32;
	for(i=0;i<=limit;i++)
	{
		mid = num.data[i]+cf;
		Result.data[i] = mid+data[i];
		if (mid>=cf) cf=Result.data[i]<data[i];
	}
	if(cf>0) 
	{
//		Result.data[limit]=cf;
		Result.data[limit+1]=cf;
		Result.bit_len=Result.bit_len+1;
	}
	Result.standardize();
	return Result;
}

MyNumber MyNumber::bitminus(MyNumber&num)
{
	MyNumber Result=*this;
	unsigned int mid=0,cf=0,limit,i;
	if (bit_len>=num.bit_len) limit=(bit_len-1)/32;
	else limit=(num.bit_len-1)/32;
	for(i=0;i<=limit;i++)
	{
		unsigned int u=num.data[i]+cf;
		if (u>=cf)
		{		
			Result.data[i] = data[i]-u;
			cf =Result.data[i]> data[i];
		}
	}
	if(cf>0) cout<<"bitminus overflow!"<<endl;
	return Result;
}

MyNumber MyNumber::operator+( MyNumber&num)
{
	MyNumber Result;
	if(fuhao==num.fuhao)
	{
		Result = this->bitadd(num);
		Result.fuhao = fuhao;
		Result.standardize();
		return Result;
	}
	if(this->abs()>num.abs())
	{
		Result = this->bitminus(num);
		Result.fuhao = fuhao;
		Result.standardize();
		return Result;
	}
	else
	{
		Result = num.bitminus(*this);
		Result.fuhao = num.fuhao;
		Result.standardize();
		return Result;
	}

}

MyNumber MyNumber::operator-( MyNumber num)
{
	num.fuhao=!num.fuhao;
	return (*this + num);
}

MyNumber MyNumber:: operator*( MyNumber&num)
{
	MyNumber Result;
	unsigned int m,c,i,limit,keep;
	unsigned int len1=(bit_len-1)/32+1,len2=(num.bit_len-1)/32+1;
	limit=len1+len2;
	keep=bit_len+num.bit_len;
	Result.bit_len=keep;
	for(i=0;i<MAX_LEN;i++)
		Result.data[i]=0;
	for(i=0;i<len1;i++)
	{
		m = data[i];
		c = 0; 
		for ( unsigned j=i; j<len2+i; j++ )
		{
			unsigned w, v = Result.data[j], p = num.data[j-i];
			v += c; c = ( v < c );
			w = lo(p)*lo(m); v += w; c += ( v < w );
			w = lo(p)*hi(m); c += hi(w); w = hl(w); v += w; c += ( v < w );
			w = hi(p)*lo(m); c += hi(w); w = hl(w); v += w; c += ( v < w );
			c += hi(p) * hi(m);
			Result.data[j] = v;
		}
		while ( c && j<limit )
		{
			Result.data[j] += c;
			c = Result.data[j] < c;
			j += 1;
		}
	}
	if(c>0)cout<<"MyNumber operator* over flow!"<<endl;
	Result.fuhao = (fuhao == num.fuhao);
	keep %= 32;
	if (keep) Result.data[limit-1] &= (( (unsigned int)1 << keep)-1);
	Result.standardize();
	return Result;

}

MyNumber MyNumber::operator/( MyNumber&num)
{
	MyNumber Result,temp = *this,move,add;
	Result=(unsigned int) 0;
	add =(unsigned int) 1;
	int delta_len = bit_len - num.bit_len;
	if((this->abs())<num.abs())return Result;
	int i=delta_len;
	while (i>=0)
	{
		move = num.operator<<(i);
		if(temp>=move)
		{
			temp = temp - move;
			Result = Result+(add<<i);
		}
		i--;
	}
	Result.fuhao = (fuhao == num.fuhao);
	Result.standardize();
	return Result;
}

MyNumber MyNumber::operator% (MyNumber num)
{
	MyNumber Result = *this,move;
	if (bit_len < num.bit_len) return Result;
	int delta_len = bit_len - num.bit_len;
	if((this->abs())<num.abs())return Result;
	int i=delta_len;
	while (i>=0)
	{
		move = num.operator<<(i);
		if(Result>=move)
		{
			Result = Result - move;
			i=Result.bit_len - num.bit_len;
		}
		else i--;		
	}
	Result.fuhao = (fuhao == num.fuhao);
	Result.bit_len=num.bit_len;
	Result.standardize();
	return Result;
}

MyNumber MyNumber::operator*(unsigned int n) 
{
	MyNumber Result ;
	unsigned int m = 0,c = 0, p = n,limit;
	Result.bit_len=bit_len+32;
	limit=(bit_len-1)/32;
	Result.fuhao =fuhao ;
	for(unsigned int i=0;i<=limit;i++)
	{
		unsigned w, v = Result.data[i];
		m = data[i];
		v += c; c = ( v < c );
		w = lo(p)*lo(m); v += w; c += ( v < w );
		w = lo(p)*hi(m); c += hi(w); w = hl(w); v += w; c += ( v < w );
		w = hi(p)*lo(m); c += hi(w); w = hl(w); v += w; c += ( v < w );
		c += hi(p) * hi(m);
		Result.data[i] = v;
	}
	while ( c && i<=(limit-1)/32 )
	{
		Result.data[i] += c;
		c = Result.data[i] < c;
		i += 1;
	}
	Result.standardize();
	return Result;
}

MyNumber MyNumber::operator/(unsigned int n)
{
	MyNumber Result ;
	if(n == 0){
		cout<<"Divided by zero!"<<endl;
		return Result;
	}
	if(n<65536)
	{
		unsigned int mid = 0,cf = 0,t;
		for(int i=(bit_len-1)/32;i>=0;i--)
		{
			mid = hl(cf)+hi(data[i]);
			t= mid/n;
			cf = mid%n;
			mid = hl(cf)+lo(data[i]);
			cf = mid%n;
			Result.data[i] =hl(t)+ mid/n;
		}
		Result.standardize();
		return Result;
	}
	else
	{
		MyNumber temp = n;
		Result = (*this) / temp;
		return Result;
	}

}
MyNumber MyNumber::operator%(unsigned int n)
{
	MyNumber Result ;
	if(n == 0){
		cout<<"Mode by zero!"<<endl;
		return Result;
	}
	if(n<65536)
	{
		unsigned int mid = 0,cf = 0;
		for(int i=(bit_len-1)/32;i>=0;i--)
		{
			mid = hl(cf)+hi(data[i]);
			cf = mid%n;
			mid = hl(cf)+lo(data[i]);
			cf = mid%n;
		}
		Result.data[0]=cf;
	}
	else
	{
		MyNumber temp = n;
		Result = (*this) % temp;
	}
	Result.standardize();
	return Result;
}

MyNumber MyNumber::operator+(unsigned int n)
{
	MyNumber Result=(*this);
	unsigned int mid = 0,cf = 0;
	for(int i=0;(i<=(bit_len-1)/32)&&(i<MAX_LEN);i++)
	{
		mid = cf +n;
		if (mid>=cf)
		{
			Result.data[i] =data[i] + mid;
			cf= Result.data[i]<data[i] ;
		}
		if (cf==0) break;
		n = 0;
	}
//	Result.bit_len=Result.bit_len+1;
	Result.standardize();
	return Result;
}

MyNumber MyNumber::operator-(unsigned int n) 
{
	MyNumber Result=(*this);
	int mid = 0,cf = 0;
	for(int i=0;(i<=(bit_len-1)/32)&&(i<MAX_LEN);i++)
	{
		mid=n + cf;
		if (mid>=cf)
		{
			Result.data[i] = data[i] -mid;
			cf = Result.data[i] > data[i];
		} //else cf==1,Result.data[0]==data[0]
		if (cf==0) break;
		n = 0;
	}
	if(cf>0)cout<<"MyNumber operator -(unsigned int) over flow!"<<endl;
//	Result.bit_len=Result.bit_len+1;
	Result.standardize();
	return Result;
}

void MyNumber::makerandnumber(unsigned int len)
{
	unsigned int t;
	srand(time(NULL));
	if(len<=0){
		cout<<"MyNumber makerandnumber must has a length longer than zero!"<<endl;
		return;
	}
	fuhao = true;
	bit_len = len;
	for(int i =0;i<=(bit_len-1)/32;i++)
	{
		t=rand();
		data[i] = rand()+hl(t);
	}
	data[0] = data[0]|0x1;
	data[i-1]=data[i-1]|0x80000000;
}

void MyNumber::exp(MyNumber a,MyNumber b, MyNumber c,MyNumber& x)
{
	x=(MyNumber)1;
	while (b>0)
	{
		MyNumber d=b%2;
		if (d==0) 
		{
			a=a*a%c;
			b=b/2;
		}
		else
		{
			x=x*a%c;
			b=b-1;
		}
	}
}