mp 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584
  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. .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. int mpcmp(mpint *b1, mpint *b2)
  112. .PP
  113. .B
  114. int mpmagcmp(mpint *b1, mpint *b2)
  115. .PP
  116. .B
  117. void mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x, mpint *y)
  118. .PP
  119. .B
  120. void mpinvert(mpint *b, mpint *m, mpint *res)
  121. .PP
  122. .B
  123. int mpsignif(mpint *b)
  124. .PP
  125. .B
  126. int mplowbits0(mpint *b)
  127. .PP
  128. .B
  129. void mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient)
  130. .PP
  131. .B
  132. void mpvecadd(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *sum)
  133. .PP
  134. .B
  135. void mpvecsub(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *diff)
  136. .PP
  137. .B
  138. void mpvecdigmuladd(mpdigit *b, int n, mpdigit m, mpdigit *p)
  139. .PP
  140. .B
  141. int mpvecdigmulsub(mpdigit *b, int n, mpdigit m, mpdigit *p)
  142. .PP
  143. .B
  144. void mpvecmul(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *p)
  145. .PP
  146. .B
  147. int mpveccmp(mpdigit *a, int alen, mpdigit *b, int blen)
  148. .PP
  149. .B
  150. CRTpre* crtpre(int nfactors, mpint **factors)
  151. .PP
  152. .B
  153. CRTres* crtin(CRTpre *crt, mpint *x)
  154. .PP
  155. .B
  156. void crtout(CRTpre *crt, CRTres *r, mpint *x)
  157. .PP
  158. .B
  159. void crtprefree(CRTpre *cre)
  160. .PP
  161. .B
  162. void crtresfree(CRTres *res)
  163. .PP
  164. .B
  165. mpint *mpzero, *mpone, *mptwo
  166. .SH DESCRIPTION
  167. These routines perform extended precision integer arithmetic.
  168. The basic type is
  169. .BR mpint ,
  170. which points to an array of
  171. .BR mpdigit s,
  172. stored in little-endian order:
  173. .IP
  174. .EX
  175. typedef struct mpint mpint;
  176. struct mpint
  177. {
  178. int sign; /* +1 or -1 */
  179. int size; /* allocated digits */
  180. int top; /* significant digits */
  181. mpdigit *p;
  182. char flags;
  183. };
  184. .EE
  185. .PP
  186. The sign of 0 is +1.
  187. .PP
  188. The size of
  189. .B mpdigit
  190. is architecture-dependent and defined in
  191. .BR /$cputype/include/u.h .
  192. .BR Mpint s
  193. are dynamically allocated and must be explicitly freed. Operations
  194. grow the array of digits as needed.
  195. .PP
  196. In general, the result parameters are last in the
  197. argument list.
  198. .PP
  199. Routines that return an
  200. .B mpint
  201. will allocate the
  202. .B mpint
  203. if the result parameter is
  204. .BR nil .
  205. This includes
  206. .IR strtomp ,
  207. .IR itomp ,
  208. .IR uitomp ,
  209. and
  210. .IR btomp .
  211. These functions, in addition to
  212. .I mpnew
  213. and
  214. .IR mpcopy ,
  215. will return
  216. .B nil
  217. if the allocation fails.
  218. .PP
  219. Input and result parameters may point to the same
  220. .BR mpint .
  221. The routines check and copy where necessary.
  222. .PP
  223. .I Mpnew
  224. creates an
  225. .B mpint
  226. with an initial allocation of
  227. .I n
  228. bits.
  229. If
  230. .I n
  231. is zero, the allocation will be whatever was specified in the
  232. last call to
  233. .I mpsetminbits
  234. or to the initial value, 1056.
  235. .I Mpfree
  236. frees an
  237. .BR mpint .
  238. .I Mpbits
  239. grows the allocation of
  240. .I b
  241. to fit at least
  242. .I n
  243. bits. If
  244. .B b->top
  245. doesn't cover
  246. .I n
  247. bits,
  248. .I mpbits
  249. increases it to do so.
  250. Unless you are writing new basic operations, you
  251. can restrict yourself to
  252. .B mpnew(0)
  253. and
  254. .BR mpfree(b) .
  255. .PP
  256. .I Mpnorm
  257. normalizes the representation by trimming any high order zero
  258. digits. All routines except
  259. .B mpbits
  260. return normalized results.
  261. .PP
  262. .I Mpcopy
  263. creates a new
  264. .B mpint
  265. with the same value as
  266. .I b
  267. while
  268. .I mpassign
  269. sets the value of
  270. .I new
  271. to be that of
  272. .IR old .
  273. .PP
  274. .I Mprand
  275. creates an
  276. .I n
  277. bit random number using the generator
  278. .IR gen .
  279. .I Gen
  280. takes a pointer to a string of uchar's and the number
  281. to fill in.
  282. .PP
  283. .I Strtomp
  284. and
  285. .I mptoa
  286. convert between
  287. .SM ASCII
  288. and
  289. .B mpint
  290. representations using the base indicated.
  291. Only the bases 10, 16, 32, and 64 are
  292. supported. Anything else defaults to 16.
  293. .IR Strtomp
  294. skips any leading spaces or tabs.
  295. .IR Strtomp 's
  296. scan stops when encountering a digit not valid in the
  297. base. If
  298. .I rptr
  299. is not zero,
  300. .I *rptr
  301. is set to point to the character immediately after the
  302. string converted.
  303. If the parse pterminates before any digits are found,
  304. .I strtomp
  305. return
  306. .BR nil .
  307. .I Mptoa
  308. returns a pointer to the filled buffer.
  309. If the parameter
  310. .I buf
  311. is
  312. .BR nil ,
  313. the buffer is allocated.
  314. .I Mpfmt
  315. can be used with
  316. .IR fmtinstall (2)
  317. and
  318. .IR print (2)
  319. to print hexadecimal representations of
  320. .BR mpint s.
  321. .PP
  322. .I Mptobe
  323. and
  324. .I mptole
  325. convert an
  326. .I mpint
  327. to a byte array. The former creates a big endian representation,
  328. the latter a little endian one.
  329. If the destination
  330. .I buf
  331. is not
  332. .BR nil ,
  333. it specifies the buffer of length
  334. .I blen
  335. for the result. If the representation
  336. is less than
  337. .I blen
  338. bytes, the rest of the buffer is zero filled.
  339. If
  340. .I buf
  341. is
  342. .BR nil ,
  343. then a buffer is allocated and a pointer to it is
  344. deposited in the location pointed to by
  345. .IR bufp .
  346. Sign is ignored in these conversions, i.e., the byte
  347. array version is always positive.
  348. .PP
  349. .IR Betomp ,
  350. and
  351. .I letomp
  352. convert from a big or little endian byte array at
  353. .I buf
  354. of length
  355. .I blen
  356. to an
  357. .IR mpint .
  358. If
  359. .I b
  360. is not
  361. .IR nil ,
  362. it refers to a preallocated
  363. .I mpint
  364. for the result.
  365. If
  366. .I b
  367. is
  368. .BR nil ,
  369. a new integer is allocated and returned as the result.
  370. .PP
  371. The integer conversions are:
  372. .TF Mptouv
  373. .TP
  374. .I mptoui
  375. .BR mpint -> "unsigned int"
  376. .TP
  377. .I uitomp
  378. .BR "unsigned int" -> mpint
  379. .TP
  380. .I mptoi
  381. .BR mpint -> "int"
  382. .TP
  383. .I itomp
  384. .BR "int" -> mpint
  385. .TP
  386. .I mptouv
  387. .BR mpint -> "unsigned vlong"
  388. .TP
  389. .I uvtomp
  390. .BR "unsigned vlong" -> mpint
  391. .TP
  392. .I mptov
  393. .BR mpint -> "vlong"
  394. .TP
  395. .I vtomp
  396. .BR "vlong" -> mpint
  397. .PD
  398. .PP
  399. When converting to the base integer types, if the integer is too large,
  400. the largest integer of the appropriate sign
  401. and size is returned.
  402. .PP
  403. The mathematical functions are:
  404. .TF mpmagadd
  405. .TP
  406. .I mpadd
  407. .BR "sum = b1 + b2" .
  408. .TP
  409. .I mpmagadd
  410. .BR "sum = abs(b1) + abs(b2)" .
  411. .TP
  412. .I mpsub
  413. .BR "diff = b1 - b2" .
  414. .TP
  415. .I mpmagsub
  416. .BR "diff = abs(b1) - abs(b2)" .
  417. .TP
  418. .I mpleft
  419. .BR "res = b<<shift" .
  420. .TP
  421. .I mpright
  422. .BR "res = b>>shift" .
  423. .TP
  424. .I mpmul
  425. .BR "prod = b1*b2" .
  426. .TP
  427. .I mpexp
  428. if
  429. .I m
  430. is nil,
  431. .BR "res = b**e" .
  432. Otherwise,
  433. .BR "res = b**e mod m" .
  434. .TP
  435. .I mpmod
  436. .BR "remainder = b % m" .
  437. .TP
  438. .I mpdiv
  439. .BR "quotient = dividend/divisor" .
  440. .BR "remainder = dividend % divisor" .
  441. .TP
  442. .I mpcmp
  443. returns -1, 0, or +1 as
  444. .I b1
  445. is less than, equal to, or greater than
  446. .IR b2 .
  447. .TP
  448. .I mpmagcmp
  449. the same as
  450. .I mpcmp
  451. but ignores the sign and just compares magnitudes.
  452. .PD
  453. .PP
  454. .I Mpextendedgcd
  455. computes the greatest common denominator,
  456. .IR d ,
  457. of
  458. .I a
  459. and
  460. .IR b .
  461. It also computes
  462. .I x
  463. and
  464. .I y
  465. such that
  466. .BR "a*x + b*y = d" .
  467. Both
  468. .I a
  469. and
  470. .I b
  471. are required to be positive.
  472. If called with negative arguments, it will
  473. return a gcd of 0.
  474. .PP
  475. .I Mpinverse
  476. computes the multiplicative inverse of
  477. .I b
  478. .B mod
  479. .IR m .
  480. .PP
  481. .I Mpsignif
  482. returns the number of significant bits in
  483. .IR b .
  484. .I Mplowbits0
  485. returns the number of consecutive zero bits
  486. at the low end of the significant bits.
  487. For example, for 0x14,
  488. .I mpsignif
  489. returns 5 and
  490. .I mplowbits0
  491. returns 2.
  492. For 0,
  493. .I mpsignif
  494. and
  495. .I mplowbits0
  496. both return 0.
  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. .IP
  557. .EX
  558. typedef struct CRTres CRTres;
  559. {
  560. int n; /* number of residues */
  561. mpint *r[n]; /* residues */
  562. };
  563. .EE
  564. .PP
  565. .I Crtout
  566. takes a residue representation of a number and converts it back into
  567. the number. It also frees the residue structure.
  568. .PP
  569. .I Crepre
  570. saves a copy of the factors and precomputes the constants necessary
  571. for converting the residue form back into a number modulo
  572. the product of the factors. It returns a newly allocated structure
  573. containing values.
  574. .PP
  575. .I Crtprefree
  576. and
  577. .I crtresfree
  578. free
  579. .I CRTpre
  580. and
  581. .I CRTres
  582. structures respectively.
  583. .SH SOURCE
  584. .B /sys/src/libmp