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, mpcmp, mpextendedgcd, mpinvert, mpsignif, mplowbits0, mpvecdigmuladd, mpvecdigmulsub, mpvecadd, mpvecsub, mpveccmp, mpvecmul, mpmagcmp, mpmagadd, mpmagsub, crtpre, crtin, crtout, crtprefree, crtresfree, mpfactorial \- extended precision arithmetic
18 void mpsetminbits(int n)
21 void mpbits(mpint *b, int n)
27 mpint* mpcopy(mpint *b)
30 void mpassign(mpint *old, mpint *new)
33 mpint* mprand(int bits, void (*gen)(uchar*, int), mpint *b)
36 mpint* strtomp(char *buf, char **rptr, int base, mpint *b)
39 char* mptoa(mpint *b, int base, char *buf, int blen)
45 mpint* betomp(uchar *buf, uint blen, mpint *b)
48 int mptobe(mpint *b, uchar *buf, uint blen, uchar **bufp)
51 mpint* letomp(uchar *buf, uint blen, mpint *b)
54 int mptole(mpint *b, uchar *buf, uint blen, uchar **bufp)
60 mpint* uitomp(uint, mpint*)
66 mpint* itomp(int, mpint*)
69 mpint* vtomp(vlong, mpint*)
75 mpint* uvtomp(uvlong, mpint*)
81 void mpadd(mpint *b1, mpint *b2, mpint *sum)
84 void mpmagadd(mpint *b1, mpint *b2, mpint *sum)
87 void mpsub(mpint *b1, mpint *b2, mpint *diff)
90 void mpmagsub(mpint *b1, mpint *b2, mpint *diff)
93 void mpleft(mpint *b, int shift, mpint *res)
96 void mpright(mpint *b, int shift, mpint *res)
99 void mpmul(mpint *b1, mpint *b2, mpint *prod)
102 void mpexp(mpint *b, mpint *e, mpint *m, mpint *res)
105 void mpmod(mpint *b, mpint *m, mpint *remainder)
108 void mpdiv(mpint *dividend, mpint *divisor, mpint *quotient, mpint *remainder)
111 int mpcmp(mpint *b1, mpint *b2)
114 int mpmagcmp(mpint *b1, mpint *b2)
117 void mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x, mpint *y)
120 void mpinvert(mpint *b, mpint *m, mpint *res)
123 int mpsignif(mpint *b)
126 int mplowbits0(mpint *b)
129 void mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient)
132 void mpvecadd(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *sum)
135 void mpvecsub(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *diff)
138 void mpvecdigmuladd(mpdigit *b, int n, mpdigit m, mpdigit *p)
141 int mpvecdigmulsub(mpdigit *b, int n, mpdigit m, mpdigit *p)
144 void mpvecmul(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *p)
147 int mpveccmp(mpdigit *a, int alen, mpdigit *b, int blen)
150 CRTpre* crtpre(int nfactors, mpint **factors)
153 CRTres* crtin(CRTpre *crt, mpint *x)
156 void crtout(CRTpre *crt, CRTres *r, mpint *x)
159 void crtprefree(CRTpre *cre)
162 void crtresfree(CRTres *res)
165 mpint* mpfactorial(ulong n)
168 mpint *mpzero, *mpone, *mptwo
171 These routines perform extended precision integer arithmetic.
174 which points to an array of
176 stored in little-endian order:
179 typedef struct mpint mpint;
182 int sign; /* +1 or -1 */
183 int size; /* allocated digits */
184 int top; /* significant digits */
194 is architecture-dependent and defined in
195 .BR /$cputype/include/u.h .
197 are dynamically allocated and must be explicitly freed. Operations
198 grow the array of digits as needed.
200 In general, the result parameters are last in the
203 Routines that return an
207 if the result parameter is
215 These functions, in addition to
221 if the allocation fails.
223 Input and result parameters may point to the same
225 The routines check and copy where necessary.
230 with an initial allocation of
235 is zero, the allocation will be whatever was specified in the
238 or to the initial value, 1056.
243 grows the allocation of
251 bits it increases it to do so.
252 Unless you are writing new basic operations, you
253 can restrict yourself to
259 normalizes the representation by trimming any high order zero
260 digits. All routines except
262 return normalized results.
267 with the same value as
279 bit random number using the generator
282 takes a pointer to a string of uchar's and the number
292 representations using the base indicated.
293 Only the bases 10, 16, 32, and 64 are
294 supported. Anything else defaults to 16.
296 skips any leading spaces or tabs.
298 scan stops when encountering a digit not valid in the
303 is set to point to the character immediately after the
305 If the parse pterminates before any digits are found,
310 returns a pointer to the filled buffer.
315 the buffer is allocated.
321 to print hexadecimal representations of
329 to a byte array. The former creates a big endian representation,
330 the latter a little endian one.
335 it specifies the buffer of length
337 for the result. If the representation
340 bytes, the rest of the buffer is zero filled.
345 then a buffer is allocated and a pointer to it is
346 deposited in the location pointed to by
348 Sign is ignored in these conversions, i.e., the byte
349 array version is always positive.
354 convert from a big or little endian byte array at
364 it refers to a preallocated
371 a new integer is allocated and returned as the result.
373 The integer conversions are:
377 .BR mpint -> "unsigned int"
380 .BR "unsigned int" -> mpint
389 .BR mpint -> "unsigned vlong"
392 .BR "unsigned vlong" -> mpint
401 When converting to the base integer types, if the integer is too large,
402 the largest integer of the appropriate sign
403 and size is returned.
405 The mathematical functions are:
409 .BR "sum = b1 + b2" .
412 .BR "sum = abs(b1) + abs(b2)" .
415 .BR "diff = b1 - b2" .
418 .BR "diff = abs(b1) - abs(b2)" .
421 .BR "res = b<<shift" .
424 .BR "res = b>>shift" .
435 .BR "res = b**e mod m" .
438 .BR "remainder = b % m" .
441 .BR "quotient = dividend/divisor" .
442 .BR "remainder = dividend % divisor" .
445 returns -1, 0, or +1 as
447 is less than, equal to, or greater than
453 but ignores the sign and just compares magnitudes.
457 computes the greatest common denominator,
468 .BR "a*x + b*y = d" .
473 are required to be positive.
474 If called with negative arguments, it will
478 computes the multiplicative inverse of
484 returns the bit offset of the left most 1 bit in
487 returns the bit offset of the right most 1 bit.
488 For example, for 0x14,
494 The remaining routines all work on arrays of
498 They are the basis of all the other routines. They are separated out
499 to allow them to be rewritten in assembler for each architecture. There
500 is also a portable C version for each one.
504 .BR "quotient = dividend[0:1] / divisor" .
507 .BR "sum[0:alen] = a[0:alen-1] + b[0:blen-1]" .
508 We assume alen >= blen and that sum has room for alen+1 digits.
511 .BR "diff[0:alen-1] = a[0:alen-1] - b[0:blen-1]" .
512 We assume that alen >= blen and that diff has room for alen digits.
515 .BR "p[0:n] += m * b[0:n-1]" .
516 This multiplies a an array of digits times a scalar and adds it to another array.
517 We assume p has room for n+1 digits.
520 .BR "p[0:n] -= m * b[0:n-1]" .
521 This multiplies a an array of digits times a scalar and subtracts it fromo another array.
522 We assume p has room for n+1 digits. It returns +1 is the result is positive and
526 .BR "p[0:alen*blen] = a[0:alen-1] * b[0:blen-1]" .
527 We assume that p has room for alen*blen+1 digits.
530 This returns -1, 0, or +1 as a - b is negative, 0, or positive.
537 are the constants 2, 1 and 0. These cannot be freed.
538 .SS "Chinese remainder theorem
540 When computing in a non-prime modulus,
542 it is possible to perform the computations on the residues modulo the prime
545 instead. Since these numbers are smaller, multiplication and exponentiation
549 computes the residues of
551 and returns them in a newly allocated structure:
553 typedef struct CRTres CRTres;
555 int n; // number of residues
556 mpint *r[n]; // residues
561 takes a residue representation of a number and converts it back into
562 the number. It also frees the residue structure.
565 saves a copy of the factors and precomputes the constants necessary
566 for converting the residue form back into a number modulo
567 the product of the factors. It returns a newly allocated structure
577 structures respectively.
580 returns the factorial of
583 .B /usr/local/plan9/src/libmp
