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, mpfactorial, 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 mpint* mpfactorial(ulong n)
175 void mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x,
181 void mpinvert(mpint *b, mpint *m, mpint *res)
184 int mpsignif(mpint *b)
187 int mplowbits0(mpint *b)
190 void mpdigdiv(mpdigit *dividend, mpdigit divisor,
196 void mpvecadd(mpdigit *a, int alen, mpdigit *b, int blen,
202 void mpvecsub(mpdigit *a, int alen, mpdigit *b, int blen,
208 void mpvecdigmuladd(mpdigit *b, int n, mpdigit m, mpdigit *p)
211 int mpvecdigmulsub(mpdigit *b, int n, mpdigit m, mpdigit *p)
214 void mpvecmul(mpdigit *a, int alen, mpdigit *b, int blen,
220 int mpveccmp(mpdigit *a, int alen, mpdigit *b, int blen)
223 CRTpre* crtpre(int nfactors, mpint **factors)
226 CRTres* crtin(CRTpre *crt, mpint *x)
229 void crtout(CRTpre *crt, CRTres *r, mpint *x)
232 void crtprefree(CRTpre *cre)
235 void crtresfree(CRTres *res)
238 mpint *mpzero, *mpone, *mptwo
241 These routines perform extended precision integer arithmetic.
244 which points to an array of
246 stored in little-endian order:
249 typedef struct mpint mpint;
252 int sign; /* +1 or -1 */
253 int size; /* allocated digits */
254 int top; /* significant digits */
264 is architecture-dependent and defined in
265 .BR /$cputype/include/u.h .
267 are dynamically allocated and must be explicitly freed. Operations
268 grow the array of digits as needed.
270 In general, the result parameters are last in the
273 Routines that return an
277 if the result parameter is
286 These functions, in addition to
292 if the allocation fails.
294 Input and result parameters may point to the same
296 The routines check and copy where necessary.
301 with an initial allocation of
306 is zero, the allocation will be whatever was specified in the
309 or to the initial value, 1056.
314 grows the allocation of
324 increases it to do so.
325 Unless you are writing new basic operations, you
326 can restrict yourself to
332 normalizes the representation by trimming any high order zero
333 digits. All routines except
335 return normalized results.
340 with the same value as
352 bit random number using the generator
355 takes a pointer to a string of uchar's and the number
361 to generate a uniform random number
363 .if t 0 ≤ \fIx\fR < \fIn\fR.
373 representations using the base indicated.
374 Only the bases 2, 4, 8, 10, 16, 32, and 64 are
377 skips any leading spaces or tabs.
379 scan stops when encountering a digit not valid in the
382 is zero then C-style prefixes are interpreted to
389 for octal. Otherwise decimal is assumed.
393 is set to point to the character immediately after the
395 If the parse terminates before any digits are found,
400 returns a pointer to the
407 the buffer is allocated.
410 to zero uses hexadecimal default.
420 The conventional verb is
426 The precisition in the format string changes the base,
427 defaulting to hexadecimal when omited.
434 to a byte array. The former creates a big endian representation,
435 the latter a little endian one.
440 it specifies the buffer of length
442 for the result. If the representation
445 bytes, the rest of the buffer is zero filled.
450 then a buffer is allocated and a pointer to it is
451 deposited in the location pointed to by
453 Sign is ignored in these conversions, i.e., the byte
454 array version is always positive.
463 into a fixed length byte array.
465 fills the bytes right adjusted in big endian order so that the least
466 significant byte is at
470 fills in little endian order; left adjusted; so that the least
471 significat byte is filled into
477 convert from a big or little endian byte array at
487 it refers to a preallocated
494 a new integer is allocated and returned as the result.
496 The integer (and floating point) conversions are:
500 .BR mpint -> "unsigned int"
503 .BR "unsigned int" -> mpint
512 .BR mpint -> "unsigned vlong"
515 .BR "unsigned vlong" -> mpint
524 .BR mpint -> "double"
527 .BR "double" -> mpint
530 When converting to the base integer types, if the integer is too large,
531 the largest integer of the appropriate sign
532 and size is returned.
534 When converting to and from floating point, results are rounded using IEEE 754 "round to nearest".
535 If the integer is too large in magnitude,
537 returns infinity of the appropriate sign.
539 The mathematical functions are:
543 .BR "sum = b1 + b2" .
546 .BR "sum = abs(b1) + abs(b2)" .
549 .BR "diff = b1 - b2" .
552 .BR "diff = abs(b1) - abs(b2)" .
555 .BR "res = b<<shift" .
558 .BR "res = b>>shift" .
569 .BR "res = b**e mod m" .
572 .BR "remainder = b % m" .
575 .BR "quotient = dividend/divisor" .
576 .BR "remainder = dividend % divisor" .
579 returns -1, 0, or +1 as
581 is less than, equal to, or greater than
587 but ignores the sign and just compares magnitudes.
596 is not zero, otherwise
605 Logical operations (treating negative numbers using two's complement):
609 .BR "res = b1 & b2" .
612 .BR "res = b1 & ~b2" .
615 .BR "res = b1 | b2" .
618 .BR "res = b1 ^ b2" .
627 uses two's complement).
634 bits and stores the result in
636 The result is never negative.
643 bits, sign extends the MSB and stores the result in
651 .BR "sum = b1+b2 mod m" .
654 .BR "diff = b1-b2 mod m" .
657 .BR "prod = b1*b2 mod m" .
661 computes the greatest common denominator,
672 .BR "a*x + b*y = d" .
677 are required to be positive.
678 If called with negative arguments, it will
682 computes the multiplicative inverse of
688 returns the number of significant bits in
691 returns the number of consecutive zero bits
692 at the low end of the significant bits.
693 For example, for 0x14,
704 The remaining routines all work on arrays of
708 They are the basis of all the other routines. They are separated out
709 to allow them to be rewritten in assembler for each architecture. There
710 is also a portable C version for each one.
714 .BR "quotient = dividend[0:1] / divisor" .
717 .BR "sum[0:alen] = a[0:alen-1] + b[0:blen-1]" .
718 We assume alen >= blen and that sum has room for alen+1 digits.
721 .BR "diff[0:alen-1] = a[0:alen-1] - b[0:blen-1]" .
722 We assume that alen >= blen and that diff has room for alen digits.
725 .BR "p[0:n] += m * b[0:n-1]" .
726 This multiplies a an array of digits times a scalar and adds it to another array.
727 We assume p has room for n+1 digits.
730 .BR "p[0:n] -= m * b[0:n-1]" .
731 This multiplies a an array of digits times a scalar and subtracts it from another array.
732 We assume p has room for n+1 digits. It returns +1 is the result is positive and
736 .BR "p[0:alen+blen] = a[0:alen-1] * b[0:blen-1]" .
737 We assume that p has room for alen+blen+1 digits.
740 This returns -1, 0, or +1 as a - b is negative, 0, or positive.
747 are the constants 2, 1 and 0. These cannot be freed.
748 .SS "Time invariant computation"
750 In the field of cryptography, it is sometimes neccesary to implement
751 algorithms such that the runtime of the algorithm is not depdenent on
752 the input data. This library provides partial support for time
753 invariant computation with the
755 flag that can be set on input or destination operands to request timing
756 safe operation. The result of a timing safe operation will also have the
758 flag set and is not normalized.
759 .SS "Chinese remainder theorem
761 When computing in a non-prime modulus,
763 it is possible to perform the computations on the residues modulo the prime
766 instead. Since these numbers are smaller, multiplication and exponentiation
770 computes the residues of
772 and returns them in a newly allocated structure:
775 typedef struct CRTres CRTres;
777 int n; /* number of residues */
778 mpint *r[n]; /* residues */
783 takes a residue representation of a number and converts it back into
784 the number. It also frees the residue structure.
787 saves a copy of the factors and precomputes the constants necessary
788 for converting the residue form back into a number modulo
789 the product of the factors. It returns a newly allocated structure
799 structures respectively.