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