glenda.party
term% ls -F
term% pwd
$home/manuals/9front/2/mp
term% cat index.txt
MP(2)                         System Calls Manual                        MP(2)



NAME
       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, mpcmp, mpextendedgcd,  mp‐
       invert, mpsignif, mplowbits0, mpvecdigmuladd, mpvecdigmulsub, mpvecadd,
       mpvecsub, mpveccmp, mpvecmul,  mpmagcmp,  mpmagadd,  mpmagsub,  crtpre,
       crtin, crtout, crtprefree, crtresfree - extended precision arithmetic

SYNOPSIS
       #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 *b)

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

       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*)

       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 *quotient,
               mpint *remainder)

       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 *quotient)

       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 *p)

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

       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

DESCRIPTION
       These  routines perform extended precision integer arithmetic.  The ba‐
       sic type is mpint, which points to an array of mpdigits, stored in lit‐
       tle-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 digits as needed.

       In general, the result parameters are last in the argument list.

       Routines that return an mpint will allocate the mpint if the result pa‐
       rameter 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,  mpbits increases it to do so.  Unless you are
       writing new basic operations, you can restrict yourself to mpnew(0) and
       mpfree(b).

       Mpnorm  normalizes  the  representation by trimming any high order zero
       digits.  All routines except mpbits return normalized 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 number to fill in.

       Strtomp and mptoa convert between ASCII and mpint representations 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  im‐
       mediately  after  the string converted.  If the parse terminates before
       any digits are found, strtomp return nil.  Mptoa returns a  pointer  to
       the  filled  buffer.   If the parameter buf is nil, the buffer is allo‐
       cated.  Mpfmt can be used with  fmtinstall(2)  and  print(2)  to  print
       hexadecimal  representations  of  mpints.  The conventional verb is for
       which mp.h provides a

       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.

       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 preal‐
       located  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.

       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  magni‐
              tudes.

       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 re‐
       quired  to be positive.  If called with negative arguments, it will re‐
       turn a gcd of 0.

       Mpinvert computes the multiplicative inverse of b mod m.

       Mpsignif returns the number of significant bits in b.   Mplowbits0  re‐
       turns the number of consecutive zero bits at the low end of the signif‐
       icant bits.  For example, for 0x14, mpsignif returns 5  and  mplowbits0
       returns 2.  For 0, mpsignif and mplowbits0 both return 0.

       The  remaining  routines  all  work  on  arrays  of mpdigit rather than
       mpint's.  They are the basis of all the other routines.  They are sepa‐
       rated out to allow them to be rewritten in assembler for each architec‐
       ture.  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 subtracts it from another array.  We assume p
              has room for n+1 digits.  It returns +1 is the result  is  posi‐
              tive 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 digits.

       mpveccmp
              This returns -1, 0, or +1 as a - b is negative, 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, multiplication 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 converts it back
       into the number.  It also frees the residue structure.

       Crepre saves a copy of the factors and precomputes the constants neces‐
       sary  for  converting  the  residue  form back into a number modulo the
       product of the factors.  It returns a newly  allocated  structure  con‐
       taining values.

       Crtprefree  and  crtresfree  free  CRTpre and CRTres structures respec‐
       tively.

SOURCE
       /sys/src/libmp



                                                                         MP(2)