4 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
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, mpint *remainder)
112 int mpcmp(mpint *b1, mpint *b2)
115 int mpmagcmp(mpint *b1, mpint *b2)
118 void mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x, mpint *y)
121 void mpinvert(mpint *b, mpint *m, mpint *res)
124 int mpsignif(mpint *b)
127 int mplowbits0(mpint *b)
130 void mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient)
133 void mpvecadd(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *sum)
136 void mpvecsub(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *diff)
139 void mpvecdigmuladd(mpdigit *b, int n, mpdigit m, mpdigit *p)
142 int mpvecdigmulsub(mpdigit *b, int n, mpdigit m, mpdigit *p)
145 void mpvecmul(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *p)
148 int mpveccmp(mpdigit *a, int alen, mpdigit *b, int blen)
151 CRTpre* crtpre(int nfactors, mpint **factors)
154 CRTres* crtin(CRTpre *crt, mpint *x)
157 void crtout(CRTpre *crt, CRTres *r, mpint *x)
160 void crtprefree(CRTpre *cre)
163 void crtresfree(CRTres *res)
166 mpint *mpzero, *mpone, *mptwo
169 These routines perform extended precision integer arithmetic.
172 which points to an array of
174 stored in little-endian order:
177 typedef struct mpint mpint;
180 int sign; /* +1 or -1 */
181 int size; /* allocated digits */
182 int top; /* significant digits */
192 is architecture-dependent and defined in
193 .BR /$cputype/include/u.h .
195 are dynamically allocated and must be explicitly freed. Operations
196 grow the array of digits as needed.
198 In general, the result parameters are last in the
201 Routines that return an
205 if the result parameter is
213 These functions, in addition to
219 if the allocation fails.
221 Input and result parameters may point to the same
223 The routines check and copy where necessary.
228 with an initial allocation of
233 is zero, the allocation will be whatever was specified in the
236 or to the initial value, 1056.
241 grows the allocation of
249 bits it increases it to do so.
250 Unless you are writing new basic operations, you
251 can restrict yourself to
257 normalizes the representation by trimming any high order zero
258 digits. All routines except
260 return normalized results.
265 with the same value as
277 bit random number using the generator
280 takes a pointer to a string of uchar's and the number
290 representations using the base indicated.
291 Only the bases 10, 16, 32, and 64 are
292 supported. Anything else defaults to 16.
294 skips any leading spaces or tabs.
296 scan stops when encountering a digit not valid in the
301 is set to point to the character immediately after the
303 If the parse pterminates before any digits are found,
308 returns a pointer to the filled buffer.
313 the buffer is allocated.
319 to print hexadecimal representations of
327 to a byte array. The former creates a big endian representation,
328 the latter a little endian one.
333 it specifies the buffer of length
335 for the result. If the representation
338 bytes, the rest of the buffer is zero filled.
343 then a buffer is allocated and a pointer to it is
344 deposited in the location pointed to by
346 Sign is ignored in these conversions, i.e., the byte
347 array version is always positive.
352 convert from a big or little endian byte array at
362 it refers to a preallocated
369 a new integer is allocated and returned as the result.
371 The integer conversions are:
375 .BR mpint -> "unsigned int"
378 .BR "unsigned int" -> mpint
387 .BR mpint -> "unsigned vlong"
390 .BR "unsigned vlong" -> mpint
399 When converting to the base integer types, if the integer is too large,
400 the largest integer of the appropriate sign
401 and size is returned.
403 The mathematical functions are:
407 .BR "sum = b1 + b2" .
410 .BR "sum = abs(b1) + abs(b2)" .
413 .BR "diff = b1 - b2" .
416 .BR "diff = abs(b1) - abs(b2)" .
419 .BR "res = b<<shift" .
422 .BR "res = b>>shift" .
433 .BR "res = b**e mod m" .
436 .BR "remainder = b % m" .
439 .BR "quotient = dividend/divisor" .
440 .BR "remainder = dividend % divisor" .
443 returns -1, 0, or +1 as
445 is less than, equal to, or greater than
451 but ignores the sign and just compares magnitudes.
455 computes the greatest common denominator,
466 .BR "a*x + b*y = d" .
471 are required to be positive.
472 If called with negative arguments, it will
476 computes the multiplicative inverse of
482 returns the bit offset of the left most 1 bit in
485 returns the bit offset of the right most 1 bit.
486 For example, for 0x14,
492 The remaining routines all work on arrays of
496 They are the basis of all the other routines. They are separated out
497 to allow them to be rewritten in assembler for each architecture. There
498 is also a portable C version for each one.
502 .BR "quotient = dividend[0:1] / divisor" .
505 .BR "sum[0:alen] = a[0:alen-1] + b[0:blen-1]" .
506 We assume alen >= blen and that sum has room for alen+1 digits.
509 .BR "diff[0:alen-1] = a[0:alen-1] - b[0:blen-1]" .
510 We assume that alen >= blen and that diff has room for alen digits.
513 .BR "p[0:n] += m * b[0:n-1]" .
514 This multiplies a an array of digits times a scalar and adds it to another array.
515 We assume p has room for n+1 digits.
518 .BR "p[0:n] -= m * b[0:n-1]" .
519 This multiplies a an array of digits times a scalar and subtracts it fromo another array.
520 We assume p has room for n+1 digits. It returns +1 is the result is positive and
524 .BR "p[0:alen*blen] = a[0:alen-1] * b[0:blen-1]" .
525 We assume that p has room for alen*blen+1 digits.
528 This returns -1, 0, or +1 as a - b is negative, 0, or positive.
535 are the constants 2, 1 and 0. These cannot be freed.
536 .SS "Chinese remainder theorem
538 When computing in a non-prime modulus,
540 it is possible to perform the computations on the residues modulo the prime
543 instead. Since these numbers are smaller, multiplication and exponentiation
547 computes the residues of
549 and returns them in a newly allocated structure:
551 typedef struct CRTres CRTres;
553 int n; // number of residues
554 mpint *r[n]; // residues
559 takes a residue representation of a number and converts it back into
560 the number. It also frees the residue structure.
563 saves a copy of the factors and precomputes the constants necessary
564 for converting the residue form back into a number modulo
565 the product of the factors. It returns a newly allocated structure
575 structures respectively.
577 .B /usr/local/plan9/src/libmp
