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