tmp.3 - plan9port - [fork] Plan 9 from user space
(HTM) git clone git://src.adamsgaard.dk/plan9port
(DIR) Log
(DIR) Files
(DIR) Refs
(DIR) README
(DIR) LICENSE
---
tmp.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