mathint.cpp

RSA加密算法的实现 2^1024大的素数实现

/*----------------------------------------------------------
 Instruction: in this part we give the definition of 
 all the methods in calss mathInt,of course included 
 the overloaded operator. 
------------------------------------------------------------ */

#include"mathInt.h"
mathInt::mathInt(int integer)//construct function NOTE!!!mathInt a = 1;必需要定义相应的构造函数,相当于a(1);
{
	sign =( integer>0?1:0);
	coeff.resize(VSIZE);
	if(integer<BASE)
		coeff[0] = integer;	
	else
		for(int i=0;integer>0;i++)
		{
			coeff[i] = integer%BASE;
			integer = integer/BASE;
		}
}	
//to set size unzero coefficients.
 void mathInt::set_coeff(bool isPos,int size)	
{
	sign = isPos;

	//srand(time(NULL));
	for(int i=0;i<=size-1;i++)
		coeff[i] = (rand()%BASE);
	for(int i=size;i<=VSIZE-1;i++)
		coeff[i] = 0;
}
int mathInt::length()const
{
	int i=VSIZE-1;
	
	while(i>=0&&coeff[i]==0)
		i--;
	return i+1;
}
mathInt mathInt::abs()const
{
    return mathInt(1,coeff);
}
bool mathInt::is_odd()const
{
	return coeff[0]%2==1;//最后一位是奇数就一定是奇数;
}
bool mathInt::is_pos() const//judge whether the num is positive;
{
	return sign==1;
}
void mathInt::display()const
{
	int length = this->length();

	std::cout<<"sign-->"<<sign<<endl;
	std::cout<<"length-->"<<length<<endl;
	std::cout<<"value-->"<<coeff[0]<<"*"<<BASE<<"^"<<0;
	for(int i=1;i<=length-1;i++)
		std::cout<<"+"<<coeff[i]<<"*"<<BASE<<"^"<<i;
	std::cout<<std::endl;
}
void mathInt::OutToFile(char* name)const
{
	ofstream Outf(name,ios_base::app);
	int length = this->length();

	Outf<<sign<<endl;
	Outf<<length<<endl;
	for(int i=0;i<=length-1;i++)
		Outf<<coeff[i]<<" ";
    Outf<<endl;
	Outf.close();
}
void mathInt::OutToString(char* name,bool flag)const
{
	ofstream Outf(name,ios_base::app);

	int length = this->length();
	for(int i=0;i<=length-1;i++)
		Outf<<(char)coeff[i];
	Outf.close();
}
int mathInt::operator [](int i)const
{
	return coeff[i];
}
bool mathInt::operator ==(mathInt const&a)const
{
	if(sign==a.get_sign())
	{
		int i=VSIZE-1;
		while(i>=0&&coeff[i]==a[i])
			i--;
		if(i==-1)
			return true;
		else 
			return false;
	}
	else
		if(a.abs()==ZERO&&this->abs()==ZERO)
			return true;//positive == negative;
		else
		    return false;
}
/*In the comparition of two mathInt,we only need to
compare the highest coefficient unequal. */
bool mathInt::operator<(mathInt const& a)const
{
	if(sign==a.get_sign())
	{
		int i = VSIZE-1;
		while(coeff[i]==a[i]&&i>=1)//when i==1and coeff[i]==a[i], make sure that i be legal；
			i--;
		if(sign)
			if(coeff[i]<a[i])
				return true;
			else
				return false;
		else
			if(coeff[i]>a[i])
				return true;
			else
				return false;
	}
	else
		if(sign)//in this case *this is positive and a is negtive
			return false;
		else 
			return true;
}
bool mathInt::operator <=(mathInt const& a)const
{
	if(sign==a.get_sign())
	{
		int i = VSIZE-1;
		while(coeff[i]==a[i]&&i>=1)//when i==1and coeff[i]==a[i], make sure that i be legal；
			i--;
		if(sign)
			if(coeff[i]<=a[i])
				return true;
			else
				return false;
		else
			if(coeff[i]<a[i])
				return false;
			else
				return true;
	}
	else
		if(sign)
			return false;
		else 
			return true;
}
void mathInt::operator = (mathInt const & a)
{
	sign = a.get_sign();
	coeff = a.get_coeff();
}
//add.
mathInt mathInt::operator +(const mathInt &a) const//只计算两个同号数的运算;
{
	if(sign==a.get_sign())//如果两操作数同号
    {
		int i = 0,carry = 0,next_c = 0;//next carray;
		vector<int> result(VSIZE);
		
		for(i=0;i<=VSIZE-1;i++)
		{
			next_c = coeff[i] + a[i] + carry>=BASE?1:0;//---其实最大只可能进1,(coeff[i] + a[i] + carry)/BASE;
			result[i] = coeff[i] + a[i] + carry - BASE*next_c;
			carry = next_c;
		}
	    if(sign)
	        return mathInt(1,result);//positive	
		else
			return mathInt(0,result);
	}
	else
    {
		if(sign)
			return (*this) - mathInt(1,a.get_coeff());
		else
			return a - mathInt(1,this->get_coeff());
	}
}
//subtract.
mathInt mathInt::operator -(const mathInt &a) const//只计算positive大数-小数
{
	int i = 0,carry = 0,next_c=0;
	vector<int> result(VSIZE);

	if(sign==a.get_sign())
	{
		if(sign)//both number are positive
		{
			if(a<=*this)
			{
				for(i=0;i<=VSIZE-1;i++)
				{
					next_c = coeff[i] - a[i] - carry<0?1:0;//carry 是已经借走的~
					result[i] = coeff[i] - a[i] -carry + next_c*BASE;
					carry = next_c;
				}
				return mathInt(1,result);
			}
			else
		      return -(a - *this);
		}
		else//both number are gegative
		{
		    if(a<=*this)
				return (-a) - (-*this);
			else
				return -((-(*this)) - (-a)); 
		}
	}
	else
	{
         if(sign)//the first number is positive,and the second is negative
			 return *this + a.abs();
		 else
			 return -(this->abs()+a);
	}
}
//右移位 namely multiplied by BASE^n;
mathInt mathInt::operator >>(int n) const
{
	if(n==0)
		return *this;
	vector<int> result=coeff;
	int pos = VSIZE-1;
	while(pos>=0&&coeff[pos]==0)
		pos--;
	if(VSIZE-pos-1<n)//overflow when pos+n > VSIZE-1;
	{
		std::cerr<<"The data is overflowed!"<<std::endl;
		exit(1);
	}
	else
	{
		for(int i=pos;i>=0;i--)
			result[i+n] = result[i];//后移;
		for(int i=0;i<=n-1;i++)
			result[i] = 0;
	}
	return mathInt(sign,result);
}
mathInt mathInt::operator *(int n) const
{
	int carry = 0,next_c = 0,i = 0;
	vector<int> result(VSIZE);

	if(n==0)
		return ZERO;
	if(n==1)
		return *this;
	for(i=0;i<=VSIZE-1;i++)
	{
		next_c = (n*coeff[i]+carry)/BASE;
		result[i] = n*coeff[i] + carry - next_c*BASE;
		carry = next_c;
	}
	bool isign = n>0?1:0;
	return mathInt(sign==isign,result);
}
mathInt mathInt::operator *(const mathInt &a) const
{
	 int i = 0;

	 mathInt multy;
	 int len = this->length ();
	 if(a==ZERO||(*this)==ZERO)//positive zero and negative zero
		 return ZERO;
	 mathInt pa = a.abs();
	 for(i=0;i<=len-1;i++)
		 multy = multy + (pa>>i)*coeff[i];

	 bool mysign = sign==a.get_sign()? 1 : 0;
	 if(mysign)
		 return multy;
	 else
		 return -multy;
}
/*The original division,I use subtract to complish
   this method. it is of little efficiency.*/
/*mathInt mathInt::operator /(const mathInt &a) const
{

	if(a.abs()==ZERO)
	{
		cout<<"ERROR,a number can't be divided by ZERO!"<<endl;
		exit(1);
	}
	else if(this->abs()<a.abs())//小数除大数ZERO
		return ZERO;
	else
	{
		vector<int> quotient(VSIZE);
		mathInt dividend = (*this).abs();
		mathInt ori_divisor = a.abs();
		mathInt divisor = ori_divisor;
		int q = 0;//商中的一位;
	    int i;
		int quot_len = this->length() - a.length() +1;//商的长度

		for(i=quot_len-1;i>=0;i--)
		{
			divisor = ori_divisor>>i;//让divisor与被除数对齐;
			while(divisor<=dividend)
			{
				dividend = dividend - divisor;
				q++;
			}
			quotient[i] = q;
			q = 0;
		}
	    return mathInt(sign==a.get_sign(),quotient);
	}
}*/
/*--------------------------------------------------------------------------------------
 division
//dimidiate二分思想
instruction: just like we calculate the quotient of two num,
we try to guess what the quotient should be.eg:9/2,first we use q = 5(that is 10/2)
as the quotient, since 9-2*5<0,9 is't enouth to be subtracted,next we try q=(0+5)/2 = 2,
since 9 - 2*2>2,we need to go on with the former algorithm.Next q = (2+5)/2-->q=(3+5)/2 
----------------------------------------------------------------------------------------*/

mathInt mathInt::operator /(const mathInt &a) const
{  
	if(a.abs()==ZERO)
	{
		cerr<<"ERROR,a number can't be divided by ZERO!"<<endl;
		exit(1);
	}
	else if(this->abs()<a.abs())//小数除大数ZERO
		return ZERO;
	else
	{
		vector<int> quotient(VSIZE);
		mathInt dividend = (*this).abs();
		mathInt ori_divisor = a.abs();
		mathInt divisor = ori_divisor;
		int q = 0;//商中的一位;
	    int i;
		int quot_len = this->length() - a.length() +1;//商的长度

		for(i=quot_len-1;i>=0;i--)
		{
			divisor = ori_divisor>>i;//让divisor与被除数对齐;

			int high = BASE;//这里注意,high必需要取BASE而不能取BASE-1,因为是[ )的形式,high 必然是取不到的,但是q may equal BASE-1;
		    int low = 0;
		    q = (high+low)/2;
			while(high-low>1)
			{
				
				if(dividend-divisor*q<ZERO)//如果不够除
					high =q;
				else//是一定够除的!
				{
					if(dividend - divisor*q<divisor)
						break;
					low = q;
				}
				q = (high+low)/2;
			}
			dividend = dividend - divisor*q;
			quotient[i] = q;

		}
	    return mathInt(sign==a.get_sign(),quotient);
	}
}
mathInt mathInt::operator %(const mathInt &a)const
{

	if(a.abs()==ZERO)
	{
		std::cerr<<"ERROR,a number can't be divided by ZERO!"<<std::endl;
		exit(1);
	}
	if(*this==ZERO)
		return ZERO;
	if(this->abs()<a.abs())
	{
		if(sign)
			return *this;
		else
			return a.abs() + *this;
	}
	else
	{
		if(sign)//if the first number is positive---->eg:13%4or 13%-4
		   return *this - a*(*this/a);
		else
		   return *this - a*(*this/a) + a.abs();
	}
}
//Turn a integer into a mathInt;
mathInt to_mathInt(int intg)
{
	vector<int> result(VSIZE);
	bool sign = intg>0?1:0;
	intg = abs(intg);
	if(intg<BASE)
		result[0] = intg;	
	else
		for(int i=0;intg>0;i++)
		{
			result[i] = intg%BASE;
			intg = intg/BASE;
		}
	return mathInt(sign,result);
}
void mathInt::operator =(int const& n)
{
    return (*this) = to_mathInt(n);
}
bool mathInt::operator ==(int const& n)const
{
	return (*this)==to_mathInt(n);
}
mathInt mathInt::operator +(int const& n)const
{
	return (*this) + to_mathInt(n);
}
mathInt mathInt::operator -(int const& n) const
{
	return (*this) - to_mathInt(n);
}
mathInt mathInt::operator /(int const& n )const
{
	return (*this)/to_mathInt(n);
}

//class mathInt