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