MP(3)                                                       MP(3)

          mpsetminbits, mpnew, mpfree, mpbits, mpnorm, mpcopy,
          mpassign, mprand, strtomp, mpfmt,mptoa, betomp, mptobe,
          letomp, mptole, mptoui, uitomp, mptoi, itomp, uvtomp,
          mptouv, vtomp, mptov, mpdigdiv, mpadd, mpsub, mpleft,
          mpright, mpmul, mpexp, mpmod, mpdiv, mpfactorial, mpcmp,
          mpextendedgcd, mpinvert, mpsignif, mplowbits0,
          mpvecdigmuladd, mpvecdigmulsub, mpvecadd, mpvecsub,
          mpveccmp, mpvecmul, mpmagcmp, mpmagadd, mpmagsub, crtpre,
          crtin, crtout, crtprefree, crtresfree - extended precision

          #include <u.h>
          #include <libc.h>
          #include <mp.h>

          mpint*    mpnew(int n)

          void mpfree(mpint *b)

          void mpsetminbits(int n)

          void mpbits(mpint *b, int n)

          void mpnorm(mpint *b)

          mpint*    mpcopy(mpint *b)

          void mpassign(mpint *old, mpint *new)

          mpint*    mprand(int bits, void (*gen)(uchar*, int), mpint

          mpint*    strtomp(char *buf, char **rptr, int base, mpint

          char*     mptoa(mpint *b, int base, char *buf, int blen)

          int  mpfmt(Fmt*)

          mpint*    betomp(uchar *buf, uint blen, mpint *b)

          int  mptobe(mpint *b, uchar *buf, uint blen, uchar **bufp)

          mpint*    letomp(uchar *buf, uint blen, mpint *b)

          int  mptole(mpint *b, uchar *buf, uint blen, uchar **bufp)

          uint mptoui(mpint*)

     MP(3)                                                       MP(3)

          mpint*    uitomp(uint, mpint*)

          int  mptoi(mpint*)

          mpint*    itomp(int, mpint*)

          mpint*    vtomp(vlong, mpint*)

          vlong     mptov(mpint*)

          mpint*    uvtomp(uvlong, mpint*)

          uvlong    mptouv(mpint*)

          void mpadd(mpint *b1, mpint *b2, mpint *sum)

          void mpmagadd(mpint *b1, mpint *b2, mpint *sum)

          void mpsub(mpint *b1, mpint *b2, mpint *diff)

          void mpmagsub(mpint *b1, mpint *b2, mpint *diff)

          void mpleft(mpint *b, int shift, mpint *res)

          void mpright(mpint *b, int shift, mpint *res)

          void mpmul(mpint *b1, mpint *b2, mpint *prod)

          void mpexp(mpint *b, mpint *e, mpint *m, mpint *res)

          void mpmod(mpint *b, mpint *m, mpint *remainder)

          void mpdiv(mpint *dividend, mpint *divisor,  mpint *quo-
          tient, mpint *remainder)

          mpint*    mpfactorial(ulong n)

          int  mpcmp(mpint *b1, mpint *b2)

          int  mpmagcmp(mpint *b1, mpint *b2)

          void mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x,
          mpint *y)

          void mpinvert(mpint *b, mpint *m, mpint *res)

          int  mpsignif(mpint *b)

          int  mplowbits0(mpint *b)

          void mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit

     MP(3)                                                       MP(3)

          void mpvecadd(mpdigit *a, int alen, mpdigit *b, int blen,
          mpdigit *sum)

          void mpvecsub(mpdigit *a, int alen, mpdigit *b, int blen,
          mpdigit *diff)

          void mpvecdigmuladd(mpdigit *b, int n, mpdigit m, mpdigit

          int  mpvecdigmulsub(mpdigit *b, int n, mpdigit m, mpdigit

          void mpvecmul(mpdigit *a, int alen, mpdigit *b, int blen,
          mpdigit *p)

          int  mpveccmp(mpdigit *a, int alen, mpdigit *b, int blen)

          CRTpre*   crtpre(int nfactors, mpint **factors)

          CRTres*   crtin(CRTpre *crt, mpint *x)

          void crtout(CRTpre *crt, CRTres *r, mpint *x)

          void crtprefree(CRTpre *cre)

          void crtresfree(CRTres *res)

          mpint     *mpzero, *mpone, *mptwo

          These routines perform extended precision integer arith-
          metic.  The basic type is mpint, which points to an array of
          mpdigits, stored in little-endian order:

          typedef struct mpint mpint;
          struct mpint
               int  sign;   /* +1 or -1 */
               int  size;   /* allocated digits */
               int  top;    /* significant digits */
               mpdigit   *p;
               char flags;

          The sign of 0 is +1.

          The size of mpdigit is architecture-dependent and defined in
          /$cputype/include/u.h.  Mpints are dynamically allocated and
          must be explicitly freed.  Operations grow the array of dig-
          its as needed.

          In general, the result parameters are last in the argument

     MP(3)                                                       MP(3)


          Routines that return an mpint will allocate the mpint if the
          result parameter is nil.  This includes strtomp, itomp,
          uitomp, and btomp. These functions, in addition to mpnew and
          mpcopy, will return nil if the allocation fails.

          Input and result parameters may point to the same mpint.
          The routines check and copy where necessary.

          Mpnew creates an mpint with an initial allocation of n bits.
          If n is zero, the allocation will be whatever was specified
          in the last call to mpsetminbits or to the initial value,
          1056.  Mpfree frees an mpint.  Mpbits grows the allocation
          of b to fit at least n bits.  If b->top doesn't cover n bits
          it increases it to do so.  Unless you are writing new basic
          operations, you can restrict yourself to mpnew(0) and

          Mpnorm normalizes the representation by trimming any high
          order zero digits.  All routines except mpbits return nor-
          malized results.

          Mpcopy creates a new mpint with the same value as b while
          mpassign sets the value of new to be that of old.

          Mprand creates an n bit random number using the generator
          gen. Gen takes a pointer to a string of uchar's and the num-
          ber to fill in.

          Strtomp and mptoa convert between ASCII and mpint represen-
          tations using the base indicated.  Only the bases 10, 16,
          32, and 64 are supported.  Anything else defaults to 16.
          Strtomp skips any leading spaces or tabs.  Strtomp's scan
          stops when encountering a digit not valid in the base.  If
          rptr is not zero, *rptr is set to point to the character
          immediately after the string converted.  If the parse pter-
          minates before any digits are found, strtomp return nil.
          Mptoa returns a pointer to the filled buffer.  If the param-
          eter buf is nil, the buffer is allocated.  Mpfmt can be used
          with fmtinstall(3) and print(3) to print hexadecimal repre-
          sentations of mpints.

          Mptobe and mptole convert an mpint to a byte array.  The
          former creates a big endian representation, the latter a
          little endian one.  If the destination buf is not nil, it
          specifies the buffer of length blen for the result.  If the
          representation is less than blen bytes, the rest of the
          buffer is zero filled.  If buf is nil, then a buffer is
          allocated and a pointer to it is deposited in the location
          pointed to by bufp. Sign is ignored in these conversions,
          i.e., the byte array version is always positive.

     MP(3)                                                       MP(3)

          Betomp, and letomp convert from a big or little endian byte
          array at buf of length blen to an mpint. If b is not nil, it
          refers to a preallocated mpint for the result.  If b is nil,
          a new integer is allocated and returned as the result.

          The integer conversions are:

          mptoui  mpint->unsigned int
          uitomp  unsigned int->mpint
          mptoi   mpint->int
          itomp   int->mpint
          mptouv  mpint->unsigned vlong
          uvtomp  unsigned vlong->mpint
          mptov   mpint->vlong
          vtomp   vlong->mpint

          When converting to the base integer types, if the integer is
          too large, the largest integer of the appropriate sign and
          size is returned.

          The mathematical functions are:

          mpadd     sum = b1 + b2.
          mpmagadd  sum = abs(b1) + abs(b2).
          mpsub     diff = b1 - b2.
          mpmagsub  diff = abs(b1) - abs(b2).
          mpleft    res = b<<shift.
          mpright   res = b>>shift.
          mpmul     prod = b1*b2.
          mpexp     if m is nil, res = b**e.  Otherwise, res = b**e
                    mod m.
          mpmod     remainder = b % m.
          mpdiv     quotient = dividend/divisor.  remainder = dividend
                    % divisor.
                    returns factorial of n.
          mpcmp     returns -1, 0, or +1 as b1 is less than, equal to,
                    or greater than b2.
          mpmagcmp  the same as mpcmp but ignores the sign and just
                    compares magnitudes.

          Mpextendedgcd computes the greatest common denominator, d,
          of a and b. It also computes x and y such that a*x + b*y =
          d.  Both a and b are required to be positive.  If called
          with negative arguments, it will return a gcd of 0.

          Mpinverse computes the multiplicative inverse of b mod m.

          Mpsignif returns the bit offset of the left most 1 bit in b.
          Mplowbits0 returns the bit offset of the right most 1 bit.
          For example, for 0x14, mpsignif would return 4 and
          mplowbits0 would return 2.

     MP(3)                                                       MP(3)

          The remaining routines all work on arrays of mpdigit rather
          than mpint's.  They are the basis of all the other routines.
          They are separated out to allow them to be rewritten in
          assembler for each architecture.  There is also a portable C
          version for each one.

          mpdigdiv        quotient = dividend[0:1] / divisor.
          mpvecadd        sum[0:alen] = a[0:alen-1] + b[0:blen-1].  We
                          assume alen >= blen and that sum has room
                          for alen+1 digits.
          mpvecsub        diff[0:alen-1] = a[0:alen-1] - b[0:blen-1].
                          We assume that alen >= blen and that diff
                          has room for alen digits.
          mpvecdigmuladd  p[0:n] += m * b[0:n-1].  This multiplies a
                          an array of digits times a scalar and adds
                          it to another array.  We assume p has room
                          for n+1 digits.
          mpvecdigmulsub  p[0:n] -= m * b[0:n-1].  This multiplies a
                          an array of digits times a scalar and sub-
                          tracts it fromo another array.  We assume p
                          has room for n+1 digits.  It returns +1 is
                          the result is positive and -1 if negative.
          mpvecmul        p[0:alen*blen] = a[0:alen-1] * b[0:blen-1].
                          We assume that p has room for alen*blen+1
          mpveccmp        This returns -1, 0, or +1 as a - b is nega-
                          tive, 0, or positive.

          mptwo, mpone and mpzero are the constants 2, 1 and 0.  These
          cannot be freed.

        Chinese remainder theorem
          When computing in a non-prime modulus, n, it is possible to
          perform the computations on the residues modulo the prime
          factors of n instead.  Since these numbers are smaller, mul-
          tiplication and exponentiation can be much faster.

          Crtin computes the residues of x and returns them in a newly
          allocated structure:
               typedef struct CRTres    CRTres;
                    int  n;   // number of residues
                    mpint     *r[n];    // residues

          Crtout takes a residue representation of a number and con-
          verts it back into the number.  It also frees the residue

          Crepre saves a copy of the factors and precomputes the con-
          stants necessary for converting the residue form back into a
          number modulo the product of the factors.  It returns a

     MP(3)                                                       MP(3)

          newly allocated structure containing values.

          Crtprefree and crtresfree free CRTpre and CRTres structures