sys/man/2/mp

   1 .TH MP 2
   2 .SH NAME
   3 mpsetminbits, mpnew, mpfree, mpbits, mpnorm, mpcopy, mpassign, mprand, strtomp, mpfmt,mptoa, betomp, mptobe, letomp, mptole, mptoui, uitomp, mptoi, itomp, uvtomp, mptouv, vtomp, mptov, mpdigdiv, mpadd, mpsub, mpleft, mpright, mpmul, mpexp, mpmod, mpdiv, mpcmp, 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 void    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*  strtomp(char *buf, char **rptr, int base, mpint *b)
  38 .PP
  39 .B
  40 char*   mptoa(mpint *b, int base, char *buf, int blen)
  41 .PP
  42 .B
  43 int     mpfmt(Fmt*)
  44 .PP
  45 .B
  46 mpint*  betomp(uchar *buf, uint blen, mpint *b)
  47 .PP
  48 .B
  49 int     mptobe(mpint *b, uchar *buf, uint blen, uchar **bufp)
  50 .PP
  51 .B
  52 mpint*  letomp(uchar *buf, uint blen, mpint *b)
  53 .PP
  54 .B
  55 int     mptole(mpint *b, uchar *buf, uint blen, uchar **bufp)
  56 .PP
  57 .B
  58 uint    mptoui(mpint*)
  59 .PP
  60 .B
  61 mpint*  uitomp(uint, mpint*)
  62 .PP
  63 .B
  64 int     mptoi(mpint*)
  65 .PP
  66 .B
  67 mpint*  itomp(int, mpint*)
  68 .PP
  69 .B
  70 mpint*  vtomp(vlong, mpint*)
  71 .PP
  72 .B
  73 vlong   mptov(mpint*)
  74 .PP
  75 .B
  76 mpint*  uvtomp(uvlong, mpint*)
  77 .PP
  78 .B
  79 uvlong  mptouv(mpint*)
  80 .PP
  81 .B
  82 void    mpadd(mpint *b1, mpint *b2, mpint *sum)
  83 .PP
  84 .B
  85 void    mpmagadd(mpint *b1, mpint *b2, mpint *sum)
  86 .PP
  87 .B
  88 void    mpsub(mpint *b1, mpint *b2, mpint *diff)
  89 .PP
  90 .B
  91 void    mpmagsub(mpint *b1, mpint *b2, mpint *diff)
  92 .PP
  93 .B
  94 void    mpleft(mpint *b, int shift, mpint *res)
  95 .PP
  96 .B
  97 void    mpright(mpint *b, int shift, mpint *res)
  98 .PP
  99 .B
 100 void    mpmul(mpint *b1, mpint *b2, mpint *prod)
 101 .PP
 102 .B
 103 void    mpexp(mpint *b, mpint *e, mpint *m, mpint *res)
 104 .PP
 105 .B
 106 void    mpmod(mpint *b, mpint *m, mpint *remainder)
 107 .PP
 108 .B
 109 void    mpdiv(mpint *dividend, mpint *divisor,  mpint *quotient,
 110 .br
 111 .B
 112         mpint *remainder)
 113 .PP
 114 .B
 115 int     mpcmp(mpint *b1, mpint *b2)
 116 .PP
 117 .B
 118 int     mpmagcmp(mpint *b1, mpint *b2)
 119 .PP
 120 .B
 121 void    mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x,
 122 .br
 123 .B
 124         mpint *y)
 125 .PP
 126 .B
 127 void    mpinvert(mpint *b, mpint *m, mpint *res)
 128 .PP
 129 .B
 130 int     mpsignif(mpint *b)
 131 .PP
 132 .B
 133 int     mplowbits0(mpint *b)
 134 .PP
 135 .B
 136 void    mpdigdiv(mpdigit *dividend, mpdigit divisor,
 137 .br
 138 .B
 139         mpdigit *quotient)
 140 .PP
 141 .B
 142 void    mpvecadd(mpdigit *a, int alen, mpdigit *b, int blen,
 143 .br
 144 .B
 145         mpdigit *sum)
 146 .PP
 147 .B
 148 void    mpvecsub(mpdigit *a, int alen, mpdigit *b, int blen,
 149 .br
 150 .B
 151         mpdigit *diff)
 152 .PP
 153 .B
 154 void    mpvecdigmuladd(mpdigit *b, int n, mpdigit m, mpdigit *p)
 155 .PP
 156 .B
 157 int     mpvecdigmulsub(mpdigit *b, int n, mpdigit m, mpdigit *p)
 158 .PP
 159 .B
 160 void    mpvecmul(mpdigit *a, int alen, mpdigit *b, int blen,
 161 .br
 162 .B
 163         mpdigit *p)
 164 .PP
 165 .B
 166 int     mpveccmp(mpdigit *a, int alen, mpdigit *b, int blen)
 167 .PP
 168 .B
 169 CRTpre* crtpre(int nfactors, mpint **factors)
 170 .PP
 171 .B
 172 CRTres* crtin(CRTpre *crt, mpint *x)
 173 .PP
 174 .B
 175 void    crtout(CRTpre *crt, CRTres *r, mpint *x)
 176 .PP
 177 .B
 178 void    crtprefree(CRTpre *cre)
 179 .PP
 180 .B
 181 void    crtresfree(CRTres *res)
 182 .PP
 183 .B
 184 mpint   *mpzero, *mpone, *mptwo
 185 .DT
 186 .SH DESCRIPTION
 187 These routines perform extended precision integer arithmetic.
 188 The basic type is
 189 .BR mpint ,
 190 which points to an array of
 191 .BR mpdigit s,
 192 stored in little-endian order:
 193 .IP
 194 .EX
 195 typedef struct mpint mpint;
 196 struct mpint
 197 {
 198         int     sign;   /* +1 or -1 */
 199         int     size;   /* allocated digits */
 200         int     top;    /* significant digits */
 201         mpdigit *p;
 202         char    flags;
 203 };
 204 .EE
 205 .PP
 206 The sign of 0 is +1.
 207 .PP
 208 The size of
 209 .B mpdigit
 210 is architecture-dependent and defined in
 211 .BR /$cputype/include/u.h .
 212 .BR Mpint s
 213 are dynamically allocated and must be explicitly freed.  Operations
 214 grow the array of digits as needed.
 215 .PP
 216 In general, the result parameters are last in the
 217 argument list.
 218 .PP
 219 Routines that return an
 220 .B mpint
 221 will allocate the
 222 .B mpint
 223 if the result parameter is
 224 .BR nil .
 225 This includes
 226 .IR strtomp ,
 227 .IR itomp ,
 228 .IR uitomp ,
 229 and
 230 .IR btomp .
 231 These functions, in addition to
 232 .I mpnew
 233 and
 234 .IR mpcopy ,
 235 will return
 236 .B nil
 237 if the allocation fails.
 238 .PP
 239 Input and result parameters may point to the same
 240 .BR mpint .
 241 The routines check and copy where necessary.
 242 .PP
 243 .I Mpnew
 244 creates an
 245 .B mpint
 246 with an initial allocation of
 247 .I n
 248 bits.
 249 If
 250 .I n
 251 is zero, the allocation will be whatever was specified in the
 252 last call to
 253 .I mpsetminbits
 254 or to the initial value, 1056.
 255 .I Mpfree
 256 frees an
 257 .BR mpint .
 258 .I Mpbits
 259 grows the allocation of
 260 .I b
 261 to fit at least
 262 .I n
 263 bits.  If
 264 .B b->top
 265 doesn't cover
 266 .I n
 267 bits,
 268 .I mpbits
 269 increases it to do so.
 270 Unless you are writing new basic operations, you
 271 can restrict yourself to
 272 .B mpnew(0)
 273 and
 274 .BR mpfree(b) .
 275 .PP
 276 .I Mpnorm
 277 normalizes the representation by trimming any high order zero
 278 digits.  All routines except
 279 .B mpbits
 280 return normalized results.
 281 .PP
 282 .I Mpcopy
 283 creates a new
 284 .B mpint
 285 with the same value as
 286 .I b
 287 while
 288 .I mpassign
 289 sets the value of
 290 .I new
 291 to be that of
 292 .IR old .
 293 .PP
 294 .I Mprand
 295 creates an
 296 .I n
 297 bit random number using the generator
 298 .IR gen .
 299 .I Gen
 300 takes a pointer to a string of uchar's and the number
 301 to fill in.
 302 .PP
 303 .I Strtomp
 304 and
 305 .I mptoa
 306 convert between
 307 .SM ASCII
 308 and
 309 .B mpint
 310 representations using the base indicated.
 311 Only the bases 10, 16, 32, and 64 are
 312 supported.  Anything else defaults to 16.
 313 .IR Strtomp
 314 skips any leading spaces or tabs.
 315 .IR Strtomp 's
 316 scan stops when encountering a digit not valid in the
 317 base.  If
 318 .I rptr
 319 is not zero,
 320 .I *rptr
 321 is set to point to the character immediately after the
 322 string converted.
 323 If the parse pterminates before any digits are found,
 324 .I strtomp
 325 return
 326 .BR nil .
 327 .I Mptoa
 328 returns a pointer to the filled buffer.
 329 If the parameter
 330 .I buf
 331 is
 332 .BR nil ,
 333 the buffer is allocated.
 334 .I Mpfmt
 335 can be used with
 336 .IR fmtinstall (2)
 337 and
 338 .IR print (2)
 339 to print hexadecimal representations of
 340 .BR mpint s.
 341 The conventional verb is
 342 .LR B ,
 343 for which
 344 .I mp.h
 345 provides a
 346 .LR pragma .
 347 .PP
 348 .I Mptobe
 349 and
 350 .I mptole
 351 convert an
 352 .I mpint
 353 to a byte array.  The former creates a big endian representation,
 354 the latter a little endian one.
 355 If the destination
 356 .I buf
 357 is not
 358 .BR nil ,
 359 it specifies the buffer of length
 360 .I blen
 361 for the result.  If the representation
 362 is less than
 363 .I blen
 364 bytes, the rest of the buffer is zero filled.
 365 If
 366 .I buf
 367 is
 368 .BR nil ,
 369 then a buffer is allocated and a pointer to it is
 370 deposited in the location pointed to by
 371 .IR bufp .
 372 Sign is ignored in these conversions, i.e., the byte
 373 array version is always positive.
 374 .PP
 375 .IR Betomp ,
 376 and
 377 .I letomp
 378 convert from a big or little endian byte array at
 379 .I buf
 380 of length
 381 .I blen
 382 to an
 383 .IR mpint .
 384 If
 385 .I b
 386 is not
 387 .IR nil ,
 388 it refers to a preallocated
 389 .I mpint
 390 for the result.
 391 If
 392 .I b
 393 is
 394 .BR nil ,
 395 a new integer is allocated and returned as the result.
 396 .PP
 397 The integer conversions are:
 398 .TF Mptouv
 399 .TP
 400 .I mptoui
 401 .BR mpint -> "unsigned int"
 402 .TP
 403 .I uitomp
 404 .BR "unsigned int" -> mpint
 405 .TP
 406 .I mptoi
 407 .BR mpint -> "int"
 408 .TP
 409 .I itomp
 410 .BR "int" -> mpint
 411 .TP
 412 .I mptouv
 413 .BR mpint -> "unsigned vlong"
 414 .TP
 415 .I uvtomp
 416 .BR "unsigned vlong" -> mpint
 417 .TP
 418 .I mptov
 419 .BR mpint -> "vlong"
 420 .TP
 421 .I vtomp
 422 .BR "vlong" -> mpint
 423 .PD
 424 .PP
 425 When converting to the base integer types, if the integer is too large,
 426 the largest integer of the appropriate sign
 427 and size is returned.
 428 .PP
 429 The mathematical functions are:
 430 .TF mpmagadd
 431 .TP
 432 .I mpadd
 433 .BR "sum = b1 + b2" .
 434 .TP
 435 .I mpmagadd
 436 .BR "sum = abs(b1) + abs(b2)" .
 437 .TP
 438 .I mpsub
 439 .BR "diff = b1 - b2" .
 440 .TP
 441 .I mpmagsub
 442 .BR "diff = abs(b1) - abs(b2)" .
 443 .TP
 444 .I mpleft
 445 .BR "res = b<<shift" .
 446 .TP
 447 .I mpright
 448 .BR "res = b>>shift" .
 449 .TP
 450 .I mpmul
 451 .BR "prod = b1*b2" .
 452 .TP
 453 .I mpexp
 454 if
 455 .I m
 456 is nil,
 457 .BR "res = b**e" .
 458 Otherwise,
 459 .BR "res = b**e mod m" .
 460 .TP
 461 .I mpmod
 462 .BR "remainder = b % m" .
 463 .TP
 464 .I mpdiv
 465 .BR "quotient = dividend/divisor" .
 466 .BR "remainder = dividend % divisor" .
 467 .TP
 468 .I mpcmp
 469 returns -1, 0, or +1 as
 470 .I b1
 471 is less than, equal to, or greater than
 472 .IR b2 .
 473 .TP
 474 .I mpmagcmp
 475 the same as
 476 .I mpcmp
 477 but ignores the sign and just compares magnitudes.
 478 .PD
 479 .PP
 480 .I Mpextendedgcd
 481 computes the greatest common denominator,
 482 .IR d ,
 483 of
 484 .I a
 485 and
 486 .IR b .
 487 It also computes
 488 .I x
 489 and
 490 .I y
 491 such that
 492 .BR "a*x + b*y = d" .
 493 Both
 494 .I a
 495 and
 496 .I b
 497 are required to be positive.
 498 If called with negative arguments, it will
 499 return a gcd of 0.
 500 .PP
 501 .I Mpinverse
 502 computes the multiplicative inverse of
 503 .I b
 504 .B mod
 505 .IR m .
 506 .PP
 507 .I Mpsignif
 508 returns the number of significant bits in
 509 .IR b .
 510 .I Mplowbits0
 511 returns the number of consecutive zero bits
 512 at the low end of the significant bits.
 513 For example, for 0x14,
 514 .I mpsignif
 515 returns 5 and
 516 .I mplowbits0
 517 returns 2.
 518 For 0,
 519 .I mpsignif
 520 and
 521 .I mplowbits0
 522 both return 0.
 523 .PP
 524 The remaining routines all work on arrays of
 525 .B mpdigit
 526 rather than
 527 .BR mpint 's.
 528 They are the basis of all the other routines.  They are separated out
 529 to allow them to be rewritten in assembler for each architecture.  There
 530 is also a portable C version for each one.
 531 .TF mpvecdigmuladd
 532 .TP
 533 .I mpdigdiv
 534 .BR "quotient = dividend[0:1] / divisor" .
 535 .TP
 536 .I mpvecadd
 537 .BR "sum[0:alen] = a[0:alen-1] + b[0:blen-1]" .
 538 We assume alen >= blen and that sum has room for alen+1 digits.
 539 .TP
 540 .I mpvecsub
 541 .BR "diff[0:alen-1] = a[0:alen-1] - b[0:blen-1]" .
 542 We assume that alen >= blen and that diff has room for alen digits.
 543 .TP
 544 .I mpvecdigmuladd
 545 .BR "p[0:n] += m * b[0:n-1]" .
 546 This multiplies a an array of digits times a scalar and adds it to another array.
 547 We assume p has room for n+1 digits.
 548 .TP
 549 .I mpvecdigmulsub
 550 .BR "p[0:n] -= m * b[0:n-1]" .
 551 This multiplies a an array of digits times a scalar and subtracts it fromo another array.
 552 We assume p has room for n+1 digits.  It returns +1 is the result is positive and
 553 -1 if negative.
 554 .TP
 555 .I mpvecmul
 556 .BR "p[0:alen*blen] = a[0:alen-1] * b[0:blen-1]" .
 557 We assume that p has room for alen*blen+1 digits.
 558 .TP
 559 .I mpveccmp
 560 This returns -1, 0, or +1 as a - b is negative, 0, or positive.
 561 .PD
 562 .PP
 563 .IR mptwo ,
 564 .I mpone
 565 and
 566 .I mpzero
 567 are the constants 2, 1 and 0.  These cannot be freed.
 568 .SS "Chinese remainder theorem
 569 .PP
 570 When computing in a non-prime modulus,
 571 .IR n,
 572 it is possible to perform the computations on the residues modulo the prime
 573 factors of
 574 .I n
 575 instead.  Since these numbers are smaller, multiplication and exponentiation
 576 can be much faster.
 577 .PP
 578 .I Crtin
 579 computes the residues of
 580 .I x
 581 and returns them in a newly allocated structure:
 582 .IP
 583 .EX
 584 typedef struct CRTres   CRTres;
 585 {
 586         int     n;      /* number of residues */
 587         mpint   *r[n];  /* residues */
 588 };
 589 .EE
 590 .PP
 591 .I Crtout
 592 takes a residue representation of a number and converts it back into
 593 the number.  It also frees the residue structure.
 594 .PP
 595 .I Crepre
 596 saves a copy of the factors and precomputes the constants necessary
 597 for converting the residue form back into a number modulo
 598 the product of the factors.  It returns a newly allocated structure
 599 containing values.
 600 .PP
 601 .I Crtprefree
 602 and
 603 .I crtresfree
 604 free
 605 .I CRTpre
 606 and
 607 .I CRTres
 608 structures respectively.
 609 .SH SOURCE
 610 .B /sys/src/libmp