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 \- extended precision arithmetic
11 .ta +\w'\fLCRTpre* \fP'u
19 void mpsetminbits(int n)
22 void mpbits(mpint *b, int n)
28 mpint* mpcopy(mpint *b)
31 void mpassign(mpint *old, mpint *new)
34 mpint* mprand(int bits, void (*gen)(uchar*, int), mpint *b)
37 mpint* strtomp(char *buf, char **rptr, int base, mpint *b)
40 char* mptoa(mpint *b, int base, char *buf, int blen)
46 mpint* betomp(uchar *buf, uint blen, mpint *b)
49 int mptobe(mpint *b, uchar *buf, uint blen, uchar **bufp)
52 mpint* letomp(uchar *buf, uint blen, mpint *b)
55 int mptole(mpint *b, uchar *buf, uint blen, uchar **bufp)
61 mpint* uitomp(uint, mpint*)
67 mpint* itomp(int, mpint*)
70 mpint* vtomp(vlong, mpint*)
76 mpint* uvtomp(uvlong, mpint*)
82 void mpadd(mpint *b1, mpint *b2, mpint *sum)
85 void mpmagadd(mpint *b1, mpint *b2, mpint *sum)
88 void mpsub(mpint *b1, mpint *b2, mpint *diff)
91 void mpmagsub(mpint *b1, mpint *b2, mpint *diff)
94 void mpleft(mpint *b, int shift, mpint *res)
97 void mpright(mpint *b, int shift, mpint *res)
100 void mpmul(mpint *b1, mpint *b2, mpint *prod)
103 void mpexp(mpint *b, mpint *e, mpint *m, mpint *res)
106 void mpmod(mpint *b, mpint *m, mpint *remainder)
109 void mpdiv(mpint *dividend, mpint *divisor, mpint *quotient,
115 int mpcmp(mpint *b1, mpint *b2)
118 int mpmagcmp(mpint *b1, mpint *b2)
121 void mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x,
127 void mpinvert(mpint *b, mpint *m, mpint *res)
130 int mpsignif(mpint *b)
133 int mplowbits0(mpint *b)
136 void mpdigdiv(mpdigit *dividend, mpdigit divisor,
142 void mpvecadd(mpdigit *a, int alen, mpdigit *b, int blen,
148 void mpvecsub(mpdigit *a, int alen, mpdigit *b, int blen,
154 void mpvecdigmuladd(mpdigit *b, int n, mpdigit m, mpdigit *p)
157 int mpvecdigmulsub(mpdigit *b, int n, mpdigit m, mpdigit *p)
160 void mpvecmul(mpdigit *a, int alen, mpdigit *b, int blen,
166 int mpveccmp(mpdigit *a, int alen, mpdigit *b, int blen)
169 CRTpre* crtpre(int nfactors, mpint **factors)
172 CRTres* crtin(CRTpre *crt, mpint *x)
175 void crtout(CRTpre *crt, CRTres *r, mpint *x)
178 void crtprefree(CRTpre *cre)
181 void crtresfree(CRTres *res)
184 mpint *mpzero, *mpone, *mptwo
187 These routines perform extended precision integer arithmetic.
190 which points to an array of
192 stored in little-endian order:
195 typedef struct mpint mpint;
198 int sign; /* +1 or -1 */
199 int size; /* allocated digits */
200 int top; /* significant digits */
210 is architecture-dependent and defined in
211 .BR /$cputype/include/u.h .
213 are dynamically allocated and must be explicitly freed. Operations
214 grow the array of digits as needed.
216 In general, the result parameters are last in the
219 Routines that return an
223 if the result parameter is
231 These functions, in addition to
237 if the allocation fails.
239 Input and result parameters may point to the same
241 The routines check and copy where necessary.
246 with an initial allocation of
251 is zero, the allocation will be whatever was specified in the
254 or to the initial value, 1056.
259 grows the allocation of
269 increases it to do so.
270 Unless you are writing new basic operations, you
271 can restrict yourself to
277 normalizes the representation by trimming any high order zero
278 digits. All routines except
280 return normalized results.
285 with the same value as
297 bit random number using the generator
300 takes a pointer to a string of uchar's and the number
310 representations using the base indicated.
311 Only the bases 10, 16, 32, and 64 are
312 supported. Anything else defaults to 16.
314 skips any leading spaces or tabs.
316 scan stops when encountering a digit not valid in the
321 is set to point to the character immediately after the
323 If the parse terminates before any digits are found,
328 returns a pointer to the filled buffer.
333 the buffer is allocated.
339 to print hexadecimal representations of
341 The conventional verb is
353 to a byte array. The former creates a big endian representation,
354 the latter a little endian one.
359 it specifies the buffer of length
361 for the result. If the representation
364 bytes, the rest of the buffer is zero filled.
369 then a buffer is allocated and a pointer to it is
370 deposited in the location pointed to by
372 Sign is ignored in these conversions, i.e., the byte
373 array version is always positive.
378 convert from a big or little endian byte array at
388 it refers to a preallocated
395 a new integer is allocated and returned as the result.
397 The integer conversions are:
401 .BR mpint -> "unsigned int"
404 .BR "unsigned int" -> mpint
413 .BR mpint -> "unsigned vlong"
416 .BR "unsigned vlong" -> mpint
425 When converting to the base integer types, if the integer is too large,
426 the largest integer of the appropriate sign
427 and size is returned.
429 The mathematical functions are:
433 .BR "sum = b1 + b2" .
436 .BR "sum = abs(b1) + abs(b2)" .
439 .BR "diff = b1 - b2" .
442 .BR "diff = abs(b1) - abs(b2)" .
445 .BR "res = b<<shift" .
448 .BR "res = b>>shift" .
459 .BR "res = b**e mod m" .
462 .BR "remainder = b % m" .
465 .BR "quotient = dividend/divisor" .
466 .BR "remainder = dividend % divisor" .
469 returns -1, 0, or +1 as
471 is less than, equal to, or greater than
477 but ignores the sign and just compares magnitudes.
481 computes the greatest common denominator,
492 .BR "a*x + b*y = d" .
497 are required to be positive.
498 If called with negative arguments, it will
502 computes the multiplicative inverse of
508 returns the number of significant bits in
511 returns the number of consecutive zero bits
512 at the low end of the significant bits.
513 For example, for 0x14,
524 The remaining routines all work on arrays of
528 They are the basis of all the other routines. They are separated out
529 to allow them to be rewritten in assembler for each architecture. There
530 is also a portable C version for each one.
534 .BR "quotient = dividend[0:1] / divisor" .
537 .BR "sum[0:alen] = a[0:alen-1] + b[0:blen-1]" .
538 We assume alen >= blen and that sum has room for alen+1 digits.
541 .BR "diff[0:alen-1] = a[0:alen-1] - b[0:blen-1]" .
542 We assume that alen >= blen and that diff has room for alen digits.
545 .BR "p[0:n] += m * b[0:n-1]" .
546 This multiplies a an array of digits times a scalar and adds it to another array.
547 We assume p has room for n+1 digits.
550 .BR "p[0:n] -= m * b[0:n-1]" .
551 This multiplies a an array of digits times a scalar and subtracts it from another array.
552 We assume p has room for n+1 digits. It returns +1 is the result is positive and
556 .BR "p[0:alen*blen] = a[0:alen-1] * b[0:blen-1]" .
557 We assume that p has room for alen*blen+1 digits.
560 This returns -1, 0, or +1 as a - b is negative, 0, or positive.
567 are the constants 2, 1 and 0. These cannot be freed.
568 .SS "Chinese remainder theorem
570 When computing in a non-prime modulus,
572 it is possible to perform the computations on the residues modulo the prime
575 instead. Since these numbers are smaller, multiplication and exponentiation
579 computes the residues of
581 and returns them in a newly allocated structure:
584 typedef struct CRTres CRTres;
586 int n; /* number of residues */
587 mpint *r[n]; /* residues */
592 takes a residue representation of a number and converts it back into
593 the number. It also frees the residue structure.
596 saves a copy of the factors and precomputes the constants necessary
597 for converting the residue form back into a number modulo
598 the product of the factors. It returns a newly allocated structure
608 structures respectively.