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, 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 void mpadd(mpint *b1, mpint *b2, mpint *sum)
94 void mpmagadd(mpint *b1, mpint *b2, mpint *sum)
97 void mpsub(mpint *b1, mpint *b2, mpint *diff)
100 void mpmagsub(mpint *b1, mpint *b2, mpint *diff)
103 void mpleft(mpint *b, int shift, mpint *res)
106 void mpright(mpint *b, int shift, mpint *res)
109 void mpand(mpint *b1, mpint *b2, mpint *res)
112 void mpbic(mpint *b1, mpint *b2, mpint *res)
115 void mpor(mpint *b1, mpint *b2, mpint *res)
118 void mpnot(mpint *b, mpint *res)
121 void mpxor(mpint *b1, mpint *b2, mpint *res)
124 void mptrunc(mpint *b, int n, mpint *res)
127 void mpxtend(mpint *b, int n, mpint *res)
130 void mpasr(mpint *b, int n, mpint *res)
133 void mpmul(mpint *b1, mpint *b2, mpint *prod)
136 void mpexp(mpint *b, mpint *e, mpint *m, mpint *res)
139 void mpmod(mpint *b, mpint *m, mpint *remainder)
142 void mpdiv(mpint *dividend, mpint *divisor, mpint *quotient,
148 void mpmodadd(mpint *b1, mpint *b2, mpint *m, mpint *sum)
151 void mpmodsub(mpint *b1, mpint *b2, mpint *m, mpint *diff)
154 void mpmodmul(mpint *b1, mpint *b2, mpint *m, mpint *prod)
157 int mpcmp(mpint *b1, mpint *b2)
160 int mpmagcmp(mpint *b1, mpint *b2)
163 void mpsel(int s, mpint *b1, mpint *b2, mpint *res)
166 void mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x,
172 void mpinvert(mpint *b, mpint *m, mpint *res)
175 int mpsignif(mpint *b)
178 int mplowbits0(mpint *b)
181 void mpdigdiv(mpdigit *dividend, mpdigit divisor,
187 void mpvecadd(mpdigit *a, int alen, mpdigit *b, int blen,
193 void mpvecsub(mpdigit *a, int alen, mpdigit *b, int blen,
199 void mpvecdigmuladd(mpdigit *b, int n, mpdigit m, mpdigit *p)
202 int mpvecdigmulsub(mpdigit *b, int n, mpdigit m, mpdigit *p)
205 void mpvecmul(mpdigit *a, int alen, mpdigit *b, int blen,
211 int mpveccmp(mpdigit *a, int alen, mpdigit *b, int blen)
214 CRTpre* crtpre(int nfactors, mpint **factors)
217 CRTres* crtin(CRTpre *crt, mpint *x)
220 void crtout(CRTpre *crt, CRTres *r, mpint *x)
223 void crtprefree(CRTpre *cre)
226 void crtresfree(CRTres *res)
229 mpint *mpzero, *mpone, *mptwo
232 These routines perform extended precision integer arithmetic.
235 which points to an array of
237 stored in little-endian order:
240 typedef struct mpint mpint;
243 int sign; /* +1 or -1 */
244 int size; /* allocated digits */
245 int top; /* significant digits */
255 is architecture-dependent and defined in
256 .BR /$cputype/include/u.h .
258 are dynamically allocated and must be explicitly freed. Operations
259 grow the array of digits as needed.
261 In general, the result parameters are last in the
264 Routines that return an
268 if the result parameter is
276 These functions, in addition to
282 if the allocation fails.
284 Input and result parameters may point to the same
286 The routines check and copy where necessary.
291 with an initial allocation of
296 is zero, the allocation will be whatever was specified in the
299 or to the initial value, 1056.
304 grows the allocation of
314 increases it to do so.
315 Unless you are writing new basic operations, you
316 can restrict yourself to
322 normalizes the representation by trimming any high order zero
323 digits. All routines except
325 return normalized results.
330 with the same value as
342 bit random number using the generator
345 takes a pointer to a string of uchar's and the number
351 to generate a uniform random number
353 .if t 0 ≤ \fIx\fR < \fIn\fR.
363 representations using the base indicated.
364 Only the bases 2, 4, 8, 10, 16, 32, and 64 are
365 supported. Base 0 defaults to 16.
367 skips any leading spaces or tabs.
369 scan stops when encountering a digit not valid in the
372 is zero then C-style prefixes are interpreted to
379 for octal. Otherwise decimal is assumed.
383 is set to point to the character immediately after the
385 If the parse terminates before any digits are found,
390 returns a pointer to the filled buffer.
395 the buffer is allocated.
401 to print hexadecimal representations of
403 The conventional verb is
415 to a byte array. The former creates a big endian representation,
416 the latter a little endian one.
421 it specifies the buffer of length
423 for the result. If the representation
426 bytes, the rest of the buffer is zero filled.
431 then a buffer is allocated and a pointer to it is
432 deposited in the location pointed to by
434 Sign is ignored in these conversions, i.e., the byte
435 array version is always positive.
444 into a fixed length byte array.
446 fills the bytes right adjusted in big endian order so that the least
447 significant byte is at
451 fills in little endian order; left adjusted; so that the least
452 significat byte is filled into
458 convert from a big or little endian byte array at
468 it refers to a preallocated
475 a new integer is allocated and returned as the result.
477 The integer conversions are:
481 .BR mpint -> "unsigned int"
484 .BR "unsigned int" -> mpint
493 .BR mpint -> "unsigned vlong"
496 .BR "unsigned vlong" -> mpint
505 When converting to the base integer types, if the integer is too large,
506 the largest integer of the appropriate sign
507 and size is returned.
509 The mathematical functions are:
513 .BR "sum = b1 + b2" .
516 .BR "sum = abs(b1) + abs(b2)" .
519 .BR "diff = b1 - b2" .
522 .BR "diff = abs(b1) - abs(b2)" .
525 .BR "res = b<<shift" .
528 .BR "res = b>>shift" .
539 .BR "res = b**e mod m" .
542 .BR "remainder = b % m" .
545 .BR "quotient = dividend/divisor" .
546 .BR "remainder = dividend % divisor" .
549 returns -1, 0, or +1 as
551 is less than, equal to, or greater than
557 but ignores the sign and just compares magnitudes.
566 is not zero, otherwise
572 Logical operations (treating negative numbers using two's complement):
576 .BR "res = b1 & b2" .
579 .BR "res = b1 & ~b2" .
582 .BR "res = b1 | b2" .
585 .BR "res = b1 ^ b2" .
594 uses two's complement).
601 bits and stores the result in
603 The result is never negative.
610 bits, sign extends the MSB and stores the result in
618 .BR "sum = b1+b2 mod m" .
621 .BR "diff = b1-b2 mod m" .
624 .BR "prod = b1*b2 mod m" .
628 computes the greatest common denominator,
639 .BR "a*x + b*y = d" .
644 are required to be positive.
645 If called with negative arguments, it will
649 computes the multiplicative inverse of
655 returns the number of significant bits in
658 returns the number of consecutive zero bits
659 at the low end of the significant bits.
660 For example, for 0x14,
671 The remaining routines all work on arrays of
675 They are the basis of all the other routines. They are separated out
676 to allow them to be rewritten in assembler for each architecture. There
677 is also a portable C version for each one.
681 .BR "quotient = dividend[0:1] / divisor" .
684 .BR "sum[0:alen] = a[0:alen-1] + b[0:blen-1]" .
685 We assume alen >= blen and that sum has room for alen+1 digits.
688 .BR "diff[0:alen-1] = a[0:alen-1] - b[0:blen-1]" .
689 We assume that alen >= blen and that diff has room for alen digits.
692 .BR "p[0:n] += m * b[0:n-1]" .
693 This multiplies a an array of digits times a scalar and adds it to another array.
694 We assume p has room for n+1 digits.
697 .BR "p[0:n] -= m * b[0:n-1]" .
698 This multiplies a an array of digits times a scalar and subtracts it from another array.
699 We assume p has room for n+1 digits. It returns +1 is the result is positive and
703 .BR "p[0:alen+blen] = a[0:alen-1] * b[0:blen-1]" .
704 We assume that p has room for alen+blen+1 digits.
707 This returns -1, 0, or +1 as a - b is negative, 0, or positive.
714 are the constants 2, 1 and 0. These cannot be freed.
715 .SS "Time invariant computation"
717 In the field of cryptography, it is sometimes neccesary to implement
718 algorithms such that the runtime of the algorithm is not depdenent on
719 the input data. This library provides partial support for time
720 invariant computation with the
722 flag that can be set on input or destination operands to request timing
723 safe operation. The result of a timing safe operation will also have the
725 flag set and is not normalized.
726 .SS "Chinese remainder theorem
728 When computing in a non-prime modulus,
730 it is possible to perform the computations on the residues modulo the prime
733 instead. Since these numbers are smaller, multiplication and exponentiation
737 computes the residues of
739 and returns them in a newly allocated structure:
742 typedef struct CRTres CRTres;
744 int n; /* number of residues */
745 mpint *r[n]; /* residues */
750 takes a residue representation of a number and converts it back into
751 the number. It also frees the residue structure.
754 saves a copy of the factors and precomputes the constants necessary
755 for converting the residue form back into a number modulo
756 the product of the factors. It returns a newly allocated structure
766 structures respectively.