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
375 supported. Base 0 defaults to 16.
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 filled buffer.
405 the buffer is allocated.
411 to print hexadecimal representations of
413 The conventional verb is
425 to a byte array. The former creates a big endian representation,
426 the latter a little endian one.
431 it specifies the buffer of length
433 for the result. If the representation
436 bytes, the rest of the buffer is zero filled.
441 then a buffer is allocated and a pointer to it is
442 deposited in the location pointed to by
444 Sign is ignored in these conversions, i.e., the byte
445 array version is always positive.
454 into a fixed length byte array.
456 fills the bytes right adjusted in big endian order so that the least
457 significant byte is at
461 fills in little endian order; left adjusted; so that the least
462 significat byte is filled into
468 convert from a big or little endian byte array at
478 it refers to a preallocated
485 a new integer is allocated and returned as the result.
487 The integer (and floating point) conversions are:
491 .BR mpint -> "unsigned int"
494 .BR "unsigned int" -> mpint
503 .BR mpint -> "unsigned vlong"
506 .BR "unsigned vlong" -> mpint
515 .BR mpint -> "double"
518 .BR "double" -> mpint
521 When converting to the base integer types, if the integer is too large,
522 the largest integer of the appropriate sign
523 and size is returned.
525 When converting to and from floating point, results are rounded using IEEE 754 "round to nearest".
526 If the integer is too large in magnitude,
528 returns infinity of the appropriate sign.
530 The mathematical functions are:
534 .BR "sum = b1 + b2" .
537 .BR "sum = abs(b1) + abs(b2)" .
540 .BR "diff = b1 - b2" .
543 .BR "diff = abs(b1) - abs(b2)" .
546 .BR "res = b<<shift" .
549 .BR "res = b>>shift" .
560 .BR "res = b**e mod m" .
563 .BR "remainder = b % m" .
566 .BR "quotient = dividend/divisor" .
567 .BR "remainder = dividend % divisor" .
570 returns -1, 0, or +1 as
572 is less than, equal to, or greater than
578 but ignores the sign and just compares magnitudes.
587 is not zero, otherwise
596 Logical operations (treating negative numbers using two's complement):
600 .BR "res = b1 & b2" .
603 .BR "res = b1 & ~b2" .
606 .BR "res = b1 | b2" .
609 .BR "res = b1 ^ b2" .
618 uses two's complement).
625 bits and stores the result in
627 The result is never negative.
634 bits, sign extends the MSB and stores the result in
642 .BR "sum = b1+b2 mod m" .
645 .BR "diff = b1-b2 mod m" .
648 .BR "prod = b1*b2 mod m" .
652 computes the greatest common denominator,
663 .BR "a*x + b*y = d" .
668 are required to be positive.
669 If called with negative arguments, it will
673 computes the multiplicative inverse of
679 returns the number of significant bits in
682 returns the number of consecutive zero bits
683 at the low end of the significant bits.
684 For example, for 0x14,
695 The remaining routines all work on arrays of
699 They are the basis of all the other routines. They are separated out
700 to allow them to be rewritten in assembler for each architecture. There
701 is also a portable C version for each one.
705 .BR "quotient = dividend[0:1] / divisor" .
708 .BR "sum[0:alen] = a[0:alen-1] + b[0:blen-1]" .
709 We assume alen >= blen and that sum has room for alen+1 digits.
712 .BR "diff[0:alen-1] = a[0:alen-1] - b[0:blen-1]" .
713 We assume that alen >= blen and that diff has room for alen digits.
716 .BR "p[0:n] += m * b[0:n-1]" .
717 This multiplies a an array of digits times a scalar and adds it to another array.
718 We assume p has room for n+1 digits.
721 .BR "p[0:n] -= m * b[0:n-1]" .
722 This multiplies a an array of digits times a scalar and subtracts it from another array.
723 We assume p has room for n+1 digits. It returns +1 is the result is positive and
727 .BR "p[0:alen+blen] = a[0:alen-1] * b[0:blen-1]" .
728 We assume that p has room for alen+blen+1 digits.
731 This returns -1, 0, or +1 as a - b is negative, 0, or positive.
738 are the constants 2, 1 and 0. These cannot be freed.
739 .SS "Time invariant computation"
741 In the field of cryptography, it is sometimes neccesary to implement
742 algorithms such that the runtime of the algorithm is not depdenent on
743 the input data. This library provides partial support for time
744 invariant computation with the
746 flag that can be set on input or destination operands to request timing
747 safe operation. The result of a timing safe operation will also have the
749 flag set and is not normalized.
750 .SS "Chinese remainder theorem
752 When computing in a non-prime modulus,
754 it is possible to perform the computations on the residues modulo the prime
757 instead. Since these numbers are smaller, multiplication and exponentiation
761 computes the residues of
763 and returns them in a newly allocated structure:
766 typedef struct CRTres CRTres;
768 int n; /* number of residues */
769 mpint *r[n]; /* residues */
774 takes a residue representation of a number and converts it back into
775 the number. It also frees the residue structure.
778 saves a copy of the factors and precomputes the constants necessary
779 for converting the residue form back into a number modulo
780 the product of the factors. It returns a newly allocated structure
790 structures respectively.