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