From 78e51a8c6678b6e3dff3d619aa786669f531f4bc Mon Sep 17 00:00:00 2001 From: rsc Date: Fri, 14 Jan 2005 03:45:44 +0000 Subject: checkpoint --- man/man3/mp.html | 441 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 441 insertions(+) create mode 100644 man/man3/mp.html (limited to 'man/man3/mp.html') diff --git a/man/man3/mp.html b/man/man3/mp.html new file mode 100644 index 00000000..86dc7455 --- /dev/null +++ b/man/man3/mp.html @@ -0,0 +1,441 @@ + +mp(3) - Plan 9 from User Space + + + + +
+
+
MP(3)MP(3) +
+
+

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, mpfactorial, + mpcmp, mpextendedgcd, + mpinvert, 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) +
+ + 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 *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 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 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 + 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 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 immediately after the string converted. + If the parse pterminates 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 allocated. Mpfmt can be used + with fmtinstall(3) and print(3) to print hexadecimal + representations 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. +
+ + 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.
+ mpfactorial   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. +
+ + 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 subtracts 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 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 + necessary for converting the residue form back into a number modulo + the product of the factors. It returns a newly allocated structure + containing values. +
+ + Crtprefree and crtresfree free CRTpre and CRTres structures respectively.
+ +

+

SOURCE
+ +
+ + /usr/local/plan9/src/libmp
+ +
+ +

 +
+
+ + +
+
+
+Space Glenda +
+
+ + -- cgit v1.2.3