sys/man/2/mp

   1 .TH MP 2
   2 .SH NAME
   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
   4 .SH SYNOPSIS
   5 .B #include <u.h>
   6 .br
   7 .B #include <libc.h>
   8 .br
   9 .B #include <mp.h>
  10 .PP
  11 .ta +\w'\fLCRTpre* \fP'u
  12 .B
  13 mpint*  mpnew(int n)
  14 .PP
  15 .B
  16 void    mpfree(mpint *b)
  17 .PP
  18 .B
  19 void    mpsetminbits(int n)
  20 .PP
  21 .B
  22 void    mpbits(mpint *b, int n)
  23 .PP
  24 .B
  25 mpint*  mpnorm(mpint *b)
  26 .PP
  27 .B
  28 mpint*  mpcopy(mpint *b)
  29 .PP
  30 .B
  31 void    mpassign(mpint *old, mpint *new)
  32 .PP
  33 .B
  34 mpint*  mprand(int bits, void (*gen)(uchar*, int), mpint *b)
  35 .PP
  36 .B
  37 mpint*  mpnrand(mpint *n, void (*gen)(uchar*, int), mpint *b)
  38 .PP
  39 .B
  40 mpint*  strtomp(char *buf, char **rptr, int base, mpint *b)
  41 .PP
  42 .B
  43 char*   mptoa(mpint *b, int base, char *buf, int blen)
  44 .PP
  45 .B
  46 int     mpfmt(Fmt*)
  47 .PP
  48 .B
  49 mpint*  betomp(uchar *buf, uint blen, mpint *b)
  50 .PP
  51 .B
  52 int     mptobe(mpint *b, uchar *buf, uint blen, uchar **bufp)
  53 .PP
  54 .B
  55 void    mptober(mpint *b, uchar *buf, int blen)
  56 .PP
  57 .B
  58 mpint*  letomp(uchar *buf, uint blen, mpint *b)
  59 .PP
  60 .B
  61 int     mptole(mpint *b, uchar *buf, uint blen, uchar **bufp)
  62 .PP
  63 .B
  64 void    mptolel(mpint *b, uchar *buf, int blen)
  65 .PP
  66 .B
  67 uint    mptoui(mpint*)
  68 .PP
  69 .B
  70 mpint*  uitomp(uint, mpint*)
  71 .PP
  72 .B
  73 int     mptoi(mpint*)
  74 .PP
  75 .B
  76 mpint*  itomp(int, mpint*)
  77 .PP
  78 .B
  79 mpint*  vtomp(vlong, mpint*)
  80 .PP
  81 .B
  82 vlong   mptov(mpint*)
  83 .PP
  84 .B
  85 mpint*  uvtomp(uvlong, mpint*)
  86 .PP
  87 .B
  88 uvlong  mptouv(mpint*)
  89 .PP
  90 .B
  91 mpint*  dtomp(double, mpint*)
  92 .PP
  93 .B
  94 double  mptod(mpint*)
  95 .PP
  96 .B
  97 void    mpadd(mpint *b1, mpint *b2, mpint *sum)
  98 .PP
  99 .B
 100 void    mpmagadd(mpint *b1, mpint *b2, mpint *sum)
 101 .PP
 102 .B
 103 void    mpsub(mpint *b1, mpint *b2, mpint *diff)
 104 .PP
 105 .B
 106 void    mpmagsub(mpint *b1, mpint *b2, mpint *diff)
 107 .PP
 108 .B
 109 void    mpleft(mpint *b, int shift, mpint *res)
 110 .PP
 111 .B
 112 void    mpright(mpint *b, int shift, mpint *res)
 113 .PP
 114 .B
 115 void    mpand(mpint *b1, mpint *b2, mpint *res)
 116 .PP
 117 .B
 118 void    mpbic(mpint *b1, mpint *b2, mpint *res)
 119 .PP
 120 .B
 121 void    mpor(mpint *b1, mpint *b2, mpint *res)
 122 .PP
 123 .B
 124 void    mpnot(mpint *b, mpint *res)
 125 .PP
 126 .B
 127 void    mpxor(mpint *b1, mpint *b2, mpint *res)
 128 .PP
 129 .B
 130 void    mptrunc(mpint *b, int n, mpint *res)
 131 .PP
 132 .B
 133 void    mpxtend(mpint *b, int n, mpint *res)
 134 .PP
 135 .B
 136 void    mpasr(mpint *b, int n, mpint *res)
 137 .PP
 138 .B
 139 void    mpmul(mpint *b1, mpint *b2, mpint *prod)
 140 .PP
 141 .B
 142 void    mpexp(mpint *b, mpint *e, mpint *m, mpint *res)
 143 .PP
 144 .B
 145 void    mpmod(mpint *b, mpint *m, mpint *remainder)
 146 .PP
 147 .B
 148 void    mpdiv(mpint *dividend, mpint *divisor,  mpint *quotient,
 149 .br
 150 .B
 151         mpint *remainder)
 152 .PP
 153 .B
 154 void    mpmodadd(mpint *b1, mpint *b2, mpint *m, mpint *sum)
 155 .PP
 156 .B
 157 void    mpmodsub(mpint *b1, mpint *b2, mpint *m, mpint *diff)
 158 .PP
 159 .B
 160 void    mpmodmul(mpint *b1, mpint *b2, mpint *m, mpint *prod)
 161 .PP
 162 .B
 163 int     mpcmp(mpint *b1, mpint *b2)
 164 .PP
 165 .B
 166 int     mpmagcmp(mpint *b1, mpint *b2)
 167 .PP
 168 .B
 169 void    mpsel(int s, mpint *b1, mpint *b2, mpint *res)
 170 .PP
 171 .B
 172 void    mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x,
 173 .br
 174 .B
 175         mpint *y)
 176 .PP
 177 .B
 178 void    mpinvert(mpint *b, mpint *m, mpint *res)
 179 .PP
 180 .B
 181 int     mpsignif(mpint *b)
 182 .PP
 183 .B
 184 int     mplowbits0(mpint *b)
 185 .PP
 186 .B
 187 void    mpdigdiv(mpdigit *dividend, mpdigit divisor,
 188 .br
 189 .B
 190         mpdigit *quotient)
 191 .PP
 192 .B
 193 void    mpvecadd(mpdigit *a, int alen, mpdigit *b, int blen,
 194 .br
 195 .B
 196         mpdigit *sum)
 197 .PP
 198 .B
 199 void    mpvecsub(mpdigit *a, int alen, mpdigit *b, int blen,
 200 .br
 201 .B
 202         mpdigit *diff)
 203 .PP
 204 .B
 205 void    mpvecdigmuladd(mpdigit *b, int n, mpdigit m, mpdigit *p)
 206 .PP
 207 .B
 208 int     mpvecdigmulsub(mpdigit *b, int n, mpdigit m, mpdigit *p)
 209 .PP
 210 .B
 211 void    mpvecmul(mpdigit *a, int alen, mpdigit *b, int blen,
 212 .br
 213 .B
 214         mpdigit *p)
 215 .PP
 216 .B
 217 int     mpveccmp(mpdigit *a, int alen, mpdigit *b, int blen)
 218 .PP
 219 .B
 220 CRTpre* crtpre(int nfactors, mpint **factors)
 221 .PP
 222 .B
 223 CRTres* crtin(CRTpre *crt, mpint *x)
 224 .PP
 225 .B
 226 void    crtout(CRTpre *crt, CRTres *r, mpint *x)
 227 .PP
 228 .B
 229 void    crtprefree(CRTpre *cre)
 230 .PP
 231 .B
 232 void    crtresfree(CRTres *res)
 233 .PP
 234 .B
 235 mpint   *mpzero, *mpone, *mptwo
 236 .DT
 237 .SH DESCRIPTION
 238 These routines perform extended precision integer arithmetic.
 239 The basic type is
 240 .BR mpint ,
 241 which points to an array of
 242 .BR mpdigit s,
 243 stored in little-endian order:
 244 .IP
 245 .EX
 246 typedef struct mpint mpint;
 247 struct mpint
 248 {
 249         int     sign;   /* +1 or -1 */
 250         int     size;   /* allocated digits */
 251         int     top;    /* significant digits */
 252         mpdigit *p;
 253         char    flags;
 254 };
 255 .EE
 256 .PP
 257 The sign of 0 is +1.
 258 .PP
 259 The size of
 260 .B mpdigit
 261 is architecture-dependent and defined in
 262 .BR /$cputype/include/u.h .
 263 .BR Mpint s
 264 are dynamically allocated and must be explicitly freed.  Operations
 265 grow the array of digits as needed.
 266 .PP
 267 In general, the result parameters are last in the
 268 argument list.
 269 .PP
 270 Routines that return an
 271 .B mpint
 272 will allocate the
 273 .B mpint
 274 if the result parameter is
 275 .BR nil .
 276 This includes
 277 .IR strtomp ,
 278 .IR itomp ,
 279 .IR uitomp ,
 280 .IR btomp ,
 281 and
 282 .IR dtomp .
 283 These functions, in addition to
 284 .I mpnew
 285 and
 286 .IR mpcopy ,
 287 will return
 288 .B nil
 289 if the allocation fails.
 290 .PP
 291 Input and result parameters may point to the same
 292 .BR mpint .
 293 The routines check and copy where necessary.
 294 .PP
 295 .I Mpnew
 296 creates an
 297 .B mpint
 298 with an initial allocation of
 299 .I n
 300 bits.
 301 If
 302 .I n
 303 is zero, the allocation will be whatever was specified in the
 304 last call to
 305 .I mpsetminbits
 306 or to the initial value, 1056.
 307 .I Mpfree
 308 frees an
 309 .BR mpint .
 310 .I Mpbits
 311 grows the allocation of
 312 .I b
 313 to fit at least
 314 .I n
 315 bits.  If
 316 .B b->top
 317 doesn't cover
 318 .I n
 319 bits,
 320 .I mpbits
 321 increases it to do so.
 322 Unless you are writing new basic operations, you
 323 can restrict yourself to
 324 .B mpnew(0)
 325 and
 326 .BR mpfree(b) .
 327 .PP
 328 .I Mpnorm
 329 normalizes the representation by trimming any high order zero
 330 digits.  All routines except
 331 .B mpbits
 332 return normalized results.
 333 .PP
 334 .I Mpcopy
 335 creates a new
 336 .B mpint
 337 with the same value as
 338 .I b
 339 while
 340 .I mpassign
 341 sets the value of
 342 .I new
 343 to be that of
 344 .IR old .
 345 .PP
 346 .I Mprand
 347 creates an
 348 .I n
 349 bit random number using the generator
 350 .IR gen .
 351 .I Gen
 352 takes a pointer to a string of uchar's and the number
 353 to fill in.
 354 .PP
 355 .I Mpnrand
 356 uses
 357 .I gen
 358 to generate a uniform random number
 359 .IR x ,
 360 .if t 0 ≤ \fIx\fR < \fIn\fR.
 361 .if n 0 ≤ x < n.
 362 .PP
 363 .I Strtomp
 364 and
 365 .I mptoa
 366 convert between
 367 .SM ASCII
 368 and
 369 .B mpint
 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.
 373 .IR Strtomp
 374 skips any leading spaces or tabs.
 375 .IR Strtomp 's
 376 scan stops when encountering a digit not valid in the
 377 base.  If
 378 .I base
 379 is zero then C-style prefixes are interpreted to
 380 find the base:
 381 .B 0x
 382 for hexadecimal,
 383 .B 0b
 384 for binary and
 385 .B 0
 386 for octal. Otherwise decimal is assumed.
 387 .I rptr
 388 is not zero,
 389 .I *rptr
 390 is set to point to the character immediately after the
 391 string converted.
 392 If the parse terminates before any digits are found,
 393 .I strtomp
 394 return
 395 .BR nil .
 396 .I Mptoa
 397 returns a pointer to the filled buffer.
 398 If the parameter
 399 .I buf
 400 is
 401 .BR nil ,
 402 the buffer is allocated.
 403 .I Mpfmt
 404 can be used with
 405 .IR fmtinstall (2)
 406 and
 407 .IR print (2)
 408 to print hexadecimal representations of
 409 .BR mpint s.
 410 The conventional verb is
 411 .LR B ,
 412 for which
 413 .I mp.h
 414 provides a
 415 .LR pragma .
 416 .PP
 417 .I Mptobe
 418 and
 419 .I mptole
 420 convert an
 421 .I mpint
 422 to a byte array.  The former creates a big endian representation,
 423 the latter a little endian one.
 424 If the destination
 425 .I buf
 426 is not
 427 .BR nil ,
 428 it specifies the buffer of length
 429 .I blen
 430 for the result.  If the representation
 431 is less than
 432 .I blen
 433 bytes, the rest of the buffer is zero filled.
 434 If
 435 .I buf
 436 is
 437 .BR nil ,
 438 then a buffer is allocated and a pointer to it is
 439 deposited in the location pointed to by
 440 .IR bufp .
 441 Sign is ignored in these conversions, i.e., the byte
 442 array version is always positive.
 443 .PP
 444 .I Mptober
 445 and
 446 .I mptolel
 447 fill
 448 .I blen
 449 lower bytes of an
 450 .I mpint
 451 into a fixed length byte array.
 452 .I Mptober
 453 fills the bytes right adjusted in big endian order so that the least
 454 significant byte is at
 455 .I buf[blen-1]
 456 while
 457 .I mptolel
 458 fills in little endian order; left adjusted; so that the least
 459 significat byte is filled into
 460 .IR buf[0] .
 461 .PP
 462 .IR Betomp ,
 463 and
 464 .I letomp
 465 convert from a big or little endian byte array at
 466 .I buf
 467 of length
 468 .I blen
 469 to an
 470 .IR mpint .
 471 If
 472 .I b
 473 is not
 474 .IR nil ,
 475 it refers to a preallocated
 476 .I mpint
 477 for the result.
 478 If
 479 .I b
 480 is
 481 .BR nil ,
 482 a new integer is allocated and returned as the result.
 483 .PP
 484 The integer (and floating point) conversions are:
 485 .TF Mptouv
 486 .TP
 487 .I mptoui
 488 .BR mpint -> "unsigned int"
 489 .TP
 490 .I uitomp
 491 .BR "unsigned int" -> mpint
 492 .TP
 493 .I mptoi
 494 .BR mpint -> "int"
 495 .TP
 496 .I itomp
 497 .BR "int" -> mpint
 498 .TP
 499 .I mptouv
 500 .BR mpint -> "unsigned vlong"
 501 .TP
 502 .I uvtomp
 503 .BR "unsigned vlong" -> mpint
 504 .TP
 505 .I mptov
 506 .BR mpint -> "vlong"
 507 .TP
 508 .I vtomp
 509 .BR "vlong" -> mpint
 510 .TP
 511 .I mptod
 512 .BR mpint -> "double"
 513 .TP
 514 .I dtomp
 515 .BR "double" -> mpint
 516 .PD
 517 .PP
 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.
 521 .PP
 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,
 524 .I mptod
 525 returns infinity of the appropriate sign.
 526 .PP
 527 The mathematical functions are:
 528 .TF mpmagadd
 529 .TP
 530 .I mpadd
 531 .BR "sum = b1 + b2" .
 532 .TP
 533 .I mpmagadd
 534 .BR "sum = abs(b1) + abs(b2)" .
 535 .TP
 536 .I mpsub
 537 .BR "diff = b1 - b2" .
 538 .TP
 539 .I mpmagsub
 540 .BR "diff = abs(b1) - abs(b2)" .
 541 .TP
 542 .I mpleft
 543 .BR "res = b<<shift" .
 544 .TP
 545 .I mpright
 546 .BR "res = b>>shift" .
 547 .TP
 548 .I mpmul
 549 .BR "prod = b1*b2" .
 550 .TP
 551 .I mpexp
 552 if
 553 .I m
 554 is nil,
 555 .BR "res = b**e" .
 556 Otherwise,
 557 .BR "res = b**e mod m" .
 558 .TP
 559 .I mpmod
 560 .BR "remainder = b % m" .
 561 .TP
 562 .I mpdiv
 563 .BR "quotient = dividend/divisor" .
 564 .BR "remainder = dividend % divisor" .
 565 .TP
 566 .I mpcmp
 567 returns -1, 0, or +1 as
 568 .I b1
 569 is less than, equal to, or greater than
 570 .IR b2 .
 571 .TP
 572 .I mpmagcmp
 573 the same as
 574 .I mpcmp
 575 but ignores the sign and just compares magnitudes.
 576 .TP
 577 .I mpsel
 578 assigns
 579 .I b1
 580 to
 581 .I res
 582 when
 583 .I s
 584 is not zero, otherwise
 585 .I b2
 586 is assigned to
 587 .IR res .
 588 .PD
 589 .PP
 590 Logical operations (treating negative numbers using two's complement):
 591 .TF mpxtend_
 592 .TP
 593 .I mpand
 594 .BR "res = b1 & b2" .
 595 .TP
 596 .I mpbic
 597 .BR "res = b1 & ~b2" .
 598 .TP
 599 .I mpor
 600 .BR "res = b1 | b2" .
 601 .TP
 602 .I mpxor
 603 .BR "res = b1 ^ b2" .
 604 .TP
 605 .I mpnot
 606 .BR "res = ~b1" .
 607 .TP
 608 .I mpasr
 609 .BR "res = b>>shift"
 610 (\fImpasr\fR, unlike
 611 .IR mpright ,
 612 uses two's complement).
 613 .TP
 614 .I mptrunc
 615 truncates
 616 .I b
 617 to
 618 .I n
 619 bits and stores the result in
 620 .IR res .
 621 The result is never negative.
 622 .TP
 623 .I mpxtend
 624 truncates
 625 .I b
 626 to
 627 .I n
 628 bits, sign extends the MSB and stores the result in
 629 .IR res .
 630 .PD
 631 .PP
 632 Modular arithmetic:
 633 .TF mpmodmul_
 634 .TP
 635 .I mpmodadd
 636 .BR "sum = b1+b2 mod m" .
 637 .TP
 638 .I mpmodsub
 639 .BR "diff = b1-b2 mod m" .
 640 .TP
 641 .I mpmodmul
 642 .BR "prod = b1*b2 mod m" .
 643 .PD
 644 .PP
 645 .I Mpextendedgcd
 646 computes the greatest common denominator,
 647 .IR d ,
 648 of
 649 .I a
 650 and
 651 .IR b .
 652 It also computes
 653 .I x
 654 and
 655 .I y
 656 such that
 657 .BR "a*x + b*y = d" .
 658 Both
 659 .I a
 660 and
 661 .I b
 662 are required to be positive.
 663 If called with negative arguments, it will
 664 return a gcd of 0.
 665 .PP
 666 .I Mpinvert
 667 computes the multiplicative inverse of
 668 .I b
 669 .B mod
 670 .IR m .
 671 .PP
 672 .I Mpsignif
 673 returns the number of significant bits in
 674 .IR b .
 675 .I Mplowbits0
 676 returns the number of consecutive zero bits
 677 at the low end of the significant bits.
 678 For example, for 0x14,
 679 .I mpsignif
 680 returns 5 and
 681 .I mplowbits0
 682 returns 2.
 683 For 0,
 684 .I mpsignif
 685 and
 686 .I mplowbits0
 687 both return 0.
 688 .PP
 689 The remaining routines all work on arrays of
 690 .B mpdigit
 691 rather than
 692 .BR mpint 's.
 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.
 696 .TF mpvecdigmuladd
 697 .TP
 698 .I mpdigdiv
 699 .BR "quotient = dividend[0:1] / divisor" .
 700 .TP
 701 .I mpvecadd
 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.
 704 .TP
 705 .I mpvecsub
 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.
 708 .TP
 709 .I mpvecdigmuladd
 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.
 713 .TP
 714 .I mpvecdigmulsub
 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
 718 -1 if negative.
 719 .TP
 720 .I mpvecmul
 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.
 723 .TP
 724 .I mpveccmp
 725 This returns -1, 0, or +1 as a - b is negative, 0, or positive.
 726 .PD
 727 .PP
 728 .IR mptwo ,
 729 .I mpone
 730 and
 731 .I mpzero
 732 are the constants 2, 1 and 0.  These cannot be freed.
 733 .SS "Time invariant computation"
 734 .PP
 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
 739 .I MPtimesafe
 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
 742 .I MPtimesafe
 743 flag set and is not normalized.
 744 .SS "Chinese remainder theorem
 745 .PP
 746 When computing in a non-prime modulus,
 747 .IR n,
 748 it is possible to perform the computations on the residues modulo the prime
 749 factors of
 750 .I n
 751 instead.  Since these numbers are smaller, multiplication and exponentiation
 752 can be much faster.
 753 .PP
 754 .I Crtin
 755 computes the residues of
 756 .I x
 757 and returns them in a newly allocated structure:
 758 .IP
 759 .EX
 760 typedef struct CRTres   CRTres;
 761 {
 762         int     n;      /* number of residues */
 763         mpint   *r[n];  /* residues */
 764 };
 765 .EE
 766 .PP
 767 .I Crtout
 768 takes a residue representation of a number and converts it back into
 769 the number.  It also frees the residue structure.
 770 .PP
 771 .I Crepre
 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
 775 containing values.
 776 .PP
 777 .I Crtprefree
 778 and
 779 .I crtresfree
 780 free
 781 .I CRTpre
 782 and
 783 .I CRTres
 784 structures respectively.
 785 .SH SOURCE
 786 .B /sys/src/libmp