bigint.cpp

rsa加密算法的vc实现

		t = t->next;
	}
	++(t->num);
	if(t->num == 0)
		t->next = new intNode(1);
	return *this;
}
BigInt& BigInt::operator -- ()
{
	intNode *t = head;
	intNode *tt = head;

	if(head->next == NULL)
	{
		--(t->num);
		return *this;
	}
	while(t->next != NULL)
	{
		--(t->num);
		if(t->num != FULL)
			return *this;
		tt = t;
		t = t->next;
	}
	--(t->num);
	if(t->num == 0)
	{
		delete t;
		tt->next = NULL;
	}
	return *this;
}

bool BigInt::BIlisZero() const
{
	return ((head->next == NULL) && (head->num == 0));
}

int BigInt::BICompareABS(const BigInt& p) const
{
	intNode* t1 = head;
	intNode* t2 = p.head;

	int comp = 0;

	while((t1 != NULL) && (t2 != NULL))
	{
		if(t1->num > t2->num)
			comp = 1;
		if(t1->num < t2->num)
			comp = -1;
		t1 = t1->next;
		t2 = t2->next;
	}
	if(t1 != NULL)
		comp = 1;
	if(t2 != NULL)
		comp = -1;
	
	return comp;
}

int BigInt::BICompareABS(const unsigned int& p) const
{
	if((head->next != NULL) || (head->num > p))
		return 1;
	if(head->num < p)
		return -1;
	return 0;
}

void BigInt::copy(const BigInt& p)
{
	if(head == NULL)
		head = new intNode;
	intNode* t1 = head;
	intNode* t2 = p.head;

	positive = p.positive;

	while(t2->next != NULL)
	{
		if(t1->next == NULL)
			t1->next = new intNode;
		t1->num = t2->num;
		t1 = t1->next;
		t2 = t2->next;
	}
	t1->num = t2->num;
	
	t2 = t1->next;
	t1->next = NULL;
	while(t2 != NULL)
	{
		t1 = t2;
		t2 = t2->next;
		delete t1;
	}
}

unsigned int BigInt::getLast32Bit()
{
	if(head != NULL)
		return head->num;
	else
		return 0;
}

void BigInt::add(const BigInt& p, BigInt& temp) const
{
	if(temp.head == NULL)
		temp.head = new intNode;

	intNode* t1 = temp.head;
	intNode* t2 = p.head;
	intNode* t3 = head;
	intNode* t4 = temp.head;
	unsigned int carry = 0;
	
	while((t2 != NULL) && (t3 != NULL))
	{
		if(t1->next == NULL)
			t1->next = new intNode;
		t1->num = carry;
		carry = 0;
		t1->num += t2->num;
		if(t1->num < t2->num)
			carry = 1;
		t1->num += t3->num;
		if(t1->num < t3->num)
			carry = 1;
		t4 = t1;
		t1 = t1->next;
		t2 = t2->next;
		t3 = t3->next;
	}

	if(t2 == NULL)
		t2 = t3;
	while(t2 != NULL)
	{
		if(t1->next == NULL)
			t1->next = new intNode;
		t1->num = t2->num + carry;
		if(t1->num < carry)
			carry = 1;
		else
			carry = 0;
		t4 = t1;
		t2 = t2->next;
		t1 = t1->next;
	}
	t1->num = carry;
	if(t1->num == 0)
	{
		delete t1;
		t4->next = NULL;
	}
}

void BigInt::minuse(const BigInt& p, BigInt& temp) const
{
	temp.copy(*this);

	intNode* t1 = p.head;
	intNode* t2 = temp.head;
	unsigned int carry = 0;
	while(t1 != NULL)
	{
		t2->num -= carry;
		if((carry == 1) && (t2->num == FULL))
			carry = 1;
		else
			carry = 0;
		t2->num -= t1->num;
		if((t2->num + t1->num) < t2->num)
			carry = 1;
		t2 = t2->next;
		t1 = t1->next;
	}
	if(carry == 1)
	{
		while(t2 != NULL)
		{
			--(t2->num);
			if(t2->num != FULL)
				break;
			t2 = t2->next;
		}
	}

	for(t1 = temp.head; t1 != NULL; t1 = t1->next)
	{
		if(t1->num != 0)
			t2 = t1;
	}
	t1 = t2->next;
	t2->next = NULL;
	while(t1 != NULL)
	{
		t2 = t1;
		t1 = t1->next;
		delete t2;
	}
}

void BigInt::add(const unsigned int& p,BigInt& temp) const
{
	temp.copy(*this);
	intNode* t = temp.head;

	t->num += p;
	if(t->num >= p)
		return;

	if(t->next == NULL)
	{
		t->next->next = new intNode;
		t->next->num = 1;
		return;
	}

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

	t->next = new intNode;
	t->next->num = 1;
}

void BigInt::minuse(const unsigned int& p,BigInt& temp) const
{
	temp.copy(*this);

	intNode* t = temp.head;

	t->num -= p;
	if((t->num + p) > t->num)
		return;

	t = t->next;
	while(t->next->next != NULL)
	{
		--(t->num);
		if(t->num != FULL)
			return;
		t = t->next;
	}

	--(t->num);
	if(t->num != FULL)
		return;
	--(t->next->num);
	if(t->next->num == 0)
	{
		delete t->next;
		t->next = NULL;
	}
}

void BigInt::clear()
{
	if(head == NULL)
		return;

	intNode* t;
	while(head != NULL)
	{
		t = head;
		head = head->next;
		delete t;
	}
}

void BigInt::MakeClose(BigInt& p)
{
	intNode* t1 = head;
	intNode* t2 = p.head;
	while(t2 != NULL)
	{
		t1 = t1->next;
		t2 = t2->next;
	}

	while(t1 != NULL)
	{
		t1 = t1->next;
		t2 = new intNode(p.head);
		p.head = t2;
	}
}
BigInt BigInt::BIdivision(const BigInt& p, BigInt& pr)
{
	int test = BICompareABS(p);
	BigInt re;

	if(test == 0)
	{
		pr.setZero();
		++re;
		return re;
	}

	if(test < 0)
	{
		pr.copy(*this);
		return re;
	}

	BigInt t1;
	BigInt t2;
	t2.copy(p);
	t1.copy(*this);
	MakeClose(t2);
	while(BICompareABS(t2) > 0) 
		t2 <<= 1;
	while(BICompareABS(t2) < 0)
		t2 >>= 1;

	while((p.BICompareABS(t1) <= 0) || (p.BICompareABS(t2) <= 0))
	{
		if(t1.BICompareABS(t2) >= 0)
		{
			t1 = t1 - t2;
			re <<= 1;
			++re;
		}
		else
			re <<= 1;
		t2 >>= 1;
	}
	pr.copy(t1);

	return re;
}

BigInt& BigInt::operator += (const unsigned int& p)
{
	intNode* temp = head;

	temp->num += p;
	if(temp->num >= p)
		return *this;
	if(temp->next == NULL)
	{
		temp->next = new intNode(1);
		return *this;
	}
	temp = temp->next;
	while(temp->next != NULL)
	{
		++(temp->num);
		if(temp->num != 0)
			return *this;
		temp = temp->next;
	}
	++(temp->num);
	if(temp->num == 0)
		temp->next = new intNode(1);
	return *this;
}

BigInt BigInt::BIinverse(const BigInt& p) const
{
	BigInt y, g0, g1, g2, v0, v1, v2;

	g0.copy(p);
	g1.copy(*this);
	++v1;
	while(! g1.BIlisZero())
	{
		y = g0.BIdivision(g1, g2);
		g0.copy(g1);
		g1.copy(g2);
		v2 = y * v1;
		while(v0.BICompareABS(v2) < 0)
			v0 = v0 + p;
		v0 = v0 - v2;
		BIswap(v0,v1);
	}

	y.clear();
	g0.clear();
	g1.clear();
	g2.clear();
	v1.clear();
	v2.clear();
	return v0;
}
int BigInt::nodeNumber() const
{
	intNode* t;
	t = head;
	int i = 0;
	while(t != NULL)
	{
		t =  t->next;
		++i;
	}
	return i;
}

BigInt BIgcd(const BigInt& p1, const BigInt& p2)
{
	BigInt a;
	a.copy(p1);
	BigInt b;
	b.copy(p2);

	while(! b.BIlisZero())
	{
		a = a % b;
		BIswap(a, b);
	}

	b.clear();
	return a;
}
void BIswap(BigInt& a, BigInt& b)
{
	bool bo;
	bo = a.positive;
	a.positive = b.positive;
	b.positive = bo;

	intNode* temp;
	temp = a.head;
	a.head = b.head;
	b.head = temp;
}

void MakeModBaseTable(const BigInt& pp)
{
	TableModBase[0].copy(pp);
	for(int i = 1; i < 25; ++i)
	{
		TableModBase[i].copy(TableModBase[i - 1]);
		TableModBase[i] <<= 2;
	}
}

BigInt BImodmul(const BigInt& p1, const BigInt& p2, const BigInt pp)
{
	BigInt a, b, c, result;
	int i;
	intNode* t;

	if(p1.BIlisZero())
		return result;
	if(p2.BIlisZero())
		return result;
	if(TableModBase[0] != pp)
		MakeModBaseTable(pp);
	a = p1 % pp;
	b = p2 % pp;
	b.head = t = backToFront(b.head);
	while( t != NULL)
	{
		result <<= 32;
		if(t->num != 0)
		{
			c = a * t->num;
			result = result + c;
		}
		if(result.BICompareABS(pp) >= 0)
		{
			for(i = 24; i >= 0; --i)
			{
				while(result.BICompareABS(TableModBase[i]) >= 0)
					result = result - TableModBase[i];
			}
		}
		t = t->next;
	}

	a.clear();
	b.clear();
	c.clear();
	return result;
}
BigInt BImodmul2(const BigInt& p1, const BigInt& p2, const BigInt pp)
{
	BigInt pre_a[16], a, b, pp2, pp4, pp8, result;
	unsigned int ma1, ma2;
	int i, j, test;
	intNode* t;

	a.copy(p1);
	b.copy(p2);

	test = a.BICompareABS(pp);
	if(test > 0)
		a = a % pp;
	if(test == 0)
		return result;
	if(a.BIlisZero())
		return result;

	test = b.BICompareABS(pp);
	if(test > 0)
		b = b % pp;
	if(test == 0)
		return result;
	if(b.BIlisZero())
		return result;

	pre_a[0].setZero();
	pre_a[1].copy(a);
	for(i = 2; i < 16; ++i)
	{
		pre_a[i] = pre_a[i - 1] + a;
		if(pre_a[i].BICompareABS(pp) > 0)
			pre_a[i] = pre_a[i] - pp;
	}
	pp2.copy(pp);
	pp2 <<= 1;
	pp4.copy(pp2);
	pp4 <<= 1;
	pp8.copy(pp4);
	pp8 <<= 1;
	b.head = t = backToFront(b.head);
	while(t != NULL)
	{
		ma1 = 0xF0000000;
		for(i = 7; i >= 0; --i)
		{
			result <<= 4;
			ma2 = t->num & ma1;
			if(ma2 != 0)
			{
				j = (i << 2);
				ma2 >>= j;
				result = result + pre_a[ma2 & 0xf];
			}
			while(result.BICompareABS(pp8) > 0)
				result = result - pp8;
			while(result.BICompareABS(pp4) > 0)
				result = result - pp4;
			while(result.BICompareABS(pp2) > 0)
				result = result - pp2;
			while(result.BICompareABS(pp) > 0)
				result = result - pp;
			ma1 >>= 4;
		}
		t = t->next;
	}

	for(i = 0; i < 16; ++i)
		pre_a[i].clear();
	a.clear();
	b.clear();
	pp2.clear();
	pp4.clear();
	pp8.clear();
	return result;
}

BigInt BImodexp(const BigInt& p1, const BigInt& p2, const BigInt pp)
{
	BigInt a, b, result;

	a = p1 % pp;
	b.copy(p2);
	if(a.BIlisZero())
		return result;
	if(b.BIlisZero())
	{
		++result;
		return result;
	}
	++result;

	do{
		if((b.head->num & 1) == 1)
			result = BImodmul(a, result, pp);
		b >>= 1;
		if(! b.BIlisZero())
			a = BImodmul(a, a, pp);
	}while(! b.BIlisZero());

	a.clear();
	b.clear();
	return result;
}

BigInt BImodpow2(const BigInt& p1, const BigInt& pp, const int& d)
{
	BigInt result;
	int i;

	result.copy(p1);
	for(i = d; i > 0; --i)
		result = BImodmul(result, result, pp);

	return result;
}
void MakePreTable(const BigInt& p, const BigInt& pp)
{
	int i;
	PreTable[0].setZero();
	++PreTable[0];
	PreTable[1].copy(p);
	for(i = 2; i < 16; ++i)
		PreTable[i] = BImodmul2(PreTable[i - 1], p, pp);
}

BigInt BImodexp2(const BigInt& p1, const BigInt& p2, const BigInt pp)
{
	BigInt a, b, result;
	unsigned int tmp;
	int iz, Lt, count, kZero;

	if(p1.BIlisZero())
		return result;
	++result;
	if(p2.BIlisZero())
		return result;

	a = p1 % pp;
	b.copy(p2);
	if(a.BICompareABS(PreTable[1]) != 0)
		MakePreTable(a, pp);

	Lt = b.nodeNumber();
	count = 32 * Lt;
	intNode* t = b.head;
	if(! TheLastNode(t))
	{
		result.positive = false;
		return result;
	}
	kZero = FindZeroBit(t->num);
	b <<= kZero;
	count -= kZero;
	do{
		tmp = (t->num & 0xF0000000);
		if(count > 3)
		{
			tmp >>= 28;

			b <<= 4;
			count -= 4;
		}
		else
		{
			tmp >>= (32 - count);
			b <<= count;
			count = 0;
		}
		result = BImodmul2(result, PreTable[tmp & 0x0f], pp);
		iz = 0;
		if(count != 0)
		{
			while(((t->num & 0x80000000) != 0x80000000) && (count > 0))
			{
				b <<= 1;
				--count;
				++iz;
			}
			if(count > 3)
				iz += 4;
			else
				iz += count;
			result = BImodpow2(result, pp, iz);
		}
	}while(count != 0);

	a.clear();
	b.clear();

	return result;
}
intNode* BigInt::getHead() const
{
	return head;
}
void BigInt::print(int choose)
{
	char* ch;
	int lent;
	
	switch(choose)
	{
	case 1:
		ch = outputDEC(lent);
		break;
	case 2:
		ch = outputHEX(lent);
		break;
	case 3:
		ch = outputSTR(lent);
		break;
	default:
		break;
	}

	for(int i = 0; i < lent; ++i)
		cout << ch[i];
	cout << endl;
	delete[] ch;
}