1 #define _MPINT 1 2 3 // the code assumes mpdigit to be at least an int 4 // mpdigit must be an atomic type. mpdigit is defined 5 // in the architecture specific u.h 6 7 typedef struct mpint mpint; 8 9 struct mpint 10 { 11 int sign; // +1 or -1 12 int size; // allocated digits 13 int top; // significant digits 14 mpdigit *p; 15 char flags; 16 }; 17 18 enum 19 { 20 MPstatic= 0x01, 21 Dbytes= sizeof(mpdigit), // bytes per digit 22 Dbits= Dbytes*8 // bits per digit 23 }; 24 25 // allocation 26 void mpsetminbits(int n); // newly created mpint's get at least n bits 27 mpint* mpnew(int n); // create a new mpint with at least n bits 28 void mpfree(mpint *b); 29 void mpbits(mpint *b, int n); // ensure that b has at least n bits 30 void mpnorm(mpint *b); // dump leading zeros 31 mpint* mpcopy(mpint *b); 32 void mpassign(mpint *old, mpint *new); 33 34 // random bits 35 mpint* mprand(int bits, void (*gen)(uchar*, int), mpint *b); 36 37 // conversion 38 mpint* strtomp(char*, char**, int, mpint*); // ascii 39 int mpfmt(Fmt*); 40 char* mptoa(mpint*, int, char*, int); 41 mpint* letomp(uchar*, uint, mpint*); // byte array, little-endian 42 int mptole(mpint*, uchar*, uint, uchar**); 43 mpint* betomp(uchar*, uint, mpint*); // byte array, little-endian 44 int mptobe(mpint*, uchar*, uint, uchar**); 45 uint mptoui(mpint*); // unsigned int 46 mpint* uitomp(uint, mpint*); 47 int mptoi(mpint*); // int 48 mpint* itomp(int, mpint*); 49 uvlong mptouv(mpint*); // unsigned vlong 50 mpint* uvtomp(uvlong, mpint*); 51 vlong mptov(mpint*); // vlong 52 mpint* vtomp(vlong, mpint*); 53 54 // divide 2 digits by one 55 void mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient); 56 57 // in the following, the result mpint may be 58 // the same as one of the inputs. 59 void mpadd(mpint *b1, mpint *b2, mpint *sum); // sum = b1+b2 60 void mpsub(mpint *b1, mpint *b2, mpint *diff); // diff = b1-b2 61 void mpleft(mpint *b, int shift, mpint *res); // res = b<<shift 62 void mpright(mpint *b, int shift, mpint *res); // res = b>>shift 63 void mpmul(mpint *b1, mpint *b2, mpint *prod); // prod = b1*b2 64 void mpexp(mpint *b, mpint *e, mpint *m, mpint *res); // res = b**e mod m 65 void mpmod(mpint *b, mpint *m, mpint *remainder); // remainder = b mod m 66 67 // quotient = dividend/divisor, remainder = dividend % divisor 68 void mpdiv(mpint *dividend, mpint *divisor, mpint *quotient, mpint *remainder); 69 70 // return neg, 0, pos as b1-b2 is neg, 0, pos 71 int mpcmp(mpint *b1, mpint *b2); 72 73 // extended gcd return d, x, and y, s.t. d = gcd(a,b) and ax+by = d 74 void mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x, mpint *y); 75 76 // res = b**-1 mod m 77 void mpinvert(mpint *b, mpint *m, mpint *res); 78 79 // bit counting 80 int mpsignif(mpint*); // number of sigificant bits in mantissa 81 int mplowbits0(mpint*); // k, where n = 2**k * q for odd q 82 83 // well known constants 84 extern mpint *mpzero, *mpone, *mptwo; 85 86 // sum[0:alen] = a[0:alen-1] + b[0:blen-1] 87 // prereq: alen >= blen, sum has room for alen+1 digits 88 void mpvecadd(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *sum); 89 90 // diff[0:alen-1] = a[0:alen-1] - b[0:blen-1] 91 // prereq: alen >= blen, diff has room for alen digits 92 void mpvecsub(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *diff); 93 94 // p[0:n] += m * b[0:n-1] 95 // prereq: p has room for n+1 digits 96 void mpvecdigmuladd(mpdigit *b, int n, mpdigit m, mpdigit *p); 97 98 // p[0:n] -= m * b[0:n-1] 99 // prereq: p has room for n+1 digits 100 int mpvecdigmulsub(mpdigit *b, int n, mpdigit m, mpdigit *p); 101 102 // p[0:alen*blen-1] = a[0:alen-1] * b[0:blen-1] 103 // prereq: alen >= blen, p has room for m*n digits 104 void mpvecmul(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *p); 105 106 // sign of a - b or zero if the same 107 int mpveccmp(mpdigit *a, int alen, mpdigit *b, int blen); 108 109 // divide the 2 digit dividend by the one digit divisor and stick in quotient 110 // we assume that the result is one digit - overflow is all 1's 111 void mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient); 112 113 // playing with magnitudes 114 int mpmagcmp(mpint *b1, mpint *b2); 115 void mpmagadd(mpint *b1, mpint *b2, mpint *sum); // sum = b1+b2 116 void mpmagsub(mpint *b1, mpint *b2, mpint *sum); // sum = b1+b2 117 118 // chinese remainder theorem 119 typedef struct CRTpre CRTpre; // precomputed values for converting 120 // twixt residues and mpint 121 typedef struct CRTres CRTres; // residue form of an mpint 122 123 struct CRTres 124 { 125 int n; // number of residues 126 mpint *r[1]; // residues 127 }; 128 129 CRTpre* crtpre(int, mpint**); // precompute conversion values 130 CRTres* crtin(CRTpre*, mpint*); // convert mpint to residues 131 void crtout(CRTpre*, CRTres*, mpint*); // convert residues to mpint 132 void crtprefree(CRTpre*); 133 void crtresfree(CRTres*); 134 135