//428

#ifndef CLASS_BIGINT
#define CALSS_BIGINT
#define TOTALBITS 64
#define TOTALBOXS 66
#define FULL 0xFFFFFFFFFFFFFFFF
#define ZERO 0x0

#define MAXDEC 0x3B9ACA00
#define MAXDEC2 0x0DE0B6B3A7640000
#define LenMAXHEX 16
#define LenMAXWRD 8
#define LenMAXDEC 9
#define LenZ 15
#include<iostream>
#include<string>
using namespace std;
class BigInt
{
public:
	BigInt();
	virtual ~BigInt();
	unsigned __int64 iVal[TOTALBOXS];   //value
    unsigned short iIdx;

	void setZero();
	void setFull();
	void setUpperBlock(const short & which);
	void loadDEC(const string itext);
	void loadHEX(const string itext);
	void loadSTR(const string itext);
	string outputDEC();
	string outputHEX();
	string outputSTR();
	BigInt & operator<<=(const short & iBit);
	BigInt & operator>>=(const short & iBit);
	BigInt & operator=(const BigInt & p1);
	BigInt & operator=(const unsigned __int64 & p1);
/*	friend BigInt operator +(const BigInt & p1,const BigInt & p2);
	friend BigInt operator +(const BigInt & p1,const unsigned __int64 & p2);

	//429
    friend BigInt operator-(const BigInt & p1,const BigInt & p2);
	friend BigInt operator*(const BigInt & p1,const BigInt & p2);
	friend BigInt operator*(const BigInt & p1,const unsigned __int64 & p2);
	friend BigInt operator/(const BigInt & p1,const BigInt & p2);
	friend BigInt operator%(const BigInt & p1,const BigInt & p2);
	friend inline bool operator>(const BigInt & p1,const BigInt & p2);
	friend inline bool operator==(const BigInt & p1,const BigInt & p2);
	friend inline bool operator!=(BigInt & p1,BigInt & p2);*/
	BigInt & operator ++(int);
	BigInt & operator --(int);
	short Get8BitBlock(const short & unUseHeader,const short & BitIndex);
	unsigned char Get4BitBlock(const short & which);
	unsigned char Get8BitBlock(const short & which);
	unsigned short Get12BitBlock(const short & which);
	unsigned char Get4BitBlockZero();
	unsigned __int64 First64Bits();
	unsigned __int64 First32Bits();
	void ShiftAdd(const unsigned __int64 p1);
};

unsigned char hdigit(unsigned char c);
bool BIisZero(const BigInt & x);
int BIcompare(const BigInt & p1,const BigInt & p2);
int BIcompare(const BigInt & p1,const unsigned __int64 & p2);
void BIswap(BigInt & p1,BigInt & p2);
BigInt BIdivision(const BigInt & p1,const BigInt & p2,BigInt & pr);
BigInt BImodmul(const BigInt & p1,const BigInt & p2,const BigInt & pp);
BigInt BImodmul2(const BigInt & p1,const BigInt & p2,const BigInt & pb);
BigInt BImodexp(const BigInt & p1,const BigInt & p2,const BigInt & pp);
BigInt BIgcd(const BigInt & p1,const BigInt & p2);
BigInt BIinverse(const BigInt & p1,const BigInt & p2); //求可逆數計算
BigInt BImodpow2(const BigInt & p1,const BigInt & pp,const short & d);
//建立預處理表
void MakePreTable(const BigInt & p1,const BigInt & pp);
//兩個大整數模乘（預處理）
BigInt BImodmulPre(const BigInt &  p2,const BigInt & pp);
//大整數（預處理）
BigInt BImodexpPre(const BigInt & p1,const BigInt & p2,const BigInt & pp);
BigInt BImodexpPre2(const BigInt & p1,const BigInt & p2,const BigInt & pp);
void BImul(const unsigned __int64 & p1,const unsigned __int64 & p2,unsigned __int64 & high,unsigned __int64 & low);
void MakeThemClose(const BigInt & p1,BigInt & p2);
short FindZeroBit(const unsigned __int64 & p1);
void MakeModBaseTable(const BigInt & pp);

//430

//建立預處理表（乘法積）
void MakeModMultTable(const BigInt & pp);
//Montgomery乘法
BigInt MontMult(BigInt & p1,BigInt & p2,BigInt & pp);
//Montgomery模冪
BigInt MontExpo(BigInt & p1,BigInt &p2,BigInt & pp);

#endif