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.  Base 0 defaults to 16.
 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 filled buffer.
 401 If the parameter
 402 .I buf
 403 is
 404 .BR nil ,
 405 the buffer is allocated.
 406 .I Mpfmt
 407 can be used with
 408 .IR fmtinstall (2)
 409 and
 410 .IR print (2)
 411 to print hexadecimal representations of
 412 .BR mpint s.
 413 The conventional verb is
 414 .LR B ,
 415 for which
 416 .I mp.h
 417 provides a
 418 .LR pragma .
 419 .PP
 420 .I Mptobe
 421 and
 422 .I mptole
 423 convert an
 424 .I mpint
 425 to a byte array.  The former creates a big endian representation,
 426 the latter a little endian one.
 427 If the destination
 428 .I buf
 429 is not
 430 .BR nil ,
 431 it specifies the buffer of length
 432 .I blen
 433 for the result.  If the representation
 434 is less than
 435 .I blen
 436 bytes, the rest of the buffer is zero filled.
 437 If
 438 .I buf
 439 is
 440 .BR nil ,
 441 then a buffer is allocated and a pointer to it is
 442 deposited in the location pointed to by
 443 .IR bufp .
 444 Sign is ignored in these conversions, i.e., the byte
 445 array version is always positive.
 446 .PP
 447 .I Mptober
 448 and
 449 .I mptolel
 450 fill
 451 .I blen
 452 lower bytes of an
 453 .I mpint
 454 into a fixed length byte array.
 455 .I Mptober
 456 fills the bytes right adjusted in big endian order so that the least
 457 significant byte is at
 458 .I buf[blen-1]
 459 while
 460 .I mptolel
 461 fills in little endian order; left adjusted; so that the least
 462 significat byte is filled into
 463 .IR buf[0] .
 464 .PP
 465 .IR Betomp ,
 466 and
 467 .I letomp
 468 convert from a big or little endian byte array at
 469 .I buf
 470 of length
 471 .I blen
 472 to an
 473 .IR mpint .
 474 If
 475 .I b
 476 is not
 477 .IR nil ,
 478 it refers to a preallocated
 479 .I mpint
 480 for the result.
 481 If
 482 .I b
 483 is
 484 .BR nil ,
 485 a new integer is allocated and returned as the result.
 486 .PP
 487 The integer (and floating point) conversions are:
 488 .TF Mptouv
 489 .TP
 490 .I mptoui
 491 .BR mpint -> "unsigned int"
 492 .TP
 493 .I uitomp
 494 .BR "unsigned int" -> mpint
 495 .TP
 496 .I mptoi
 497 .BR mpint -> "int"
 498 .TP
 499 .I itomp
 500 .BR "int" -> mpint
 501 .TP
 502 .I mptouv
 503 .BR mpint -> "unsigned vlong"
 504 .TP
 505 .I uvtomp
 506 .BR "unsigned vlong" -> mpint
 507 .TP
 508 .I mptov
 509 .BR mpint -> "vlong"
 510 .TP
 511 .I vtomp
 512 .BR "vlong" -> mpint
 513 .TP
 514 .I mptod
 515 .BR mpint -> "double"
 516 .TP
 517 .I dtomp
 518 .BR "double" -> mpint
 519 .PD
 520 .PP
 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.
 524 .PP
 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,
 527 .I mptod
 528 returns infinity of the appropriate sign.
 529 .PP
 530 The mathematical functions are:
 531 .TF mpfactorial
 532 .TP
 533 .I mpadd
 534 .BR "sum = b1 + b2" .
 535 .TP
 536 .I mpmagadd
 537 .BR "sum = abs(b1) + abs(b2)" .
 538 .TP
 539 .I mpsub
 540 .BR "diff = b1 - b2" .
 541 .TP
 542 .I mpmagsub
 543 .BR "diff = abs(b1) - abs(b2)" .
 544 .TP
 545 .I mpleft
 546 .BR "res = b<<shift" .
 547 .TP
 548 .I mpright
 549 .BR "res = b>>shift" .
 550 .TP
 551 .I mpmul
 552 .BR "prod = b1*b2" .
 553 .TP
 554 .I mpexp
 555 if
 556 .I m
 557 is nil,
 558 .BR "res = b**e" .
 559 Otherwise,
 560 .BR "res = b**e mod m" .
 561 .TP
 562 .I mpmod
 563 .BR "remainder = b % m" .
 564 .TP
 565 .I mpdiv
 566 .BR "quotient = dividend/divisor" .
 567 .BR "remainder = dividend % divisor" .
 568 .TP
 569 .I mpcmp
 570 returns -1, 0, or +1 as
 571 .I b1
 572 is less than, equal to, or greater than
 573 .IR b2 .
 574 .TP
 575 .I mpmagcmp
 576 the same as
 577 .I mpcmp
 578 but ignores the sign and just compares magnitudes.
 579 .TP
 580 .I mpsel
 581 assigns
 582 .I b1
 583 to
 584 .I res
 585 when
 586 .I s
 587 is not zero, otherwise
 588 .I b2
 589 is assigned to
 590 .IR res .
 591 .TP
 592 .I mpfactorial
 593 returns \fIn\fR!.
 594 .PD
 595 .PP
 596 Logical operations (treating negative numbers using two's complement):
 597 .TF mpxtend_
 598 .TP
 599 .I mpand
 600 .BR "res = b1 & b2" .
 601 .TP
 602 .I mpbic
 603 .BR "res = b1 & ~b2" .
 604 .TP
 605 .I mpor
 606 .BR "res = b1 | b2" .
 607 .TP
 608 .I mpxor
 609 .BR "res = b1 ^ b2" .
 610 .TP
 611 .I mpnot
 612 .BR "res = ~b1" .
 613 .TP
 614 .I mpasr
 615 .BR "res = b>>shift"
 616 (\fImpasr\fR, unlike
 617 .IR mpright ,
 618 uses two's complement).
 619 .TP
 620 .I mptrunc
 621 truncates
 622 .I b
 623 to
 624 .I n
 625 bits and stores the result in
 626 .IR res .
 627 The result is never negative.
 628 .TP
 629 .I mpxtend
 630 truncates
 631 .I b
 632 to
 633 .I n
 634 bits, sign extends the MSB and stores the result in
 635 .IR res .
 636 .PD
 637 .PP
 638 Modular arithmetic:
 639 .TF mpmodmul_
 640 .TP
 641 .I mpmodadd
 642 .BR "sum = b1+b2 mod m" .
 643 .TP
 644 .I mpmodsub
 645 .BR "diff = b1-b2 mod m" .
 646 .TP
 647 .I mpmodmul
 648 .BR "prod = b1*b2 mod m" .
 649 .PD
 650 .PP
 651 .I Mpextendedgcd
 652 computes the greatest common denominator,
 653 .IR d ,
 654 of
 655 .I a
 656 and
 657 .IR b .
 658 It also computes
 659 .I x
 660 and
 661 .I y
 662 such that
 663 .BR "a*x + b*y = d" .
 664 Both
 665 .I a
 666 and
 667 .I b
 668 are required to be positive.
 669 If called with negative arguments, it will
 670 return a gcd of 0.
 671 .PP
 672 .I Mpinvert
 673 computes the multiplicative inverse of
 674 .I b
 675 .B mod
 676 .IR m .
 677 .PP
 678 .I Mpsignif
 679 returns the number of significant bits in
 680 .IR b .
 681 .I Mplowbits0
 682 returns the number of consecutive zero bits
 683 at the low end of the significant bits.
 684 For example, for 0x14,
 685 .I mpsignif
 686 returns 5 and
 687 .I mplowbits0
 688 returns 2.
 689 For 0,
 690 .I mpsignif
 691 and
 692 .I mplowbits0
 693 both return 0.
 694 .PP
 695 The remaining routines all work on arrays of
 696 .B mpdigit
 697 rather than
 698 .BR mpint 's.
 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.
 702 .TF mpvecdigmuladd
 703 .TP
 704 .I mpdigdiv
 705 .BR "quotient = dividend[0:1] / divisor" .
 706 .TP
 707 .I mpvecadd
 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.
 710 .TP
 711 .I mpvecsub
 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.
 714 .TP
 715 .I mpvecdigmuladd
 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.
 719 .TP
 720 .I mpvecdigmulsub
 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
 724 -1 if negative.
 725 .TP
 726 .I mpvecmul
 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.
 729 .TP
 730 .I mpveccmp
 731 This returns -1, 0, or +1 as a - b is negative, 0, or positive.
 732 .PD
 733 .PP
 734 .IR mptwo ,
 735 .I mpone
 736 and
 737 .I mpzero
 738 are the constants 2, 1 and 0.  These cannot be freed.
 739 .SS "Time invariant computation"
 740 .PP
 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
 745 .I MPtimesafe
 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
 748 .I MPtimesafe
 749 flag set and is not normalized.
 750 .SS "Chinese remainder theorem
 751 .PP
 752 When computing in a non-prime modulus,
 753 .IR n,
 754 it is possible to perform the computations on the residues modulo the prime
 755 factors of
 756 .I n
 757 instead.  Since these numbers are smaller, multiplication and exponentiation
 758 can be much faster.
 759 .PP
 760 .I Crtin
 761 computes the residues of
 762 .I x
 763 and returns them in a newly allocated structure:
 764 .IP
 765 .EX
 766 typedef struct CRTres   CRTres;
 767 {
 768         int     n;      /* number of residues */
 769         mpint   *r[n];  /* residues */
 770 };
 771 .EE
 772 .PP
 773 .I Crtout
 774 takes a residue representation of a number and converts it back into
 775 the number.  It also frees the residue structure.
 776 .PP
 777 .I Crepre
 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
 781 containing values.
 782 .PP
 783 .I Crtprefree
 784 and
 785 .I crtresfree
 786 free
 787 .I CRTpre
 788 and
 789 .I CRTres
 790 structures respectively.
 791 .SH SOURCE
 792 .B /sys/src/libmp