#pragma	src	"/sys/src/libmp"#pragma	lib	"libmp.a" #define _MPINT 1 // the code assumes mpdigit to be at least an int// mpdigit must be an atomic type.  mpdigit is defined// in the architecture specific u.h typedef struct mpint mpint; struct mpint{	int	sign;	// +1 or -1	int	size;	// allocated digits	int	top;	// significant digits	mpdigit	*p;	char	flags;}; enum{	MPstatic=	0x01,	Dbytes=		sizeof(mpdigit),	// bytes per digit	Dbits=		Dbytes*8		// bits per digit}; // allocationvoid	mpsetminbits(int n);	// newly created mpint's get at least n bitsmpint*	mpnew(int n);		// create a new mpint with at least n bitsvoid	mpfree(mpint *b);void	mpbits(mpint *b, int n);	// ensure that b has at least n bitsvoid	mpnorm(mpint *b);		// dump leading zerosmpint*	mpcopy(mpint *b);void	mpassign(mpint *old, mpint *new); // random bitsmpint*	mprand(int bits, void (*gen)(uchar*, int), mpint *b); // conversionmpint*	strtomp(char*, char**, int, mpint*);	// asciiint	mpfmt(Fmt*);char*	mptoa(mpint*, int, char*, int);mpint*	letomp(uchar*, uint, mpint*);	// byte array, little-endianint	mptole(mpint*, uchar*, uint, uchar**);mpint*	betomp(uchar*, uint, mpint*);	// byte array, little-endianint	mptobe(mpint*, uchar*, uint, uchar**);uint	mptoui(mpint*);			// unsigned intmpint*	uitomp(uint, mpint*);int	mptoi(mpint*);			// intmpint*	itomp(int, mpint*);uvlong	mptouv(mpint*);			// unsigned vlongmpint*	uvtomp(uvlong, mpint*);vlong	mptov(mpint*);			// vlongmpint*	vtomp(vlong, mpint*); // divide 2 digits by onevoid	mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient); // in the following, the result mpint may be// the same as one of the inputs.void	mpadd(mpint *b1, mpint *b2, mpint *sum);	// sum = b1+b2void	mpsub(mpint *b1, mpint *b2, mpint *diff);	// diff = b1-b2void	mpleft(mpint *b, int shift, mpint *res);	// res = b<<shiftvoid	mpright(mpint *b, int shift, mpint *res);	// res = b>>shiftvoid	mpmul(mpint *b1, mpint *b2, mpint *prod);	// prod = b1*b2void	mpexp(mpint *b, mpint *e, mpint *m, mpint *res);	// res = b**e mod mvoid	mpmod(mpint *b, mpint *m, mpint *remainder);	// remainder = b mod m // quotient = dividend/divisor, remainder = dividend % divisorvoid	mpdiv(mpint *dividend, mpint *divisor,  mpint *quotient, mpint *remainder); // return neg, 0, pos as b1-b2 is neg, 0, posint	mpcmp(mpint *b1, mpint *b2); // extended gcd return d, x, and y, s.t. d = gcd(a,b) and ax+by = dvoid	mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x, mpint *y); // res = b**-1 mod mvoid	mpinvert(mpint *b, mpint *m, mpint *res); // bit countingint	mpsignif(mpint*);	// number of sigificant bits in mantissaint	mplowbits0(mpint*);	// k, where n = 2**k * q for odd q // well known constantsextern mpint	*mpzero, *mpone, *mptwo; // sum[0:alen] = a[0:alen-1] + b[0:blen-1]// prereq: alen >= blen, sum has room for alen+1 digitsvoid	mpvecadd(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *sum); // diff[0:alen-1] = a[0:alen-1] - b[0:blen-1]// prereq: alen >= blen, diff has room for alen digitsvoid	mpvecsub(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *diff); // p[0:n] += m * b[0:n-1]// prereq: p has room for n+1 digitsvoid	mpvecdigmuladd(mpdigit *b, int n, mpdigit m, mpdigit *p); // p[0:n] -= m * b[0:n-1]// prereq: p has room for n+1 digitsint	mpvecdigmulsub(mpdigit *b, int n, mpdigit m, mpdigit *p); // p[0:alen*blen-1] = a[0:alen-1] * b[0:blen-1]// prereq: alen >= blen, p has room for m*n digitsvoid	mpvecmul(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *p); // sign of a - b or zero if the sameint	mpveccmp(mpdigit *a, int alen, mpdigit *b, int blen); // divide the 2 digit dividend by the one digit divisor and stick in quotient// we assume that the result is one digit - overflow is all 1'svoid	mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient); // playing with magnitudesint	mpmagcmp(mpint *b1, mpint *b2);void	mpmagadd(mpint *b1, mpint *b2, mpint *sum);	// sum = b1+b2void	mpmagsub(mpint *b1, mpint *b2, mpint *sum);	// sum = b1+b2 // chinese remainder theoremtypedef struct CRTpre	CRTpre;		// precomputed values for converting					//  twixt residues and mpinttypedef struct CRTres	CRTres;		// residue form of an mpint struct CRTres{	int	n;		// number of residues	mpint	*r[1];		// residues}; CRTpre*	crtpre(int, mpint**);			// precompute conversion valuesCRTres*	crtin(CRTpre*, mpint*);			// convert mpint to residuesvoid	crtout(CRTpre*, CRTres*, mpint*);	// convert residues to mpintvoid	crtprefree(CRTpre*);void	crtresfree(CRTres*);  #pragma	varargck	type	"B"	mpint*