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