bigint.cpp

rsa加密算法的vc实现

BigInt TableModBase[25];//for modlue multie
BigInt PreTable[16];
//constructor
BigInt::BigInt()
{
	head = new intNode();
	positive = true;
}

//disconstuctor
BigInt::~BigInt()
{
}

//set the number to 0
void BigInt::setZero()
{
	intNode* temp;
	while(head->next != NULL)
	{
		temp = head;
		head = head->next;
		delete temp;
	}
	positive = true;
	head -> num = 0;
}
//load the number at the base of ten
void BigInt::loadDEC(const char* str, const int length)
{
	unsigned int temp = 0;
	unsigned int base = MAXDEC;
	
	setZero();

	int i = 0;
	if(str[i] == '-')
	{
		positive = false;
		++i;
	}

	for(; i < length; ++i)
	{
		temp *= 10;
		temp += ((unsigned int) (str[i] - '0'));
		if((i + 1) % 9 == 0)
		{
			*this = *this * base;
			*this += temp;
			temp = 0;
		}
	}
	base = (unsigned int)pow(10, (length % 9));
	*this = * this * base;
	*this += temp;
}

//load the number at the base of 16
void BigInt::loadHEX(const char* str, const int length)
{
	unsigned int temp = 0;
	unsigned char t;
	
	setZero();

	int i = 0;
	if(str[i] == '-')
	{
		positive = false;
		++i;
	}

	for(; i < length; ++i)
	{
		temp <<= 4;
		t = (unsigned char) str[i];
		temp |= hdigit(t);
		if((i + 1) % 8 == 0)
		{
			*this <<= 32;
			*this += temp;
			temp = 0;
		}
	}
	*this <<= (length % 8) * 4;
	*this += temp;
}

//convert the string to big number
void BigInt::loadSTR(const char* str, const int length)
{
	unsigned int temp = 0;

	setZero();

	int i = 0;
	int mi = 1;
	if(str[0] == '-')
	{
		positive = false;
		++i;
		mi = 0;

	}
	for(; i < length ; ++i)
	{
		temp <<= 8;
		temp |= (unsigned int)str[i];
		if( (i +mi) % 4 == 0)
		{
			*this <<= 32;
			*this += temp;
			temp = 0;
		}
	}
	* this <<= (length % 4) * 8;
	*this += temp;
}

//output the number at the base ten
char* BigInt::outputDEC(int& length)
{
	unsigned int temp;
	unsigned int base = MAXDEC;
	int i;
	unsigned char c = '0';
	stack s;//the stack to store the charactors

	BigInt a;

	a.copy(*this);
	unsigned char* ch;
	if(a.BIlisZero())
	{
		ch = new unsigned char[1];
		ch[0] = '0';
		length = 1;
		return (char*)ch;
	}
	while(! a.BIlisZero())
	{
		temp = a % base;
		a = a / base;
		for(i = 0; i < 9; ++i)
		{
			c = (unsigned char)((temp % 10) + ((unsigned int)'0'));
			s.push(c);
			temp /= 10;
		}
	}//convent the number at the base of ten to charactors and store the in the stack

	c = '0';
	while(c == '0')
		s.pop(c);

	length = s.getLength() + 1;
	i = 0;
	if(!positive)
		++length;
	ch = new unsigned char[length];

	if(!positive)
	{
		++i;
		ch[0] = '-';
	}
	for(; i < length; ++i)
	{
		ch[i] = c;
		s.pop(c);
	}//pop the characors and put the in the characotors

	return (char*)ch;
}
//output the number at the base of 16
char* BigInt::outputHEX(int& length)
{
	unsigned int temp;
	BigInt a;
	a.copy(*this);
	stack s;
	unsigned char c = '0';
	int i;

	unsigned char* ch;
	if(a.BIlisZero())
	{
		ch = new unsigned char[1];
		ch[0] = '0';
		length = 1;
		return (char*)ch;
	}

	while(!a.BIlisZero())
	{
		temp = a.getLast32Bit();
		a >>= 32;

		for(i = 0; i < 8; ++i)
		{
			c = HArray[temp & 0xF];
			s.push(c);
			temp >>= 4;
		}
	}//convent the number at the base of 16 to charactors and store the in the stack

	c = '0';
	while(c == '0')
		s.pop(c);

	length = s.getLength() + 1;
	i = 0;
	if(!positive)
		++length;
	ch = new unsigned char[length];

	if(!positive)
	{
		++i;
		ch[0] = '-';
	}
	for(; i < length; ++i)
	{
		ch[i] = c;
		s.pop(c);
	}//pop the characors and put the in the characotors

	return (char*)ch;
}
//output the number at form of ASCII 
char* BigInt::outputSTR(int& length)
{
	unsigned int temp;
	BigInt a;
	a.copy(*this);
	stack s;
	unsigned char c;
	int i;
	unsigned char* ch;
	if(a.BIlisZero())
	{
		ch = new unsigned char [1];
		ch[0] = 0;
		length = 1;
		return (char*)ch;
	}

	while(! a.BIlisZero())
	{
		temp = a.getLast32Bit();
		a >>= 32;
		for(i = 0; i < 4; ++i)
		{
			c = (unsigned char)(temp & 0xFF);
			s.push(c);
			temp >>= 8;
		}
	}//convent the number at the base of 16 to charactors and store the in the stack
	c = 0;
	while(c == 0)
		s.pop(c);

	length = s.getLength() + 1;
	ch = new unsigned char[length];

	for(i = 0; i < length; ++i)
	{
		ch[i] = c;
		s.pop(c);
	}//pop the characors and put the in the characotors

	return (char*)ch;
}
//reload the operator +
BigInt BigInt::operator + (const BigInt& p) const
{
	BigInt temp;

	if((positive && p.positive) || ((!positive) && (!p.positive)))
	{
		add(p, temp);
		temp.positive = positive;
	}
	else
	{
		if( BICompareABS(p) > 0)
		{
			minuse(p,temp);
			temp.positive = positive;
		}
		else
		{
			if( BICompareABS(p) == 0)
				temp.setZero();
			else
			{
				p.minuse(*this,temp);
				temp.positive = ! positive;
			}
		}//end of second else
	}//end of first else
	return temp;
}
//reload the operator + 
BigInt BigInt::operator + (const unsigned int& p) const
{
	BigInt temp;

	if(positive)
	{
		add(p, temp);
		temp.positive = true;
	}
	else
	{
		temp.setZero();

		if( BICompareABS(p) > 0)
		{
			minuse(p, temp);
			temp.positive = false;
		}

		if(BICompareABS(p) < 0)
		{
			temp.head -> num = p - head->num;
			temp.positive = true;
		}
	}
	return temp;
}

BigInt BigInt::operator - (const BigInt& p) const
{
	BigInt temp;

	if((positive && (!p.positive)) || ((!positive) && p.positive))
	{
		add(p, temp);
		temp.positive = positive;
	}
	else
	{
		if( BICompareABS(p) > 0)
		{
			minuse(p,temp);
			temp.positive = positive;
		}
		else
		{
			if( BICompareABS(p) == 0)
				temp.setZero();
			else
			{
				p.minuse(*this,temp);
				temp.positive = ! positive;
			}
		}//end of second else
	}//end of first else

	return temp;
}

BigInt BigInt::operator - (const unsigned int& p) const
{
	BigInt temp;

	if(!positive)
	{
		add(p, temp);
		temp.positive = false;
	}
	else
	{
		temp.setZero();

		if( BICompareABS(p) > 0)
		{
			minuse(p, temp);
			temp.positive = true;
		}

		if(BICompareABS(p) < 0)
		{
			temp.head->num = p - head->num;
			temp.positive = false;
		}
	}
	return temp;
}

BigInt BigInt::operator * (const unsigned int& p) const
{
	BigInt bin;

	unsigned int high = 0;
	unsigned int low = 0;
	intNode* temp = head;
	intNode* t1 = bin.head;
	intNode* t2 = bin.head;

	while(temp != NULL)
	{
		multi(p, temp->num, high, low);
		t1->num += low;
		if(t1->num < low)
			++high;
		t1->next = new intNode;
		t2 = t1;
		t1 = t1->next;
		t1->num = high;

		temp = temp->next;
	}

	if(t1->num == 0)
	{
		delete t1;
		t2->next = NULL;
	}

	bin.positive = positive;

	return bin;
}

BigInt BigInt::operator * (const BigInt& p) const
{
	BigInt bin;

	unsigned int high = 0;
	unsigned int low = 0;
	unsigned int carry = 0;

	intNode* temp1 = head;
	intNode* temp2 = p.head;
	intNode* t1 = bin.head;
	intNode* t2 = bin.head;
	intNode* t3 = bin.head;

	bin.positive = (positive && p.positive) || ((! positive) && (! p.positive));

	while(temp1 != NULL)
	{
		t2 = t1;
		temp2 = p.head;
		while(temp2 != NULL)
		{
			multi(temp1->num, temp2->num, high, low);
			t2->num += carry;
			if(t2->num < carry)
				carry = 1;
			else
				carry = 0;
			t2->num += low;
			if(t2->num < low)
				++carry;
			carry += high;
			if(t2->next == NULL)
			{
				t3 = t2;
				t2->next = new intNode;
			}
			t2 = t2->next;
			temp2 = temp2->next;
		}
		t2->num = carry;
		carry = 0;
		temp1 = temp1 -> next;
		t1 = t1->next;
	}
	if(t2->num == 0)
	{
		delete t2;
		t3->next = NULL;
	}

	return bin;
}

BigInt BigInt::operator / (const BigInt& p)
{
	BigInt d;
	BigInt r;

	r = BIdivision(p, d);
	r.positive = (positive && p.positive) || ((!positive) && (!p.positive));

	d.clear();
	return r;
}

BigInt BigInt::operator / (const unsigned int& p)
{
	BigInt d;
	BigInt r;
	BigInt pp;
	pp = p;

	r.positive = positive;
	r = BIdivision(pp, d);

	d.clear();
	pp.clear();

	return r;
}

BigInt BigInt::operator % (const BigInt& p) const
{
	BigInt a, mb;
	BigInt temp;

	a.copy(*this);

	a.positive = (p.positive && positive) || ((!p.positive) && (!positive));

	if(a.BICompareABS(p) > 0)
	{
		mb.copy(p);
		a.MakeClose(mb);
		while(a.BICompareABS(mb) > 0)
			mb <<= 1;
		
		while(a.BICompareABS(p) > 0)
		{
			while(a.BICompareABS(mb) < 0)
			mb >>= 1;
			temp = a - mb;
			a.copy(temp);
		}
	}
	if(a.BICompareABS(p) == 0)
		a.setZero();

	mb.clear();
	temp.clear();
	return a;
}

unsigned int BigInt::operator % (const unsigned int& p) const
{
	BigInt mb;
	mb = p;
	BigInt a;
	a = (*this) % mb;

	unsigned int temp;
	temp = a.head->num;

	mb.clear();
	a.clear();

	return temp;
}

bool BigInt::operator > (const BigInt& p) const
{
	if(positive && (!p.positive))
		return true;
	if((!positive) && p.positive)
		return false;

	if(positive && (BICompareABS(p) > 0))
		return true;
	if(!positive && (BICompareABS(p) < 0))
		return true;

	return false;
}
bool BigInt::operator > (const unsigned int p) const
{
	if(! positive)
		return false;

	if(BICompareABS(p) > 0)
		return true;

	return false;
}

bool BigInt::operator == (const BigInt& p) const
{
	if(positive &&(! p.positive))
		return false;
	return (BICompareABS(p) == 0);
}

bool BigInt::operator != (const BigInt& p) const
{
	if(positive && (! p.positive))
		return true;
	return (BICompareABS(p) != 0);
}

BigInt& BigInt::operator <<= (int iBit)
{
	if(BIlisZero())
		return *this;

	int block = 0;
	intNode* t1 = head;
	intNode* t2 = head;

	block = iBit / 32;
	for(int i = 0; i < block; ++i)
	{
		t2 = new intNode(head);
		head = t2;
	}

	iBit %= 32;
	if(iBit == 0)
		return *this;

	unsigned int carry = 0;
	unsigned int highF =((FULL >> (32 - iBit)) << (32 - iBit));
	unsigned int high;
	for(t2 = t1; t2->next != NULL; t2 = t2->next)
	{
		high = (t2->num & highF) >> (32 - iBit);
		t2->num <<= iBit;
		t2->num |= carry;
		carry = high;
	}
	high = (t2->num & highF) >> (32 - iBit);
	t2->num <<= iBit;
	t2->num |= carry;
	carry = high;
	if(carry != 0)
		t2->next = new intNode(carry);

	return *this;
}

BigInt& BigInt::operator >>= (int iBit)
{
	if(BIlisZero())
		return *this;

	int block = iBit / 32;
	intNode* t = head;
	for(int i = 0; (i < block) && (head != NULL); ++i)
	{
		t = head;
		head = head->next;
		delete t;
	}
	if(head == NULL)
	{
		head = new intNode;
		return *this;
	}

	iBit %= 32;
	if(iBit == 0)
		return *this;

	t = head;
	if(t->next == NULL)
	{
		t->num >>= iBit;
		return *this;
	}

	unsigned int low;
	unsigned int lowF = ((FULL << (32 - iBit)) >> (32 - iBit));
	unsigned int carry = 0;
	for(t = head; t->next->next != NULL; t = t->next)
	{
		low = ((t->next->num & lowF) << (32-iBit));
		t->num = ((t->num >> iBit) | low);
	}
	low = ((t->next->num & lowF) << (32-iBit));
	t->num = ((t->num >> iBit) | low);
	t->next->num >>= iBit;
	if(t->next->num == 0)
	{
		delete t->next;
		t->next = NULL;
	}
	return *this;
}

BigInt& BigInt::operator = (const BigInt& p)
{
	positive = p.positive;
	clear();
	head = p.head;
	return *this;
}

BigInt& BigInt::operator = (const unsigned int& p)
{
	positive = true;
	clear();
	head = new intNode(p);
	return *this;
}

BigInt& BigInt::operator ++ ()
{
	intNode *t = head;

	while(t->next != NULL)
	{
		++(t->num);
		if(t->num != 0)
			return *this;