sys/include/mp.h

   1 #pragma src     "/sys/src/libmp"
   2 #pragma lib     "libmp.a"
   3
   4 #define _MPINT 1
   5
   6 /*
   7  * the code assumes mpdigit to be at least an int
   8  * mpdigit must be an atomic type.  mpdigit is defined
   9  * in the architecture specific u.h
  10  */
  11 typedef struct mpint mpint;
  12
  13 struct mpint
  14 {
  15         int     sign;   /* +1 or -1 */
  16         int     size;   /* allocated digits */
  17         int     top;    /* significant digits */
  18         mpdigit *p;
  19         char    flags;
  20 };
  21
  22 enum
  23 {
  24         MPstatic=       0x01,   /* static constant */
  25         MPnorm=         0x02,   /* normalization status */
  26         MPtimesafe=     0x04,   /* request time invariant computation */
  27         MPfield=        0x08,   /* this mpint is a field modulus */
  28
  29         Dbytes=         sizeof(mpdigit),        /* bytes per digit */
  30         Dbits=          Dbytes*8                /* bits per digit */
  31 };
  32
  33 /* allocation */
  34 void    mpsetminbits(int n);    /* newly created mpint's get at least n bits */
  35 mpint*  mpnew(int n);           /* create a new mpint with at least n bits */
  36 void    mpfree(mpint *b);
  37 void    mpbits(mpint *b, int n);        /* ensure that b has at least n bits */
  38 mpint*  mpnorm(mpint *b);               /* dump leading zeros */
  39 mpint*  mpcopy(mpint *b);
  40 void    mpassign(mpint *old, mpint *new);
  41
  42 /* random bits */
  43 mpint*  mprand(int bits, void (*gen)(uchar*, int), mpint *b);
  44 /* return uniform random [0..n-1] */
  45 mpint*  mpnrand(mpint *n, void (*gen)(uchar*, int), mpint *b);
  46
  47 /* conversion */
  48 mpint*  strtomp(char*, char**, int, mpint*);    /* ascii */
  49 int     mpfmt(Fmt*);
  50 char*   mptoa(mpint*, int, char*, int);
  51 mpint*  letomp(uchar*, uint, mpint*);   /* byte array, little-endian */
  52 int     mptole(mpint*, uchar*, uint, uchar**);
  53 void    mptolel(mpint *b, uchar *p, int n);
  54 mpint*  betomp(uchar*, uint, mpint*);   /* byte array, big-endian */
  55 int     mptobe(mpint*, uchar*, uint, uchar**);
  56 void    mptober(mpint *b, uchar *p, int n);
  57 uint    mptoui(mpint*);                 /* unsigned int */
  58 mpint*  uitomp(uint, mpint*);
  59 int     mptoi(mpint*);                  /* int */
  60 mpint*  itomp(int, mpint*);
  61 uvlong  mptouv(mpint*);                 /* unsigned vlong */
  62 mpint*  uvtomp(uvlong, mpint*);
  63 vlong   mptov(mpint*);                  /* vlong */
  64 mpint*  vtomp(vlong, mpint*);
  65
  66 /* divide 2 digits by one */
  67 void    mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient);
  68
  69 /* in the following, the result mpint may be */
  70 /* the same as one of the inputs. */
  71 void    mpadd(mpint *b1, mpint *b2, mpint *sum);        /* sum = b1+b2 */
  72 void    mpsub(mpint *b1, mpint *b2, mpint *diff);       /* diff = b1-b2 */
  73 void    mpleft(mpint *b, int shift, mpint *res);        /* res = b<<shift */
  74 void    mpright(mpint *b, int shift, mpint *res);       /* res = b>>shift */
  75 void    mpmul(mpint *b1, mpint *b2, mpint *prod);       /* prod = b1*b2 */
  76 void    mpexp(mpint *b, mpint *e, mpint *m, mpint *res);        /* res = b**e mod m */
  77 void    mpmod(mpint *b, mpint *m, mpint *remainder);    /* remainder = b mod m */
  78
  79 /* logical operations */
  80 void    mpand(mpint *b1, mpint *b2, mpint *res);
  81 void    mpbic(mpint *b1, mpint *b2, mpint *res);
  82 void    mpor(mpint *b1, mpint *b2, mpint *res);
  83 void    mpnot(mpint *b, mpint *res);
  84 void    mpxor(mpint *b1, mpint *b2, mpint *res);
  85 void    mptrunc(mpint *b, int n, mpint *res);
  86 void    mpxtend(mpint *b, int n, mpint *res);
  87 void    mpasr(mpint *b, int shift, mpint *res);
  88
  89 /* modular arithmetic, time invariant when 0≤b1≤m-1 and 0≤b2≤m-1 */
  90 void    mpmodadd(mpint *b1, mpint *b2, mpint *m, mpint *sum);   /* sum = b1+b2 % m */
  91 void    mpmodsub(mpint *b1, mpint *b2, mpint *m, mpint *diff);  /* diff = b1-b2 % m */
  92 void    mpmodmul(mpint *b1, mpint *b2, mpint *m, mpint *prod);  /* prod = b1*b2 % m */
  93
  94 /* quotient = dividend/divisor, remainder = dividend % divisor */
  95 void    mpdiv(mpint *dividend, mpint *divisor,  mpint *quotient, mpint *remainder);
  96
  97 /* return neg, 0, pos as b1-b2 is neg, 0, pos */
  98 int     mpcmp(mpint *b1, mpint *b2);
  99
 100 /* res = s != 0 ? b1 : b2 */
 101 void    mpsel(int s, mpint *b1, mpint *b2, mpint *res);
 102
 103 /* extended gcd return d, x, and y, s.t. d = gcd(a,b) and ax+by = d */
 104 void    mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x, mpint *y);
 105
 106 /* res = b**-1 mod m */
 107 void    mpinvert(mpint *b, mpint *m, mpint *res);
 108
 109 /* bit counting */
 110 int     mpsignif(mpint*);       /* number of sigificant bits in mantissa */
 111 int     mplowbits0(mpint*);     /* k, where n = 2**k * q for odd q */
 112
 113 /* well known constants */
 114 extern mpint    *mpzero, *mpone, *mptwo;
 115
 116 /* sum[0:alen] = a[0:alen-1] + b[0:blen-1] */
 117 /* prereq: alen >= blen, sum has room for alen+1 digits */
 118 void    mpvecadd(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *sum);
 119
 120 /* diff[0:alen-1] = a[0:alen-1] - b[0:blen-1] */
 121 /* prereq: alen >= blen, diff has room for alen digits */
 122 void    mpvecsub(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *diff);
 123
 124 /* p[0:n] += m * b[0:n-1] */
 125 /* prereq: p has room for n+1 digits */
 126 void    mpvecdigmuladd(mpdigit *b, int n, mpdigit m, mpdigit *p);
 127
 128 /* p[0:n] -= m * b[0:n-1] */
 129 /* prereq: p has room for n+1 digits */
 130 int     mpvecdigmulsub(mpdigit *b, int n, mpdigit m, mpdigit *p);
 131
 132 /* p[0:alen+blen-1] = a[0:alen-1] * b[0:blen-1] */
 133 /* prereq: alen >= blen, p has room for m*n digits */
 134 void    mpvecmul(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *p);
 135 void    mpvectsmul(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *p);
 136
 137 /* sign of a - b or zero if the same */
 138 int     mpveccmp(mpdigit *a, int alen, mpdigit *b, int blen);
 139 int     mpvectscmp(mpdigit *a, int alen, mpdigit *b, int blen);
 140
 141 /* divide the 2 digit dividend by the one digit divisor and stick in quotient */
 142 /* we assume that the result is one digit - overflow is all 1's */
 143 void    mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient);
 144
 145 /* playing with magnitudes */
 146 int     mpmagcmp(mpint *b1, mpint *b2);
 147 void    mpmagadd(mpint *b1, mpint *b2, mpint *sum);     /* sum = b1+b2 */
 148 void    mpmagsub(mpint *b1, mpint *b2, mpint *sum);     /* sum = b1+b2 */
 149
 150 /* chinese remainder theorem */
 151 typedef struct CRTpre   CRTpre;         /* precomputed values for converting */
 152                                         /*  twixt residues and mpint */
 153 typedef struct CRTres   CRTres;         /* residue form of an mpint */
 154
 155 #pragma incomplete CRTpre
 156
 157 struct CRTres
 158 {
 159         int     n;              /* number of residues */
 160         mpint   *r[1];          /* residues */
 161 };
 162
 163 CRTpre* crtpre(int, mpint**);                   /* precompute conversion values */
 164 CRTres* crtin(CRTpre*, mpint*);                 /* convert mpint to residues */
 165 void    crtout(CRTpre*, CRTres*, mpint*);       /* convert residues to mpint */
 166 void    crtprefree(CRTpre*);
 167 void    crtresfree(CRTres*);
 168
 169 /* fast field arithmetic */
 170 typedef struct Mfield   Mfield;
 171
 172 struct Mfield
 173 {
 174         mpint;
 175         int     (*reduce)(Mfield*, mpint*, mpint*);
 176 };
 177
 178 mpint *mpfield(mpint*);
 179
 180 Mfield *gmfield(mpint*);
 181 Mfield *cnfield(mpint*);
 182
 183 #pragma varargck        type    "B"     mpint*