3 mpsetminbits, mpnew, mpfree, mpbits, mpnorm, mpcopy, mpassign, mprand, mpnrand, strtomp, mpfmt,mptoa, betomp, mptobe, mptober, letomp, mptole, mptolel, mptoui, uitomp, mptoi, itomp, uvtomp, mptouv, vtomp, mptov, mptod, dtomp, mpdigdiv, mpadd, mpsub, mpleft, mpright, mpmul, mpexp, mpmod, mpmodadd, mpmodsub, mpmodmul, mpdiv, mpcmp, mpsel, 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)
25 mpint* mpnorm(mpint *b)
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* mpnrand(mpint *n, void (*gen)(uchar*, int), mpint *b)
40 mpint* strtomp(char *buf, char **rptr, int base, mpint *b)
43 char* mptoa(mpint *b, int base, char *buf, int blen)
49 mpint* betomp(uchar *buf, uint blen, mpint *b)
52 int mptobe(mpint *b, uchar *buf, uint blen, uchar **bufp)
55 void mptober(mpint *b, uchar *buf, int blen)
58 mpint* letomp(uchar *buf, uint blen, mpint *b)
61 int mptole(mpint *b, uchar *buf, uint blen, uchar **bufp)
64 void mptolel(mpint *b, uchar *buf, int blen)
70 mpint* uitomp(uint, mpint*)
76 mpint* itomp(int, mpint*)
79 mpint* vtomp(vlong, mpint*)
85 mpint* uvtomp(uvlong, mpint*)
91 mpint* dtomp(double, mpint*)
97 void mpadd(mpint *b1, mpint *b2, mpint *sum)
100 void mpmagadd(mpint *b1, mpint *b2, mpint *sum)
103 void mpsub(mpint *b1, mpint *b2, mpint *diff)
106 void mpmagsub(mpint *b1, mpint *b2, mpint *diff)
109 void mpleft(mpint *b, int shift, mpint *res)
112 void mpright(mpint *b, int shift, mpint *res)
115 void mpand(mpint *b1, mpint *b2, mpint *res)
118 void mpbic(mpint *b1, mpint *b2, mpint *res)
121 void mpor(mpint *b1, mpint *b2, mpint *res)
124 void mpnot(mpint *b, mpint *res)
127 void mpxor(mpint *b1, mpint *b2, mpint *res)
130 void mptrunc(mpint *b, int n, mpint *res)
133 void mpxtend(mpint *b, int n, mpint *res)
136 void mpasr(mpint *b, int n, mpint *res)
139 void mpmul(mpint *b1, mpint *b2, mpint *prod)
142 void mpexp(mpint *b, mpint *e, mpint *m, mpint *res)
145 void mpmod(mpint *b, mpint *m, mpint *remainder)
148 void mpdiv(mpint *dividend, mpint *divisor, mpint *quotient,
154 void mpmodadd(mpint *b1, mpint *b2, mpint *m, mpint *sum)
157 void mpmodsub(mpint *b1, mpint *b2, mpint *m, mpint *diff)
160 void mpmodmul(mpint *b1, mpint *b2, mpint *m, mpint *prod)
163 int mpcmp(mpint *b1, mpint *b2)
166 int mpmagcmp(mpint *b1, mpint *b2)
169 void mpsel(int s, mpint *b1, mpint *b2, mpint *res)
172 void mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x,
178 void mpinvert(mpint *b, mpint *m, mpint *res)
181 int mpsignif(mpint *b)
184 int mplowbits0(mpint *b)
187 void mpdigdiv(mpdigit *dividend, mpdigit divisor,
193 void mpvecadd(mpdigit *a, int alen, mpdigit *b, int blen,
199 void mpvecsub(mpdigit *a, int alen, mpdigit *b, int blen,
205 void mpvecdigmuladd(mpdigit *b, int n, mpdigit m, mpdigit *p)
208 int mpvecdigmulsub(mpdigit *b, int n, mpdigit m, mpdigit *p)
211 void mpvecmul(mpdigit *a, int alen, mpdigit *b, int blen,
217 int mpveccmp(mpdigit *a, int alen, mpdigit *b, int blen)
220 CRTpre* crtpre(int nfactors, mpint **factors)
223 CRTres* crtin(CRTpre *crt, mpint *x)
226 void crtout(CRTpre *crt, CRTres *r, mpint *x)
229 void crtprefree(CRTpre *cre)
232 void crtresfree(CRTres *res)
235 mpint *mpzero, *mpone, *mptwo
238 These routines perform extended precision integer arithmetic.
241 which points to an array of
243 stored in little-endian order:
246 typedef struct mpint mpint;
249 int sign; /* +1 or -1 */
250 int size; /* allocated digits */
251 int top; /* significant digits */
261 is architecture-dependent and defined in
262 .BR /$cputype/include/u.h .
264 are dynamically allocated and must be explicitly freed. Operations
265 grow the array of digits as needed.
267 In general, the result parameters are last in the
270 Routines that return an
274 if the result parameter is
283 These functions, in addition to
289 if the allocation fails.
291 Input and result parameters may point to the same
293 The routines check and copy where necessary.
298 with an initial allocation of
303 is zero, the allocation will be whatever was specified in the
306 or to the initial value, 1056.
311 grows the allocation of
321 increases it to do so.
322 Unless you are writing new basic operations, you
323 can restrict yourself to
329 normalizes the representation by trimming any high order zero
330 digits. All routines except
332 return normalized results.
337 with the same value as
349 bit random number using the generator
352 takes a pointer to a string of uchar's and the number
358 to generate a uniform random number
360 .if t 0 ≤ \fIx\fR < \fIn\fR.
370 representations using the base indicated.
371 Only the bases 2, 4, 8, 10, 16, 32, and 64 are
372 supported. Base 0 defaults to 16.
374 skips any leading spaces or tabs.
376 scan stops when encountering a digit not valid in the
379 is zero then C-style prefixes are interpreted to
386 for octal. Otherwise decimal is assumed.
390 is set to point to the character immediately after the
392 If the parse terminates before any digits are found,
397 returns a pointer to the filled buffer.
402 the buffer is allocated.
408 to print hexadecimal representations of
410 The conventional verb is
422 to a byte array. The former creates a big endian representation,
423 the latter a little endian one.
428 it specifies the buffer of length
430 for the result. If the representation
433 bytes, the rest of the buffer is zero filled.
438 then a buffer is allocated and a pointer to it is
439 deposited in the location pointed to by
441 Sign is ignored in these conversions, i.e., the byte
442 array version is always positive.
451 into a fixed length byte array.
453 fills the bytes right adjusted in big endian order so that the least
454 significant byte is at
458 fills in little endian order; left adjusted; so that the least
459 significat byte is filled into
465 convert from a big or little endian byte array at
475 it refers to a preallocated
482 a new integer is allocated and returned as the result.
484 The integer (and floating point) conversions are:
488 .BR mpint -> "unsigned int"
491 .BR "unsigned int" -> mpint
500 .BR mpint -> "unsigned vlong"
503 .BR "unsigned vlong" -> mpint
512 .BR mpint -> "double"
515 .BR "double" -> mpint
518 When converting to the base integer types, if the integer is too large,
519 the largest integer of the appropriate sign
520 and size is returned.
522 When converting to and from floating point, results are rounded using IEEE 754 "round to nearest".
523 If the integer is too large in magnitude,
525 returns infinity of the appropriate sign.
527 The mathematical functions are:
531 .BR "sum = b1 + b2" .
534 .BR "sum = abs(b1) + abs(b2)" .
537 .BR "diff = b1 - b2" .
540 .BR "diff = abs(b1) - abs(b2)" .
543 .BR "res = b<<shift" .
546 .BR "res = b>>shift" .
557 .BR "res = b**e mod m" .
560 .BR "remainder = b % m" .
563 .BR "quotient = dividend/divisor" .
564 .BR "remainder = dividend % divisor" .
567 returns -1, 0, or +1 as
569 is less than, equal to, or greater than
575 but ignores the sign and just compares magnitudes.
584 is not zero, otherwise
590 Logical operations (treating negative numbers using two's complement):
594 .BR "res = b1 & b2" .
597 .BR "res = b1 & ~b2" .
600 .BR "res = b1 | b2" .
603 .BR "res = b1 ^ b2" .
612 uses two's complement).
619 bits and stores the result in
621 The result is never negative.
628 bits, sign extends the MSB and stores the result in
636 .BR "sum = b1+b2 mod m" .
639 .BR "diff = b1-b2 mod m" .
642 .BR "prod = b1*b2 mod m" .
646 computes the greatest common denominator,
657 .BR "a*x + b*y = d" .
662 are required to be positive.
663 If called with negative arguments, it will
667 computes the multiplicative inverse of
673 returns the number of significant bits in
676 returns the number of consecutive zero bits
677 at the low end of the significant bits.
678 For example, for 0x14,
689 The remaining routines all work on arrays of
693 They are the basis of all the other routines. They are separated out
694 to allow them to be rewritten in assembler for each architecture. There
695 is also a portable C version for each one.
699 .BR "quotient = dividend[0:1] / divisor" .
702 .BR "sum[0:alen] = a[0:alen-1] + b[0:blen-1]" .
703 We assume alen >= blen and that sum has room for alen+1 digits.
706 .BR "diff[0:alen-1] = a[0:alen-1] - b[0:blen-1]" .
707 We assume that alen >= blen and that diff has room for alen digits.
710 .BR "p[0:n] += m * b[0:n-1]" .
711 This multiplies a an array of digits times a scalar and adds it to another array.
712 We assume p has room for n+1 digits.
715 .BR "p[0:n] -= m * b[0:n-1]" .
716 This multiplies a an array of digits times a scalar and subtracts it from another array.
717 We assume p has room for n+1 digits. It returns +1 is the result is positive and
721 .BR "p[0:alen+blen] = a[0:alen-1] * b[0:blen-1]" .
722 We assume that p has room for alen+blen+1 digits.
725 This returns -1, 0, or +1 as a - b is negative, 0, or positive.
732 are the constants 2, 1 and 0. These cannot be freed.
733 .SS "Time invariant computation"
735 In the field of cryptography, it is sometimes neccesary to implement
736 algorithms such that the runtime of the algorithm is not depdenent on
737 the input data. This library provides partial support for time
738 invariant computation with the
740 flag that can be set on input or destination operands to request timing
741 safe operation. The result of a timing safe operation will also have the
743 flag set and is not normalized.
744 .SS "Chinese remainder theorem
746 When computing in a non-prime modulus,
748 it is possible to perform the computations on the residues modulo the prime
751 instead. Since these numbers are smaller, multiplication and exponentiation
755 computes the residues of
757 and returns them in a newly allocated structure:
760 typedef struct CRTres CRTres;
762 int n; /* number of residues */
763 mpint *r[n]; /* residues */
768 takes a residue representation of a number and converts it back into
769 the number. It also frees the residue structure.
772 saves a copy of the factors and precomputes the constants necessary
773 for converting the residue form back into a number modulo
774 the product of the factors. It returns a newly allocated structure
784 structures respectively.