bint.h

大数运算类,用于RSA算法,支持4096位二进制的数学运算

#include "afxwin.h"
#ifndef __CBint__
#define __CBint__

#define BI_MAXLEN 512
typedef enum _NUMERIC_SYSTEM
{	AUTO_SYSTEM		=0,
	BIN_SYSTEM		=2,
	OCT_SYSTEM		=8,
	DEC_SYSTEM		=10,
	HEX_SYSTEM		=16
}NUMERIC_SYSTEM;

class CBint
{
private:
	NUMERIC_SYSTEM m_InSystem;			//字符串赋值时默认的数据进制
	NUMERIC_SYSTEM m_OutSystem;			//字符串输出时默认的数据进制
	void InitData();					//初始化类成员变量
public:
	int m_Sign;							//记录大数的符号，支持负值运算
	int m_Length;						//记录0x100000000进制的位数，0-40之间，相当于2进制的0-1280位
	unsigned long m_Value[BI_MAXLEN];   //记录每一位的“数字”

	CBint();
	CBint(const CBint& Value);
	CBint(const /*unsigned*/ __int64 Value);
	CBint(LPCSTR Value);
	CBint(const CString& Value);
	~CBint();

	NUMERIC_SYSTEM InSystem() { return m_InSystem; }		//输入数据的进制
	NUMERIC_SYSTEM OutSystem() { return m_OutSystem; }		//输出数据的进制
	bool SetInSystem(NUMERIC_SYSTEM Value)
	{	bool Result=false;
		switch(Value)
		{	case AUTO_SYSTEM:
			case BIN_SYSTEM:
			case OCT_SYSTEM:
			case DEC_SYSTEM:
			case HEX_SYSTEM:
				m_InSystem=Value;
				Result=true;
				break;
		}
		return true;
	}
	bool SetOutSystem(NUMERIC_SYSTEM Value)
	{	bool Result=false;
		switch(Value)
		{	case AUTO_SYSTEM:
			case BIN_SYSTEM:
			case OCT_SYSTEM:
			case DEC_SYSTEM:
			case HEX_SYSTEM:
				m_OutSystem=Value;
				Result=true;
				break;
		}
		return Result;
	}

	//将大数赋值为另一个大数 
	CBint& SetValue(const CBint& Src);
	CBint& SetValue(const /*unsigned*/ __int64 intValue); 
	CBint& SetValue(const CString& szValue);

	CBint& operator = (const /*unsigned*/ __int64 Value);
	CBint& operator = (const CString& szValue);
	CBint& operator = (LPCSTR szValue);
	
	operator CString() const;
	unsigned long operator[](int nIndex) const;
	
	//将输入的10进制或16进制字符串转换成大数
	int InPutFromStr(CString& str, const unsigned int system=AUTO_SYSTEM);
	//将大数按10进制或16进制格式输出到字符串
	int OutPutToStr(CString& str, const unsigned int system=DEC_SYSTEM);
	
	//比较两个大数大小 若A>B,则返回1,相等返回0,否则返回-1
	int Compare(const CBint& B) const;
	int Compare(long B) const;
	int CompareAbs(const CBint& B) const;
	int CompareAbs(unsigned long B) const;
	//----------------------------------------------------------
	const friend bool operator > (const CBint& A,const CBint& B)
	{
		return(A.Compare(B)>0);
	}
	const friend bool operator > (const CBint&A,long B)
	{
		return(A.Compare(B)>0);
	}
	const friend bool operator > (long A,CBint &B)
	{
		return(B.Compare(A)<0);
	}
	//---------------------------------------------------------
	const friend bool operator < (const CBint& A,const CBint &B)
	{
		return(A.Compare(B)<0);
	}
	const friend bool operator < (const CBint A,long B)
	{
		return(A.Compare(B)<0);
	}
	const friend bool operator < (long A,const CBint&B)
	{
		return(B.Compare(A)>0);
	}
	//----------------------------------------------------------
	const friend bool operator >= (const CBint& A,const CBint& B)
	{
		return(A.Compare(B)>=0);
	}
	const friend bool operator >= (const CBint&A,long B)
	{
		return(A.Compare(B)>=0);
	}
	const friend bool operator >= (long A,CBint &B)
	{
		return(B.Compare(A)<=0);
	}
	//---------------------------------------------------------
	const friend bool operator <= (const CBint& A,const CBint &B)
	{
		return(A.Compare(B)<=0);
	}
	const friend bool operator <= (const CBint A,long B)
	{
		return(A.Compare(B)<=0);
	}
	const friend bool operator <= (long A,const CBint&B)
	{
		return(B.Compare(A)>=0);
	}
	//----------------------------------------------------------
	//计算两个大数的和 
	CBint Add(const CBint& B) const;
	CBint Add(long B) const;
	// N+=B
	CBint& operator +=(const CBint &B) 
	{
		*this=Add(B);
		return *this;
	}
	CBint& operator +=(long B)
	{
		*this=Add(B);
		return *this;
	}
	//++前缀,调用形式 ++N
	CBint& operator ++()			
	{	int i=0;
		if(m_Sign==1)
		{	while(m_Value[i]==0xFFFFFFFF)
			{	m_Value[i]=0;
				i++;
			}
			m_Value[i]++;
			if(i<BI_MAXLEN && i>0)
				m_Length=i+1;
		}
		else
		{	while(m_Value[i]==0)
			{	m_Value[i]=0xFFFFFFFF;
				i++;
			}
			if(i>0 && m_Value[i]==1)
				m_Length--;
			m_Value[i]--;
		}
		return *this;
	}
	//后缀++,调用形式 N++
	const CBint operator ++(int)	
	{	CBint old(*this);
		++(*this);
		return old;
	}
	//----------------------------------------------------------
	const friend CBint operator + (const CBint &A,const CBint& B)
	{	
		return A.Add(B);
	}
	const friend CBint operator + (const CBint &A,long B)
	{
		return A.Add(B);
	}
	const friend CBint operator + (long A,const CBint &B)
	{
		return B.Add(A);
	}

	//计算两个大数的差
	CBint Sub(const CBint& B) const;
	CBint Sub(long B) const;
	// N-=B
	CBint& operator -=(const CBint &B)
	{
		*this=Sub(B);
		return *this;
	}
	CBint& operator -=(long B)
	{
		*this=Sub(B);
		return *this;
	}
	//--前缀,调用形式 --N
	CBint& operator --()			
	{	int i=0;
		if(m_Sign==1)
		{	while(m_Value[i]==0)
			{
				m_Value[i]=0xFFFFFFFF;
				i++;
			}
			if(i>0 && m_Value[i]==1)
				m_Length--;
			m_Value[i]--;
		}
		else
		{	while(m_Value[i]==0xFFFFFFFF)
			{	m_Value[i]=0;
				i++;
			}
			m_Value[i]++;
			if(i<BI_MAXLEN && i>0)
				m_Length=i+1;
		}
		return *this;
	}
	//后缀--,调用形式 N--
	const CBint operator --(int)	
	{
		CBint old(*this);
		--(*this);
		return old;
	}
	//----------------------------------------------------------
	CBint operator - () const
	{	CBint X(*this);
		X.m_Sign=1-X.m_Sign;
		return X;
	}
	const friend CBint operator - (const CBint& A,const CBint& B)
	{
		return A.Sub(B);
	}
	const friend CBint operator - (const CBint& A,long B)
	{
		return A.Sub(B);
	}
	const friend CBint operator - (long A,const CBint &B)
	{
		return B.Sub(A);
	}
	//----------------------------------------------------------
	//计算两个大数的积
	CBint Mul(const CBint& B) const;
	CBint Mul(long B) const;
	CBint& operator *= (const CBint& B)
	{
		*this=Mul(B);
		return *this;
	}
	CBint& operator *= (long B)
	{
		*this=Mul(B);
		return *this;
	}
	//----------------------------------------------------------
	CBint operator * (const CBint& B)
	{
		return Mul(B);
	}
	CBint operator * (long B)
	{
		return Mul(B);
	}
	const friend CBint operator * (long A,const CBint& B)
	{
		return B.Mul(A);
	}
	//重载函数以支持大数与普通整数相乘

	//计算两个大数的商
	CBint Div(const CBint& A) const;
	CBint Div(long A) const;
	CBint& operator /= (const CBint& B)
	{
		*this=Div(B);
		return *this;
	}
	CBint& operator /= (long B)
	{
		*this=Div(B);
		return *this;
	}
	//----------------------------------------------------------
	CBint operator / (const CBint& B)
	{
		return Div(B);
	}
	CBint operator / (long B)
	{
		return Div(B);
	}
	const friend CBint operator / (long A,const CBint& B)
	{
		return CBint(A).Div(B);
	}
	//----------------------------------------------------------
	//计算两个大数相除的余数
	CBint Mod(const CBint& A) const;
	long Mod(long A) const; 
	long ModAbs(long A) const;
	CBint& operator %=(const CBint& B)
	{
		*this=Mod(B);
		return *this;
	}
	CBint& operator %=(long A)
	{
		*this=Mod(A);
		return *this;
	}
	//欧几里德算法求：Y=X.Euc(A)，使满足：YX mod A = 1
	CBint Euc(CBint& A);

	//蒙哥马利算法求：Y=X.Mon(A,B)，使满足：X^A mod B = Y
	CBint Mon(CBint& A, CBint& B);

	//求X^Y次方 mod N
	CBint Powmod(CBint Y,CBint N);
	CBint Powmod(unsigned long Y,CBint N);
	
	//判断是否为素数
	bool IsPrimeNumber();
	CBint Sqrt();
	static CBint Sqrt(CBint X)
	{
		return X.Sqrt();
	}
	CBint Abs()
	{	if(m_Sign==0)
		{
			CBint X(*this);
			X.m_Sign=1;
			return X;
		}
		return *this;
	}
};

#endif